编译原理课件chap04(陈火旺).ppt

第四章语法分析--自上而下分析第四章语法分析——自上而下分析高级语言的语法结构适合用上下无关文法描述，因此，我们将上下文无关文法作为语法分析的根底。本章和下一章，我们将介绍编译程序构造中的一些典型的语法分析方法4.1语法分析器功能语法分析是编译过程的核心局部。它的任务是在词法分析识别出单词符号串的根底上，分析并判定程序的语法结构是否符合语法规那么。以下图说明了语法分析器在编译程序中的地位。

第四章语法分析--自上而下分析源程序词法分析单词符号取下一单词语法分析词法分析树编译后续符号表语法分析器在编译程序中地位

第四章语法分析--自上而下分析语法分析是编译程序的核心局部：在词法分析的根底上，识别单词符号序列是否是给定文法的正确句子〔程序〕。常用方法自顶向下分析自底向上分析确定不确定算符优先分析LR分析

第四章语法分析--自上而下分析自顶向下语法分析方法自顶向下分析法就是从文法的开始符号出发，试图推导出与输入的单词串完全匹配的句子。如果能够推导出，那么该输入串是给定文法的句子；如果不能推导出，那么该输入串不是给定文法的句子。

第四章语法分析--自上而下分析例：符号串S=cad文法G[Z]:Z→cAdA→ab|a求解S?L(G[Z])分析过程是设法建立一棵语法树,使语法树的末端结点与给定符号串相匹配.1.开始:令Z为根结点Z2.用Z的右部,符号串去匹配输入串·ZcAd完成一步推导Z?cAd检查c-c匹配A是非终结符,将匹配任务交给A

第四章语法分析--自上而下分析663.选用A的右部符号串匹配输入串A有两个右部,选第一个·cAdabZ完成进一步推导A?ab检查,a-a匹配,b-d不匹配(失败)但是还不能冒然宣布S?L(G[Z])4.回溯即砍掉A的子树改选A的第二右部·ZcAdaA?a检查a-a匹配d-d匹配建立语法树,末端结点为cad与输入cad相匹配,建立了推导序列E?cAd?cad∴cad?L(G(E))S=cadG[Z]:Z→cAdA→ab|a分析工作要局部地或全部地退回去重做叫回溯

第四章语法分析--自上而下分析自顶向下语法分析要解决的关键问题假定要被代换的最左非终结符号是B，且有n条规那么：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？

第四章语法分析--自上而下分析1.分析过程是带有预测的，对输入符号串要预测属于什么语法成分，然后根据该语法成分的文法建立语法树。2.分析过程是一种试探过程，是尽一切方法(选用不同规那么)设法建立语法树的过程，由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。

第四章语法分析--自上而下分析自顶向下分析存在的问题及解决方法自顶向下分析方法的根本缺点：不能处理具有左递归性的文法自顶向下分析为什么不能处理左递归文法？文法G，存在U∈Vn，ifU==U…,则G为左递归文法+1．左递归文法：左递归文法回溯问题

第四章语法分析--自上而下分析1010如果我们在匹配输入串过程中，假定正好轮到要用非终结符U直接匹配输入串，即要用U的右部符号串U¨¨去匹配，为了用U¨¨去匹配，又得用U去匹配，这样无限的循环下去将无法终止。如果文法具有间接左递归，那么也将发生上述问题，只不过环的圈子兜的更大。要实行自顶向下分析，必须要消除文法的左递归，下面我们将介绍直接左递归的消除方法，在此根底上再介绍一般左递归的消除方法。自顶向下分析为什么不能处理左递归文法？

第四章语法分析--自上而下分析1111①消除直接左递归:1111规那么一〔提因子〕i)U→xy|xw|…|xz解：U→x(y|w|…|z)得：U→xU’U’→y|w|…|ziii)U→x|xy解：U→x(y|ε)使用提因子法，不仅有助于消除直接左递归。而且有助于压缩文件的长度，使我们更加有效的分析句子。ii)U→xy|xw|…|xzy→y1y2w→y1w2解：U→x(y1(y2|w2)|…|z)得：U→xU’U’→y1y1’|…|zy1’→y