编译原理-第4章+语法分析.ppt

1,第四章 语法分析,4.1 引言 4.2 自顶向下语法分析 4.3 自底向上语法分析 4.4 语法分析程序的自动生成,2,4.1 引言 一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法,3,一、语法分析任务 词法分析阶段，主要介绍了单词符号的结构、识别（用状态转换图），描述（通过正规式）以及有限自动机DFA和NFA。 在一个编译程序对某个源程序完成了词法工作以后,就进入了语法分析阶段。由词法分析程序所产生的单词符号流，作为语法分析程序的输入串，按文法规则分析检查是否构成了合法的句子。 首先来了解一下语法分析的任务。,4,1.语法检查 根据语法规则对各种语法成分进行分析，确定它们的语法关系以检查语法上的正确和错误，并指出错误的性质和出错位置。 如：if B then S1 else S2 若写成 if B then else S2 就错了（then后少一个S1）,5,2. 根据语法符号进行一定语义处理加工 如语法分析过程得到一个合法的句子时，往往同时进行必要的语义分析等 如：当遇到处理表达式a+b*c时，若该表达式语法关系正确，就可以进行语义处理加工，可将该表达式变成中间语言，以便以后生成目标程序,6,二、语法分析方法 语法分析方法很多，但能够产生计算机程序并能得到广泛应用的主要有两大类，按照生成语法树的顺序，分别称为自顶向下和自底向上分析方法。,7,1.自顶向下语法分析方法 （1）递归下降分析法 （2）LL（1）分析法,8,2.自底向上语法分析方法,（1）简单优先分析法 （2）算符优先分析法 （3）LR分析法,9,4.2 自顶向下语法分析 一、消除左递归 二、消除回溯 三、递归下降分析法 四、LL(1)分析法,10,一、消除左递归,（1）问题的提出 在自顶向下分析过程中，假定现在轮到要用非终结符U去匹配输入串， 而在文法中第一条规则是 UU 这样会产生什么问题呢？,11,若文法具有间接左递归，即有 UU 那么，也会发生上述问题。,12,例如：已知文法GS S AB A bB|Aa (存在直接左递归） B Sb|a 现分析符号串baabaab是否是文法G的句子。,其分析过程如下：,13,（2） 消除左递归方法 1）用重复表示法（扩充的表示法）改写语法规则 假定一个文法中有关于非终结符的规则为 其中非空，不以开头，则等价地改写为 ,14,例如，下述直接左递归规则： 可改写为 ,E,E,T,E,T,E,T,T,等价,E,T + T + T + T,T + T + T + T,15,同样，规则 *,等价于（*）,可改写为 * 这样，改写后的文法消除了直接左递归。可以证明，改写前后的文法 是等价的 。,16,2）改写方法规则消除直接左递归 还可用另一种方法来改写形如文法规则的直接左递归。对引入一个新的非终结符，将等价写成 由于不以开头，不以开头，因此改写后两条规则不是直接左递归。同样可以证明这种形式和原来形式是等价的。,17,A,A,A,A, ,等价,A,A,A,A,A, ,18,就一般而言，关于的规则具有下面形式： nn 这时可改写成如下形式： A(n) n 由消除直接左递归方法，得 (n) (n),19,例如：A Ac|Aad|bd|e 等价于A A（c|ad）|bd|e ， 所以可以改写成： A （bd|e）A A （c|ad）A| ,20,例如：有文法 ， T*， （）i 用上述方法可改写成： ， ， *， （）i,21,上述两种方法可消除任意直接左递归，但不能消除间接左递归 例如，有文法 cc bb aa 该文法无直接左递归，但有间接左递归，例如有 c bc abc 即abc,22,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|,23,4) 消除文法递归的一般算法 要求：文法不含形如 的推导，也不存在这样规则，算法思想如下： 将文法的所有非终结符整理成某种顺序，n 从U1开始消除U1规则的直接左递归 用左部为U1的所有规则右部替换左部为U2，右部以U1开始的规则中的U1，并消除U2规则的直接左递归。 用类似的方法用U1，U2的右部替换左部为U3，右部以U1，U2开始的规则中，消除U3规则中的直接左递归。 重复上一步，直到最后把左部为U1，U2，Un-1的右部带入Un规则中，并消除Un中的直接左递归。 消除多余规则,24, 将文法的所有非终结符整理成某种顺序，n，然后按此顺序执行下一步； 执行循环语句： i: n j i-1 把形如 ijy的规则改写成 Uixyxyxky 其中Ujxxxk 是Uj的所有规则 消除关于Ui规则中直接左递归 去掉多余规则（如果有的话）,消除左递归算法 ：,25,例4.2设有文法 ab cde 应用上述算法，将非终结符排列，。然后执行循环语句 i 2 j i- 消除Ui规则中直接左递归 ,26,当i时，上述语句对文法不产生影响。 当i时，应改写规则d， 因为ab， 所以adbd， 此时文法变换成为 ab c adbde 消除关于的直接左递归即可。 ab bde cad 该文法没有多余的规则。,27,二、消除回溯 （1） 回溯分析方法定义 在进行自顶向下语法分析时，对于文法规则中具有同一左部而右部有不同规则时，在分析时按顺序一个个试探，若能分析下去则成，否则在退回到出错点换另一规则重新试探。这种方法称回溯分析方法。其实质就是使用不同规则反复试探。 如：ScAd Aab|a 要判断“cad”是否为该文法的句子。,28,若按自上而下语法分析程序的步骤进行分析判断，其过程如下： P: S=cAd A=ab|a,S,A,d,c,ScAd,cad,i,29,若按自上而下语法分析程序的步骤进行分析判断，其过程如下： P: S=cAd A=ab|a,S,A,d,c,ScAd cabd,cad,i,a,b,30,若按自上而下语法分析程序的步骤进行分析判断，其过程如下： P: S=cAd A=ab|a,S,A,d,c,ScAd cabd,cad,i,a,b,ERROR!,31,（2） 回溯问题的解决 1）路标法 定义：设有规则Ua1V1|a2V2|anVn 若ai为互不相同的终结符时，将ai作为路标，当被分析符号串为ai时，便可按规则UaiVi往下分析，这样可以消除回溯。 如： ：|if then 当分析语句：if AB then A:=B时，我们可以根据第二个产生式以if开始直接选用它作判断。 if在这里就是路标,32,一般地，设U为文法的任意非终结符号，若U有如下规则 Un i + 若定义任一个选择i的所有可能推出终结符号串的首符号集FIRST（ i ）为 FIRST（ i）a i*a，a 显然 FIRST （ i） ,33,为了避免回溯，我们对文法要求是： FIRST(i ）FIRST(j ）（ij） 如：当前输入符号为b(b )， 如果b FIRST(i），则可以选择第i个产生式去匹配输入串。,34,一般地说，如果有规则 Uaaan 则可以将这些规则写成 U aU Un 其中a称为左公因子，经过反复提取公因子即可将每个非终结符的所有选择首符号集变成两两不相交。,2) 提取左因子法 当文法不满足上述路标法条件，即右部各规则首符号相同时，我们可以采用提取左因子法对文法进行改写。,35,例如： Uxy|x, 可写成 UxU U:=y| 当分析符号串遇到 时，认为总能匹配，可以一直分析下去。,36,为避免分析时回溯，可以将文法改写成： S xAy , A *（*|） 进一步改写成 S xAy , A *B ，B *|,例如： 有文法 S xAy , A *|* 分析x*y是否是该文法的句子。,从开始符号出发，得自顶向下语法分析： SxAy SxAy x*By SxAy x*Byx*y SxAy x*By x*y x*y,37,S,x,y,A,*,B,38,三、递归下降分析法/ 递归子程序分析法 1.递归子程序定义 2.递归调用子程序的处理 3.分析实例 4.递归子程序特点,39,1.递归子程序定义 一个子程序以直接或间接方式调用本身，称为递归子程序。如：PASCAL语言中的递归函数就是递归子程序。,40,2.递归调用子程序的处理 （1）处理基本思想 对于递归子程序调用，用栈存放返回地址，当调用该子程序时，由递归入口部分将返回地址压入栈中，当返回时，递归出口部分从栈中取出返回地址。返回到调用点后继续执行。,41,（2）构造递归子程序的方法 1)对文法中每个非终结符号U（它们都分别代表一种语法成分）都编出一个子程序 P（U） 2)子程序包含： 递归入口部分S； 子程序处理部分； 递归出口部分S。,42,3)对于规则Uxxxn，可用下列方法构造（U）的处理流程： IF ch IN FRIST(X1) THEN ELSE IF ch IN FRIST(X2) THEN ELSE ELSE IF ch IN FRIST(Xn) THEN ELSE ERROR 其中全程变量ch中存放了当前输入字符； ERROR为出错信息,表示源程序中语法有错。当输入符号遇选择项为时，就自动认为获得了匹配。,43,4)对于符号串xyyym，如果yi， 则（yi）为 IF chyi THEN READ(ch) ELSE ERROR 这就是说，如果当前文法中的符号与输入符号匹配，则继续读入下一个字符至ch中；否则表明源程序有错。,44,3.分析实例,设有文法 eBaA abAcB dEdaC edC 此文法共有四个非终结符，编写四个相应的递归子程序：（E）、（）、（）、（）。在第一次执行前，ch中已存有输入串中首字符。,45,递归子程序：（E）,SCIN,ch=e?,1,2,READ,P(B),ch=a?,ERROR,READ,P(A),ERROR,SCOUT,eBaA,=,=,3,4,5,6,7,8,46,递归子程序：（A）,abAcB,SCIN,ch=a?,1,2,READ,ch=c?,P(A),ERROR,SCOUT,=,3,4,7,6,10,ch=b?,READ,5,=,ERROR,READ,8,P(B),9,47,递归子程序：（B）,SCIN,ch=d?,1,2,READ,P(E),ch=d?,READ,P(C),ERROR,dEdaC,=,=,3,4,5,6,7,9,ERROR,READ,8,=,ch=a?,SCOUT,10,48,递归子程序：（C）,edC,49,例：判别字符串 eadeaa 是否是文法的句子。,e a d e a a,分析步骤从识别符号E开始，扫描字符串eadeaa ，设一个全程变量ch用于存放存放输入串中的字符。并设一个返回地址栈用于存放返回地址,栈底,TOP,50,e a d e a a,（1）开始时，在全程变量ch中存放了输入串中的首字符e，故分析与识别从符号e开始。 此时主程序调用子程序P(E),子程序P(E),栈底,TOP,51,e a d e a a,（2）进入P(E)后，执行P(E)子程序，首先通过递归入口子程序SCIN将P(E)在主程序中的返回地址送入返回栈中,子程序P(E),主返,TOP,52,e a d e a a,（3）根据P(E)子程序，首先判断ch?e，如果是e，接着读入下一个字符a，即cha,子程序P(E),主返,TOP,53,e a d e a a,（4）P(E)子程序调用子程序P(B)，P(B)调用递归入口子程序SCIN，将P(B)在P(E)中的返回地址送入返回栈中,子程序P(E),主返 P(E):5,TOP,54,e a d e a a,（4）P(E)子程序调用子程序P(B)，P(B)调用递归入口子程序SCIN，将P(B)在P(E)中的返回地址送入返回栈中,子程序P(B),主返 P(E):5,TOP,55,e a d e a a,（5）然后子程序P(B)中将分析ch?d，如果不是，再判定ch？a。,子程序P(B),主返 P(E):5,TOP,56,e a d e a a,（6）现在的情况输入的第二个字符是a，再读入下一个字符d，再调用子程序P(C),子程序P(B),主返 P(E):5,TOP,57,e a d e a a,（7）P(B)子程序调用子程序P(C)，P(C)调用递归入口子程序SCIN，将P(C)在P(B)中的返回地址送入返回栈中,子程序P(B),主返 P(E):5 P(B):10,TOP,58,e a d e a a,（8）接着应该判定ch?e。如果不是字符e，再接着判定ch?d。,子程序P(C),主返 P(E):5 P(B):10,TOP,59,e a d e a a,（9）现在第三个字符是d，于是再读入一个字符e。,子程序P(C),主返 P(E):5 P(B):10,TOP,60,e a d e a a,（10）P(C)子程序调用新子程序P(C)，新P(C)调用递归入口子程序SCIN，将新P(C)在原P(C)中的返回地址送入返回栈中。,原子程序P(C),主返 P(E):5 P(B):10 P(C):7,TOP,61,e a d e a a,（11）P(C)子程序调用新子程序P(C)，新P(C)调用递归入口子程序SCIN，将新P(C)在原P(C)中的返回地址送入返回栈中。,新子程序P(C),主返 P(E):5 P(B):10 P(C):7,TOP,62,e a d e a a,（12）这时要判定ch?e。,子程序P(C),主返 P(E):5 P(B):10 P(C):7,TOP,63,e a d e a a,（13）现在che,于是再读入一个字符a。,子程序P(C),主返 P(E):5 P(B):10 P(C):7,TOP,64,e a d e a a,（14）新P(C)调用递归出口子程序SCOUT，将返回栈中新P(C)在原P(C)中的返回地址P(C):7取出。,子程序P(C),主返 P(E):5 P(B):10 P(C):7,TOP,65,e a d e a a,（14）新P(C)调用递归出口子程序SCOUT，将返回栈中新P(C)在原P(C)中的返回地址P(C):7取出。,子程序P(C),主返 P(E):5 P(B):10,TOP,66,e a d e a a,（15）原P(C)调用递归出口子程序SCOUT，将返回栈中原P(C)在P(B)中的返回地址P(B):10取出。,子程序P(C),主返 P(E):5 P(B):10,TOP,67,e a d e a a,（15）原P(C)调用递归出口子程序SCOUT，将返回栈中原P(C)在P(B)中的返回地址P(B):10取出。,子程序P(B),主返 P(E):5,TOP,68,e a d e a a,（16）P(B)调用递归出口子程序SCOUT，将返回栈中P(B)在P(E)中的返回地址P(E):5取出。,子程序P(B),主返 P(E):5,TOP,69,e a d e a a,（16）P(B)调用递归出口子程序SCOUT，将返回栈中P(B)在P(E)中的返回地址P(E):5取出。,主返,TOP,子程序P(E),70,e a d e a a,（17）P(E) 子程序判别ch?a。,主返,TOP,子程序P(E),71,e a d e a a,（18）现在第个输入字符是a，于是读入下一个字符，它又是a,主返,TOP,子程序P(E),72,e a d e a a,（19）P(E)子程序调用子程序P(A)，P(A)调用递归入口子程序SCIN，将P(A)在P(E)中的返回地址送入返回栈中,主返 P(E):8,TOP,子程序P(E),73,e a d e a a,（19）P(E)子程序调用子程序P(A)，P(A)调用递归入口子程序SCIN，将P(A)在P(E)中的返回地址送入返回栈中,主返 P(E):8,TOP,74,e a d e a a,（20）子程序P(A)判断ch?a。,主返 P(E):8,TOP,75,e a d e a a,（21）现在cha，于是又读入下一个字符，由于输入串eadeaa后面再也没有其他字符了，故读入的是句子的终结符#,主返 P(E):8,TOP,子程序P(A),76,e a d e a a,（21） P(A)调用递归出口子程序SCOUT，将返回栈中P(A)在P(E)中的返回地址P(E):8取出。,主返 P(E):8,TOP,子程序P(A),77,e a d e a a,（21） P(A)调用递归出口子程序SCOUT，将返回栈中P(A)在P(E)中的返回地址P(E):8取出。,主返,TOP,子程序P(E),78,e a d e a a,（21） P(E)调用递归出口子程序SCOUT，将返回栈中P(E)在主程序中的返回地址取出，即返回主程序，结束。,主返,TOP,子程序P(E),79,e a d e a a,（21） P(E)调用递归出口子程序SCOUT，将返回栈中P(E)在主程序中的返回地址取出，即返回主程序，结束。,栈底,TOP,子程序P(E),80,要求：不含有左递归，并且每个非终结符的各个选择所推出的终结符号串首符号集合两两不相交。,也就是说，字符串eadeaa被语法分析程序 所接受，这表明字符串eadeaa是文法（）的句子。,81,再举一个例子,GE=(+, (,), , E,F,T,E,T, P, E) P: E:=TE E:=+TE| T:=FT T:=*FT| F:=(E)|i,82,用类PASCAL语言写出它的递归子程序,规则 E:=+TE| PROCEDURE E; BEGIN IF ch=+ THEN BEGIN getch(ch); T; E END END,规则 E:=TE PROCEDURE E; BEGIN T; E END,83,规则 T:=FT PROCEDURE T; BEGIN F; T END,规则 T:=*FT| PROCEDURE T; BEGIN IF CH=* THEN BEGIN getch(ch); F; T END END,用类PASCAL语言写出它的递归子程序,84,PROCEDURE F; BEGIN IF CH=( THEN BEGIN getch(ch); E; IF ch=) THEN getch(ch) ELSE error END ELSE IF CH=i THEN getch(ch) ELSE error END,规则 F:=(E)|i,85,4. 递归子程序法特点 优点 （1）程序结构和层次清晰，易于手工实现 。 （2）子程序与文法规则一一对应，但要求对文法规则消除左递归和回溯。 （3）可以加入语义加工子程序 缺点 （1）编写程序和调试工作量大 （2）对上下文无关文法需要改写,86,四、LL（1）分析法 1.定义 2.LL（1）分析方法 3.构造分析表 4.LL（1）文法,87,1. 定义 LL（1）分析方法也是一种自顶向下不带回溯的分析方法，LL的意思是：从左（Left）到右扫描输入符号串并建立它的最左推导（Left most derivations）。数字是指向前看一个符号来决定选择同一个非终结符不同规则。如果向前查看K个符号（K1）才能确定应选规则时，这种语法分析方法就称LL（K）分析法。,88,2. LL（1）分析方法 （1）基本思想 借助于一张分析表及一个语法分析栈，在一个总控程序控制下实现。我们通常把按LL（1）方法执行语法分析任务的程序称为LL（1）分析程序或LL（1）分析器，它由一个总控程序、一张分析表和一个分析栈组成，如下图所示。,a1 a2 ai an #,输入串,总控程序,分析表m,X . . . #,分析栈,89,（2）LL（1）方法分析过程 考虑文法: FT * （）i 1）建立文法LL（1）的分析表 相应的分析表如下表所示（其构造方法，在后面叙述)。,90,91,由上述分析过程可以看出，在分析的每一时刻，当前已读过的符号与栈中的符号一起总是构成了当前的左句型，（）分析器确实构造了输入串的一个最左推导。,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 # # 成功,92,（3）一般分析步骤 其步骤如下： 1） 分析开始时，首先将符号#及文法的开始符号依次置于分析栈的底部，并把各指示器调整至起始位置,即分别指向分析栈的栈顶元素和输入串的首字符。然后反复执行第（2）步 2） 设在分析的某一步，分析栈及余留的输入符号串处于如下格局 #X1X2Xm-1Xm aiai+1# 其中，m为分析过程中所得的文法符号，此时，可视栈顶符号m的不同情况，分别做如下的动作:,93,若m，则以m及ai组成符号对（m，ai）查分析表，设m,ai为一产生式，譬如说Xm，此时将m从分析栈中退出，并将按反序推入栈中（即用该产生式推导一步），从而得到新的格局: #X1X2Xm-1WVU aiai+1# 但若m，ai“”，则调用出错处理程序进行处理 ;,94,若mai#，则表明栈顶符号已与当前正扫视的输入符号得到匹配，此时应将m（即ai）从栈中退出，并将输入符号指示器向前推进一个位置； 若mai#，则表明输入串已完全得到匹配，此时即可宣告分析成功而结束分析工作。,95,(4)几点说明 分析表M根据具体文法构造，文法不同M就不同 LL（1）分析法的总控程序对于不同文法总是一样的。 分析表的元素MA，a或指出应选规则或指出错误（空白时） LL（1）语法分析程序的机器模型是一个下推自动机,构造一个LL（1）分析器问题，主要归结为构造LL（1）分析表的问题。,96,3. 构造分析表 （1）头终结符号集合和后继终结符号集合 1）头终结符号集合 定义 为了构造分析表，我们引进与文法有关的集合FIRST集和FOLLOW集。假定是文法G的任一符号串，或者说（VTV）* ，我们定义 FIRST（）a*a，a 特别是，若*，则规定 FIRST（） 即 FIRST（）是的所有可能推导的开头终结符或可能的,97,例如：设文法G T AB A PQ|BC P pP| Q qQ| B bB|e C cC|f 求FIRST（PQ）,由定义有 PQ pPQ=p PQ Q Q q Q q PQ Q Q 所以 FIRST（PQ）=p,q, 同理 FIRST（BC) =b,e,对于一个简单的文法我们用手工可以求得其FIRST集，对于复杂的文法我们通常使用下述算法求解,98,构造头终结符号集合FIRST的算法 对于文法中的每一个文法符()，构造（）时， 只要连续使用下列规则，直至每个集不再扩大为止。 a.若X，则（）。 b.若，且有形如a规则（a），或的规则，把a或（和）加入（）中。 c.设文法中有形如Y的规则，若，则将 FIRST（）中一切非符号加进（）中，对于一切 2ik，若*，则把2中首符号集（除外）也加进FIRST（）中，如此继续下去，直到k-1 *，则把YK中首符号集(除外)也入FIRST(X)中。 d.若每个非终结符号都可能推导出空符号串，即 *，则把也加进（）中。,99,现在，可以对文法G的任何符号串n， 可按如下步骤构造FIRST（）。 首先置FIRST()=,然后将FIRST(X1)中一切非的符号加进FIRST（）中，若FIRST（），再将FIRST（）的一切非加进FIRST（）中，如此等等。最后，若对于in，（i），则再将加进（）中。,100,考虑文法: FT * （）i,由算法步骤 a.得 FIRST（+）=+ FIRST（*）=* FIRST（）=（ FIRST（）=） FIRST（i）=i,由算法步骤 b.得 FIRST（E）=+， FIRST（T）=*， FIRST（F）=（，i,101,文法: ,FT *,（）i 对于算法步骤 c.和 d. 因为FT且F不能推出 所以 FIRST（T）=FIRST（F）；所以FIRST（T）不能被加入FIRST（T）,利用该算法还能方便地得到如下的符号串头终结符号集： FIRST（TE）=FIRST（T） =FIRST（F） =（，i FIRST（+TE）=FIRST（+） FIRST（FT）=FIRST（F）=（，i FIRST（*FT）=FIRST（*）=* FIRST（E）=FIRST（）=（ FIRST（ ）=,102,2)后继终结符号集合 定义 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义 FOLLOW（A）= a|S *Aa,a 特别是，若S *A，则规定#FOLLOW（A） 即： FOLLOW（A）是所有句型中出现在紧接A之后的终结符或#,103, 构造后继符号集合FOLLOW的算法 对文法中每个非终结符，为了构造（），可反复应用如下规则，直到每个集不再扩大为止。 a.对于文法的开始符号，令#（）。(因为 S * S 由定义#FOLLOW（S） b.若文法中有形如的规则，且，则将FIRST（）中一切非符号加进（）中。 c.若文法中有形如B或B的规则，且 *，则（）中全部终结符均属于（）,104,考虑文法: FT * （）i 1.求FOLLOW（E） ,） 由算法步骤 a.得：# FOLLOW（E）(E是文法开始符号） 由算法步骤 b.规则得： ） FOLLOW（E） 所以 FOLLOW（E） ,） 2.求FOLLOW（E） ,） 由算法步骤 c.规则得：FOLLOW(E) FOLLOW(E) 所以 FOLLOW（E） ,）,105,考虑文法: FT * （）i 3.求FOLLOW（T） +,） 1)由算法步骤 b.规则、 得： + FOLLOW（T）(因为 FIRST(E) -=+) 2)由算法步骤 c.规则得： FOLLOW（E）FOLLOW（T）即），# FOLLOW(T) (由规则得： *,所以由算法c.规则得： FOLLOW（E）FOLLOW（T）即），# FOLLOW(T) 所以 FOLLOW（T） +,）,106,考虑文法: FT * （）i 4.求FOLLOW（T) +,） 由算法步骤 c.规则得： FOLLOW（T）FOLLOW（ T)即 +， # ,） FOLLOW(T) 所以 FOLLOW（ T)+， # ,）,107,考虑文法: FT * （）i 5.求FOLLOW（F) +,*，,） 1)由算法步骤 b.规则 、得： * FOLLOW（F）(因为 FIRST(T) -=*) 2)由算法步骤 c.规则得： FOLLOW（T）FOLLOW（F） 即 +,），# FOLLOW(F) (由规则得： *,所以由算法c.规则得： FOLLOW（T）FOLLOW（F） 即 +,），# FOLLOW(F) 所以 FOLLOW（T） +,*,）,108,(2)构造分析表M 1)构造分析表M算法 求出集和集后，就可以构造文法的（）分析表，对于中每一个规则，可按如下算法确定表中各元素 对（）中每一终结符a，置A,a“” 若（），则对属于（）中的每一符号b(b为终结符或)，置，b“”； 把中所有不能按规则、定义的元素均置为出错。,109,2)构造分析表M过程（以文法为例） 下面列出文法符号串头终结符号集合和非终结符后继终结符号集合 文法: FT * （）i,110,对下述文法求出符号串头终结符号集合和非终结符后继终结符号集合整理得： 文法: FT * （）i FIRST（TE）=（，i FIRST（+TE）=+ FIRST（FT）=（，i FIRST（*FT）=* FIRST（E）=（ FIRST（ ）= FOLLOW（E）=FOLLOW（E）=），# FOLLOW（E） ,） FOLLOW（T）=FOLLOW（T）=），#，+ FOLLOW（T) +,） FOLLOW（F）=），#，+，*,111,2)构造分析表M过程（以文法为例） FT * （）i 1.对于规则 由于FIRST（TE）=(，i， 由算法步骤 于是置 ME,（ = “” ME，i = “”,112,2)构造分析表M过程（以文法为例） FT * （）i 2.对于规则 由于FIRST（+TE）=+ ， 由算法步骤 于是置 M ,+= “” 由于 ，则 FIRST（ ）=，而 FOLLOW（E）= )，# 由算法步骤 于是置 M，）= “ ” M，# = “ ”,113,2)构造分析表M过程（以文法为例） FT * （）i 3.对于规则FT 由于FIRST（FT）=(，i， 由算法步骤 于是置 MT，（ = “FT” M T，i = “FT”,114,2)构造分析表M过程（以文法为例） FT * （）i 4.对于规则* 由于FIRST(*FT)=* ， 由算法步骤 于是置 M，*=“*” 由于T ，则 FIRST（ ）=，而 FOLLOW（T）=），#，+， 由算法步骤 于是置 MT，） = “T ” MT，# = “T ” MT，+ = “T ”,115,2)构造分析表M过程（以文法为例） FT * （）i 5.对于规则（）i 由于FIRST（E）=（ ， 由算法步骤 于是置 MF，(= = “（）” 由于FIRST（i）=i ， 由算法步骤 于是置 MF，i = “i”,116,三、LL（1）分析法 4. LL（1）文法 (1)定义 一个文法G，如果它的LL(1)分析表M不含多重定义入口，则称该文法是LL（1）文法，可以证明,一个LL(1)文法所定义的语言,恰好是它分析表所识别全部句子。 所谓多重定义入口是指分析表中某MA，a有两个或两个以上产生式。,LL（1）文法是2型文法，但并不是所有2型文法都是LL（1）文法。对LL（1）文法进行LL（1）分析才是有意义的。,117,例如 ：文法： ita e b,它是2型文法却不是LL（1）文法。 我们可以按照上述方法构造它的分析表,从该表可以看出,元素MS,e有两条规则,即MS,e有多重定义入口,所以该文法不是LL（1）文法.,118,(2) LL(1)文法性质 LL（1）文法有一些明显的性质，它不是二义的，也不含左递归。 还可以证明是LL（1）的，当且仅当的任何两个规则 满足下面条件： 1) FIRST() FIRST()，也就是和推导不出 以某个同一终结符a为首的符号串。 2) 和中最多只有一个可能推出空串。 3) 如果 *，那么推出任何串不会以FOLLOW(A)中的 终结符开始，即若 *则FIRST() FOLLOW(A) ,注意：对于某些文法可以通过消除左递归和提取左因子（消除回溯） 变成LL（1）文法,119,4.3 自底向上语法分析,120,例2.24 设有文法G=(VN,VT,P,S),其中 VN=A,B,S VT=a,b,c,d,e P: S=aAcBe A=Ab|b B=d 试分析w=abbcde是否为此文法的句子。,121,为了具体实现方便，我们统一以符号“#”作为待分析符号串左右分界符，作为初始状态，先将符号串的左分界符压入符号栈，作为栈底符号。对符号串abbcde分析过程如下所示。,步骤 符号栈 输入符号串 动作 # abbcde# 左界符进栈 #a bbcde# a进栈 #ab bcde# b进栈 #aA bcde# 用Ab归约 # aAb cde# b进栈 #aA cde# 用AAb归约 #aAc de# c进栈 #aAcd e# d进栈 #aAcB e# 用Bd归约 #aAcBe # e进栈 #S # 用SAcBe归约 # S # 接受,P: S=aAcBe A=Ab|b B=d,122,4.3 自底向上语法分析 一、简单优先文法分析法 二、算符优先分析法 三、优先函数及其构造 四、LR分析法 五、二义性文法的应用,123,四、LR分析法 1. LR分析法一般概述 2. LR分析器工作原理 3. LR（0）分析表构造 4. SLR（1）分析表构造 5. LR（1）分析表构造 6. LALR分析表构造,124,1. LR分析法一般概述,前面我们介绍的几种语法分析方法如：递归下降分析法、LL(1)分析法对相应的文法都有一定的要求。 因此，上述这些方法在使用上有一定局限性。 LR分析法是1965年由Knuth提出一种自底向上语法分析方法，可用于一大类上下文无关文法分析，这种技术叫做LR（K）分析技术。,125,(1) LR（K）分析法定义 LR（K）分析法意思是：L是指从左(Left)到右扫描输入符号串，R是构造最右（Rightmost）推导的逆过程。K是指在决定分析动作时向前看符号的个数。若K0，就为LR(0)分析，说明分析动作时，不向前看任何符号， LR（1）分析，说明分析动作时只向前看一个符号。,126,(1) LR（K）分析法定义 这是一类对上下文无关文法进行“自左到右扫描和最左归约”的自底向上的分析方法，在这种分析过程中，它至多只向前查看个输入符号就能确定当前的动作是移进还是归约；若动作归约，它还能唯一地选中一个规则去归约当前已识别的句柄。,127,（2）LR分析法的特点 1) LR分析器（程序）基本上可以识别所有上下文无关文法写的编程语言结构，分析能力强且适用范围广 2) LR分析法是当前最一般“移进-归约”分析方法 3) LR分析法在自左向右扫描输入串时能发现其中错误，并能指出出错地点。 4) LR分析程序可以自动生成,128,(3) LR分析器的组成 从逻辑上说，一个LR分析器包括两部分：一个总控程序和一张分析表。一般说来，所有LR分析器总控程序是一样的，只是分析表各不相同。,129,(4) LR分析表种类 1) 最简单分析表LR（0）：局限性大，但它是建立其它分析表的基础 2) 简单分析表SLR：比较容易实现，SLR分析表的功能比LR（0）稍强些 3) LR（K）分析表：分析能力最强，但实现代价高。主要讨论LR（1） 4) LALR分析表：称为向前看LR分析表，功能介于SLR（1）和LR（1）之间，适用于大多数程序设计语言的结构，并且可以比较有效地实现。,130,2. LR分析器工作原理,Sm . . . S1 S0,总控程序,分析表,Sm . . . S2 S1 S0,Xm