源程序 词法分析器 第 3 章语法分析 记 号 取下一个记号 符号表 分析器 分析树 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 前端的中间其余部分表示 3.1 上下文无关文法 3.1.1 上下文无关文法的定义 正规式能定义一些简单的语言, 能表示给定结构的固定次数的重复或者没有指定次数的重复例 :a (a) 5, a (a)* 正规式不能用于描述配对或嵌套的结构例 1: 配对括号串的集合例 2:{wcw w 是 a 和 的串 } 3.1 上下文无关文法 上下文无关文法是四元组 (V T, V N,, P) V T : 终结符集合 V N : 非终结符集合 : 开始符号 P : 产生式集合, 产生式形式 : 例 ( {, +,,, (, )}, {expr, op}, expr, P ) expr expr op expr expr (expr) expr expr expr op + op 3.1 上下文无关文法 简化表示 expr expr op expr (expr) expr op + 简化表示 E EE (E ) E + 3.1.2 推导 3.1 上下文无关文法 把产生式看成重写规则, 把符号串中的非终结符用其产生式右部的串来代替 例 E E + E E E (E ) E E E (E) (E + E) ( + E) ( + ) 概念 上下文无关语言 等价的文法 句型 记号 * + w 3.1 上下文无关文法 例 E E + E E E (E ) E 最左推导 E lm E lm (E) lm (E + E) lm ( + E) lm ( + ) 最右推导 ( 规范推导 ) E rm E rm (E) rm (E + E) rm (E + ) rm ( + ) 1
3.1 上下文无关文法 3.1.3 分析树 例 E E + E E E (E ) E E E ( E ) E + E 3.1 上下文无关文法 3.1.4 二义性 E E E E E + E E E E +E E + E E + E + E + E + + E E E * E E + E + E E * E E 文法的优点 文法为语言给出了精确的 易于理解的语法规范 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改 文法的问题 文法只能描述编程语言的大部分语法, 而不是所有的语法 3.2.1 正规式和上下文无关文法的比较 正规式 (a ) * a a 文法 0 a 0 0 a 1 1 2 2 开始 0 a 1 2 例 L={a n n n 1 } a a L 是不能用正规式描述的语言的一个范例 若存在接受 L 的 DF D, 状态数为 k 个 设 D 读完, a, aa,, a k 分别到达状态 s 0, s 1,, s k 至少有两个状态相同, 例如是 s i 和 s j, 则 a j i 属于 L s 0 标记为 a i 的路径 标记为 a j i 的路径 s i 标记为 i 的路径 f 3.2.2 分离词法分析器理由 为什么要用正规式定义词法 词法规则非常简单, 不必用上下文无关文法 对于词法记号, 采用正规式描述简洁且易于理解 从正规式构造出的词法分析器效率高 2
从软件工程角度看, 词法分析和语法分析的分离有如下好处 能否把词法分析并入到语法分析中, 直接从字符流进行语法分析? 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分 若把词法分析和语法分析合在一起, 则必须将语言的注释和空白的规则反映在文法中, 文法将大大复杂 注释和空白由自己来处理的分析器, 比注释和空白已由词法分析器删除的分析器要复杂得多 3.2.3 验证文法产生的语言 G : ( ) L(G) = 配对的括号串的集合 3.2.3 验证文法产生的语言 G : ( ) L(G) = 配对的括号串的集合 按推导步数进行归纳 : 推出的是配对括号串 归纳基础 : 归纳假设 : 少于 n 步的推导都产生配对的括号串 归纳步骤 :n 步的最左推导如下 : ( ) * (x) * (x) y 3.2.3 验证文法产生的语言 G : ( ) L(G) = 配对的括号串的集合 按串长进行归纳 : 配对括号串可由 推出 归纳基础 : 归纳假设 : 长度小于 2n 的都可以从 推导出来 归纳步骤 : 考虑长度为 2n(n 1) 的 w = (x) y ( ) * (x) * (x) y 3.2.4 适当的表达式文法 用一种层次观点看待表达式 (+) + + (+) 文法 expr expr + term term term term factor factor factor (expr) 3
expr expr + term term term term factor factor factor (expr) expr term factor term * term * factor factor 分析树 expr expr + term factor term factor term * factor + 分析树 3.2.5 消除二义性 stmt if expr then stmt ifexpr then stmt else stmt other 句型 :if expr then if expr then stmt else stmt 两个最左推导 : stmt if expr then stmt if expr then if expr then stmt else stmt stmt if expr then stmt else stmt if expr then if expr then stmt else stmt 无二义的文法 stmt matched _stmt unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt other unmatched_stmt if expr then stmt ifexpr then matched_stmt else unmatched_stmt 3.2.6 消除左递归 文法左递归 + 直接左递归 串的特点 消除直接左递归 例算术表达文法 E E + T T ( T + T...+T ) T T F F ( F F... F ) F ( E ) 消除左递归后文法 E TE E + TE T FT T FT F ( E ) 非直接左递归 a d 先变换成直接左递归 a ad d 再消除左递归 a d ad 4
3.2.7 提左因子 有左因子的文法 1 2 提左因子 1 2 例悬空 else 的文法 stmt if expr then stmt else stmt ifexpr then stmt other 提左因子 stmt if expr then stmt optional_else_part other optional_else_part else stmt 3.3.1 自上而下分析的一般方法 例文法 ac C cd c 为输入串 w = ac 建立分析树 a C a C c d 不能处理左递归 a C c 不能处理左递归的例子 算术表达文法 E E + T T E T T F F F ( E ) E + T E + T E + T 3.3.1 自上而下分析的一般方法 例文法 ac C cd c 为输入串 w = ac 建立分析树 a C a C a C c d c 不能处理左递归, 需要使用复杂的回溯技术 3.3.1 自上而下分析的一般方法 例文法 ac C cd c 为输入串 w = ac 建立分析树 a C a C a C c d c 不能处理左递归, 需要使用复杂的回溯技术, 回溯导致分析工作推倒重来 5
3.3.1 自上而下分析的一般方法 例文法 ac C cd c 为输入串 w = ac 建立分析树 a C a C a C c d c 不能处理左递归, 需要使用复杂的回溯技术, 回溯导致分析工作推倒重来, 难以报告出错的确切位置 3.3.1 自上而下分析的一般方法 例文法 ac C cd c 为输入串 w = ac 建立分析树 a C a C a C c d c 不能处理左递归, 需要使用复杂的回溯技术, 回溯导致分析工作推倒重来, 难以报告出错的确切位置, 效率低 3.3.2 LL(1) 文法 对文法加什么样的限制可以保证没有回溯? 先定义两个和文法有关的函数 FIRT( ) = {a * a, a V T } 特别是, * 时, 规定 FIRT( ) 对 的任何两个不同的选择 i 和 j, 希望有 FIRT( i ) FIRT( j )= 若 FIRT( i ) 或 FIRT( j ) 含, 还需增加条件 3.3.2 LL(1) 文法 对文法加什么样的限制可以保证没有回溯? 先定义两个和文法有关的函数 FIRT( ) = {a * a, a V T } 特别是, * 时, 规定 FIRT( ) FOLLOW()={a * a,a V T } 如果 是某个句型的最右符号, 那么结束标记 $ 属于 FOLLOW() LL(1) 文法任何两个产生式 都满足下列条件 : FIRT( ) FIRT( )= 若 *, 那么 FIRT( ) FOLLOW() = 例如, 对于下面的文法, 面临 a 时不知用什么规则 B a a FIRT(a) FOLLOW() B a C C LL(1) 文法任何两个产生式 都满足下列条件 : FIRT( ) FIRT( )= 若 *, 那么 FIRT( ) FOLLOW() = LL(1) 文法有一些明显的性质 没有公共左因子 不是二义的 不含左递归 6
例 E TE E + TE T FT T FT F (E) FIRT(E)=FIRT(T)=FIRT(F)={(,} FIRT(E )={+, } FRIT(T )={, } FOLLOW(E) = FOLLOW(E )={),$} FOLLOW(T) = FOLLOW (T )={+,),$} FOLLOW(F)={+,,),$} 3.3.3 递归下降的预测分析 为每一个非终结符写一个分析过程 这些过程可能是递归的 例 type simple array [simple]oftype simple integer char num dotdot num 一个辅助过程 vo match (terminal t) { if (lookahead == t) lookahead = nexttoken( ); else error( ); } vo type( ) { if ( (lookahead == integer) (lookahead == char) (lookahead == num) ) simple( ); else if ( lookahead == ){match( ); match();} else if (lookahead == array) { match(array); match( [ ); simple( ); match( ] ); match(of ); type( ); } } else error( ); type simple array [simple] of type vo simple( ) { if ( lookahead == integer) match(integer); else if (lookahead == char) match(char); else if (lookahead == num) { match(num); match(dotdot); match(num); } else error( ); } simple integer char num dotdot num 3.3.4 非递归的预测分析 栈 X Y Z $ 输入 a + $ 预测分析程序 分析表 M 输出 7
分析表的一部分 非终 输 入符 号 结符 + E E TE E E +TE T T FT T T T FT F F 预测分析器接受输入 * + 的前一部分动作 栈输入输出 $E + $ 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $E + $ $E T + $ E TE 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $E + $ $E T + $ E TE $E T F + $ T FT 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $E + $ $E T + $ E TE $E T F + $ T FT $E T + $ F 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $E + $ $E T + $ E TE $E T F + $ T FT $E T + $ F $E T + $ 匹配 8
预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $E + $ $E T + $ E TE $E T F + $ T FT $E T + $ F $E T + $ 匹配 $E T F + $ T FT 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $E + $ $E T + $ E TE $E T F + $ T FT $E T + $ F $E T + $ 匹配 $E T F + $ T FT $E T F + $ 匹配 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $E + $ $E T + $ E TE $E T F + $ T FT $E T + $ F $E T + $ 匹配 $E T F + $ T FT $E T F + $ 匹配 $E T + $ F 3.3.5 构造预测分析表 (1) 对文法的每个产生式, 执行 (2) 和 (3) (2) 对 FIRT( ) 的每个终结符 a, 把 加入 M[, a] (3) 如果 在 FIRT( ) 中, 对 FOLLOW() 的每个终结符 ( 包括 $), 把 加入 M[, ] (4)M 中其他没有定义的条目都是 error 多重定义的条目 消去多重定义 非终 输入符号 非终 输入符号 结符 other else 结符 other else stmt stmt other stmt stmt other e_part expr expr e_part else stmt e_part e_part expr expr e_part else stmt 9
3.3.6 预测分析的错误恢复 1 先对编译器的错误处理作一个概述 词法错误, 如标识符 关键字或算符的拼写错 语法错误, 如算术表达式的括号不配对 语义错误, 如算符和运算对象之间的类型不匹配 逻辑错误, 如无穷的递归调用 2 分析器对错误处理的基本目标 清楚而准确地报告错误的出现, 并尽量少出现伪错误 迅速地从每个错误中恢复过来, 以便诊断后面的错误 它不应该使处理正确程序的速度降低太多 3 非递归预测分析在什么场合下发现错误? 栈顶的终结符和下一个输入符号不匹配 a + $ 输入 3 非递归预测分析在什么场合下发现错误? 栈顶是非终结符, 输入符号是 a, 而 M[, a] 是空白 a + $ 输入 栈 X Y Z $ 预测分析程序 分析表 M 输出 栈 X Y Z $ 预测分析程序 分析表 M 输出 4 非递归预测分析 : 采用紧急方式的错误恢复 发现错误时, 分析器每次抛弃一个输入记号, 直到输入记号属于某个指定的同步记号集合为止 6 同步记号集合的选择 把 FOLLOW() 的所有终结符放入非终结符 的同步记号集合 5 同步词法分析器当前提供的记号流能构成的语法构造, 正是语法分析器所期望的 10
6 同步记号集合的选择 把 FOLLOW() 的所有终结符放入非终结符 的同步记号集合 if expr then stmt (then 是 expr 的一个同步记号 ) 6 同步记号集合的选择 把 FOLLOW() 的所有终结符放入非终结符 的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 6 同步记号集合的选择 把 FOLLOW() 的所有终结符放入非终结符 的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 a = expr; if ( 语句的开始符号作为表达式的同步记号, 以免表达式出错又遗漏分号时忽略 if 语句等一大段程序 ) 6 同步记号集合的选择 把 FOLLOW() 的所有终结符放入非终结符 的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 把 FIRT() 的终结符加入 的同步记号集合 a = expr;, if ( 语句的开始符号作为语句的同步符号, 以免多出一个逗号时会把 if 语句忽略了 ) 6 同步记号集合的选择 把 FOLLOW() 的所有终结符放入非终结符 的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 把 FIRT() 的终结符加入 的同步记号集合 如果非终结符可以产生空串, 若出错时栈顶是这样的非终结符, 则可以使用推出空串的产生式 例栈顶为 T, 面临 时出错 非终 输 入 符 号 结符 + E E TE E E +TE T T FT T 出错 T T FT 11
T 可以产生空串, 报错并用 T 非终 输 入 符 号 结符 + E E TE E E +TE T T FT T 出错, T T FT 用 T 同步记号集合的选择 把 FOLLOW() 的所有终结符放入非终结符 的同步记号集合 把高层结构的开始符号加到低层结构的同步记号集合中 把 FIRT() 的终结符加入 的同步记号集合 如果非终结符可以产生空串, 若出错时栈顶是这样的非终结符, 则可以使用推出空串的产生式 如果终结符在栈顶而不能匹配, 弹出此终结符 3.4.1 归约 例 abe c B d 3.4.1 归约 例 abe c B d acde( 读入 a) a 3.4.1 归约 例 abe c B d acde acde( 归约 ) 3.4.1 归约 例 abe c B d acde acde( 再读入 c) a a c 12
3.4.1 归约 例 abe c B d acde acde ade( 归约 ) 3.4.1 归约 例 abe c B d acde acde ade( 再读入 d) a c a c d 3.4.1 归约 例 abe c B d acde acde ade abe( 归约 ) a B c d 3.4.1 归约 例 abe c B d acde acde ade abe( 再读入 e) a B c d e 3.4.1 归约 例 abe c B d acde acde ade abe a ( 归约 ) B c d e 3.4.1 归约 例 abe c B d acde acde B ade abe a c d e rm abe rm ade rm acde rm acde 13
3.4.2 句柄句型的句柄是和某产生式右部匹配的子串, 并且, 把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步 abe c B d rm abe rm ade rm acde rm acde 句柄的右边仅含终结符如果文法二义, 那么句柄可能不唯一 例句柄不唯一 E E + E E E (E ) 例句柄不唯一 E E + E E E (E ) E rm E E rm E E + E rm E E + 3 rm E + 3 rm 1 + 3 例句柄不唯一 E E + E E E (E ) E rm E E E rm E + E rm E E + E rm E + 3 rm E E + 3 rm E E + 3 rm E + 3 rm E + 3 rm 1 + 3 rm 1 + 3 在句型 E E 中, 句柄不唯一 3.4.3 用栈实现移进 归约分析 栈输入动作 $ 先通过观察移进 归约分析器在分析输入串 1 时的动作序列来了解移进 归约分析的工作方式 14
栈输入动作 $ $E $ $E $E $E $ 15
$E $E $E $E $E 2 $ $E $E $E 2 $E $E $E 2 $E E $ $E $E $E 2 $E E $E $E $E 2 $E E $E E $ 16
$E $E $E 2 $E E $E E $E $E $E 2 $E E $E E $E E+ 3 $ $E $E $E 2 $E E $E E $E E+ 3 $E $E $E 2 $E E $E E $E E+ 3 $E E+E $ $E $E $E 2 $E E $E E $E E+ 3 $E E+E $ 按 E E+E 归约 $E $E $E 2 $E E $E E $E E+ 3 $E E+E $ 按 E E+E 归约 $E E $ 17
$E $E $E 2 $E E $E E $E E+ 3 $E E+E $ 按 E E+E 归约 $E E $ 按 E E E 归约 $E $E $E 2 $E E $E E $E E+ 3 $E E+E $ 按 E E+E 归约 $E E $ 按 E E E 归约 $E $ $E $E $E 2 $E E $E E $E E+ 3 $E E+E $ 按 E E+E 归约 $E E $ 按 E E E 归约 $E $ 接受 要想使用移进 归约方式分析句子, 尚需解决一些问题 如何决策选择移进还是归约 进行归约时, 确定右句型中将要归约的子串 进行归约时, 如何确定选择哪一个产生式 3.4.4 移进 归约分析的冲突 1 移进 归约冲突 例 stmt if expr then stmt ifexpr then stmt else stmt other 如果移进 归约分析器处于格局栈输入 if expr then stmt else $ 2 归约 归约冲突 stmt (parameter_list) expr = expr parameter_list parameter_list, parameter parameter parameter expr (expr_list) expr_list expr_list, expr expr 由 (I, J) 开始的语句 栈 ( 归约成 expr 还是 parameter? 输入,) 18
2 归约 归约冲突 stmt (parameter_list) expr = expr parameter_list parameter_list, parameter parameter parameter expr (expr_list) expr_list expr_list, expr expr 由 (I, J) 开始的语句 ( 词法分析查符号表, 区分第一个 ) 栈 proc ( 需要修改上面的文法 输入, ) 本节介绍 LR(k) 分析技术 特点 适用于一大类上下文无关文法 效率高 介绍构造 LR 分析表的三种技术 详细介绍简单的 LR 方法 ( 简称 LR) 概要介绍规范的 LR 方法 概要介绍向前看的 LR 方法 ( 简称 LLR) 3.5.1 构造 LR 分析表 例 1 (1) E E + T (4) T F (2) E T (5) F (E ) (3) T T F (6) F 若分析器的格局是栈输入 E + T + 则肯定句柄已经在栈顶 但仅从栈顶符号 T 不能判断句柄是 T 还是 E + T 例 2 若分析器的格局是栈输入 proc (, ) 则知道栈顶的 就是句柄 但不看到栈顶向下的第 3 个符号, 就不知把栈顶的 归约成哪个非终结符 思考栈中文法符号包含的信息偏少 ; 需要重新设计栈, 让栈中每个符号能概括栈中它下面部分所含的信息 术语 :LR(0) 项目 ( 简称项目 ) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 术语 :LR(0) 项目 ( 简称项目 ) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 expr expr + term 19
术语 :LR(0) 项目 ( 简称项目 ) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 expr expr + term term * factor 术语 :LR(0) 项目 ( 简称项目 ) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 expr expr + term term * factor 术语 :LR(0) 项目 ( 简称项目 ) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 例 XYZ 对应有四个项目 XYZ X YZ XY Z XYZ 例 只有一个项目和它对应 构造 LR 分析表的两大步骤 1 从文法构造识别活前缀的 DF 2 从上述 DF 构造分析表 1 从文法构造识别活前缀的 DF 1) 拓广文法 E E + T T T T F F F ( E ) 1 从文法构造识别活前缀的 DF 1) 拓广文法 E E E E + T T T T F F F ( E ) 20
1 从文法构造识别活前缀的 DF 2) 构造每个产生式的状态转换图 E E E E + T E T E E E E E E + T E E+T E E +T E E+ T E E+T E T T...... E T 1 从文法构造识别活前缀的 DF 3) 增加 转换, 得到完整 NF 的状态转换图 E E E E + T E T E E E E E E + T E E+T E E +T E E+ T E E+T T 指向 T F 对应的状态 E T E T 指向 T T F 对应的状 指向 T F 对应的状态态指向 T T F 对应的状态 1 从文法构造识别活前缀的 DF 4) 将 NF 用子集构造法确定化成 DF I 0 E I 1 + I 6 T I 9 F 指向 I 3 ( 指向 I 4 指向 I 5 T I 2 I 7 F I 10 ( F 指向 I 4 I 3 指向 I 5 ( I 4 E ) I 11 ( I 5 T F I 8 指向 I 2 指向 I 3 + 指向 I 6 I 1 : E E E E + T 指向 I 7 I 0 : E E E E + T E T T T F T F F (E) F I 0 E I 1 + I 6 T I 9 指向 I 7 F 指向 I 3 ( 指向 I 4 指向 I 5 T F 把每个状态 I 2 I 7 I 10 都作为接受状 ( F 指向 I 4 态, 则这是接 I 3 指向 I 5 受文法活前缀 ( E ) I 4 I 11 的 DF ( I 5 T F I 8 指向 I 2 指向 I 3 + 指向 I 6 1 从文法构造识别活前缀的 DF 活前缀 指文法 G 的某个右句型的一个前缀, 该前缀不超过该右句型的最右句柄的右端 在活前缀的右端添若干终结符可使它成为右句型 由一个拓广文法构造的这种 DF 是接受该文法活前缀的 DF 21
构造 LR 分析表的两大步骤 1 从文法构造识别活前缀的 DF 2 从 DF 构造分析表 E E E E + T T T T F F F ( E ) 2 从 DF 构造分析表 DF 的状态转换表 状态 + ( ) $ E T F 0 5 4 1 2 3 1 6 2 7 3 4 5 4 8 2 3 5 6 5 4 9 3 7 5 4 10 8 6 11 9 7 10 11 2 从 DF 构造分析表 (1) 将状态转换表分成终结符和非终结符两部分 DF 的状态转换表 状态 + ( ) $ E T F 0 5 4 1 2 3 1 6 2 7 3 4 5 4 8 2 3 5 6 5 4 9 3 7 5 4 10 8 6 11 9 7 10 11 2 从 DF 构造分析表 (2) 在终结符部分中的数字前加上 s, 表示状态 DF 的状态转换表 状态 + ( ) $ E T F 0 s5 s4 1 2 3 1 s6 2 s7 3 4 s5 s4 8 2 3 5 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 s7 10 11 2 从 DF 构造分析表 (3) 在终结符表中增加归约信息 (4) 空白条目都表示出错 DF 的状态转换表 状态 + ( ) $ E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 3.5.2 LR 分析算法 栈 s m X m s m-1 X m-1 s 0 输入 a1 a i a n $ LR 分析程序 action goto LR 分析器的模型 输出 22
例 E E+T E T T T F T E F (E ) F 栈输入动作 0 + $ 状态 动 作 转 移 + ( ) $ E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 栈输入动作 0 + 0 + 0 5 + $ 0 + 0 5 + $ 按 F 归约 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 23
0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + $ 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 T 2 7 + $ 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 T 2 7 + 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 T 2 7 + 0 T 2 7 5 + $ 24
0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 T 2 7 + 0 T 2 7 5 + $ 按 F 归约 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 T 2 7 + 0 T 2 7 5 + $ 按 F 归约 0 T 2 7 F 10 + $ 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 T 2 7 + 0 T 2 7 5 + $ 按 F 归约 0 T 2 7 F 10 + $ 按 T T F 归约 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 T 2 7 + 0 T 2 7 5 + $ 按 F 归约 0 T 2 7 F 10 + $ 按 T T F 归约 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 T 2 7 + 0 T 2 7 5 + $ 按 F 归约 0 T 2 7 F 10 + $ 按 T T F 归约 0 E 1 $ 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + 0 T 2 7 + 0 T 2 7 5 + $ 按 F 归约 0 T 2 7 F 10 + $ 按 T T F 归约 0 E 1 $ 接受 25
LR 分析方法和 LL 分析方法的比较 在下面的推导中, 最后一步用的是 l LR(1) 决定用该产生式的位置 rm rm w rm l w LL(1) 决定用该产生式的位置 3.5.3 其他 LR 分析表构造概述 LR 技术能力有限 V = E E V E V E V I 0 : V = E E V E V E V = 是 E 的一个后继符 : $ V = E $ E = E $ V I 2 : V = E E V I 2 中第一个项目使得 action[2, = ] = s6 I 2 中第二个项目使得 action[2, = ] 为按 E V 归约, 因为 = 是 E 的一个后继符 3.5.3 其他 LR 分析表构造概述 LR 技术能力有限 V = E E V E V E V I 0 : V = E E V E V E V 在所关注场合 E 的后继是 $: $ V = E $ E = E $ $ E $ V $ V I 2 : V = E E V I 2 中第一个项目使得 action[2, = ] = s6 I 2 中第二个项目使得 action[2, = ] 为按 E V 归约, 因为 = 是 E 的一个后继符 改进 LR(1) 分析技术的办法 把 LR(0) 项目拓展为 LR(1) 项目让 LR(0) 项目带上搜索符, 成为如下形式 [, a] 形式为 [, a] 的项目告知在面临 a 时按产生式 进行归约 按该思路构造的分析表称为规范的 LR 分析表 一个文法的 LR(1) 项目比它的 LR(0) 项目多得多, 相应的状态转换图也大得多 LLR 分析技术是一种折中的技术 LR 分析技术富有吸引力的原因 LR 分析技术能够用来识别所有能用上下文无关文法写出的编程语言构造 LR 分析技术是最一般的无回溯移进 - 归约技术, 能和其他移进 - 归约技术一样有效地实现 LR 分析技术能分析的文法类是预测分析或者说 LL 方法能分析的文法类的真超集 在自左向右扫描输入的前提下,LR 分析器能尽可能快地发现语法错误 3.5.4 非二义且非 LR 的上下文无关文法若自左向右扫描的移进 归约分析器能及时识别出现在栈顶的句柄, 那么相应的文法就是 LR 的 语言 L ={ww R w (a )*} 的文法 aa 不是 LR 的 aaaa 语言 L ={wcw R w (a )*} 的文法 aa c 是 LR 的 aacaa 26
例为语言 L = { a m n n > m 0 } 写三个文法, 它们分别是 LR(1) 的 二义的和非二义且非 LR(1) 的 LR(1) 文法 : B a B B 例为语言 L = { a m n n > m 0 } 写三个文法, 它们分别是 LR(1) 的 二义的和非二义且非 LR(1) 的 LR(1) 文法 : B a B B 非二义且非 LR(1) 的文法 : a B B B aaa aaa 3.6 语法分析器的生成器 例为语言 L = { a m n n > m 0 } 写三个文法, 它们分别是 LR(1) 的 二义的和非二义且非 LR(1) 的 LR(1) 文法 : B a B B 非二义且非 LR(1) 的文法 : a B B B 二义的文法 : a 3.6.1 分析器的生成器 Yacc Yacc 源程序 translate.y y.ta.c Yacc 编译器 C 编译器 y.ta.c a.out a a a 输入 a.out 输出 3.6 语法分析器的生成器 3.6.2 用 Yacc 处理二义文法 例台式计算器 输入一个表达式并回车, 显示计算结果 也可以输入一个空白行 3.6 语法分析器的生成器 %{ # include <ctype.h> # include <stdio.h > # define YYTYPE doule / 将栈定义为 doule 类型 / %} %token NUMBER %left + %left / %right UMINU %% 27
3.6 语法分析器的生成器 lines : lines expr \n {printf ( %g \n, $2 ) } lines \n / / ; expr : expr + expr {$$ = $1 + $3; } expr expr {$$=$1 $3; } expr expr {$$=$1 $3; } expr / expr {$$ = $1 / $3; } ( expr ) {$$ = $2; } expr %prec UMINU {$$ = $2; } NUMBER ; %% 3.6 语法分析器的生成器 lines : lines expr \n {printf ( %g \n, $2 ) } lines \n / / ; expr : expr + expr {$$ = $1 + $3; } expr expr {$$=$1 $3; } expr expr {$$=$1 $3; } expr / expr {$$ = $1 / $3; } ( expr ) {$$ = $2; } expr %prec UMINU {$$ = $2; } NUMBER ; %% -5+10 看成是 -(5+10), 还是 (-5)+10? 取后者 3.6 语法分析器的生成器 yylex ( ) { int c; while((c=getchar())== ); if((c==. ) (isdigit(c))){ ungetc (c, stdin); scanf ( % lf, &yylval); return NUMBER; } return c; } 3.6 语法分析器的生成器 3.6.3 Yacc 的错误恢复 编译器设计者的工作 决定哪些 主要的 非终结符将有错误恢复与它们相关联 为各主要非终结符 加入形式为 error 的错误产生式, 其中 是文法符号串 为这样的产生式配上语义动作 Yacc 把错误产生式当作普通产生式处理 3.6 语法分析器的生成器 遇到语法错误时 3.6 语法分析器的生成器 遇到语法错误时 从栈中弹出状态, 直到发现栈顶状态的项目集包含形为 error 的项目为止 栈. s... 发现错误 s : C 1 2 error error s 1 : C 1 2 s 2 : error 栈 ṣ... 发现错误 s : C 1 2 error error s 1 : C 1 2 s 2 : error 28
3.6 语法分析器的生成器 遇到语法错误时 从栈中弹出状态, 直到发现栈顶状态的项目集包含形为 error 的项目为止 把虚构的终结符 error 移进 栈 3.6 语法分析器的生成器 遇到语法错误时 从栈中弹出状态, 直到发现栈顶状态的项目集包含形为 error 的项目为止 把虚构的终结符 error 移进 栈 抛弃若干输入符号, 直至找到, 把 移进栈 栈 s 2 s... 发现错误 s : C 1 2 error error s 1 : C 1 2 s 2 : error 栈 s 2 s... s : C 1 2 error error s 1 : C 1 2 s 2 : error 3.6 语法分析器的生成器 遇到语法错误时 从栈中弹出状态, 直到发现栈顶状态的项目集包含形为 error 的项目为止 把虚构的终结符 error 移进 栈 抛弃若干输入符号, 直至找到, 把 移进栈 把 error 归约为, 恢复正常分析 s : 栈 C 1 2 error s 1 s... error s 1 : C 1 2 s 2 : error 3.6 语法分析器的生成器 增加错误恢复的台式计算器 lines : lines expr \n {printf ( %g \n, $2 ) } lines \n / / error \n {yyerror ( 重新输入上一行 ); yyerrok;} ; 本章要点 文法和语言的基本知识 自上而下的分析方法 : 预测分析, 非递归的预测分析,LL(1) 文法 自下而上的分析方法 : LR(1) 方法 语法分析器的生成器 Yacc 的基本原理 语法分析的错误恢复方法 例题 1 下面的二义文法描述命题演算公式的语法, 为它写一个等价的非二义文法 and or not p q () 非二义文法的产生式如下 : E E or T T T T and F F F not F ( E) p q 29
例题 1 下面的二义文法描述命题演算公式的语法, 为它写一个等价的非二义文法 and or not p q () 非二义文法的产生式如下 : E E or T T T T and F F F not E ( E) p q? not p and q 有两种不同的最左推导 例题 1 下面的二义文法描述命题演算公式的语法, 为它写一个等价的非二义文法 and or not p q () 非二义文法的产生式如下 : E E or T T not p and q T T and F F not p and q F not E ( E) p q? not p and q 有两种不同的最左推导 例题 2 设计一个文法 : 字母表 {a, } 上 a 和 的个数相等的所有串的集合 二义文法 : a a aaaa aaaa 例题 2 设计一个文法 : 字母表 {a, } 上 a 和 的个数相等的所有串的集合 二义文法 : a a aaaa aaaa 二义文法 : ab a B abb aaaa aaaa aaaa B B B B B B 例题 2 设计一个文法 : 字母表 {a, } 上 a 和 的个数相等的所有串的集合 二义文法 : a a aaaa aaaa 二义文法 : ab a B abb aaaa aaaa aaaa 非二义文法 : ab a a a aa B abb ab 例题 3 试说明下面文法不是 LR(1) 的 : L ML a M L M M M L L L a 句子 a 的分析树 30
例题 4 下面的文法不是 LR(1) 的, 对它略做修改, 使之成为一个等价的 LR(1) 文法 program egin declist ; statement end declist d;declist d statement s;statement s 该文法产生的句子的形式是 egin d ; d ; ;d;s;s; ;send 习 题 第一次 :3.2, 3.4()(c), 3.6(a)() 第二次 :3.8, 3.13 第三次 :3.14, 3.17 第四次 :3.19, 3.22 修改后的文法如下 : program egin declist statement end declist d;declist d; statement s;statement s 31