编译原理语法分析详解.ppt

第四章语法分析 贵州大学 计算机科学与信息学院 第四章 语法分析 本章内容 自顶向下分析和自底向上分析 围绕语法分析器的自动生成展开 第四章 语法分析 4.1 语法分析器概述 4.2 书写文法 4.3 自顶向下分析 4.4 自底向上分析概述 4.5 算符优先分析法 4.6 LR分析器 4.7 二义文法的应用 4.1 语法分析器概述 语法分析器是编译器前端的重要组成部分，许多编译器，特别是由自动生成工具构造的编译器，往往其前端的中心部件就是语法分析器。语法分析器在编译器中的位置和作用如下： 语法分析器概述 语法分析器的主要作用有两点： 1 检查词法分析器输出的单词序列是否是源语言中的句子，亦即是否符合源语言的语法规则 2 检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理 两大类分析方法： 自顶向下分析 自底向上分析 4.2 书写文法 定义：如果一个文法有非终结符A，对某个串α，存在推导A ?+Aα ，则称该文法是左递归的。形式为A→Aα的产生式引起的左递归称为直接左递归。 直接左递归 A?Aa |b 串的特点 ba . . . a 消除直接左递归 A ? b A? A?? a A? | ? 4.2.1 消除左递归 一般而言，假定关于P的全部产生式是 P→P?1 | P?2 | … | P?m | ?1 | ?2|…|?n 其中，每个?都不等于?，每个?都不以P开头 那么，消除P的直接左递归就是把这些规则改写成： P→?1P? | ?2P? | … | ?nP? P?→?1P? | ?2P? |… | ?mP? | ? 4.2.1 消除左递归 例 算术表达式文法 E ? E + T | T （ T + T . . . + T ） T ? T ? F | F （ F ? F . . . ? F ） F ? ( E ) | id 消除左递归后文法 E ? TE ? E ? ? + TE ? | ? T ? FT ? T ? ? ? F T ? | ? F ? ( E ) | id 4.2.1 消除左递归 非直接左递归 S ? Aa | b A ? Sd | ? 先变换成直接左递归 S ? Aa | b A ? Aad | bd | ? 再消除左递归 S ? Aa | b A ? bd A? | A? A? ? adA? | ? 4.2.1 消除左递归 例 考虑文法G(S) S→Qc|c Q→Rb|b (3.1) R→Sa|a 令它的非终结符的排序为R、Q、S。 对于R，不存在直接左递归。 把R代入到Q的有关候选后，把Q的规则变为 Q→Sab | ab | b 4.2.1 消除左递归 例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a 令它的非终结符的排序为R、Q、S。 Q的规则变为 Q→Sab | ab | b 现在的Q不含直接左递归，把它代入到S的有关候选后，S变成 S→Sabc | abc | bc | c 4.2.1 消除左递归 例 考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a S变成 S→Sabc | abc | bc | c 消除S的直接左递归后： S→abcS? | bcS? | cS? S?→abcS? | ? Q→Sab |ab | b R→Sa|a 4.2.1 消除左递归 消除S的直接左递归后： S→abcS? | bcS? | cS? S?→abcS? | ? Q→Sab |ab | b R→Sa|a 关于Q和R的规则已是多余的，化简为： S→abcS? | bcS? | cS? S?→abcS? | ? (3.2) 4.2.1 消除左递归 注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。 例如，若对文法(3.1)的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是： S→Qc | c Q→Rb | b R→bcaR? | caR? |a R? (3.3) R?→ bca R? | ? 文法(3.2)和(3.3)的等价性是显然的。 4.2.2 提左因子 有左因子的文法 A ???1 | ??2 提左因子 A ? ? A