LIWensheng,SCST,BUPT第4章语法分析知识点：预测分析方法、LL(1)分析程序移进-归约分析方法、LR分析程序SLR(1)、LR(1)、LALR(1)分析表WenshengLiBUPT@20082/152§4语法分析简介4.1语法分析程序4.2自顶向下分析方法4.3自底向上分析方法4.4LR分析方法4.5软件工具YACC小结WenshengLiBUPT@20083/152语法分析简介语法分析是编译过程的核心部分语法分析任务由语法分析程序完成语法分析的工作依据是：语言的语法规则本章内容安排：首先讨论常用的语法分析方法和技术自顶向下的方法自底向上的方法WenshengLiBUPT@20084/1524.1语法分析程序语法分析程序的任务–从源程序记号序列中识别出各类语法成分–进行语法检查语法分析程序的地位：语法分析程序取记号词法分析程序记号符号表语义分析程序分析树WenshengLiBUPT@20085/152常用的分析方法–自顶向下的方法：从树根到叶子来建立分析树–自底向上的方法：从树叶到树根来建立分析树对输入符号串的扫描顺序：自左向右语法分析程序的作用–输入：记号流/记号序列–工作依据：语法规则–功能：将记号组合成语法成分、语法检查–输出：分析树–错误处理WenshengLiBUPT@20086/1524.2自顶向下分析方法一、递归下降分析二、递归调用预测分析三、非递归预测分析WenshengLiBUPT@20087/152一、递归下降分析从文法的开始符号出发，进行推导，试图推出要分析的输入串的过程。对给定的输入串，从对应于文法开始符号的根结点出发，自顶向下地为输入串建立一棵分析树。试探过程，是反复使用不同产生式谋求匹配输入串的过程。WenshengLiBUPT@20088/152例:试分析输入串=cad是否为如下文法的一个句子。ScAdAab|a(文法4.1)ScAdcad试图为输入符号串建立一个最左推导序列的过程。cadScAdabcadScAda推导？WenshengLiBUPT@20089/152–因为对输入串的扫描是自左至右进行的，只有使用最左推导，才能保证按扫描的顺序匹配输入串。递归下降分析方法的实现–文法的每一个非终结符号对应一个递归过程，即可实现这种带回溯的递归下降分析方法。–每个过程作为一个布尔过程，一旦发现它的某个产生式与输入串匹配，则用该产生式展开分析树，并返回true，否则分析树不变，返回false。实践中存在的困难和缺点–左递归的文法，可能导致分析过程陷入死循环。–回溯–工作的重复–效率低、代价高：穷尽一切可能的试探法。为什么采用最左推导？WenshengLiBUPT@200810/152二、递归调用预测分析一种确定的、...
