编译原理 - 自上而下的语法分析.pptVIP

第四章 语法分析—自上而下分析 内容 语法分析器的功能 自上而下分析面临的问题 LL（1）分析法 递归下降分析程序构造 预测分析程序 LL（1）分析中的错误处理 4.1 语法分析器的功能 语法分析器的功能 语法分析器的功能 语法分析方法 自上而下分析面临的问题 LL（1）分析法 递归下降分析程序构造 预测分析程序 LL（1）分析中的错误处理 4.1.1 语法分析器的功能 高级语言的语法结构 适合用上下文无关文法描述 语法分析器 任务：分析与判定程序的语法结构是否符合语法规则 工作本质：根据产生式识别输入串是否为一个句子 在编译器中的地位：核心部分 4.1.2 语法分析方法 自上而下分析法 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导 将文法开始符号做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串 自下而上分析法 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号 从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树 4.2 自上而下分析面临的问题 语法分析器的功能 自上而下分析面临的问题 自上而下分析的主旨 回溯举例 自上而下的带回溯试探法 自上而下分析面临的问题 左递归与回溯 LL（1）分析法 递归下降分析程序构造 预测分析程序 LL（1）分析中的错误处理 4.2.1 自上而下分析的主旨 自上而下 从文法的开始符号出发，向下推导，推出句子 存在问题：带“回溯” 克服方法 不带回溯的递归子程序（递归下降）分析方法 自上而下分析的主旨 为输入串寻找一个最左推导 对任何输入串，试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下地为输入串建立一棵语法树 4.2.2 回溯举例 例4.1 假定有文法 (1) S→xAy (2) A→**|* 分析输入串x*y(记为?)。 4.2.3 自上而下的带回溯试探法 实现途径 让每个非终结符对应一个递归子程序 如果发现某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值 否则，保持原来的语法树和IP值不变，并返回“假”值 4.2.4 自上而下分析面临的问题 自上而下分析面临的五个问题 消除左递归性 克服回溯 消除虚假匹配 确定出错位置 避免穷尽一切 4.2.5 左递归与回溯 文法的左递归问题 一个文法是含有左递归的，若存在非终结符P 将使自上而下分析陷入无限循环 回溯问题 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。这时，不得不“回溯” 4.3 LL(1)分析法 语法分析器的功能 自上而下分析面临的问题 LL(1)分析法 不带回溯的自上而下分析算法 左递归的消除 回溯的消除 LL(1)分析条件 递归下降分析程序构造 预测分析程序 LL(1)分析中的错误处理 4.3.1 不带回溯的自上而下分析算法 自上而下分析方法 不允许文法含有任何左递归 构造不带回溯的自上而下分析算法 消除文法的左递归性 找出克服回溯的充分必要条件 4.3.2 左递归的消除（一） 直接消除产生式中的左递归 假定关于非终结符P的规则为 P→P? | ? 其中?不以P开头 那么，我们可以把P的规则等价地改写为如下的非直接左递归形式： P→?P? P?→?P?|? 4.3.2 左递归的消除（二） 一般而言，假定关于P的全部产生式是 P→P?1 | P?2 | … | P?m | ?1 | ?2|…|?n 其中，每个?都不等于?，而每个?都不以P开头 那么，消除P的直接左递归性就是改写这些规则： P→?1P? | ?2P? | … | ?nP? P?→?1P? | ?2P? |… | ?mP? | ? 4.3.2 左递归的消除（三） 例4.2 文法 E→E＋T | T T→T*F | F F→(E) | i 经消去直接左递归后变成： E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i 4.3.2 左递归的消除（四） 例如文法 S→Qc|c Q→Rb|b R→Sa|a 虽没有直接左递归，但S、Q、R都是左递归的，如： S?Qc?Rbc?Sabc 一个文法消除左递归的条件 不含以?为右部的产生式（空产生式） 不含回路，形如 4.3.2 左递归的消除（五） 消除左递归的算法 把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn ；按此顺序执行；