第四章(1)自上而下语法分析

第四章第四章 自顶向下语法分析方法自顶向下语法分析方法v 自顶向下分析的一般过程和问题 v FIRST和FOLLOW集定义和计算 v LL(1)文法定义v LL(1)分析程序实现4.1 语法分析概述语法分析概述v语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。v高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。语法分析在编译系统中所处的位置语法分析在编译系统中所处的位置语法分析器的输入语法分析器的输入Token序列：词法分析的输出，是各个单词都正确的源程序的变换形式，是一个有限序列语法分析器的输出语法分析器的输出分析树：表示方法？见教材 P89错误处理信息：定位、继续编译语法分析的接口设计语法分析的接口设计v语法分析器的功能语法分析器的功能按照语言的语法构成规则,识别输入的符号输入的符号串串能否构成一个句子。这些规则是用文法的产生式来定义的。v问题问题对给定的一个输入串，如何判定它是不是一个句子？v方法方法根据文法的产生式规则，从开始符号出发，从开始符号出发，看能否推导出与这个输入串匹配的句子看能否推导出与这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。G=(E,i,+,*,(,),P,E)P：E E+E E E*E E (E)E i 解：使用最左推导：E E*E (E)*E (E+E)*E (i+E)*E (i+i)*E (i+i)*i例1：判定输入串(i+i)*i是否是下述文法的句子？结论结论：能够从开始符号出发推导出给定的输入串，因此，是句子。7 7 7 7例例2：已知符号串：已知符号串S=cad 文法文法GZ:ZcAd Aab|a 求证：求证：S L(GZ)分析过程分析过程是设法建立一棵语法树是设法建立一棵语法树,使语法树的末端结点与使语法树的末端结点与给定符号串相匹配给定符号串相匹配.1.1.开始开始开始开始:令令令令Z Z为根结点为根结点为根结点为根结点Z Z2.2.用用用用Z Z的右部的右部的右部的右部,符号串去匹配输入串符号串去匹配输入串符号串去匹配输入串符号串去匹配输入串 Z Zc cA Ad d完成一步推导完成一步推导完成一步推导完成一步推导Z ZcAdcAd 检查检查检查检查 c-cc-c匹配匹配匹配匹配 A A是非终结符是非终结符是非终结符是非终结符,将匹配任务交给将匹配任务交给将匹配任务交给将匹配任务交给A A8 8 8 83.3.选用选用选用选用A A的右部符号串匹配输入串的右部符号串匹配输入串的右部符号串匹配输入串的右部符号串匹配输入串 A A有两个右部有两个右部有两个右部有两个右部,选第一个选第一个选第一个选第一个 c cA Ad da ab bZ Z完成进一步推导完成进一步推导完成进一步推导完成进一步推导A Aabab 检查检查检查检查,a-a,a-a匹配匹配匹配匹配,b-d,b-d不匹配不匹配不匹配不匹配(失败失败失败失败)但是还不能冒然宣布但是还不能冒然宣布但是还不能冒然宣布但是还不能冒然宣布S S L(GZ)L(GZ)4.4.回溯回溯回溯回溯 即砍掉即砍掉即砍掉即砍掉A A的子树的子树的子树的子树 改选改选改选改选A A的第二右部的第二右部的第二右部的第二右部 Z Zc cA Ad da aA Aa a 检查检查检查检查 a-aa-a匹配匹配匹配匹配 d-dd-d匹配匹配匹配匹配建立语法树建立语法树建立语法树建立语法树,末端结点为末端结点为末端结点为末端结点为cadcad与与与与输入输入输入输入cadcad相匹配相匹配相匹配相匹配,建立了推导序列建立了推导序列建立了推导序列建立了推导序列 Z ZcAdcAdcadcad cadcad L(G(ZL(G(Z)S=cad GZ:S=cad GZ:ZcAdZcAd Aab|aAab|a分析工作要部分析工作要部分析工作要部分析工作要部分地或全部地分地或全部地分地或全部地分地或全部地退回去重做叫退回去重做叫退回去重做叫退回去重做叫回溯回溯回溯回溯常用的语法分析方法：常用的语法分析方法：自顶向下分析法自顶向下分析法：从文法的开始符号出发，向下推导(使用最左推导)，尽可能使用各种产生式，推导出与输入串匹配的句子，从而建立语法树。自底向上分析法自底向上分析法：从输入符号串开始，逐步进行归约(最右推导的逆过程)，直至归约到文法的开始符号，从而建立语法树。具体分类具体分类：自顶向下分析 递归下降分析预测分析(LL)自底向上分析 算符优先分析 LR分析4.2 自顶向下语法分析自顶向下语法分析v自上而下分析主要是：对任何输入串，试图用一切可能的办法，从文法的开始符号出发，自上而下地为输入串建立一个语法树。v从推导的角度看，从开始符号出发，使用最左推导，试图推导出与输入符号串相同的句子。v从语法树的角度看，从根节点出发，反复使用所有可能的产生式，谋求输入串的匹配，试图向下构造一棵语法树，其末端节点正好与输入符号串相同。v需要反复试探。句型的句型的推导推导v 最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换 最右推导被称为规范推导。由规范推导所得的句型称为规范句型。复习自顶向下分析方法特点1.分析过程是分析过程是带有预测带有预测的，对输入符号串要预测属于什么的，对输入符号串要预测属于什么 语法成分，然后根据该语法成分的文法建立语法树。语法成分，然后根据该语法成分的文法建立语法树。2.分析过程是一种分析过程是一种试探试探过程，是尽一切办法过程，是尽一切办法(选用不同规则选用不同规则)设法建立语法树的过程，由于是试探过程，故难免有失败，设法建立语法树的过程，由于是试探过程，故难免有失败，所以分析过程需进行所以分析过程需进行回溯回溯，因此我们也称这种方法是带，因此我们也称这种方法是带 回溯的自顶向下分析方法。回溯的自顶向下分析方法。例1：设有文法(1)S xAy(2)A|=现有输入串：x=y 其分析过程如右：SxAy*失败，需要退回，重新选取失败，需要退回，重新选取A A的侯选式，这时使得分析的侯选式，这时使得分析器的动作不稳定器的动作不稳定思考：产生回溯的原因？X=y输入符号串：问题问题1：回溯：回溯真正原因是：文法的产生式有问题。回溯问题14141414什么是回溯什么是回溯?分析工作要部分地或全部地退回去重做叫分析工作要部分地或全部地退回去重做叫回溯回溯造成回溯的条件：造成回溯的条件：文法中，对于某个非终结符号的规则其右部文法中，对于某个非终结符号的规则其右部 有多个选择，并根据所面临的输入符号不能准确有多个选择，并根据所面临的输入符号不能准确 的确定所要选择时，就可能出现回溯。的确定所要选择时，就可能出现回溯。回溯带来的问题：回溯带来的问题：严重的效率低，只有在理论上的意义而无实际意义严重的效率低，只有在理论上的意义而无实际意义U:=1|2|3 左递归左递归：文法中存在存在某个AVn，有A A。直接左递归直接左递归：有产生式A A间接左递归间接左递归：例2：设有文法G(E)：(1)E E+T|T (2)T T*F|F (3)F (E)|i现有输入串i*i+i,分析过程是：EE+TE+TE+T失败：对左递归文法使用失败：对左递归文法使用最左推导，出现死循环。最左推导，出现死循环。思考：产生左递归的原因？问题问题2：左递归：左递归真正原因是：文法的产生式有问题。结论结论1.左递归和回溯问题的产生直接与描述语言的文法有关2.应该改造文法，使其不含左递归和回溯，才能进行确定的自顶向下分析4.3 问题的解决方法问题的解决方法v消除左递归消除左递归v消除回溯消除回溯4.3.1 消除左递归消除左递归(1)(1)直接左递归的消除：直接左递归的消除：假定产生式为：PP|PP|，将其替换为形式等价的产生式组：例2：文法 E E+T|T T T*F|F F(E)|i消去左递归后为：T FTT*FT|PP P P E TEE+TE|F (E)|iv证明的关键步骤：证明的关键步骤：P-P|P-|P-(|)P-P,P-|P-P,P-|P 一般而言，若产生式形式为：一般而言，若产生式形式为：AAA1 1|A|A2 2|A|An n|1 1|2 2|m m 将其替换为：将其替换为：A1 B|2 B|m BB1 B|2 B|n B|练练 习习v消去文法GS的左递归S(T)|a+S|aT T,S|SS (T)|a+S|aT STT ,ST|答案：例：给定间接左递归文法，请消除左递归 1)1)代入代入 2)2)消除直接左递归消除直接左递归S Qc|cQ Rb|bR Sa|a解：第解：第1步步：为R、S、Q排序 第第2步步：代入：将R代入Q,Q代入S，得到新的文 法产生式组：R Sa|a Q Sab|ab|b S Sabc|abc|bc|c 第第3步步：消去S的直接左递归，得到S abcS|bcS|cSS abcS|(2)(2)间接左递归的消除方法间接左递归的消除方法v方法方法是是:反复“提取公共左因子提取公共左因子”，使得文法的每个非终结符号的各个候选式的首终结符集两两不相交，来避免回溯。设产生式为设产生式为：A1 1|2 2|n n AAA 1|2|n替换为：4.3.2消除回溯消除回溯v例3：有如下两个产生式：if E then S1 else S2;if E then S1;提取左因子后：if E then S1 B;B else S2|;练习练习v提取下述文法的左因子S (T)|a+S|aT ST T ,ST|S (T)|aS S +S|T STT ,ST|S答案:问题问题:如果希望没有回溯，对文法如果希望没有回溯，对文法有什么要求？有什么要求？v回溯产生的真正原因真正原因是：某非终结符对应多个侯选式，它们右部的第一个终结符相同，从而导致语法分析器选择了错误的侯选式。v如果希望没有回溯，对文法有什么要求？对不含左递归的文法G，对某非终结符的侯选式侯选式：First()=a|a,aVT 若 ，则 First()*4.4.1 4.4.1 侯选式的首终结符集的定义侯选式的首终结符集的定义即，由该候选式推导出的所有符号串中的第一个终结符的集合。4.4 LL(1)文法文法例：对右边的文法G，每个候选式的First集为：SApAa|AcAAa aAFirst(Ap)=a,c,pFirst(a)=aFirst()=First(cA)=cFirst(aA)=a解：解：SApSBqAaAcABbBdB 练习：练习：求给定文法的每个候选式的First集First(S1)=First(Ap)a,c First(S2)=First(Bq)=b,d First(A1)=aFirst(A2)=cFirst(B1)=bFirst(B2)=d解：解：(1)S xAy(2)A =|v在右边给定的文法中，A的候选式有两个，其首终结符集为：First(A1)=First(A2)=相交,就会产生回溯 因此，因此，只要存在某个非终结符的多个候选式的的多个候选式的首终结符集相交首终结符集相交，就会在推导的某时刻产生回溯。从而导致语法分析器选择了错误的侯选式。v因此，不产生回溯的条件不产生回溯的条件就是：对非终结符A的任意两个不同的侯选式ai 和aj，都有：First(ai)FirstFirstFirstFirst(aj)=v当要求用A进行匹配时，就能根据所面临的输入字符，准确地选取一个A的侯选式。32323232例子例子设有文法设有文法GS:S-Aa|BbA-d|cAB-b|aB对对S:FIRST(Aa)=d,c,FIRST(Bb)=a,b,FIRST(Aa)FIRST(Bb)=对对A:FIRST(d)=d,FIRST(CA)=c,FIRST(d)FIRST(Ca)=对对B:FIRST(b)=b,FIRST(aB)=a,FIRST(b)FIRST(aB)=若给定若给定 w=abb则自顶而下分析对应的推导为则自顶而下分析对应的推导为:S=Bb=aBb=abb求非终结符求非终结符A A的的FirstFirst集的算法集的算法 求某一非终结符A的首终结符集First(A)的算法为：v1.若有产生式Aa,aVT，把a加到First(A)中；v2.若有产生式A,把加到First(A)中；v3.若有产生式AX，XVN，把First(X)中非元素加到First(A)中；v4.若有产生式AX1X2X3.Xk,其中X1X2.XkVN。则当X1X2X3.Xi=(1ik)时，把First(Xi+1.Xk)的非元素加到 First(A)中；当X1X2X3.Xk=时，把First()加入First(A)中v5.重复执行上述过程，直到First(A)不再增大*SApSBqAaAcABbBdB 例：用算法求下述文法的每个非终结符的First集First(A)=a,cFirst(B)=b,dFirst(S)=First(A)First(B)=a,c,b,d 解解：vE TEE +TEE T FTT *FTT F (E)F i First(F)=(，i First(T)=*，First(E)=+，First(T)=First(F)=(，i First(E)=First(T)=(，i 练练 习习求下列文法的每个非终结符的First集 是否满足：没有左递归，每个侯选式的首终结符集不相交这两个条件，就一定能进行有效的自顶向下分析呢？思考题思考题确定的自上而下的分析v举例1：对于文法G1S：SpA SqB AcAd Aa对输入串pccadd，自上而下的推导过程是：S=pA=pcAd=pccAdd=pccadd对应的分析树：v例2：对于文法G2S：SAp SBqAa AcA Bb BdB输入串ccap，自上而下的推导过程是：S=Ap=cAp=ccAp=ccap4.4.2 4.4.2 后随符号集的定义后随符号集的定义v假定S是文法的开始符号，对于 AN N：Follow(AFollow(A)=a|S)=a|SAaAa，aaT T 特别，若 S SAA，则，则，#FOLLOW(A)FOLLOW(A)v当非终结符A面临a时，a不属于A的任何侯选首终结符集，但A的某个候选首终结符集中含，只有当a FOLLOW(A)FOLLOW(A)时才能自动进行匹配。*注：注：FOLLOW集合中不能有集合中不能有v对右边给定的文法，求A的后随符号集follow(A)SApAa|AcAAa aAfollow(A)=p求非终结符求非终结符A A的的FollowFollow集的算法集的算法 1.1.如果如果A A是开始符号，是开始符号，Follow(AFollow(A)2.2.若有产生式若有产生式B BAa,aAa,aVVT T，则则把把a a加入到加入到Follow(AFollow(A)中；中；3.3.若有产生式若有产生式B BAXAX，X XVVN N，则则把把First(XFirst(X)中非中非元素加入元素加入Follow(AFollow(A)中；中；4.4.若若B BAA 或或 B BAA，=，则则把把Follow(BFollow(B)加入到加入到Follow(AFollow(A)中；中；5.5.连续使用上述规则，直到连续使用上述规则，直到Follow(AFollow(A)不再增大。不再增大。*例:求下题的Follow集 SApSBqAaAcABbBdB 解：Follow(S)=#Follow(A)=p Follow(B)=q规则1规则2规则2练练 习习1.E TE2.E +TE3.E 4.T FT5.T *FT6.T 7.F(E)8.F i follow(E)=#，)follow(E)=follow(E)=#，)follow(T)=(first(E)-)follow(E)=#,),+follow(T)=follow(T)=#，)，+follow(F)=(first(T)-)follow(T)=*,#,),+E是开始符号，应用规则1，根据产生式7，应用规则2根据产生式1，应用规则4根据产生式2，应用规则3，根据产生式2，3，应用规则4根据产生式4，应用规则4根据产生式4，应用规则3根据产生式4，6，应用规则4求下题的Follow集例：仍讨论文法GS:S AB|bC A b|B aD|CAD|b D aS|c 所有非终结符求FOLLOW集过程如下：FOLLOW(S)=#FOLLOW(D)FOLLOW(A)=aa,cFOLLOW(S)FOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B)FOLLOW(C)从FOLLOW(S)=#开始，不断循环求解直到所有 FOLLOW集不再增大，最后可得：FOLLOW(S)=#FOLLOW(A)=a,c,#$FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#4.4.3 LL(1)分析方法分析方法 所谓LL(1)分析方法。如此命名该分析方法的原因在于相应的语法分析将按自左至右的顺序扫描输入符号串，并在此过程中产生一个句子的最左推导。至于括号中的“1”，则表示在分析过程中，每进行一步推导，只要向前查看一个输入符号，便能确定当前所应选用的产生式（规则）。因此，我们通常把按上述方法执行语法分析任务的程序称为LL(1)分析程序或LL(1)分析器。v(对文法进行不带回溯的确定的自顶向下分析的条件)，据此判别是否为LL(1)文法。(1)文法不含左递归(2)对文法中的任一个非终结符A的各个候选式的首终结符集两两不相交(是否有回溯)，即：若A1|2|n ，则 First(ai)First(First(aj)=(i (i j )j )(3)对文法中的每个非终结符A,若它的某个首终结符集含有，则 First(A)Follow(Follow(A)=LL(1)LL(1)文法的判别文法的判别v例：判断下述文法是否是LL(1)文法：S aASS bA bAA 解：(1)该文法不含左递归 (2)First(SaAS)=a First(Sb)=b First(AbA)=b First(A)=S和A的侯选式的first集都不相交，满足条件2 (3)由于 First(A)Follow(A)=First(S)=a,b Follow(A)First(A bA)不满足条件3，则不是LL(1)文法练练 习习判断给定的文法是否为LL(1)文法，若不是，进行改造v解答：First(Aab)=a;First(Aa)=a;不满足条件2，故不是LL(1)文法v改造方法：(消除回溯提取公因子)S SxAyxAy;A;Aa(b|a(b|)=SxAy;AaA;A b|S xAyA ab|av例3：使用下述文法对 i+i 进行分析：E TE E+TE|T FT T *FT|F(E)|i第一步：iFirst(TE)iFirst(FT)iFirst(F)ETEFTi第三步：+First(E)第二步：+first(T)First(T)，+Follow(T)自动匹配,不读输入符号+TEFTiLL(1)LL(1)分析过程分析过程follow(E)=#，)follow(E)=follow(E)=#，)follow(T)=follow(E)(first(E)-)=#,),+follow(T)=follow(T)=#，)，+follow(F)=(first(T)-)follow(T)=*,#,),+LL(1)LL(1)文法的分析过程文法的分析过程v假设要用非终结符A进行匹配，面临输入符号a，A的所有侯选式为：A1|2|nv分析过程为分析过程为：(总结)若a First(Ai),使用i去匹配。若a不属于任何一个产生式的首终结符集，v(1)若不属于任何一个 First(Ai)，则出错。v(2)若属于某个First(Ai),同时a Follow(A),则让A 与自动匹配；否则，a的出现是一种语法错误。4.5 递归下降分析方法递归下降分析方法v是进行语法分析的一种方法v要求文法是LL(1)文法v实现思想：为文法中每个非终结符编写一个递归过程，为文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，串，当某非终结符的产生式有多个候选式时，按按LL(1)形式唯一确定选择哪个候选式进行形式唯一确定选择哪个候选式进行推导，若遇到某候选式为推导，若遇到某候选式为，认为其自动匹，认为其自动匹配。把这些配。把这些递归过程组合起来就构成了文法递归过程组合起来就构成了文法的递归下降分析程序。的递归下降分析程序。基本架构基本架构(1)(1)对于每个非终结符号的产生式对于每个非终结符号的产生式Uu1|u2|un处理处理的方法如下：的方法如下：U()ch=当前符号;if(ch是u1符号串的第一个符号)处理u1 else if(ch是u2符号串的第一个符号)处理u2else error()由于无回溯的文法保证选择是唯一的。当存在时，可以用error()替代为return;这样可以较晚发现错误。约定：进入这个过程时，已读入U的第一个符号。离开这个过程时，下一个符号已经被读到当前符号。基本架构基本架构(2)(2)对于U的每个右部ui=x1x2xn的处理架构如下：处理x1的程序；处理x2的程序；处理xn的程序；v如果右部为空，则不处理。基本架构基本架构(3)(3)对于右部中的每个符号xiv如果xi为终结符号：If(x=当前输入符号串中的符号)NextCh()；return;else出错处理v如果xi为非终结符号，直接调用相应的过程：xi()基本架构基本架构（4）对于形如Xi的产生式，在相应的子程序Pi()中，应该能够判断当前输入符号a是否属于集合FOLLOW(Xi)，从而决定是从Pi()返回还是报错。在给定的语法定义中选择与IF语句有关的产生式。:=if then else :=:=|=|=:=:=:=:=|:=0|1|2|3|9如：对应于产生式:=if then 的过程的算法描述为：ifs()gettoken();If (token!=“if”)error;getnexttoken();bool_expr();getnexttoken();If (token!=“then”)error;getnexttoken();exe_sentence();相应于产生式：:=的过程：bool_expr()gettoken();handle_variblehandle_varible();();Getnexttoken();If (token not in!(|=|=)error;Getnexttoken();handle_variblehandle_varible();();v思考 请写出for语句的递归下降的分析程序：:=for:=to do:=|:=*|/|:=:=|:=:=:=.例：为下列表达式文法GE编写递归下降识别程序。E E+T|T T T*F|F F(E)|i解：解：步骤步骤1：消除左递归：消除左递归：E TE E+TE|T FT T*FT|F(E)|i 步骤步骤2：编写递归下降识别子程序，：编写递归下降识别子程序，这里使用这里使用C语言形式。见下页图。语言形式。见下页图。步骤3：编写递归下降识别主程序main()lookahead=getsymbol();E();if lookahead=$exit;else error();使用该识别程序识别输入串：使用该识别程序识别输入串：i*i+i，首先读入符号，首先读入符号i，然后调用子，然后调用子程序程序E，在，在E中调用子程序中调用子程序T，在，在T中调用子程序中调用子程序F，匹配，匹配i，读入下一符，读入下一符号号*，子程序，子程序F调用完毕，回到调用完毕，回到T。在。在T中继续调用子程序中继续调用子程序T，匹配，匹配*，读入下一符号读入下一符号i。在。在T中继续调用子程序中继续调用子程序F，匹配，匹配i，读入下一符号，读入下一符号+，回到子程序回到子程序T。在。在T中递归调用子程序中递归调用子程序T，不执行任何操作返回，不执行任何操作返回T，进而返回进而返回T，进而返回，进而返回E。在。在E中继续调用子程序中继续调用子程序E，匹配，匹配+，读入下一，读入下一符号符号i，调用子程序，调用子程序T。在。在T中调用子程序中调用子程序F，匹配，匹配i，读入下一符号，为，读入下一符号，为输入串结束符输入串结束符$，返回，返回E。在。在E中递归调用中递归调用E，不执行任何操作返回，不执行任何操作返回E，进而返回，进而返回E。至此子程序。至此子程序E调用完毕，回到主程序，检查到达输入调用完毕，回到主程序，检查到达输入串末尾，从而识别成功。串末尾，从而识别成功。由于有些信息需要保留，通常在入口处需保留某些信息，出口时需由于有些信息需要保留，通常在入口处需保留某些信息，出口时需要恢复。由于递归过程是遵循先进后出要恢复。由于递归过程是遵循先进后出 规律，所以通常需要开辟先进规律，所以通常需要开辟先进后出栈来处理。后出栈来处理。递归分析程序的优点递归分析程序的优点v实现思想简单明了。程序结构和语法规则直接对应。v因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。v需要书写程序的语言支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效的。4.6 预测分析程序预测分析程序v递归下降分析法：采用递归过程。因此实现分析程序所使用的高级语言必须支持递归过程才行。v预测分析法是自顶向下分析的另一种方法。v使用下推自动机的方式实现。v使用一个二维分析表和栈联合进行控制来实现分析。预测分析器模型预测分析器的组成：预测分析器的组成：预测分析程序(与文法无关)先进后出栈预测分析表与文法有关v分析分析表表M:是一个从VN(VT#)到产生式的映射。在分析时遇到A和a时，应该选择MA,a中存放的产生式。如果MA,a为空，表示出现语法错误。分析表格式:i+*()#ETETEE+TE TFTFT T*FT Fi(E)第1列为非终结符第1行为终结符+#每个元素为产生式或空E TEE +TE|T FTT *FT|F(E)|i 总控程序:v将#压入堆栈中，将开始符号S压入堆栈中v读取第一个输入符号到a；v循环执行下述操作：栈顶符号弹出放入X中；如果X为终结符号：v如果X=a!=#，表明成功匹配a符号;读取下一个符号到a，否则出错；如果X=#v如果X=a，分析结束，接受句子。v如果 X!=a，出错处理。如果X为非终结符号,则查分析表M:v如果MX,a为空，出错处理。v如果MX,a=X1 X2Xn,则:将右部Xn X2 X1反序压入堆栈中。预测分析过程预测分析过程下面用预测分析方法对输入串i+i*i#进行分析，给出栈的变化过程如下：7#ET+i*i#+匹配1#Ei+i*i#ETE2#ETi+i*i#TFT 3#ETFi+i*i#Fi4#ETii+i*i#i匹配5#ET+i*i#T6#E+i*i#E+TE步骤 分析栈剩余输入串所用产生式步骤分析栈剩余输入串所用产生式8#ETi*i#TFT 9#ETFi*i#F i10#ETii*i#i匹配11#ET*i#T *FT12#ETF*i#*匹配13#ETFi#F i14#ETii#i匹配15#ET#T 16#E#E 17#接受 构造预测分析表构造预测分析表v预测分析过程的总控程序是固定的。对于某个文法，分析表是分析过程的核心。v表中MA,a=AX1X2Xn 表示对应于X1X2Xn字的首终结符可以是a。就是说X1X2Xn=aw。可以通过这个方式来确定分析表中的值。(即：求首终结符)*预测分析表的构造算法预测分析表的构造算法v对文法的每个文法符号X构造First(X)v对于每一产生式 A,对于每个终结符aFirst(),将A填入 MA,a；如果First()，则构造Follow(A)，对任何元素 bFollow(A)，将A填入MA,b；v将所有无定义的 MA,a 标上错误标志。如果文法是LL(1)文法，其预测分析表中没有多重定义的元素，可以进行确定的分析。例：求对应于下述文法的预测分析表：1.首先求first集E TEE +TE|T FTT *FT|F(E)|i First(E)=(，i First(E)=+，First(T)=(，i First(T)=*，First(F)=(，i 2.由于 First(E),First(T)求E和T的Follow集Follow(E)=#，)Follow(T)=#，)，+E TEE +TEE T FTT *FTT F(E)F ii+*()#ETETEE+TE TFTFT T*FT Fi(E)3.根据集合的值填表，得到综合练习综合练习设文法G(S)：S(L)|aS|aLL，S|S(1)消除左递归和回溯；(2)计算每个非终结符的First和Follow集；(3)构造预测分析表。预测分析表a，()SSaSS(L)SSSSSSSSLLSLLSLLL,SLLFirst(S)(,a Follow(S)#,，,)First(S)(,a,Follow(S)#,，,)First(L)(,a Follow(L)First(L)，,Follow(L)S(L)|aSS S|LSLL,SL|4.6自上而下语法分析程序的设计自上而下语法分析程序的设计 实现的语法成分包括实现的语法成分包括：(1)带类型的简单变量的说明语句；(2)算术表达式和布尔表达式；(3)简单赋值语句；(4)各种控制语句：如if语句、while语句、repeat语句、for语句 源程序举例：program example;const i5；vara,b,c:integer;x:char;beginif(a+c*3b)and(b3)then c:=3;x:=2+(3*a)-b*c*8;for x:=1+2 to 3 do b:=100;while ab do c:=5;repeat a:=10;until ab;end.总控程序的框架 void paser()/*语法分析总控程序*/token=getnexttoken();if(token 不是“program”)error()；/*程序中缺少program*/token=getnexttoken();if(token 不是标识符)error()；/*program后应跟程序名*/token=getnexttoken();if(token 不为;或()error();/*程序也可不带(input,output)*/token=getnexttoken();if(token 是 const)handle_const(token);/*调用常量说明处理*/if(token 是 var)handle_var(token)；/*调用变量说明处理*/token=getnexttoken();if(token 不是 begin)error();/*begin标识可执行程序开始*/token=getnexttoken();ST_SORT(token);/*分类调用处理各个可执行语句*/token=getnexttoken();if(token 不是 end.)error()；/*end.标识整个程序结束*/语句分类函数ST_SORT(token)v功能：根据传递的单词判断应该调用哪个语句的处理函数。ST_SORT(token)if(token 是 if）ifs()；if(token 是 for）fors()；if(token 是 while）whiles()；if(token 是 repeat）repeat()；if(token 是 标识符）assigns()else error();可执行语句语法分析的实现举例 if E then S1 else S2;ifs()/*当读取的首字符是if时，才调用该函数*/token=getnexttoken();/*读下一个单词，是E的一部分*/BEXP();/*调用布尔表达式的语法分析程序*/token=getnexttoken();/*读下一个单词*/if(token!=then)error;token=getnexttoken();ST_SORT();/*用ST_SORT()分类处理then后的不同语句*/token=getnexttoken();if(token=else)/*if then-else结构时处理else部分*/token=getnexttoken();ST_SORT();/*处理else后的可执行语句*/else if(token!=;)error;/*无else的if-then结构，后必有；*/