《自上而下语法分析》PPT课件.ppt

第5章 自上而下语法分析,消除左递归方法 LL(K)文法 确定的LL(1)分析器的构造 递归下降分析程序、设计 带回溯的分析方法 小结,语法分析是编译过程的第2阶段，主要任务是对词法分析的输出结果单词序列进行分析，识别合法的语法单位。,语法分析,自上而下分析方法,自下而上分析方法,带回溯,带回溯,语法分析,文法的左递归性,例5.1 设文法G22A： A B B XBA X Xa|Xb|a|b,左递归 直接左递归： UUx|y，y的首字符不是U 间接左递归： U+ Ux,用扩展的BNF表示法消除左递归, ：x表示符号串出现零次或多次。 ：n表示符号串可以重复出现的最大次数，m表示符号串可以重复出现的最小次数。 ：x=x或 ，表示符号串x可以出现一次或不出现，表示可选项。 () ：可以提出一个非终结符的多个产生式右部的公共因子。,n,m,例5.2,设文法G: | 0|1|2|3|4|5|6|7|8|9 a|b|c|x|y|z,直接改写法,产生式直接左递归形式可以改写为一个等价的非直接左递归形式。 UUx|y 可改写为： U yU UxU| 一般地 UUx1|Ux2 |Ux3 |Uxm|y1|y2| |yn 其中xi , yi的头字符都不是U (i=1,2,m. j=1,2,n) 可改写为： U y1U|y2U|ynU U x1U|x2U|xmU| ,消除左递归算法,将文法G中的所有非终结符号整理成某一顺序U1，U2，, Un； for i=1 to n do for j=1 to i-1 do 用Uj1|2|m把产生式Ui Uj替换成： Ui 1 |2 |m； 消除Ui产生式中的直接左递归； 化简改写之后的文法，删除多余的产生式。,基本思想：将文法中的非直接左递归，转换为直接左递归，再利用直接改写法消除左递归。,假设非终结符A，B，C的顺序为 C，B，A；,例5.4 设文法G24A: ABcd BCe|f CAb|c,(2) 将BCe|f 替换成 BAbe|ce|f,(3) 将ABcd 替换成 AAbecd|cecd|fcd消除A的产生式中的直接左递归， A cecdA|fcdA A becdA|,(4) 改写后的GA： A cecdA|fcdA A becdA| B Abe|ce|f C Ab|c,(5) 化简后的文法GA ：A cecdA|fcdA A becdA|,LL(k)文法,LL(k)文法是一种自上而下的分析方法。从文法的开始符号出发，生成句子的最左推导。从左到右扫描源程序，每次向前查看k(k1)个字符，便能确定当前应该选择的产生式。如果每次向前查看1个字符，则称为LL(1)文法。,First和Follow集定义,设是文法G的一个符号串, (VNVT)*， First()=a| * a, aVT, (VNVT)*，特别地，若有 * ，则First()。 设S是文法的识别符号（开始符号）， UVN Follow(U)=b|S * xUby, bVT, x,y(VNVT)*,例5.5,设文法G26A: A B B XB BAB| X aX|bX XaX|bX|,First(XB)=a, b, Follow(X)= First(X)=a, b, ,LL(1)文法的判断条件,定义5.1 设U是文法G的任一个非终结符号，其产生式为 U x1|x2|.|xn形式。 如果 First(xi) First(xj)= (ij, i,j=1,2,n) 当First(xj)时，有 First(xi) First(U)= 称文法G是LL(1)文法。,First集的构造,(1)设X(VNVT)，First(X)的构造 若XVT，则First(X)=X; 若XVN，如果有产生式Xa， aVT，则aFirst(X);如果有产生式X ，First(X) 若XVN，如果有产生式XY， YVN，则First(Y)-First(X); 如果有产生式XY1Y2Yk(其中Y1Y2Yi-1都是非终结符并且Y1Y2Yi-1*) ，则First(Yi)-First(X)，如果Y1Y2Yk*，则 First(X),First集的构造(续),(2)设(VNVT)*，= X1 X2Xn， First()的构造 若= ，First()=; 若 ，First(X1)-First();如果有产生式X ，First(X) 如果X1X2Xi-1*， First(Xi)-First(); X1X2Xn*， First(X),Follow集的构造,(3)设UVN，Follow(U)的构造 若U是文法的识别符号，则Follow(U); 若有产生式AxUy， First(y)-Follow(U) 若有产生式AxU，或AxUy，y*，则 Follow(A)Follow(U),SELECT集的构造,(4)集合Select(U)的构造 Select (U)=,First(),First()Follow(U),不可空,否则,LL(1)文法判断条件,对于文法G的每一个非终结符U的产生式 U1|2|n如果 Select(Ui)Select(Uj)= (ij, i,j=1,2,n)，则文法G是一个LL(1)文法,例5.6 设文法G27S: SA A BA AiBA| B CB B +CB| C )A*|(,Select(AiBA)Select(A)=First(iBA)(First()Follow(A) Select(B+CB)Select(B)=First(+CB)(First()Follow(B) Select(C )A*)Select(C()=First()A*)First()=)(= ABA, B CB Follow(A)=Follow(A), Follow(B)= Follow(B) S是识别符号并且没有出现在任何产生式的右部,Follow(S)=# SA, Follow(S) Follow(A), #Follow(A), C )A*, First(*) Follow(A) 即* Follow(A), Follow(A)=*,# AiBA|, First(A)-=i, -=iFollow(B), Follow(A)=*,#Follow(B), Follow(B)= *,i,# Select(AiBA)Select(A)=First(iBA)(First()Follow(A)= i,*,#= Select(B+CB)Select(B)=First(+CB)(First()Follow(B)=+,*,i,#= 此文法是LL(1)文法。,构造分析表M的算法,LL(1)分析器需要用到一个分析表M和一个符号栈S。分析表M是进行LL(1)分析的重要依据。 分析表M是一个矩阵， 它的元素MU, a可以存放一条产生式，表明当符号栈S的栈顶元素非终结符U遇到当前输入字符（终结符）a时，所应选择的产生式。 元素MU, a也可以存放一个出错标志，说明符号栈S的栈顶元素非终结符U不应遇到当前输入字符（终结符）a。,构造分析表M的算法过程,对文法的每一条产生式U，若aFirst()，则MU,a=U； 若First()，则MU,b=U，其中b； Follow(U); 分析表的其他元素均为出错标记error，通常用空白表示。,例5.7 以例5.6中的文法G27S为例 SA A BA AiBA| B CB B +CB| C )A*|(,对于产生式SA， First(A) =(,)， MS, (=SA， MS, )=SA 对于产生式A BA，First(B) =(,)， MA, (=A BA， MA, )=A BA 对于产生式AiBA，First(iBA) =i， MA, i=AiBA 对于产生式A， Follow(A) =*, #， MA, *=A MA, #=A 对于产生式B CB, First(C) =(,), MB, (=B CB, MB, )=B CB 对于产生式B+CB,First(+CB) =+, MB, +=B+CB 对于产生式B,Follow(B) =i,*, #, MB, i=B, MB, *=B, MB, #=B 对于产生式C )A*, MC, )=C )A* , 对于产生式C (, MC, (=C (,G27S分析表,LL(1)分析器的总控算法,数据结构：LL(1)分析表M、一个符号栈S（指针为i）、待分析的符号串存放在数组str中，下标指针为j，尾符号为#.当前字符存放在ch中.,算法过程： (1) j=1,S1=#,S2=识别符, ch=strj； (2) if TOP(S)VT (#也看作终结符) (2.1)if TOP(S)ch error stop; (2.2)if TOP(S)=#,表明输入符号串是一个合法句子，算法终止 else 表明输入符号串当前字符是合法字符，读入符号串的下一个字符（j=j+1），同时S退栈（i=i-1）; (2.3) goto (2) ; (3) if TOP(S)VN (3.1) if MTOP(S),ch=Ux1x2xn 倒置x1x2xn并且替换栈顶U; goto(2); else error stop;,符号串(i(的分析过程,递归下降分析程序,递归下降分析方法是一种确定的自上而下分析方法，它的基本思想是给文法的每个非终结符号设计一个相应的子程序，由于文法的产生式往往是递归的，所以这些子程序也是递归的，这种方法也称为递归子程序法。,子程序,设aVT，P(a)代表语句：if ch=a then READ(ch) else error 设=x1x2xn，x1(VNVT), P()代表语句：P(x1); P(x2); P(xn); 设UVN，产生式U1|2|m, 定义P(U): read(ch); if ch First(1) then P(1) else if ch First(2) then P(2) else if ch First(m) then P(m) else error,全局变量ch，代表输入符号的当前符号；read(ch)函数，读入符号串的下一个符号并存入ch中。,子程序(续),设UVN，产生式U1|2|m|, 定义P(U): read(ch); if ch First(1) then P(1) else if ch First(2) then P(2) else if ch First(m) then P(m) else if ch Follow(U) then return else error,例5.9 文法G28S: S(A)|aAb AeA|dSA AdA|,Read(ch),ch=( ?,ch=a ?,ch=b ?,Read(ch),P(A),Read(ch),Read(ch),error,P(A),ch=) ?,Y,N,N,Y,N,P(S):,例5.9（续） AeA|dSA,ch=e ?,ch=d ?,P(S),P(A),Read(ch),error,Y,N,P(A):,带回溯的自上而下分析法,带回溯的自上而下方法，实际上是穷举所有可能的推导，看是否能推导出待检查的符号串。对上下无关文法具有通用性（确定的自上而下分析方法，并不适用所有文法，而是对文法有所限制），几乎没有什么限制，但是，速度慢是这种方法的主要缺点。,文法在内存中的存放形式,一维数组： 文法产生式的左部和右部存放在一维数组中，并且在每个产生式的右部的尾符号之后放置一个“|”作为产生式右部的结束符号； 在一个非终结符的最后一个产生式的尾部符号之后放置一个“$”作为这个非终结符号的所有产生式右部的结束符。,例5.9（续） AdA|,ch=d ?,chFollow(A)?,Read(ch