第4章语法分析(2)

1、1第四章第四章 语法分析语法分析(2)4.4 自顶向下语法分析24.4 自顶向下语法分析自顶向下语法分析q 自顶向下(top-down)的语法分析算法是通过最左推导来分析输入的单词序列(tokens)q 自顶向下的分析算法有两类允许回溯的递归下降分析LL(1)分析：一种没有回溯的递归下降分析法。wSlm3例例4.14 id+id*id的语法分析树构造过程的语法分析树构造过程q 对应文法E TE E +TE | T FT T *FT | F ( E ) | id4id+id*id E TE E +TE | T FT T *FT | F ( E ) | idE=TE=FTE=idTE=idE=id

2、+TElookaheada+b*c最左推导最左推导5id+id*id64.4.1 递归下降语法分析的一般方法递归下降语法分析的一般方法q 为输入tokens寻找最左推导。q 递归下降分析的基本方法将一个非终结符A的文法规则看作识别A的过程的定义。A的文法规则的右部指示过程的代码结构匹配文法规则中出现的终结符a：match(a)调用文法规则中出现的非终结符文法S cAd A ab | a写出代码7非终结符对应的典型过程非终结符对应的典型过程8考虑文法S cAd A ab | a为输入串w = cad 建立分析树。例例4.15 文法文法cadScdAcadScdAabcadScdAacadScdA

3、ab出现问题出现问题: 回溯回溯backtrack！cadScdAa9缺点缺点q 不能处理左递归q 复杂的回溯技术q 回溯导致语义工作推倒重来q 难以报告出错的确切位置q 效率低104.4.5 FIRST和和FOLLOW函数函数q 对文法加什么样的限制可以保证没有回溯？q 先定义两个和文法有关的函数FIRST()FOLLOW(A)10S=stmt=. if ( abc 0 )lookahead例：stmt if expr then stmt else stmt | while expr do stmt | begin stmt_list end First(if expr then stmt

4、else stmt)= if First(while expr do stmt)= while 另一种情况：另一种情况：11E TEE +TE | T FT T *FT | F ( E ) | idFirst(TE)= First(T) = First(+TE) = + Follow(E) = ), $ E=E=. ( a + c ) * elookahead12FIRST( )q FIRST()是从推导出的串的起始终结符的集合。q FIRST( ) = a | a, a VT 特别是， 时，规定FIRST( ) 例如：A xB|yC，First(xB)=x,First(yC)=yq 对A的任

5、何两个不同的选择i 和j，希望有FIRST(i ) FIRST(j ) = 但有一个前提， FIRST(i )和FIRST(j)都不含*例如：A 1 | 2| 3假设First (1)=a,b, First(2)=c,d,e,First(3)=f,gS uAvBw, 当前输入:c*13FOLLOW(A)q FOLLOW(A)是在所有句型中紧跟在A后面的终结符集合。q FOLLOW(A) = a|S Aa，a VTS Aa 约定：如果A是某个句型的最右符号（SA），那么$属于FOLLOW(A) 因为 S$ A$*14计算计算FIRST(X)q若X VT，则FIRST(X) = X。q若X ，则将

6、 加入FIRST(X)。 q若X VN，且X Y1Y2Yk ，则将FIRST(Y1) 加入FIRST(X) 若Y1 ，将FIRST(Y2) 加入FIRST(X)； 若Y1 Y2 ，将FIRST(Y3) 加入FIRST(X)； 若Y1.Yk-1 ，将FIRST(Yk) 加入FIRST(X)； 若对所有的j=1,2,k, Yj* ，将加入FIRST(X)；例如：X为a*例如A xB|yC，First(xB)=x,First(yC)=y, First(A)=x,y;15q 例：stmt if expr then stmt else stmt | while expr do stmt| begin s

7、tmt_list endq First(stmt) = ifif, whilewhile, beginbegin P1P2P3IFIFWHILEWHILEBEGINBEGINENDENDstmt产生式P1产生式P2产生式P31515S=stmt=. if ( abc 0 )lookahead First(if expr then stmt else stmt)= if First(while expr do stmt)= while 16计算计算FOLLOW(A)q 给定一个非终结符号A，则集合FOLLOW(A)由终结符号或$组成，定义如下：若A是文法开始符号，则$在FOLLOW(A)中；若存

8、在产生式A B ，则FIRST()-在Follow(B)中；若存在产生式A B或A B，且*，则FOLLOW(B)包括FOLLOW(A)。1. (因为：若A B，则.Aa.=. B a.,此时，a是B的follow)17q 注意：$标记输入结束。 永远也不是FOLLOW集合中的元素。FOLLOW仅针对非终结符定义。18例例4.19已知文法产生式：已知文法产生式：S iEtSS | aS eS | E bFIRST(S) = i, aFIRST(S) = e, FIRST(E) = bFOLLOW(S) 包含$；S iEtSS，将FIRST(S)即e加入 FOLLOW(S) S eS，将FOLL

