ch5-自顶向下语法分析方法.ppt

Page 1,第五章 自顶向下语法分析,在上一章中用正规式描述了单词符号的结构，并研究了如何用有限自动机构造词法分析器的问题。由于正规式与正规文法是等价的，它们的描述能力有限，而高级语言的语法结构适合用上下文无关文法描述，因此，我们将上下文无关文法用作语法分析的基础。本章介绍编译程序构造中的一些典型的语法分析方法。,Page 2,语法分析就是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序).语法分析常用的方法:自顶向下分析与自底向上分析.而自底向上分析又可分为:算符优先分析与LR分析. 自顶向下分析也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子. 自顶向下分析方法分为:确定的和不确定的.确定的分析方法需要对文法有一定的限制;而不确定的方法是一种穷举的试探方法.,Page 3,5.1 确定的自顶向下分析,若有文法G1s： S-pA|qB A-cAd|a B-dB|b 构造输入串W=pccadd的语法树。 该文法的特点： 1）每个产生式的右部都由终结符号开始； 2）若两个产生式有相同的左部，则它们的右部由不同的终结符开始。,确定的自顶向下分析方法是从文法的开始符号出发，如何根据当前的输入符号唯一确定选用哪个产生式替换相应非终结符往下推导，或构造一颗相应的语法树。,这种文法完全可以根据当前的输入符号决定选 择哪个产生式往下推导,因此分析过程是唯一 确定的.,Page 4,文法G2S为： S-Ap S-Bq A-a A-cA B-b B-dB 给出输入串W=ccap的推导过程。 该文法的特点： 1）产生式的右部不全是由终结符开始； 2）若两个产生式有相同的左部，则它们的右部是由不同的终结符或非终结符开始； 3）文法中无空产生式。,Page 5,文法G3S为： S-aA S-d A-bAS A- 给出W=abd的推导过程。,Page 6,相关概念：FIRST 集,【定义】 设G=(VN,VT,S,P)是上下文无关文法,又设 是文法 G 的任一字符串，定义 的首符集 FIRST()= a | a, a VT 若 ， FIRST() FIRST()是从 可推导出的所有首终结符或可能的。,*,*,Page 7,相关概念：FOLLOW 集,【定义】 假设 S 是文法 G 的开始符号，对于 G 的任何非终结符 A，定义非终结符 A 的后继符号的集合： FOLLOW(A)=a |S .Aa.，aVT 。 特别是，若S.A，则规定 #FOLLOW（A）。 FOLLOW(A)是 G 的所有句型中紧接在 A 之后出现的终结符或 #。 这里 # 作为输入串的结束符。 因此,当文法中含有形如: A- A- 的产生式时,其中AVN, , V*,当和不同时推导出空时,则对非终结符A的替换仍可唯一地确定候选.,*,*,Page 8,相关概念：SELECT 集,【定义】 假设 A 是文法 G 的任一规则，定义规则 A 的选择集合 SELECT 为 ： SELECT(A)= 其中 AVN，(VNVT)*，,*,Page 9,LL(1)文法,这里的第一个 L 表示从左到右扫描字符串，第二个 L 表示最左推导，1 表示每一步只需向前看一个符号。,一个上下文无关文法 G 是 LL(1)文法， 当且仅当对 G 中每个非终结符 A 的任何两个不同的规则 A|， 满足: SELECT(A) SELECT(A)= 其中 、 中至多只有一个能推导出 串。,Page 10,5.2 LL(1)文法的判别,判断LL(1)文法的步骤: 1.求出能够推出的非终结符 1)初始化 2) 扫描文法的产生式 a)删除所有右部含有终结符的产生式,若以某一非终结符为左部的所有产生式都被删除,则将数组中对应该非终结符的标记修改为“否”; b)若某一非终结符的某一产生式右部为,则将数组中对应该非终结符的标志置为“是”,并从文法中删除该非终结符的所有产生式.,Page 11,判别步骤(续),3) 扫描产生式右部的每一符号 a)若所扫描到的非终结符号在数组中的对应标志是“是”,则删去该非终结符,若这使得产生式右部为空,则对产生式左部的非终结符在数组中对应的标志改为“是”,并删去该非终结符为左部的所有产生式; b)若所扫描到的非终结符号在数组中的对应标志是“否,则删去该产生式,若这使得产生式左部非终结符的有关产生式都被删去,则将数组中该非终结符对应的标志改成”否“. 4) 重复3),直到扫描完一遍文法的产生式,数组中非终结符对应的特征再没有改变为止.,Page 12,2.计算FIRST集,1)计算每一文法符号X的FIRST集-FIRST(X) (a)若XVT,则FIRST(X)= X ; (b)若XVN且有产生式X-a.,a VT,则a FIRST(X); (c)若XVN且有产生式X-,则 FIRST(X); (d) XVN且Y1, ,Yi都VN,而有产生式X- Y1 Yn.当Y1, ,Yi-1= (其中1i n),则FIRST(Y1)-, , FIRST(Yi-1)-,FIRST(Yi)都包含在FIRST(X)中; (e)若(d)中所有Yi= (i=1, ,n),则FIRST(X)=FIRST(Y1) FIRST(Y2) FIRST(Yn) ,*,*,Page 13,计算FIRST集(续),2)求每个符号串的FIRST集 a)若符号串 V*, =X1Xn,当X1不能= ,则置FIRST()=FIRST(X1); b)若对任何j(1ji-1, 2in), FIRST(Xj)则FIRST()=(FIRST(X1)-) (FIRST(X2)-) (FIRST(Xi-1)-) FIRST(Xi) ; c)当所有FIRST(Xj)都含有时,则 FIRST()= ( FIRST(Xj) .,*,Page 14,3.计算FOLLOW集,对文法中每一A VN计算FOLLOW(A) a)设S为文法中开始符号,将“#”加入FOLLOW(S)中; b)若A-B是一个产生式,则将FIRST()的非空元素加入FOLLOW(B)中;若= ,则将FOLLOW(A)也加入FOLLOW(B)中. c)重复使用(b)直到每个非终结符的FOLLOW集不再增大为止.,*,4.计算SELECT集,Page 15,5.3 某些非LL(1)文法到LL(1)文法的等价变换,在确定的自顶向下分析中,要求对给定语言的文法必须是LL(1)文法,然而不一定每个语言都有LL(1)文法. 在本节讨论如何对一个语言的非LL(1)文法变换为等价的LL(1)形式.由LL(1)文法的定义知道,当文法中含有直接或间接左递归,或含有左公共因子时,这样的文法肯定不是LL(1)文法. 下面首先设法消除文法中的左递归与提取左公共因子对文法进行等价变换.在某些情况下,使其变换为LL(1)文法.,Page 16,1.提取左公共因子 提取左公共因子是指当文法中含有形如： A1|2|.|n|1|2|.|m 的规则， 可以把它修改成： A A|1|2|.|m A1|2|.|n 经过反复提取左公共因子，就能够做到使每个非终结符的所有候选首符集变成两两不相交。 该做法的代价是大量引进非终结符和-产生式。,Page 17,【例】文法GS: SaAb Ade|d,利用提取公共左因子的方法对其进行改写，得到： SaAb AdA Ae| 这是一个 LL(1)文法,Page 18,【例】文法GS: Sad|Ae AaS|bA,对于非终结符 S 的规则，因为有： SELECT(Sad)SELECT(SAe) = aa,b 故它不是一个 LL(1)文法。 因为非终结符 S 的两个右部的公共左因子是隐式的，因此，再提取公共左因子之前，对 S 右部以非终结符 A 开头的规则，用A的两条规则进行相应替换，得到： Sad|aSe|bAe AaS|bA 对 S 提取公共左因子得 SaS|bAe Sd|Se AaS|bA,Page 19,【例】文法GS:,SAe|Bd AaAe|b BaBd|b,对于非终结符 S 的规则，因为有： SELECT(SAe)SELECT(SBd)=a,ba,b 故它不是一个 LL(1)文法。 对 S 规则，用A，B的两条规则进行相应替换，得到： SaAee|be|aBdd|bd AaAe|b BaBd|b 对 S 提取公共左因子得 SaS|bS” SAee|Bdd S”e|d AaAe|b BaBd|b 它还不是 LL(1)文法，但无论重复上述步骤多少次都无法改写为 LL(1)文法。,Page 20,假定文法中含有关于非终结符号 A 的产生式，其形如 AA| ，其中 不等于 ，不以 A 开头，我们称该文法为直接左递归或规则左递归文法。,2.消除左递归 一个文法含有下列形式的产生式: a)A-A 直接左递归 b)A-B,B-A 间接左递归 称为左递归文法. 1)消除直接左递归,产生式 AA| 定义的是重复 串且以 串开头的串。 修改的思路是用右递归代替左递归实现句子中某子串的重复。,Page 21,引进一个新的非终结符，把左递归规则改写成等价的非左递归形式： AA AA| 一般地，对于 A 的全部产生式（其中每个i不等于 ，每个j不以 A 开头）： AA1|A2|.|Am|1|2|.|n 可等价地改写成如下非左递归(右递归)形式： A1A|2A|.|nA A1A|2A|.|mA|,Page 22,【例4.2】文法GE:,EE+T|E-T|T TT*F|T/F|F F（E）|id 消除非终结符 E，T 的直接左递归，可等价地改写成如下非左递归形式： ETE E+TE|-TE| TFT T*FT|/FT| F(E)|id,Page 23,【例4.3】文法GA:,AAc|Aad|bd|e 消除非终结符 A 的直接左递归，可等价地改写成如下非左递归形式： AbdA | eA AcA | adA|,Page 24,2）消除间接左递归,如果一个文法含有形如 A A的推导，我们称该文法为间接左递归或左递归文法。对所包含的直接左递归情形按前述情况处理。,+,【例】文法GS： SQc|c QRb|b RSa|a 是间接左递归文法。因为存在着如下推导： SQcRbcSabc。 修改的思路是用代入法，使其出现直接左递归，按前述方法消除直接左递归，然后化简文法，去掉无用的产生式，即消除那些从开始符号出发，永远无法到达的非终结符的产生式规则。,Page 25,如果一个文法不含回路（形如 PP的推导），也不含以 为右部的产生式，则下述算法将保证消除左递归（改写后的文法可能含有以 为右部的产生式）: 消除文法中一切左递归的算法:,+,把文法 G 的所有非终结符按任意顺序排列成 P1，P2 . Pn ；按此顺序执行： FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如 Pi Pj 的规则改写成： Pid1|d2|dk 。 其中 Pjd1|d2|dk 是关于 Pj 的所有规则； 消除 Pi 的直接左递归 END 删除无用产生式.,Page 26,令非终结符顺序为 R、Q、S R 代入 Q 得： QSab|ab|b Q 不含左递归，代入 S 得： SSabc|abc|bc|c 消除S的直接左递归得文法： SabcS|bcS|cS SabcS| QRb|b R Sa |a 其中，关于 Q、R 的产生式多余，删除之，得文法： Sa bcS|bcS|CS SabcS| 由于对非终结符排序的任意性，可能使变换后的文法不唯一。,【例】文法GS： SQc|c QRb|b RSa|a,Page 27,5.4 非确定的自上而下分析法的思想,当文法不满足LL(1)时,则不能用确定的自顶向下分析,但可用不确定的自顶向下分析方法,也就是带回溯的自顶向下分析法. 非确定的自上而下分析的基本思想： 对任意给定的输入串，从文法的开始符号出发，寻找一个最左推导过程或自上而下地建立一棵语法树，试图产生一个和输入串相同的句子。 或者说，为输入串寻找一个最左推导。如果试探成功，则输入串为相应文法的句子，否则不是文法句子。 这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。,Page 28,实现这种自上而下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。这种子程序可作为一个布尔过程。 一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值； 否则，保持原来的语法树和输入串指示器 IP 值不变，并返回“假”值。,Page 29,【例4.1】 设有文法G S： SaAb Ade|d 若输入串为 W=adb#，则其自上而下的分析过程是，从文法的开始符号出发，从左至右地匹配整个输入串 W。 以文法开始符号 S 为树根，对输入串从左到右扫描，输入串指针 IP 总是指向当前正在识别的符号, 当一个符号识别后，IP 总是指向下一个未处理的符号。我们自上而下地建立输入串的语法树。,自上而下分析过程可能遇到的问题 问题一：产生式的多个候选式有相同首符即相同左部的产生式的右部FIRST集交集不为空.,Page 30,开始时，IP 指向 a，可使用产生式 SaAb 推导，使 IP 指向的 a 与产生式 SaAb 右端的 a 匹配。如图。,IP,第二步，IP 指向 d，让 A 去匹配，非终结符 A 有两个选择： Ade 或 Ad， 试着用第一个选择去匹配输入串。如图。,IP,S,Page 31,第三步，IP 指向 b，子树 A 的第二个结点是终结符 e， 与当前输入符号 b 不一致。匹配失败。 A 的一个选择不适合用于构造 W 的语法树。应回溯，必须退回到出错点，选择 A 的其它可能的规则重新匹配。,IP,为了实现回溯，应把 A 的第一个选择所构造的子树删除，调试把输入指针回退，重新指向 d。,IP,Page 32,第四步，IP 指向 d，重新试探用 A 的第二个规则去匹配，子树 A 只有一个子结点，而且和输入符号匹配，也是 A 完成匹配，如图。,IP,第五步，IP 指向 b，在 S 的第二个结点完成匹配后，进行 S 的第三个结点去匹配，由于 b 这个子结点和当前输入一致，完成了为 W 构造语言树的任务。 所以输入串 Wadb是文法 GS的一个句子。,IP,Page 33,这种解决办法是使用一种穷举的试探方法，即当后面的匹配无法进行时，输入指针回退，刚刚产生的语法树删去，这样的过程我们称之为回溯。有时回溯要进行多步。 这种分析方法分析效率较低，代价较高。,Page 34,问题二：文法含有左递归,【例】有文法GB： BBb|a 以及输入串 abb# ，要求证明输入串是文法的一个句子。,开始时，IP 指向 a，如果使用产生式Ba推导，IP指向的a 与 产生式 Ba 右端的 a 匹配，但无法推导出整个输入串；如果使用产生式 BBb 推导，则如图所示。,IP,Page 35,第二步，IP 仍指向 a，在我们不知道后面的字符的情况下，用产生式 BBb 推导则如图所示.,IP,第三步，使用产生式Ba推导,匹配成功.,Page 36,问题三：由于相同左部非终结符的右部存在能推出(星号推出)产生式,且该非终结符FOLLOW集中含有其它右部FIRST集的元素.,【例】有文法GS： SaAS, S-b, AbAS| 以及输入串 ab# ，要求证明输入串是文法的一个句子。,开始时，IP 指向 a，使用产生式 SaAS 推导， 则如图(1)。 第二步，IP 仍指向 b， b 与产生式 AbAS 右端的 b 匹配，则如图(2)。,A,A,b,A,S,Page 37,第三步 输入指针向右移动,输入符结束.但ASS并不能推出,因此推导失败.,第四步 回溯使输入指针退回到b,对A的推导改为选用 下一个产生式A-,对b用A的后跟符匹配. 继续用S的产生式和b匹配,S的两个产生式只能选用 S-b,则最终得到匹配,成功.,Page 38,5.5 确定的自顶向下分析方法,1.递归下降分析法 当一个文法满足 LL（1）条件时，我们就可以为它构造一个不带回溯的自上而下的分析程序，它由一组递归过程组成，每个过程对应文法的一个非终结符，这样的一个分析程序称递归下降分析器。,在开始工作前，输入串指示器 IP 指向第一个输入符号，当每个子程序工作完毕后 IP 总是指向下一个未处理的符号。,递归过程的功能是识别由该非终结符推出的串,当某非终结符 的产生式有多个候选时能够唯一确定某个产生式进行推导.,Page 39,用高级语言的递归过程描述递归下降分析器只有当 具有实现这种语言的编译系统时才有实际意义。即 写编译程序的元语言允许递归。 另外速度特别慢，一般在指数的数量级上，所以对 于实际的编译器不合适。,Page 40,构造递归下降分析程序时，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构编写。,构造方法,当遇到终结符 a 时，则编写语句 if (当前读到的输入符号=a) 读入下一个输入符号。 当遇到非终结符 A 时，则编写语句调用 A(). 当遇到 A 规则时，则编写语句 if (当前读到的输入符号 FOLLOW(A) error()。 当某个非终结符的规则有多个候选式时，按LL(1)文法的条件唯一确定一个候选式进行推导。,Page 41,【例4.9】设有文法GS：Sa|(T) TT,S|S 试构造一个识别该文法句子的多个下降分析程序。,第一步：消除文法左递归，得到文法GS,Sa|(T) TST T,ST|,第二步：判断文法 G 是否为 LL(1)文法， 如果不是，需要进行构造。,SELECT(Sa)SELECT(S) = SELECT(Sa)SELECT(S(T) = SELECT(S)SELECT(S(T) = SELECT(T，ST)SELECT(T) = FIRST(,ST)(FIRST() FOLLOW(T) = ,) = 所以文法 GS 是 LL(1)文法。,Page 42,第三步：构造相应的多个下降分析程序,分析程序中函数 Scaner() 的功能是读进源程序的下一个单词符号并将它放在全程变量 sym 中； 函数 error() 是出错处理程序。,主程序 main() Scaner(); S(); if (sym =#) printf(“success”); else printf(“fail”); ,S() if (sym =a|sym =) Scaner(); else if (sym =() Scaner(); T(); if (sym =) Scaner(); else error(); T() S(); T(); T() if (sym =,) Scaner(); S();T(); else if (sym!=) error(); ,Page 44,2.预测分析法与预测分析表的构造,预测分析方法是自顶向下分析的另一种方法. 一个预测分析器由三部分组成:预测分析程序、先进后出栈和预测分析表.,Page 45,预测分析器的工作模型,一张预测分析表(LL(1)分析表)、一个先进后出栈和一个总控程序三个部分组成。,Tj,分 析 栈 Sk,总控程序,预测分析表,输出,Page 46,输入缓冲区 Tj 中存放待分析的输入符号串，它以右界符 # 作为结束。 分析栈 Sk 中存放替换当前非终结符的某种规则右部符号串，句子右界符存入栈底。 预测分析表 M 是预测分析法的关键，通常是一个 MA，a 形式的矩阵，其中 A VN，aVT 或 #。 元素 MA，a 中存放着一条关于 A 的产生式， 指出当 A 面临输入符号 a 时应采用的候选式。 MA，a 中也可能存放出错标志(有时用空白表示)，指出 A 面临 a 是一种错误。,Page 47,预测分析程序工作过程,这里的$符号 与书中的#号 意义相同,总控程序在分析过程中对于任何文法来说作用都是一样的，它在任何时候都是根据栈顶符号 X 和当前输入指针 IP 指向的符号 a 来决定下一步动作。每一步都将执行下列三种动作之一：,若X=a=#，则宣布分析成功； 若X=a#，则将栈顶符号 X（终结符）弹出，让 IP 指针指向下一个输入符号； 若 X 是一个非终结符，则查看分析表 M。如果分析表的 MA,a 中是一条产生式，则先将栈顶符号 X（非终结符）弹出，然后把该产生式右端符号串按反序（从右到左）压入栈中（串不入栈），同时可能还要执行一系列的动作，比如建立语法树、进行语义计算等；如果分析表的 MA,a 中是出错标志或空白，则执行相应的出错处理程序。,栈 STACK 用于存放文法符号。分析开始时，将#压入栈底，然后压入文法开始符。我们还假定输入串以#符号结尾。分析工作结束的标志是，栈中只有#符号，IP 指针也指向#符号。,栈STACK用于存放文法符号。分析开始时，栈底先放一个#，然后，放进文法开始符号。同时假定输入串之后也总有一个#标志结束。总控程序：包括三种动作：成功、出栈且读下一符号、出栈且产生式右部入栈。 BEGIN 首先把#和文法开始符号依次推进 STACK 栈； 把第一个输入符号读进 a； WHILE FLAG DO BEGIN 把 STACK 栈顶符号弹出放进X中； IF XVT THEN IF X=a THEN 把下一个符号读进 a ELSE ERROR ELSE IF X=#THEN IF X=a THEN FLAG := FALSE ELSE ERROR ELSE IF MA,a=XX1 X2 . XK THEN 把 Xk,Xk-1,X1 一一压入 STACK 栈 /*若X1 X2 . XK=，什么也不压栈*/ ELSE ERROR END OF WHILE STOP END,Page 50,预测分析表的构造,输入：文法 G 输出：预测分析表 方法：,假设a表示每个终结符或#号.若aSELECT(A-),则将A放入MA，a中.将所有无定义的 MA,a 标上“出错标志”(表中用空格表示)。,结论：一个文法G的预测分析表M不含多重入口，当且仅当该文法为LL(1)文法。,Page 51,【例4.10】设有文法GS： 试构造该文法的预测分析表。,首先需要判断文法是否 LL(1)文法，前例中已经证明过。 计算该文法每个非终结符的FIRST和FOLLOW集。,Sa|(T) TST T,ST|,Page 52,构造预测分析表,对规则Sa， 因为FIRST(a)=a, 所以 MS,a=Sa 对规则S， 因为FIRST()=, 所以 MS,=S 对规则S(T)，因为FIRST(T)=(, 所以 MS,(=S(T) 对规则TST，因为FIRST(ST)=a,(,所以MT,a=TST MT,=TST MT,(=TST 对规则T,ST，因为FIRST(,ST)=,所以 MT,=T,ST 对规则T，因为FOLLOW(T)=), 所以 MT,)=T,Page 53,对输入串(a,a)# 预测分析器作出的移动过程,Page 54,S(T) (ST) (aT) (a,ST) (a,aT) (aa),生成动作的列表和输入串最左推导的步骤 完全对应。,S(T) TST Sa T,ST Sa T,这是自上而下分析的特征。 如果要在分析进行时构造一个分析树，则可当将每个非终结符或终结符压入栈中时添加结点来构造动作。 因此分析树根结点的构造是在分析开始时进行的(与开始符号对应),Page 55,【例】文法G：,ETE E+TE| TFT T*FT| F(E)|i,首先判断文法是否 LL(1)文法。,SELECT(E+TE) = FIRST(+TE) = + SELECT(E) = FIRST()FOLLOW(E) = $,) SELECT(T*FT) = FIRST(*FT = * SELECT(T) = FIRST()FOLLOW(T) = +,$ = ,+,$ 所以 SELECT(E+TE)SELECT(E) = SELECT(T*FT)SELECT(T) = 故该文法是 LL(1)文法,Page 56,计算该文法每个非终结符的 FIRST 和 FOLLOW 集。,ETE E+TE| TFT T*FT| F(E)|i,Page 57,对规则ETE，因为FIRST(TE)=(,i, 所以 ME,(=ETE ME,i=ETE 对规则E+TE，因为FIRST(+TE)=+, 所以 ME,+=E+TE 对规则E，因为FOLLOW(E)=$,), 所以 ME,$=E ME,$)=E 对规则TFT，因为FIRST(FT)=(,i, 所以 MT,(=TFT MT,i=TFT 对规则T*FT，因为FIRST(*FT)=*, 所以 MT,*=T+FT 对规则T，因为FOLLOW(T)=$,),+, 所以 MT