《第四章_语法分析_自上而下_3.0.ppt》由会员分享，可在线阅读，更多相关《第四章_语法分析_自上而下_3.0.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 语法分析语法分析自上而下分析自上而下分析本章内容本章内容l语法分析的任务与分类语法分析的任务与分类l自上而下分析面临的问题自上而下分析面临的问题l递归下降分析程序构造递归下降分析程序构造l预测分析程序预测分析程序lLL(1)LL(1)文法文法 一、一、语法分析的任务与分类语法分析的任务与分类l 语法分析的任务：语法分析的任务：对任一给定对任一给定 w Vw VT T*，判断，判断 w Lw L（G G）l 语法分析器：是一个程序，它按照语法分析器：是一个程序，它按照P P，做识别，做识别ww的工作的工作词法分析器词法分析器语法分析器语法分析器编译程序后续部分编译程序后续部分符号表
2、符号表源程序源程序单词符号单词符号取下一个取下一个单词符号单词符号语法分析语法分析图图4.1 4.1 语法分析器在编译程序中的地位语法分析器在编译程序中的地位二、自上而下分析面临的问题二、自上而下分析面临的问题1 1、主旨：主旨：从文法开始符号出发，从文法开始符号出发，自上而下自上而下的为输入的为输入串建立一棵语法树串建立一棵语法树l 语法分析的分类：语法分析的分类：自下而上自下而上 自上而下自上而下l 例例4.1 4.1 文法文法G1G1：S S cAdcAd A A ab|aab|a 输入串：输入串：w=cadw=cad，为它建立语法树，为它建立语法树ScAdabaS S cAdcAdA
3、A ababA A a a输入串输入串w:w:文法文法G:G:IPIP分析过程：分析过程：1 1）ww输入串；输入串；IPIP c c S S扩充；扩充；c a dc a d2 2）=c A d=c A d；与与 IPIP c c匹配；匹配；3 3）IPIP a aA A扩展，第一式扩展，第一式abab,IPIP a a与与abab匹配；匹配；IPIP d d,但但d d与与b b不匹配不匹配;4 4）报告失败，撤销）报告失败，撤销A A的子的子树，回到树，回到A;A;指针回退到指针回退到IPIP a a;A A还有替换式未试过，而又还有替换式未试过，而又可能匹配；可能匹配；语法树的形成语法树
4、的形成l上述分析方法的实现：上述分析方法的实现：每一非终结符对应一个递归子程序，在只生成每一非终结符对应一个递归子程序，在只生成两个串的文法，过程无须递归，而对生成无数个串的文两个串的文法，过程无须递归，而对生成无数个串的文法，递归是不可避免的；法，递归是不可避免的；递归子程序：是一个布尔过程，一旦发现它的递归子程序：是一个布尔过程，一旦发现它的某个候选式与输入串匹配，它就按此式扩充语法树，某个候选式与输入串匹配，它就按此式扩充语法树，并返回并返回truetrue，指针移过已匹配子串。否则，指针移过已匹配子串。否则，返回返回falsefalse，保持原来的语法树和指针不变。，保持原来的语法树和
5、指针不变。l程序实现：程序实现：l使用记号：使用记号：input_symbolinput_symbol：当前符号内容：当前符号内容input_pointerinput_pointer：输入字符指针：输入字符指针l使用过程：使用过程：ADVANCE()ADVANCE()：把：把input_pointerinput_pointer移到下一输入符号移到下一输入符号位置，置位置，置input_symbolinput_symbol是当前符号内容；是当前符号内容；使用两个过程：使用两个过程：S()S()和和A()A()，它们送回，它们送回true or true or falsefalse，决定于它们是否
6、在输入串中找到相应的非终结，决定于它们是否在输入串中找到相应的非终结符所构成的串。符所构成的串。procedure S();procedure S();beginbegin if if input_symbolinput_symbol=c cthenthen begin beginADVANCE();ADVANCE();if A()thenif A()then if if inputSymbolinputSymbol=d d then thenbeginbegin ADVANCE();ADVANCE();return true return trueendend end;end;return
7、false;return false;end;end;procedure A();procedure A();beginbegin isaveisave:=:=input_pointerinput_pointer;if if input_symbolinput_symbol=a a then then begin beginADVANCE();ADVANCE();if if inputSymbolinputSymbol=b b then then begin begin ADVANCE();return true;ADVANCE();return true;end end end end/*f
8、ailure to find/*failure to find abab*/*/input_pointerinput_pointer:=:=isaveisave;if if inputSymbolinputSymbol=a a then thenbeginbegin ADVANCE();return true;ADVANCE();return true;endend else return false;else return false;end;end;2 2、困难和问题、困难和问题l文法的左递归文法的左递归l回溯回溯l用替换符的顺序会影响所接受的语言用替换符的顺序会影响所接受的语言 如：如：
9、A A ab|aab|a 改为改为 A A a|aba|ab l难以报告出错的确切位置难以报告出错的确切位置l穷举试探法穷举试探法低效的分析方法低效的分析方法三、自上而下分析的问题解决三、自上而下分析的问题解决消除文法的左递归消除文法的左递归克服回溯问题克服回溯问题1 1、区分三种类型的左递归、区分三种类型的左递归-直接左递归直接左递归 即形如：即形如：N-NN-N-间接左递归间接左递归 即形如：即形如：N-AN-A A-B A-B B-N B-N-潜在左递归潜在左递归即形如：即形如：N-N-NN 而而 2 2、直接左递归的消除、直接左递归的消除候选式：候选式：A-AA-A|A -A -A A
10、A A-A|消除方法：消除方法：若：若：A A A A|，其中，其中不以不以A A开头开头则修改规则为：则修改规则为：A A AA A A A|A|消去直接左递归后：消去直接左递归后：E E TETE EE +TE|+TE|T T FTFT TT*FT|FT|F F （E E）|i|i例例4.2 4.2 文法：文法：E E E+T|TE+T|TT T T*F|FT*F|FF F （E E）|i|i消除方法：消除方法：若：若：A A A A|，(不以不以P P开头开头)则修改规则为：则修改规则为：A A AA A A A|A|3 3、间接和潜在左递归的消除、间接和潜在左递归的消除代入法代入法 将
11、一个产生式规则右部的将一个产生式规则右部的中的非终结符中的非终结符NN替替换为换为NN的候选式。如果的候选式。如果NN有有 n n个候选式，右边的个候选式，右边的重复重复n n次，而且每一次重复都有次，而且每一次重复都有NN的不同候选式来的不同候选式来代替代替NN。例例4.34.3 N-N-a|Bca|Bc|在在S-S-pNqpNq中的代入结果为中的代入结果为S-S-paq|pBcq|pqpaq|pBcq|pq间接和潜在左递归通常通过代入能转换为间接和潜在左递归通常通过代入能转换为直接左递归直接左递归4 4、消除一个文法的一切左递归算法、消除一个文法的一切左递归算法l对文法对文法G G的所有非
12、终结符进行排序的所有非终结符进行排序l按上述顺序对每一个非终结符按上述顺序对每一个非终结符Pi Pi依次执行依次执行:for(j=1for(j=1；j i-1jA-1 1|2 2|m m，那么，要知道哪一个那么，要知道哪一个i i是获得以是获得以a a开头的串的唯一替换式。开头的串的唯一替换式。即：选择哪一个即：选择哪一个i i，亦即通过查看第一个（当前）符号来发，亦即通过查看第一个（当前）符号来发现合适的替换式现合适的替换式i i。怎样选择怎样选择i i？以以a a为头的为头的i i如有多个如有多个i i以以a a为头的，这是文法的问题为头的，这是文法的问题例如，有产生式：例如，有产生式：语
13、句语句-if if 条件条件 then then 语句语句 else else 语句语句|whilewhile 条件条件 do do 语句语句|beginbegin 语句表语句表 end end 若要寻找一个若要寻找一个语句语句，那么关键字，那么关键字 if if，whilewhile，beginbegin就就提示我们哪一个替换式是仅有可能成功的替换式。提示我们哪一个替换式是仅有可能成功的替换式。抽象地看问题：抽象地看问题：若要求不得回溯，文法若要求不得回溯，文法G G（当然（当然G G不含左递归）不含左递归）的必要条件是什么，也即对文法有什么要求？的必要条件是什么，也即对文法有什么要求？若由
14、若由i i a a，选该，选该必中，但若必中，但若j j a a，就会导致无法百发百中，解决办法是对文法本身提就会导致无法百发百中，解决办法是对文法本身提出要求：出要求：“不会出现以上情况不会出现以上情况”，把这些阐明清楚，把这些阐明清楚是用一个是用一个FIRST(FIRST()。l定义定义FIRST(FIRST()：FIRST(FIRST()=a|)=a|a a,aVaVT T 若若 ，规定，规定FFIRST(IRST()l定理定理若一个若一个 A AV VNN，就有许多，就有许多FIRST(FIRST(i i)，如果，如果A A的的任何两个候选式任何两个候选式i i和和j j，均有，均有F
15、IRST(FIRST(i i)FIRST()FIRST(j j)=)=意味着，意味着，A A的每一候选式的每一候选式推导后所得的字符串推导后所得的字符串第一个第一个V VT T均不同。均不同。于是，对输入符号于是，对输入符号a a，如果，如果a aFIRST(FIRST(i i)，则，则a nota notFIRSTFIRST(j j)，(jiji)，因此，对，因此，对A A的展开无疑应选候选式的展开无疑应选候选式i i，才有可能命中。才有可能命中。l消除回溯目的：消除回溯目的：非终结符非终结符A A的所有侯选式的首符集两两不相交的所有侯选式的首符集两两不相交l方法：提取公共左因子方法：提取公
16、共左因子若若：A A 1 1|2 2|n n|1 1|2 2|mm (其中其中,每个每个不以不以开头开头)那么那么,可以把这些规则改写成可以把这些规则改写成 A A A A|1 1|2 2|mm A A1 1|2 2|n n四、递归下降分析程序构造四、递归下降分析程序构造在在不含左递归不含左递归和和每个非终结符的所有候选每个非终结符的所有候选式的终结首符集都两两不相交式的终结首符集都两两不相交条件下，构造一条件下，构造一个不带回溯的自上而下分析程序，该分析程序个不带回溯的自上而下分析程序，该分析程序由一组递归过程组成，每个过程对应文法的一由一组递归过程组成，每个过程对应文法的一个非终结符。个非
17、终结符。这样的一个分析程序称为这样的一个分析程序称为递归下降分析器。递归下降分析器。1 1 例例4.44.4 文法文法 G G：PROCEDURE PROCEDURE E;E;BEGINBEGIN T;E T;EEND;END;PROCEDURE PROCEDURE T;T;BEGINBEGIN F;T F;TEND;END;PROCEDURE PROCEDURE E E;IF IF SYM=SYM=+THEN THEN BEGINBEGIN ADVANCE;ADVANCE;T;E T;EEND;END;E E TETEEE +TE|+TE|T T FTFTPROCEDURE TPROCEDU
18、RE T;IF SYM=IF SYM=*THENTHENBEGINBEGIN ADVANCE;ADVANCE;F;T F;TEND;END;PROCEDURE F;PROCEDURE F;IF SYM=IF SYM=i iTHENTHEN ADVANCE ADVANCEELSEELSE IF SYM=IF SYM=(THENTHEN BEGIN BEGIN ADVANCE;ADVANCE;E;E;IF SYM=IF SYM=)THEN ADVANCE THEN ADVANCE ELSE ERROR ELSE ERROR END END ELSE ERROR;ELSE ERROR;面临输入：面临
19、输入：i i1 1+i+i2 2*i*i3 3时的分析步骤如下：时的分析步骤如下：T T*FT|FT|F F （E E）|i|iETEFTi i1 1PROCEDURE PROCEDURE E;E;BEGINBEGIN T;E T;EEND;END;PROCEDURE PROCEDURE T;T;BEGINBEGIN F;T F;TEND;END;PROCEDURE F;PROCEDURE F;IF SYM=IF SYM=i iTHENTHEN ADVANCE ADVANCEELSEELSE IF SYM=IF SYM=(THENTHEN BEGIN BEGIN ADVANCE;ADVANCE
20、;E;E;IF SYM=IF SYM=)THEN ADVANCE THEN ADVANCE ELSE ERROR ELSE ERROR END END ELSE ERROR;ELSE ERROR;PROCEDURE TPROCEDURE T;IF SYM=IF SYM=*THENTHENBEGINBEGIN ADVANCE;ADVANCE;F;T F;TEND;END;ETEFT+ETFT*FTi i1 1i i2 2i i3 3PROCEDURE PROCEDURE E E;IF IF SYM=SYM=+THEN THEN BEGINBEGIN ADVANCE;ADVANCE;T;E T;E
21、END;END;PROCEDURE TPROCEDURE T;IF SYM=IF SYM=*THENTHENBEGINBEGIN ADVANCE;ADVANCE;F;T F;TEND;END;2 2、注意：、注意：有有，自动匹配，不会失败，自动匹配，不会失败无成功无成功/失败消息返回失败消息返回出错位置不确切出错位置不确切五、预测分析程序五、预测分析程序改进：改进：使用一张分析表和一个栈同样可实现使用一张分析表和一个栈同样可实现递归下降分析，用这种方法实现的语法分析程递归下降分析，用这种方法实现的语法分析程序叫序叫预测分析程序预测分析程序。a a 总控程序总控程序预测分析表预测分析表M Mx
22、x#输输 出出栈栈输入串输入串l预测分析程序有预测分析程序有四四部分部分求值X:=ABD条件控制WHILE ABD DO SIF ABaX-a，则则 a FIRST(X)a FIRST(X)X-X-，则则 FIRST(X)FIRST(X)若若XVXVNN,X-Y,X-Y,YVYVNN,则则 FIRST(Y)FIRST(Y)FIRST(X)FIRST(X)X-YX-Y1 1Y Y2 2Y Yi-1i-1Y Yi iY Yk k,Y Yj jVVN N ,1ji-1,1ji-1 FIRST(YFIRST(Yj j )，即，即Y Y1 1Y Y2 2Y Yi-1i-1 ，则，则 FIRST(FIRS
23、T(Y Yj j )FIRST(X)FIRST(X)当当 则则 FIRST(X)FIRST(X)FIRST(XFIRST(X1 1)的的非非终结符终结符加入加入FIRST(FIRST()若若FIRST(XFIRST(X1 1)，则则FIRST(XFIRST(X2 2)的所有非的所有非终结符加入终结符加入FIRST(FIRST()若若FIRST(XFIRST(X1 1),),FIRST(XFIRST(X2 2)，则则FIRST(XFIRST(X3 3)的所有非的所有非终结符加入终结符加入FIRST(FIRST()最后，若最后，若 FIRST(XFIRST(Xi i),),i=1.n i=1.n，
24、则，则 加入加入FIRST(FIRST()3 3）构造）构造FOLLOW(A)FOLLOW(A)应用下列规则，直到再没有什么加进任一应用下列规则，直到再没有什么加进任一FOLLOWFOLLOW为止为止4 4）例）例4.64.6 已知文法已知文法G G：E E TE TE T T*FT|FT|EE +TE|+TE|F F （E E）|i|iT T FTFT求它的求它的FIRST(FIRST(),FOLLOW(A),FOLLOW(A)#属于属于FOLLOW(S)FOLLOW(S)若存在若存在A-A-B B，则，则FIRST(FIRST()FOLLOW(B),)FOLLOW(B),除除外外FOLLO
25、W集的构造：集的构造：FIRST(TFIRST(T)=*,)=*,FIRST(EFIRST(E)=+,)=+,即即 FOLLOW(F)=*,若有若有A-A-B B，或，或 A-A-B B 且且FIRST(FIRST(),),则则FOLLOW(B)FOLLOW(A)FOLLOW(B)FOLLOW(A)FOLLOW(E)=),#FOLLOW(T)=+FOLLOW(F)=*由由得得：E E TETE得得 FOLLOW(E)FOLLOW(E)，即即 FOLLOW(E )=,)#E E TETE且且 E E 得得 FOLLOW(E)FOLLOW(E)FOLLOW(T)，即即 FOLLOW(T)=+,)#
26、T T FTFT得得 FOLLOW(T)FOLLOW(T)FOLLOW(T),即即 FOLLOW(T )=,T T FTFT且且 T T 得得 FOLLOW(T)FOLLOW(F),)#+)#+最终构造结果：最终构造结果：5 5）构造分析表）构造分析表算法：输入算法：输入G1G1文法，输出文法，输出分析表分析表MM六、六、LLLL（1 1）分析法）分析法lLLLL：第一个：第一个L L表示从左到右扫描输入串，表示从左到右扫描输入串，第二个第二个L L表示最左推导表示最左推导l（1 1）：表示分析时每一步只需向前查看一个符号）：表示分析时每一步只需向前查看一个符号2 2、LLLL（1 1）文法的
27、条件）文法的条件（1 1）FIRST(FIRST(）FIRST(FIRST()=)=（2 2）若）若 ，则，则 FIRSTFIRST（）FOLLOWFOLLOW（A A）=文法文法G G是是LL(1)LL(1)的，则对于的，则对于G G的每一个非终结符的每一个非终结符A A的任何两个不同产生式的任何两个不同产生式 A-A-|,有：有：使用使用LL(1)LL(1)文法，一定可以实现文法，一定可以实现不带回溯不带回溯的的自上而下分析自上而下分析；对对 A-A-|，若条件（若条件（1 1）不成立，）不成立，则则FIRST(FIRST(）FIRST(FIRST()，假假设，设，FIRST(FIRST(
28、）FIRST(FIRST()=a)=a 那么那么，当，当A A面临输入符号面临输入符号a a，而，而a a同时属于同时属于FIRST(FIRST(）和）和 FIRST(FIRST()，则分析无法继续进行下，则分析无法继续进行下去，因为不能确定用哪一个候选式可以保证一定去，因为不能确定用哪一个候选式可以保证一定能够得到匹配而不进行回溯。能够得到匹配而不进行回溯。实质实质就是分析表的就是分析表的MA,aMA,a中包含两条候选式中包含两条候选式A-A-A-A-反之，反之，分析表的分析表的MA,aMA,a中只包含一条候选式中只包含一条候选式则意味着可以进行确定性的无回溯的分析。则意味着可以进行确定性的
29、无回溯的分析。对对 A-A-|，若若 ，且，且条件（条件（2 2）不成立，）不成立，则则 FIRSTFIRST（）FOLLOWFOLLOW（A A）假假设，设，FIRST(FIRST(）FOLLOW(A)FOLLOW(A)=a =a 那么，当那么，当A A面临输入符号面临输入符号a a时时，若选候选式若选候选式A-A-，则由于，则由于a FIRST(a FIRST(）可以）可以使使a a一定得到匹配；一定得到匹配；同时，若选候选式同时，若选候选式A-A-也可以满足要求，也可以满足要求，这是这是由由 ，而，而a FOLLOW(A)a FOLLOW(A)。实质实质同样是由于分析表的同样是由于分析表
30、的MA,aMA,a中包含两条候选式：中包含两条候选式：A-A-A-A-而这与而这与LL(1)LL(1)文法的定义互相矛盾。文法的定义互相矛盾。综上所述，综上所述，若某文法为若某文法为LL(1)LL(1)文法，则该文文法，则该文法一定满足这两个条件，它意味着进行自上而下分法一定满足这两个条件，它意味着进行自上而下分析时可以对候选式进行不带回溯的确定性的选择。析时可以对候选式进行不带回溯的确定性的选择。因此，不能确定用哪一个候选式可以保因此，不能确定用哪一个候选式可以保证一定能够得到证一定能够得到a a的后续匹配而不进行回溯。的后续匹配而不进行回溯。但是，条件语句文法不能改造成但是，条件语句文法不
31、能改造成LL(1)LL(1)文法文法语句语句 if if 条件条件 then then 语句语句 else else 语句语句|if|if 条件条件 then then 语句语句例例4.8 S iCtS|iCtSeS|a C b提公因子后，文法成为：提公因子后，文法成为：S iCtSS|a SeS|C b 计算该文法的计算该文法的FIRSTFIRST集和集和FOLLOWFOLLOW集为：集为：abeit#SS aSiCtSS S S eS CC bFIRST(S)=iFIRST(S)=i，a a FIRST(SFIRST(S)=e)=e，FIRST(C)=b FIRST(C)=b FOLLOW
32、(S)=#FOLLOW(S)=#，e e FOLLOW(SFOLLOW(S)=#)=#，e e FOLLOW(C)=t FOLLOW(C)=t 按构造分析表算法，该文法的分析表按构造分析表算法，该文法的分析表MM为：为：文法：文法：S iCtSS|a SeS|C babeit#SS aSiCtSS SS S eSS CC b FIRST(SFIRST(S)=e)=e，而：而：FOLLOW(SFOLLOW(S)=#,e)=#,e SS-填入填入 M SM S,#,#和和 M SM S,e,e，即，即候选式候选式 S S-填法（填法（SSeSeS|）：由上表可见，改造后的文法仍然是非由上表可见，改
33、造后的文法仍然是非LL(1)LL(1)文文法。法。（这是因为，（这是因为，M SM S,e ,e 含有多个候选式含有多个候选式;或说：或说：FIRST(eS)FOLLOW(SFIRST(eS)FOLLOW(S)=e )=e ）因此，因此，强制令强制令 M SM S,e =S,e =S-eSeS （即：坚持把（即：坚持把e e和最近的和最近的t t相结合。）相结合。）从程序语言来看，相当于规定从程序语言来看，相当于规定ELSEELSE坚持与坚持与最近的最近的THENTHEN相结合。相结合。参考资料参考资料l陈火旺，程序设计语言编译原理（第三版）陈火旺，程序设计语言编译原理（第三版）,国国防工业出版社，防工业出版社，66836683l冯博琴译，现代编译程序设计，邮电出版社冯博琴译，现代编译程序设计，邮电出版社2.2.32.2.3，2.2.42.2.4lKenneth C.Kenneth C.LoudenLouden,冯博琴冯博琴 等译，编译原理与实等译，编译原理与实践，机械工业出版社践，机械工业出版社