《编译原理》第五章

《《编译原理》第五章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、确定分析自顶向下语法分析(CH5)不确定分析(回溯)语法分析算符优先分析(CH6)自底向上语法分析LR分析(CH7)注：在以后各个章节的分析中，若没有特别说明，所讨论的文法均为上下文无关文法。1（上下文无关文法）句型的分析句型分析就是识别一个符号串是否为某文法的句型的过程，或者说是某个推导的构造过程。2语法树－推导的几何表示句型aabbaa的可能推导序列和语法树例:G[S]:SS→aASaASA→SbASbAaA→SSabaS→aSaASaAaaSbAaaSbbaaaabbaaA→baSaASaSbASaabASa

2、abbaSaabbaaSaASaSbASaSbAaaabAaaabbaa3语法分析在语言的编译实现中，把句子分析的过程称为语法分析，即完成这个任务的程序称为语法分析程序或称为识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。4语法分析算法分类自上而下分析法：从文法的开始符号出发，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。

3、5两种方法反映了语法树的两种构造过程。自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串；自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树。6自上而下分析对任何输入串，试图用一切可能的办法，从文法开始符号着手，自上而下地为输入串构造一棵语法树，或者说，为输入串寻找一个最左推导。本质上是一个试探过程，反复使用不同地产生式谋求匹配输入串的过程。7自上而下的语法分析的一般过程例：文法G：S→cAdA→abA→a识别输入串w=cabd是否为该文法的句子SSScAdc

4、Adab推导过程：ScAdcAdcabd8自上而下的语法分析的一般过程(1)S→cAd(2)A→ab(3)A→a识别输入串w=cad是否为该文法的句子识别输入串w=caa的过程：1.ScAd1.ScAd2.后选择(2)扩展A，得到推导ScAd2.选择(2)扩展A，得到推导ScAdcabdcabd这时3.回溯回到推导ScAdw的第二个符号可以与叶子结点a得4.选择(3)扩展A，得到推导ScAd以匹配，但第三个符号d却不能与下cad一叶子结点b匹配5.A没有选择了！回溯到推导S怎么办？-查看A有无另一个选择，有！c

5、Ad回溯，把A为根的子树剪掉，扫描过6.再回溯S有无另一个选择？没有！的输入串中的a吐出来,再试探用产生宣告分析失败。式（3）构造推导ScAdcad9自上而下的语法分析面临的问题-实现考虑（1）回朔（2）文法的左递归性S→Sa10（1）回溯的原因例G[S]:S→xAyA→ab｜a若当前输入串为xay，首先构造的推导SxAy匹配进一步推导对A可选择A→ab替换，得SxAyxabyxayxaby匹配xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式A→a进行试探，Sx

6、Ayxay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。11在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：B→A1

7、A2

8、…

9、An，那么如何确定用哪个右部去替代B？-------什么信息用于Parser做正确选择?(输入串,文法特点)12（2）左递归例文法G0[S]:(1)S→Sa(2)S→b分析baa是不是文法的句子按照自上而下的分析思想选用产生式(1)来推导SSa语法树末端结点最左符号为非终结符，

10、所以选用（1）继续推导SSaSaa此时语法树末端结点最左符号仍为非终结符，所以选用（1）继续推导SSaSaaSaaa问题——试图用S匹配输入串时，出现：在没有读入任何输入符号的情况下，又得重新要求S去进行新的匹配原因——文法含有左递归13自上而下的语法分析－－左递归规则G[S]:S→SanS→bL={ba

11、n≥1}W=baaaSbSSaSa14左递归：关于非终结符P的规则直接左递归：若P→Pα

12、βα、β∈V*且α、β不以P开头一般左递归：若P=>*PαS→Aa,A→Sb,…15自上而下分析的进一步

13、讨论自上而下分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导则表明输入串是给定文法的句子，否则表明该输入不是给定文法的句子。自上而下分析对文法的要求－文法不能