9、OW(S)加入FOLLOW(S) S iEtSS ，将FOLLOW(S)加入FOLLOW(S) 因此，有FOLLOW(S) = FOLLOW(S) =e, $ FOLLOW(E) = taSb19E TEE + TE | T FTT * FT | F (E) | id例例4.17 计算计算FIRST集和集和FOLLOW集集FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E) = +, FRIST(T) = *, FOLLOW(E) = FOLLOW(E) = ), $FOLLOW(T) = FOLLOW (T) = +, ), $FOLLOW(F)

10、= +, *, ), $ 204.4.2 预测语法分析器预测语法分析器(Predictive Parsing) q 通过改写文法，消除左递归，提取左因子，也许也许可以得到不带回溯的递归下降分析器。 q 对A 1 | 2 | | n，通过观测候选式所推导出的第一个符号，能够选择合适的产生式来扩展q 例：stmt if expr then stmt else stmt | while expr do stmt| begin stmt_list endS=stmt=. if ( abc 0 )lookaheadififwhilewhilebeginbeginstmtstmt if expr then

11、 stmt else stmtstmt while expr do stmtstmt begin stmt_list endlookahead文法的预测分析表22非终结符非终结符输入符号输入符号 ( lookahead )id+*()$E E T T FETE TFT FidE+TE T T *FT F(E)TFT ETE T E E T E=E=.+TE =. a + c * elookaheadE TEE +TE | T FT T *FT | F ( E ) | idE E + T | TT T * F | FF ( E ) | id文法的预测分析表23如何构造语法分析表如何构造语法分析表

12、 M?q 1st : 计算语法的First集和Follow集q 2nd: 使用构造算法来生成M。Parsing Table244.4.6 预测分析表的构造预测分析表的构造算法4.4 预测分析表的构造输入：文法G输出：分析表M方法： （1）对文法的每个产生式A ，执行(2)和(3)。（2）对FIRST()的每个终结符a，把A加入MA, a。（3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$），把A 加入MA, b。（4）M的其它没有定义的条目都是error。25例例4.38FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E) =

13、+, FRIST(T) = *, FOLLOW(E) = FOLLOW(E) = ), $FOLLOW(T) = FOLLOW (T) = +, ), $FOLLOW(F) = +, *, ), $ E TEE + TE | T FTT * FT | F (E) | idINPUT SYMBOLid+*()$E E T T FETE TFT FidE+TE T T *FT F(E)TFT ETE T E E T 264.4.7 LL(1)文法文法q L: 从左到右扫描输入串q L : 最左推导q 1 : 向前看一个字符lookaheadq 分析表中没有多重定义的表目的文法称为LL(1)文法。2

14、7例例4.19 多重定义的条目多重定义的条目 S iEtSS | aS eS | E bFIRST(S) = i, a FIRST(S) = e, FIRST(E) = b FOLLOW(S) = FOLLOW(S) =e, $ FOLLOW(E) = t非终非终结符结符 输输 入入 符符 号号 a b eit$S S a S iEtSS S S S eS S E E b 28q 该文法是具有二义性的：遇到e(else)时不知该选择哪个产生式。q 消除二义性可以只选择S eS ，遵循与e最近的t(then)配对的原则29LL(1)文法文法q LL(1)文法中的任何两个产生式文法中的任何两个产生

15、式A | 都满足下列条都满足下列条件：件：FIRST( ) FIRST( ) = 不存在终结符a，使得 和 导出的串都以a开始。若若 * ，那么，那么FIRST( ) FOLLOW(A) = 和 至多一个能导出空串 如果导出空串，那么不能导出以FOLLOW(A)中终结符开始的任何串。30LL(1)文法文法q LL(1)文法具有的特殊性质没有公共左因子不是二义的不含左递归文法S cAd A ab | a要提取公共左因子aA aAA b | 要提取消除左递归D bDD aD | S cDD Da | bS=cD=cbD= Follow(S)= $ = Follow(D) = Follow(D)31

16、4.4.4 非递归的预测分析非递归的预测分析q 可以使用显式的栈，而不是递归调用来完成分析。32成功的自顶向下的分析的一般示意法：成功的自顶向下的分析的一般示意法：q 两个基本动作：利用文法选择A 将栈顶部的非终结符A替换成串。将栈顶的记号和下一个输入记号匹配。分析栈 输入(lookahead) 动作$StartSymbol InputString$ $ $ 接受 33例：生成配对括号的文法例：生成配对括号的文法S (S) S | 对串（），下表给出自顶向下的分析程序的动作：分析栈输入动作$ S ( ) $ S (S) S $ S ) S ( ( ) $ 匹配$ S ) S ) $ S $ S

