资源描述
自上而下语法分析方法自上而下语法分析方法第四章（第四章（1） 本节要求本节要求主要内容主要内容：1. 语法分析的任务和设计语法分析的任务和设计2. 自上而下语法分析方法及其相关概念自上而下语法分析方法及其相关概念重点掌握：重点掌握：1. 语法分析的任务和接口语法分析的任务和接口2.自顶向下自顶向下语法分析面临的问题及解决方法语法分析面临的问题及解决方法 3. LL(1)文法的判定及分析表的构造文法的判定及分析表的构造5. 能够使用递归下降分析方法和预测分析方能够使用递归下降分析方法和预测分析方法实现语法分析器，并对给定的输入串进行法实现语法分析器，并对给定的输入串进行分析分析 高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。 语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定输入的符号串的语法结构是否符合语法规则。4.1 语法分析概述语法分析概述 问题：问题： 在上一章词法分析中讲解了如何判断源程序中单词的正确性，并输出了正确的单词符号。那么如何知道如何知道这些正确的单词是否是否能构成正正确确的语法单位（表达式、语句或程序）呢？ 语法分析的任务语法分析的任务 在词法分析识别出正确的单词符号串的基础在词法分析识别出正确的单词符号串的基础上，分析并判定这些输入符号串是否上，分析并判定这些输入符号串是否符合语符合语法规则（即，是否是给定文法的一个句子）。法规则（即，是否是给定文法的一个句子）。 语法分析在编译系统中所处的位置语法分析在编译系统中所处的位置 语法分析器的输入语法分析器的输入 Token序列：词法分析的输出，是各个单词都正确的源程序的变换形式，是一个有限序列 语法分析器的输出语法分析器的输出 分析树：表示方法？线索树 错误处理信息：定位、继续编译4.2 语法分析的接口设计语法分析的接口设计 语法分析器的功能语法分析器的功能 按照语言的语法构成规则, 识别输入符号串输入符号串能否构成一个句子。这些规则是用文法的产生式来定义的。 问题问题 对给定的一个输入符号串，如何判定它是不是一个句子？ 方法方法 根据文法的产生式规则，看能否建立与输入看能否建立与输入串匹配的语法树串匹配的语法树。（第二章使用“推导”）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例：判定输入串(i+i)*i是否是下述文法的句子？结论结论：能够从开始符号出发推导出给定的输入串， 因此，是句子。 常用的语法分析方法常用的语法分析方法（根据建立语法树的方向）（根据建立语法树的方向）：自顶向下分析法自顶向下分析法：从文法的开始符号出发，向下推导(使用最左推导) ，尽可能使用各种产生式，推导出与输入串匹配的句子，从而建立语法树。自底向上分析法自底向上分析法：从输入符号串开始，逐步进行归约(最右推导的逆过程)，直至归约到文法的开始符号，从而建立语法树。具体分类具体分类：自顶向下分析 递归下降分析预测分析(LL)自底向上分析 算符优先分析 LR分析4.2 自上而下语法分析面临的问题及其自上而下语法分析面临的问题及其解决方法解决方法 自上而下分析：对任何输入串，试图用一切可能的办法，从文法的开始符号出发，自上而下地为输入串建立一个语法树。 从推导的角度看，从开始符号出发，使用最左推导，试图推导出与输入符号串相同的句子。 从语法树的角度看，从根节点出发，反复使用所有可能的产生式，谋求输入串的匹配，试图向下构造一棵语法树，其末端节点正好与输入符号串相同。 需要反复试探。 例1：设有文法(1) S xAy (2) A *|* 现有输入串：x*y 其分析过程如右：SxAy*失败，需要退回，重新选取失败，需要退回，重新选取A A的侯选式，这时使得分析的侯选式，这时使得分析器的动作不稳定器的动作不稳定思考：产生回溯的原因？x*y输入符号串：问题问题1：回溯：回溯真正原因是：文法的产生式有问题。左递归左递归：文法中存在存在某个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. 应该改造文法，使其不含左递归和回溯，才能进行确定的自顶向下分析问题的解决方法问题的解决方法消除左递归消除左递归消除回溯消除回溯消除左递归消除左递归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) | i 一般而言，若产生式形式为：一般而言，若产生式形式为： 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|练练 习习 消去文法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. 间接左递归的消除方法间接左递归的消除方法 方法方法是是: :反复 “提取公共左因子提取公共左因子”，使得文法的每个非终结符号的各个候选式的首终结符集两两不相交，来避免回溯。 设产生式为设产生式为：A1 1| |2 2| | |n n AAA 1|2|n替换为：消除回溯消除回溯 例3：有如下两个产生式： if E then S1 else S2 if E then S1提取左因子后： if E then S1 B B else S2 | 练习练习 提取下述文法的左因子S (T) | a + S | aT ST T ,ST | S (T) | aS S + S | T STT ,ST | S答案:问题问题: : 如果希望没有回溯，对文法如果希望没有回溯，对文法有什么要求？有什么要求？ 回溯产生的真正原因真正原因是：某非终结符对应多个侯选式，它们右部的第一个终结符相同，从而导致语法分析器选择了错误的侯选式。 如果希望没有回溯，对文法有什么要求？对不含左递归的文法G，对某非终结符的侯选式侯选式： First() = a| a,aVT 若 ，则 First()即，由该候选式推导出的所有符号串中的第一个终结符的集合。侯选式的首终结符集的定义侯选式的首终结符集的定义 例：对右边的文法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 *|* 在右边给定的文法中，A的候选式有两个，其首终结符集为：First(A1) = *First(A2) = *相交,就会产生回溯 因此，因此，只要存在某个非终结符的多个候选式的的多个候选式的首终结符集相交首终结符集相交，就会在推导的某时刻产生回溯。从而导致语法分析器选择了错误的侯选式。 因此，不产生回溯的条件不产生回溯的条件就是：对非终结符A的任意两个不同的侯选式ai 和aj ，都有：First(ai)aj) = 当要求用A进行匹配时，就能根据所面临的输入字符，准确地选取一个A的侯选式。非终结符非终结符A的首终结符集的定义的首终结符集的定义即，由该非终结符推导出的所有符号串中的第一个终结符的集合。对不含左递归的文法G，对某非终结符非终结符A： First(A) = a| A a,aVT 若A ，则 First(A) SApSBqAaAcABbBdB 练习：求给定文法的每个非终结符的First集。 解：解：First(A)=a,cFirst(B)=b,dFirst(S)=a,c,b,d求非终结符求非终结符A的的First集的算法集的算法 求某一非终结符A的首终结符集First(A)的算法为： 1.若有产生式Aa,aVT，把a加到First(A)中； 2.若有产生式A, 把加到First(A)中； 3.若有产生式AX，XVN，把First(X)中非元素加到First(A)中； 4.若有产生式AX1X2X3.Xk,其中X1X2.XkVN。则当X1X2X3.Xi =(1ik)时，把First(Xi+1.Xk)的非元素加到 First(A)中； 当X1X2X3.Xk=时，把First()加入First(A)中 5.重复执行上述过程，直到First(A)不再增大* SApSBqAaAcABbBdB 例：用算法求下述文法的每个非终结符的First集First(A) = a,cFirst(B) = b,dFirst(S) = First(A) First(B)= a,c,b,d 解解： E 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对应的分析树：a aS Sp pA A=S Sp pA Ac cA Ad d=S Sp pA Ac cA Ad dc cA Ad d=S Sp pA Ac cA Ad dc cA Ad dv例2：对于文法G2S：S Sp pA A=S Sp pA Ac cA A=S Sp pA Ac cA Ac cA A=S Sp pA Ac cA Ac cA Aa aSAp SBqAa AcA Bb BdB输入串ccap，自上而下的推导过程是：S = Ap = cAp = ccAp = ccap 例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) 用自动匹配 不读输入符号+TEFTi后随符号集的定义后随符号集的定义 假定S是文法的开始符号，对于 AN N： Follow(AFollow(A)=a|S)=a|SAaAa，aaT T 特别，若 S SA A，则，则，# # FOLLOW(A)FOLLOW(A)* * *当非终结符A面临a时， a不属于A的任何侯选首终结符集，但A的某个候选首终结符集中含，只有当a FOLLOW(A)时才能自动进行匹配。 对右边给定的文法，求A的后随符号集follow(A) SApAa |AcAAa aAfollow(A) = p求非终结符求非终结符A的的Follow集的算法集的算法 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集 (对文法进行不带回溯的确定的自顶向下分析的条件)，据此判别是否为LL(1)文法。 (1) 文法不含左递归 (2) 对文法中的任一个非终结符A的各个候选式的首终结符集两两不相交，即：若A1|2|n ，则 First(ai)aj) = (3) 对文法中的每个非终结符A,若它的某个首终结符集含有，则 First(A)A) = LL(1) 文法的定义文法的定义LL(1)文法的判别文法的判别 根据 LL(1)的三个条件来判断. 判别步骤: 1. 首先检查是否含有左递归 2. 若无，计算First集, 判别是否满足条件2(即是否有回溯) 3. 若存在某个A=,求A的 Follow集，并判别条件 (3) 是否满足(是否可以使用-产生式进行匹配)* 例：判断下述文法是否是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)文法，若不是，进行改造 解答：First(Aab)=a ; First(Aa)=a ; 不满足条件2，故不是LL(1)文法 改造方法：(消除回溯提取公因子)S SxAyxAy ; A ; Aa(b|a(b|) ) = SxAy ; AaA ; A b| S xAyA ab|a 例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)分析过程分析过程follow(E) =#，) follow(E) = follow(E) = #，) follow(T) =follow(E)(first(E)-) =#,),+ follow(T) =follow(T) =#，)，+ follow(F) =(first(T)-)follow(T) =*,#,),+ LL(1)文法的分析过程文法的分析过程 假设要用非终结符A进行匹配，面临输入符号a，A的所有侯选式为： A1|2|n 分析过程为分析过程为：(总结) 若a First(Ai),使用i去匹配。若a不属于任何一个产生式的首终结符集， (1)若不属于任何一个 First(Ai)，则出错。 (2)若属于某个First(Ai),同时a Follow(A), 则让A 与自动匹配；否则，a的出现是一种语法错误。4.3 确定的自上而下的语法分析确定的自上而下的语法分析递归下降分析方法递归下降分析方法 是进行语法分析的一种方法 要求文法是LL(1)文法 实现思想： 识别程序由一组过程组成。每个过程对应于文法的一个非终结符号。 每一个过程的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的过程来完成。基本架构基本架构(1)(1) 对于每个非终结符号的产生式对于每个非终结符号的产生式Uu1|u2|un处理处理的方法如下：的方法如下：U( ) ch=当前符号; if(ch是u1符号串的第一个符号) 处理u1 else if(ch是u2符号串的第一个符号) 处理u2elseerror() 由于无回溯的文法保证选择是唯一的。 当存在时，可以用error()替代为return;这样可以较晚发现错误。 约定：进入这个过程时，已读入U的第一个符号。离开这个过程时，下一个符号已经被读到当前符号。基本架构基本架构(2)(2) 对于U的每个右部ui=x1x2xn的处理架构如下：处理x1的程序；处理x2的程序； 处理xn的程序； 如果右部为空，则不处理。基本架构基本架构(3)(3)对于右部中的每个符号xi 如果xi为终结符号：If (x = 当前输入符号串中的符号)NextCh()；return;else出错处理 如果xi为非终结符号，直接调用相应的过程： xi() P75 表4.1的过程对应于下述文法：E TEE +TE |T FTT *FT |F (E) |i 实例：写实例：写IF语句的递归下降的分析程序语句的递归下降的分析程序方法：在给定的语法定义中选择与IF语句有关的产生式，再对每个非终结符写一个函数。 := if then := := | | = | = := := := := | :=0|1|2|3|9对应于非终结符，有产生式 := if then 则对应的函数可描述为：ifs() token =getnexttoken();If (token !=“if”) error; token = getnexttoken();bool_expr(); token = getnexttoken();If (token !=“then”) error; token = getnexttoken();exe_sentence(); 相应于非终结符，有产生式： := 的函数可描述为：bool_expr() gettoken();Getnexttoken();If (token not in ! ( | | = | = ) error;Getnexttoken(); 练习：请写出for语句的递归下降的分析程序：:= for := to do :=|:= *|/|:=:=| := := := .递归分析程序的优点递归分析程序的优点 实现思想简单明了。程序结构和语法规则直接对应。 因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 需要书写程序的语言支持递归调用。如果递归调用机制是高效的，那么分析程序也是高效的。预测分析程序预测分析程序 递归下降分析法：采用递归过程。因此实现分析程序所使用的高级语言必须支持递归过程才行。 预测分析法是自顶向下分析的另一种方法。 使用下推自动机的方式实现。 使用一个二维分析表和栈联合进行控制来实现分析。预测分析器模型 预测分析器的组成：预测分析器的组成：预测分析程序(与文法无关)先进后出栈预测分析表与文法有关 分析分析表表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 总控程序: 将#压入堆栈中，将开始符号S压入堆栈中 读取第一个输入符号到a； 循环执行下述操作： 栈顶符号弹出放入X中； 如果X为终结符号： 如果X = a != #，表明成功匹配a符号; 读取下一个符号到a，否则出错； 如果X = # 如果X = a ，分析结束，接受句子。 如果 X!= a ，出错处理。 如果X为非终结符号, 则查分析表M: 如果MX,a为空，出错处理。 如果MX,a=X1 X2Xn , 则: 将右部Xn X2 X1反序压入堆栈中。 预测分析过程预测分析过程下面用预测分析方法对输入串i+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+TE7#ET+i*i# +匹配步骤分析栈剩余输入串所用产生式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# #接受 构造预测分析表构造预测分析表 预测分析过程的总控程序是固定的。对于某个文法，分析表是分析过程的核心。 表中MA,a= AX1X2Xn 表示对应于X1X2Xn字的首终结符可以是a。就是说X1X2Xn=aw。可以通过这个方式来确定分析表中的值。(即：求首终结符)*预测分析表的构造算法预测分析表的构造算法 对文法的每个文法符号X构造First(X) 对于每一产生式 A,对于每个终结符aFirst(),将A填入 MA,a；如果First()，则构造Follow(A)，对任何元素 bFollow(A)，将A填入MA,b； 将所有无定义的 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) =#，)，+ 3.根据集合的值填表，得到i+*()#ETETEE+TE TFTFT T *FT Fi(E)综合练习综合练习设文法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.4自上而下语法分析程序的设计自上而下语法分析程序的设计 实现的语法成分包括实现的语法成分包括： (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) 功能：根据传递的单词判断应该调用哪个语句的处理函数。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 S2ifs( ) /*当读取的首字符是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结构，后必有；*/
展开阅读全文