2y7xnChapt5.pptVIP免费

编译原理第五章语法分析——自下而上分析网上教学系统:070606302:编译原理http://sei.nudt.edu.cn/cp国防科技大学计算机系602教研室第五章语法分析——自下而上分析自上而下分析法(Top-down)自下而上分析法(Bottom-up)国防科技大学计算机系602教研室语法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。国防科技大学计算机系602教研室语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约国防科技大学计算机系602教研室G(E)：Ei|E+E|E-E|E*E|E/E|(E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE国防科技大学计算机系602教研室5.1.1归约采用“移进－归约”思想进行自下而上分析。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。国防科技大学计算机系602教研室例：设文法G(S)：(1)SaAcBe(2)Ab(3)AAb(4)Bd试对abbcde进行“移进－归约”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaSBcAae国防科技大学计算机系602教研室步骤:12345678910动作:进a进b归(2)进b归(3)进c进d归(4)进e归(1)edBBbccccbAAAAAAAaaaaaaaaaS国防科技大学计算机系602教研室bdbaceSABA分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串国防科技大学计算机系602教研室5.1.2规范归约定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有且AS*A则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。国防科技大学计算机系602教研室考虑文法G(E)：ET|E+TTF|T*FF(E)|i和句...