new第四章语法分析1(最后版本).ppt

编 译 原 理Compiler Principles,蒋凌云南京邮电大学.计算机学院,第四章 语法分析,教材：编译技术原理及其实现方法王汝传 编著,第四章 语法分析,4.1 引言 一、语法分析任务 二、语法分析方法4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法,2,本章内容,第四章 语法分析,4.1 引言 一、语法分析任务 二、语法分析方法4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法,3,本章内容,4.1 引言,本节内容,一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法,词法分析阶段，主要介绍了单词符号的结构、识别（用状态转换图），描述（通过正规式）以及有限自动机DFA和NFA。在一个编译程序对某个源程序完成了词法工作以后，就进入了语法分析阶段。由词法分析程序所产生的单词符号流，作为语法分析程序的输入串，按文法规则分析检查是否构成了合法的句子。首先来了解一下语法分析的任务。,5,4.1 引言,一、语法分析任务,一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法,6,4.1 引言,一、语法分析任务,7,1.语法检查 根据语法规则对各种语法成分进行分析，确定它们的 语法关系以检查语法上的正确和错误，并指出错误的性质 和出错位置。如：if B then S1 else S2 若写成 if B then else S2 就错了（then后少一个S1）,4.1 引言,一、语法分析任务,一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法,8,4.1 引言,一、语法分析任务,9,2.根据语法符号进行一定语义处理加工 如语法分析过程得到一个合法的句子时，往往同时进 行必要的语义分析等 如：当遇到处理表达式a+b*c时，若该表达式语法关 系正确，就可以进行语义处理加工，可将该表达式 变成中间语言，以便以后生成目标程序,4.1 引言,一、语法分析任务,一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法,10,4.1 引言,二、语法分析方法,语法分析方法很多，但能够产生计算机程序并能得到广泛应用的主要有两大类，按照生成语法树的顺序，分别称为自顶向下和自底向上分析方法。,11,4.1 引言,二、语法分析方法,一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法,12,4.1 引言,二、语法分析方法,13,1.自顶向下语法分析方法（1）带回溯分析方法（2）不带回溯分析方法（3）递归子程序法（4）LL（1）分析法,4.1 引言,二、语法分析方法,一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法,14,4.1 引言,二、语法分析方法,15,2.自底向上语法分析方法,（1）简单优先分析法（2）算符优先分析法（3）LR分析法（4）SLR分析法（5）LALR分析法,4.1 引言,二、语法分析方法,第四章 语法分析,4.1 引言 一、语法分析任务 二、语法分析方法4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法,16,本章内容,第四章 语法分析,4.1 引言 一、语法分析任务 二、语法分析方法4.2 自顶向下语法分析 一、自顶向下分析方法的问题及其解决办法 二、递归子程序分析法（递归下降分析法）三、LL（1）分析法4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用4.4 语法分析程序的自动生成 一、分析器的生成器YACC 二、用YACC处理二义性文法,17,本章内容,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,18,4.2 自顶向下语法分析,本节内容,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,19,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,20,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,1.消除回溯 对于自顶向下语法分析来说，对于某些文法，可能会遇到“回溯”和“左递归”的问题，为了能有效地运用这种语法分析方法，应使文法不含左递归及避免回溯。（1）回溯分析方法定义 在进行自顶向下语法分析时，对于文法规则中具有同一左部而右部有不同规则时，在分析时按顺序一个个试探，若能分析下去则成，否则再退回到出错点换另一规则重新试探。这种方法称回溯分析方法。其实质就是使用不同规则反复试探。如：ScAd Aab|a 要判断“cad”是否为该文法的句子，可以分别用Aab和Aa代入第一个产生式中试探。,21,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,（2）回溯问题的解决 1）路标法 定义：设有规则Ua1V1|a2V2|anVn 若ai为互不相同的终结符时，将ai作为路标，当被分析符号串为ai时，便可按规则UaiVi往下分析，这样可以消除回溯。如：:|if then 当分析语句：if AB then A:=B时，我们可以根据第二个产生式以if开始直接选用它作判断。if在这里就是路标 因此，我们在设计程序设计语言时，要考虑语法规则各选择项开始符号互不相同,22,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,为了避免回溯，我们对文法要求是FIRST(i）FIRST(j）（ij）即对文法中的任意一个非终结符号，其规则右部有多个选择时，若由各个选择所推出的终结符号串首符号集合要两两不相交。这样，就可能根据当时读进的符号是属于哪个选择的FIRST（i），来唯一地确定该选用哪个选择来匹配输入串。如：当前输入符号为b(b)，如果b FIRST(i），则可以选择第i个产生式去匹配输入串。,23,一般地，设U为文法的任意非终结符号，若U有如下规则 Un i+若定义任一个选择 i的所有可能推出终结符号串的首符号集FIRST（i）为FIRST（i）a i*a，a显然 FIRST（i）,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,一般地说，如果有规则Uaaan则可以将这些规则写成U aUUn其中a称为左公因子，经过反复提取公因子即可将每个非终结符的所有选择首符号集变成两两不相交。,24,2)提取左因子法当文法不满足上述路标法条件，即右部各规则首符号相同时，我们可以采用提取左因子法对文法进行改写。,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,25,注意：Uxy|x,可写成Ux(y|)，当分析符号串遇到 时，认为总能匹配，可以一直分析下去。Uxy|x,也可写成Uxy，表示y不出现或出现一次。,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,S xAy,A*（*|）进一步改写成 S xAy,A*A1，A1*|为分析符号串x*y，可以从开始符号出SxAy，下一待匹配符号为*，所以用A*A1，得 SxAy x*A1y,下一个待匹配的符号为y,所以 用 A1（若用A1*则意味着下一个为*，不能匹配）得SxAy x*A1yx*y（即x*y,匹配成功）。可见没出现回溯现象。,26,S,x,y,A,*,A1,如：有文法 S xAy,A*|*要分析x*y，显然存在回溯。为避免分析时回溯，可以将文法改写成：,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,27,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,2、消除左递归,28,（1）问题的提出 在自顶向下分析过程中，假定现在轮到要用非终结符U去匹配输入串，而在文法中第一条规则是 UU 它是一条直接左递归规则，这种左递归文法将使上述自顶向下的分析过 程陷入无限循环，即：当试图用U去匹配输入串时会发现，在没有吃进任何输入符号的情况下，又得重新要求U去匹配，如此循环下去而无终止。若文法具有间接左递归，即有 UU 那么，也会发生上述问题。,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,29,如：已知文法GS S AB A bB|Aa(存在直接左递归）B Sb|a 现分析符号串baabaab是否是文法G的句子。,其分析过程如下：S AB bBB bSbB bABbB bbBBbB(得第二个字符与输入串不匹配）S AB bBB bSbB bABbB bAaBbB(只能用A Aa推导，又遇A，出现了死循环)由于文法规则中有左递归A Aa，所以无法分析下去,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,30,（2）消除左递归方法 1）用重复表示法（扩充的表示法）改写语法规则 假定一个文法中有关于非终结符的规则为 其中非空，不以开头，则等价地改写为 例如，下述直接左递归规则：可改写为,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,31,E,E,T,E,T,E,T,T,等价,E,T+T+T+T,T+T+T+T,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,32,同样，规则*,等价于（*）,可改写为*这样，改写后的文法消除了直接左递归。可以证明，改写前后的文法是等价的。,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,33,2）消除直接左递归还可用另一种方法来改写形如文法规则的直接左递归。对引入一个新的非终结符，将等价写成 由于不以开头，不以开头，因此改写后两条规则不是直接左递归。同样可以证明这种形式和原来形式是等价的。,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,34,A,A,A,A,等价,A,A,A,A,A,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,就一般而言，关于的规则具有下面形式：nn这时可改写成如下形式：A(n)n由消除直接左递归方法，得(n)(n),35,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,36,例如：A Ac|Aad|bd|e 等价于A A（c|ad）|bd|e，所以可以改写成：A（bd|e）A（即A bdA|eA)A（c|ad）A|（即A cA|adA|）,例如：有文法，T*，（）i用上述方法可改写成：，*，（）i,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,上述两种方法可消除任意直接左递归，但不能消除两步或多步推导形成的左递归。例如，有文法ccbbaa该文法无直接左递归，但有间接左递归，例如有 c bc abc即 abc,37,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,3）消除间接左递归对于间接左递归先将间接左递归变成直接左递归，然后消除直接左递归例如；A aB|Bb(1)B Ac|d(2)先将（1）代入（2）中，得 B Bbc|aBc|d(3)由此将(3)改写为；B（aBc|d)B BbcB|加入文法开始符号的产生式得消除左递归后的等价文法为：A aB|Bb B(aBc|d)B BbcB|,38,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,4)消除文法递归的一般算法要求：文法不含形如 的推导，也不存在这样规则 算法思想如下：将文法的所有非终结符整理成某种顺序，n从U1开始消除U1规则的直接左递归用左部为U1的所有规则右部替换左部为U2，右部以U1开始的规则中的U1，并消除U2规则的直接左递归。用类似的方法把U1，U2的右部替换左部为U3，右部以U1，U2开始的规则中，消除U3规则中的直接左递归。重复上一步，直到最后把左部为U1，U2，Un-1的右部带入Un规则中，并消除Un中的直接左递归。消除多余规则,39,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,将文法的所有非终结符整理成某种顺序，n，然后按此顺序执行下一步；执行循环语句：i:n j i-1 把形如 ijy的规则改写成 Uixyxyxky 其中Ujxxxk 是Uj的所有规则 消除关于Ui规则中直接左递归 去掉多余规则（如果有的话）,40,消除左递归算法,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,例4.2设有文法 ab cde应用上述算法，将非终结符排列，。然后执行循环语句 i 2 j i-消除Ui规则中直接左递归,41,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,当i时，上述语句对文法不产生影响。当i时，应改写规则d，因为ab，所以adbd，此时文法变换成为abc adbde消除关于的直接左递归即可。该文法没有多余的规则。,42,4.2 自顶向下语法分析,一、自顶向下分析方法的问题及其解决办法,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,43,4.2 自顶向下语法分析,二、递归子程序分析法,1.递归子程序定义 一个子程序以直接或间接方式调用本身，称为递归子程序。,44,4.2 自顶向下语法分析,二、递归子程序分析法,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,45,4.2 自顶向下语法分析,二、递归子程序分析法,2.递归调用子程序的处理（1）处理基本思想 对于递归子程序调用，用栈存放返回地址，当调用该子程序时，由递归入口子程序将返回地址压入栈中，当返回时，用递归出口子程序从栈中取出返回地址。（2）构造递归子程序的方法 程序语言的许多语法成分是递归定义的，在对程序语言进行不带回溯自顶向下语法分析时，就可以采用递归子程序法。其方法步骤如下：,46,4.2 自顶向下语法分析,二、递归子程序分析法,1)对文法中每个非终结符号U（它们都分别代表一种语法成分）都编出一个子程序 P（U）2)对于递归出现的非终结符，其相应的子程序中应有递归入口部分（递归入口子程序，取名S），以便将返回地址压入栈中。此外，还应有递归出口部分，设此子程序取名S。以便从地址压入栈中取返回地址3)对于规则Uxxxn，可用下列方法构造（U）：ch R（）（）ch（）（）E ch（n）（n）,47,4.2 自顶向下语法分析,二、递归子程序分析法,其中全程变量ch中存放了当前输入字符；为出错信息，表 示源程序中语法有错。当输入符号遇选择项为时，就自动认为获得 了匹配。4)对于符号串xyyym，如果yi，则（yi）为 chyi（ch）这就是说，如果当前文法中的符号与输入符号匹配，则继续读入下 一个字符至ch中；否则表明源程序有错。如果yi，则（yi）就 代表调用与yi相应的子程序。,48,4.2 自顶向下语法分析,二、递归子程序分析法,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,49,4.2 自顶向下语法分析,二、递归子程序分析法,50,3.分析实例,设有文法eBaAabAcBdEdaCedC此文法共有四个非终结符，并且在规则中都是递归出现，故应该编写四个相应的递归子程序：（E）、（）、（）、（）。在第一次执行前，ch中已存有输入串中首字符。,4.2 自顶向下语法分析,二、递归子程序分析法,(1)构造递归子程序：(E),51,SCIN,ch=e?,1,2,READ,P(B),ch=a?,ERROR,READ,P(A),ERROR,SCOUT,eBaA（用方法 4）,=,=,3,4,5,6,7,8,(1)构造递归子程序(A),52,abAcB（用方法 3）和4）,(1)构造递归子程序(B),53,SCIN,ch=d?,1,2,READ,P(E),ch=d?,READ,P(C),ERROR,dEdaC（用方法 3）和4）,=,=,3,4,5,6,7,9,ERROR,READ,8,=,ch=a?,SCOUT,10,(1)构造递归子程序(C),54,edC（用方法 3）和4）,55,（2）分析实例 判别字符串 eadeaa 是否是文法的句子。,e a d e a a,分析步骤从识别符号E开始，扫视字符串eadeaa，设一个全程变量ch用于存放输入串中的字符。并设一个返回地址栈用于存放返回地址,栈底,TOP,#,56,e a d e a a,1）开始时，在全程变量ch中存放了输入串中的首字符e，故分析与识别从符号e开始。此时主程序调用子程序P(E),子程序P(E),栈底,TOP,#,57,e a d e a a,2)进入P(E)后，执行P(E)子程序，首先通过递归入口子程序SCIN，将P(E)在主程序中的返回地址送入返回栈中,子程序P(E),主返,TOP,#,58,e a d e a a,3)执行P(E)子程序，首先判断ch?e，现在ch e，接着读入下一个字符。,子程序P(E),主返,TOP,#,59,e a d e a a,4)读入下一个字符a，即cha,子程序P(E),主返,TOP,#,60,e a d e a a,5)P(E)子程序调用子程序P(B)，P(B)调用递归入口 子程序SCIN，将P(B)在P(E)中的返回地址P(E):5送入返回栈中,子程序P(E),主返P(E):5,TOP,#,61,e a d e a a,6）然后执行子程序P(B)，分析ch?d，现在不是d，再判定ch？a，现在cha，接着读入下一个字符。,子程序P(B),主返P(E):5,TOP,#,62,e a d e a a,7）读入下一个字符d，即chd,子程序P(B),主返P(E):5,TOP,#,63,e a d e a a,8）P(B)子程序调用子程序P(C)，P(C)调用递归入口子程序SCIN，将P(C)在P(B)中的返回地址P(B):10送入返回栈中,子程序P(B),主返P(E):5P(B):10,TOP,#,64,e a d e a a,9）接着执行P(C)，分析ch?e。现在不是字符 e，再接着判定ch?d，现在chd，接着 读入下一个字符。,子程序P(C),主返P(E):5P(B):10,TOP,#,65,e a d e a a,10）读入下一个字符e，即che,子程序P(C),主返P(E):5P(B):10,TOP,#,66,e a d e a a,11）P(C)子程序再调用子程序P(C)，P(C)调用 递归入口子程序SCIN，将P(C)在P(C)中的返 回P(C):7地址送入返回栈中。,子程序P(C),主返P(E):5P(B):10P(C):7,TOP,#,67,e a d e a a,12）然后执行子程序P(C)，这时要判定ch?e，现在che,接着读入下一个字符。,子程序P(C),主返P(E):5P(B):10P(C):7,TOP,#,68,e a d e a a,13）读入下一个字符a，即cha,子程序P(C),主返P(E):5P(B):10P(C):7,TOP,#,69,e a d e a a,14）P(C)调用递归出口子程序SCOUT，将返 回栈中返回地址P(C):7取出。,子程序P(C),主返P(E):5P(B):10P(C):7,TOP,#,70,e a d e a a,15）P(C)调用递归出口子程序SCOUT，将返回 栈中返回地址P(C):7取出。,子程序P(C),主返P(E):5P(B):10,TOP,#,71,e a d e a a,16）P(C)执行P(C):7，即P(C)调用递归出口子程序SCOUT，将返回栈中返回地址P(B):10取出。,子程序P(C),主返P(E):5P(B):10,TOP,#,72,e a d e a a,17）P(C)执行P(C):7，即P(C)调用递归出口子 程序SCOUT，将返回栈中返回地址P(B):10取 出。,子程序P(C),主返P(E):5,TOP,#,73,e a d e a a,18）P(B)执行P(B):10，即P(B)调用递归出口子 程序SCOUT，将返回栈返回地址P(E):5取出。,子程序P(B),主返P(E):5,TOP,#,74,e a d e a a,19）P(B)调用递归出口子程序SCOUT，将返回 栈中P(B)在P(E)中的返回地址P(E):5取出。,子程序P(B),主返,TOP,#,75,e a d e a a,20）P(E)执行P(E):5，即 P(E)子程序判别ch?a，现在是a，接着读入下一个字符。,主返,TOP,子程序P(E),#,76,e a d e a a,21）读入下一个字符a，即cha,主返,TOP,子程序P(E),#,77,e a d e a a,22）P(E)子程序调用子程序P(A)，P(A)调用递归 入口子程序SCIN，将P(A)在P(E)中的返回地 址P(E):8送入返回栈中,主返P(E):8,TOP,子程序P(E),#,78,e a d e a a,23）现在执行子程序P(A)，判断ch?a，现在 cha，接着读入下一个字符。,主返P(E):8,TOP,子程序P(A),#,79,e a d e a a,24）由于输入串eadeaa后面再也没有其他字符 了，故读入的是句子的终结符#,主返P(E):8,TOP,子程序P(A),#,80,e a d e a a,25）P(A)调用递归出口子程序SCOUT，将返回 栈中中返回地址P(E):8取出。,主返P(E):8,TOP,子程序P(A),#,81,e a d e a a,26）P(A)调用递归出口子程序SCOUT，将返回 栈中中返回地址P(E):8取出。,主返,TOP,子程序P(A),#,82,e a d e a a,27）P(E)执行P(E):8，即 P(A)调用递归出口子 程序SCOUT，将返回栈中返回地址主返取出。,主返,TOP,子程序P(E),#,83,e a d e a a,28）P(E)执行P(E):8，即 P(A)调用递归出口子 程序SCOUT，将返回栈中返回地址主返取出。,栈底,TOP,子程序P(E),#,84,e a d e a a,29）返回主程序，结束。,栈底,TOP,子程序P(E),#,85,要求：不含有左递归，并且每个非终结符的各个选择所推出的终结符号串首符号集合两两不相交。,也就是说，字符串eadeaa被语法分析程序所接受，这表明字符串eadeaa是文法（）的句子。,再举一个例子,GE=(+,-,(,),E,F,T,E,T,E,P)P:E:=TE E:=+TE|T:=FT T:=*FT|F:=(E)|i,86,用类PASCAL语言写出它的递归子程序,E:=+TE|（若有无出错处理）PROCEDURE E;BEGINSCINIF ch=+THEN BEGIN getch(ch);T;E;ENDSCOUTEND,87,E:=TEPROCEDURE E;BEGINSCINT;E;SCOUTEND,用类PASCAL语言写出它的递归子程序,T:=FTPROCEDURE T;BEGINSCINF;T;SCOUTEND,88,T:=*FT|（若有无出错处理）PROCEDURE T;BEGINSCINIF CH=*THEN BEGIN getch(ch);F;T;ENDSCOUTEND,用类PASCAL语言写出它的递归子程序,89,F:=(E)|iPROCEDURE F;BEGINSCINIF CH=(THEN BEGIN getch(ch);E;IF ch=)THEN getch(ch)ELSE error END ELSE IF CH=i THEN getch(ch)ELSE errorSCOUTEND,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,90,4.2 自顶向下语法分析,二、递归子程序分析法,4.递归子程序法特点(1)优点 1）程序结构和层次清晰，易于手工实现。2）子程序与文法规则一一对应，但要求对文法规 则消除左递归和回溯。3）可以加入语义加工子程序(2)缺点 1）编写程序和调试工作量大 2）对上下文无关文法需要改写,91,4.2 自顶向下语法分析,二、递归子程序分析法,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,92,4.2 自顶向下语法分析,三、LL(1)分析法,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,93,4.2 自顶向下语法分析,三、LL(1)分析法,1.定义 LL（1）分析方法也是一种自顶向下不带回溯的分析方法，LL的意思是：从左（Left）到右扫描输入符号串并建 立它的最左推导（Left most derivations）。数字是 指向前看一个符号来决定选择同一个非终结符不同规则。如果向前查看K个符号（K1）才能确定应选规则时，这 种语法分析方法就称LL（K）分析法。,94,4.2 自顶向下语法分析,三、LL(1)分析法,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,95,4.2 自顶向下语法分析,三、LL(1)分析法,96,2.LL（1）分析方法（1）基本思想 借助于一张分析表及一个语法分析栈，在一个总控程序控制下实现。我们通常把按LL（1）方法执行语法分析任务的程序称为LL（1）分析程序或LL（1）分析器，它由一个总控程序、一张分析表和一个分析栈组成，如下图所示。,a1 a2 ai an#,输入串,总控程序,分析表m,X.#,分析栈,4.2 自顶向下语法分析,三、LL(1)分析法,（2）LL（1）方法分析过程考虑文法:FT*（）i 1）建立文法LL（1）的分析表相应的分析表如下表所示（其构造方法，在后面叙述)。,97,4.2 自顶向下语法分析,三、LL(1)分析法,98,4.2 自顶向下语法分析,三、LL(1)分析法,99,由上述分析过程可以看出，在分析的每一时刻，当前已读过的符号与栈中的符号一起总是构成了当前的左句型，（）分析器确实构造了输入串的一个最左推导。,2）分析过程现在以输入符号串ii*i为例，列出利用上述算法对此符号串的分析过程如下:,步骤 分析栈 余留输入串 所用产生式#E i+i*i#ETE#ET i+i*i#TFT#ETF i+i*i#Fi#ETi i+i*i#ET+i*i#T#E+i*i#E+TE#ET+i*i#E T i*i#TFT#ETF i*i#Fi#ETi i*i#ET*i#T*FT#ETF*i#ETF i#F i#ETi i#ET#T#E#E#成功,（3）一般分析步骤其中“输入”就是待分析的符号串，它以右界符#作为结尾。分析表可用一个矩阵（或二维数组）来表示。它概括了相应文法的全部信息。分析表的每一行与文法的一个非终结符相关联，而每一列则与文法的一个终结符号或#相关联。分析表元素，a（aU#）或者指示了当前推导所应使用的产生式，或者指出了输入串中含有语法错误。分析器对每个输入串的分析在总控程序控制下进行。,100,4.2 自顶向下语法分析,三、LL(1)分析法,其步骤如下：1）分析开始时，首先将符号#及文法的开始符号依次置于分析栈的底部，并把各指示器调整至起始位置,即分别指向分析栈的栈顶元素和输入串的首字符。然后反复执行第（2）步2）设在分析的某一步，分析栈及余留的输入符号串处于如下格局#X1X2Xm-1Xm aiai+1#其中，m为分析过程中所得的文法符号，此时，可 视栈顶符号m的不同情况，分别做如下的动作:,101,4.2 自顶向下语法分析,三、LL(1)分析法,若m，则以m及ai组成符号对（m，ai）查分析表，设m,ai为一产生式，譬如说Xm，此时将m从分析栈中退出，并将按反序推入栈中（即用该产生式推导一步），从而得到新的格局:#X1X2Xm-1WVU aiai+1#但若m，ai“”，则调用出错处理程序进行处理;若mai#，则表明栈顶符号已与当前正扫视的输入符号得到匹配，此时应将m（即ai）从栈中退出，并将输入符号指示器向前推进一个位置；若mai#，则表明输入串已完全得到匹配，此时即可宣告分析成功而结束分析工作。,102,4.2 自顶向下语法分析,三、LL(1)分析法,(4)几点说明 1)分析表M根据具体文法构造，文法不同M就不同 2)LL（1）分析法的总控程序对于不同文法总是一样的。3)分析表MA，a或指出应选规则或指出错误（空白时）4)LL（1）语法分析程序的机器模型是一个下推自动机,103,构造一个LL（1）分析器问题，主要归结为构造LL（1）分析表的问题。,4.2 自顶向下语法分析,三、LL(1)分析法,一、自顶向下分析方法的问题及其解决办法 1.消除回溯 2.消除左递归 二、递归子程序分析法（递归下降分析法）1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点 三、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,104,4.2 自顶向下语法分析,三、LL(1)分析法,105,3.构造分析表（1）头终结符号集合和后继终结符号集合 1）头终结符号集合 定义为了构造分析表，我们引进与文法有关的集合FIRST集和FOLLOW集。假定是文法G的任一符号串，或者说(VTV)*，我们定义 FIRST（）b*b，b 特别是，若*，则规定 FIRST（）即 FIRST（）是的所有可能推导的开头终结符或可能的,4.2 自顶向下语法分析,三、LL(1)分析法,106,例如：设文法GT ABA PQ|BCP pP|Q qQ|B bB|eC cC|f求FIRST（PQ）,由定义有 PQ pPqQ=p PQ Q Q q Q q PQ Q Q 所以 FIRST（PQ）=p,q,同理 FIRST（BC)=b,e,对于一个简单的文法我们用手工可以求得其FISRT集，对于复杂的文法我们通常使用下述算法求解,4.2 自顶向下语法分析,三、LL(1)分析法,构造头终结符号集合FIRST的算法对于文法中的每一个文法符()，构造（）时，只要连续使用下列规则，直至每个集不再扩大为止。a.若X，则（）。b.若，且有形如b规则（b），或的规则，把b或（和）加入（）中。c.设文法中有形如Y的规则，若，则将 FIRST（）中一切非符号加进（）中，对于一切 2ik，若*，则把2中首符号集（除外）也加进FIRST（）中，如此继续下去，直到k-1*，则把YK中首符号集(除外)也入FIRST(X)中。d.若每个非终结符号都可能推导出空符号串，即*，则把也加进（）中。,107,4.2 自顶向下语法分析,三、LL(1)分析法,现在，可以对文法G的任何符号串n，可按如下步骤构造FIRST（）。首先置FIRST()=,然后将FIRST(X1)中一切非的符号加进FIRST（）若FIRST（），再将FIRST（）的一切非加进FIRST（）中，如此等等。最后，若对于in，（i），则再将加进（）中。,108,考虑文法:FT*（）i,由算法步骤 a.得FIRST（+）=+FIRST（*）=*FIRST（）=（FIRST（）=）FIRST（i）=i,由算法步骤 b.得FIRST（E）=+，FIRST（T）=*，FIRST（F）=（，i,4.2 自顶向下语法分析,三、LL(1)分析法,109,文法:,FT*,（）i 对于算法步骤 c.和 d.因为FT所以 FIRST（T）=FIRST（F）=又因为F不能推出，所以FIRST（T）不能被加入FIRST（T）,4.2 自顶向下语法分析,三、LL(1)分析法,110,利用该算法还能方便地得到如下的符号串头终结符号集：FIRST（TE）=FIRST（T）=FIRST（F）=（，iFIRST（+TE）=FIRST（+）FIRST（FT）=FIRST（F）=（，iFIRST（*FT）=FIRST（*）=*FIRST（E）=FIRST（）=（FIRST（）=,4.2 自顶向下语法分析,三、LL(1)分析法,2)后继终结符号集合 定义 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义 FOLLOW（A）=c|S*Ac,c 特别是，若S*A，则规定#FOLLOW