17、 ) ) $ 匹配$ S $ S $ $ 接受 自顶向下的分析程序的动作对于LL(1)文法，将 边作为默认选择可以解决是否选择一个 边的二义性问题。34a + b $输入预测分析程序分析表分析表M输出 XYZ$栈35输入：输入：输入符号串w和文法G的分析表M输出：输出：若wL(G)，则输出w的最左推导； 否则，报告出错信息。方法：初始状态： $在栈底，S在栈顶； w$在输入缓冲区中。 预测分析程序利用预测分析表M对于输入作出分析。 算法算法4.3 非递归预测分析方法非递归预测分析方法36置ip指向w$的第一个符号，栈为$和开始符号Srepeat 令X是栈顶符号, a是ip所指向的符号； if

18、X 是一个终结符号或$ then if X=a then从栈中弹出X，ip指向下一个符号 else error() else /*X是非终结符号*/ if MX,a=XY1Y2. . Yk then begin从栈中弹出X; 将 Yk,Yk-1,. .,Y1压入栈中，即Y1在栈顶； 输出产生式 XY1Y2. . Yk end else error()until X=$ /*栈为空*/图4-14 预测分析程序预测分析程序Input pointer就是就是lookahead37例例4.16图图4-15 文法的分析表M非终结符非终结符E TEE +TE | T FT T *FT | F ( E )

19、| id输入符号输入符号id+*()$E E T T FETE TFT FidE+TE T T *FT F(E)TFT ETE T E E T 38图图4-16 预测分析器在输入预测分析器在输入id+id*id上的动上的动作作 $E$ET$ETF$ETid$ET$E$ET+$ETid + id * id$id + id * id$id + id * id$id + id * id$+ id * id$+ id * id$+ id * id$id * id$E TET FTF idT E +TESTACKINPUTOUTPUT39图图4-16 预测分析器在输入预测分析器在输入id+id*id上的

20、动上的动作作 (续续)STACKINPUTOUTPUT$ETF$ETid$ET$ETF*$ETF$ETid$ET$E$id * id$id * id$* id$* id$id$id$T FTF idT *FTF idT E 40例子采用最左推导例子采用最左推导E TE FTE id TE id E id + TE id + FTE id + id TE id + id * FTE id + id * id TE id + id * id E id + id * id已经扫描过的输入符号加上栈中的文法符号(from top to bottom)构成该推导的左句型左句型。414.4.8 出错恢复（

21、出错恢复（Error Recovery）q 词法错误如标识符、关键字或算符的拼写错q 语法错误如算术表达式的括号不配对q 语义错误如算符作用于不相容的运算对象q 逻辑错误如无穷的递归调用42分析器对错误处理的基本目标分析器对错误处理的基本目标q 清楚而准确地报告错误的出现q 迅速地从每个错误中恢复过来，以便诊断后面的错误，并尽量少出现伪错误q 不应该使正确程序的处理速度降低太多 43栈顶的终结符和下一个输入符号不匹配栈顶的终结符和下一个输入符号不匹配栈顶是非终结符栈顶是非终结符A，输入符号是，输入符号是a，而，而MA , a是空是空白白 No allowable actions非递归预测分析在

22、什么场合下发现错误非递归预测分析在什么场合下发现错误44Panic Mode Recovery(应急方式应急方式)q 非递归预测分析采用紧急方式的错误恢复，发现错误时，分析器抛弃一些输入记号，直到输入记号属于某个指定的同步记号集合为止。45选择同步记号集合的启发式方法选择同步记号集合的启发式方法q 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合中。if expr then（then是expr的一个同步记号）46选择同步记号集合的启发式方法选择同步记号集合的启发式方法q 把高层结构的开始符号加到低层结构的同步记号集合中。assign-stmt := expr ; if （赋值语句的

23、开始符号作为表达式的同步符号，以免遗漏分号时忽略一大段程序。）47选择同步记号集合的启发式方法选择同步记号集合的启发式方法q 把FIRST(A)的终结符加入A的同步记号集合。q 如果A * ，可以将产生空串的产生式作为默认选择q 如果栈顶的终结符不能被匹配，弹出该记号，相当于所有其它记号都在同步记号集合中。48Revised Parsing Table / ExamplesynchsynchsynchNon-terminalINPUT SYMBOLid+*()$EETTFETETFTFidE+TET T*FTF(E)TFTETET E E T synchsynchsynchsynchsynchsynchFrom Follow sets. Pop stack entry T or NTSkip input symbol 假设我们已经得到文法的预测分析表假设我们已经得到文法的预测分析表E +TE | E() if(lookahead=加号) match(加号); T()