源程序 词法分析器 第三章语法分析 记 号 取下一个记号 符号表 分析器 分析树 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开分析器 (prser, syntx nlyzer) 前端的中间其余部分表示 1 3.1 上下文无关文法 3.1.1 上下文无关文法的定义上下文无关文法 context-free grmmr 正规式能定义一些简单的语言, 能表示给定结构的固定次数的重复或者没有指定次数的重复例 () 5, ()* 正规式不能用于描述配对或嵌套的结构例 1 配对括号串的集合例 2{wcw w 是 和 的串 } 2 3.1 上下文无关文法 3.1 上下文无关文法 上下文无关文法是四元组 (V T, V N, S, P) V T 终结符 (terminl, 记号 token 的第 1 元 ) 集合 V N 非终结符 (nonterminl) 集合 S 开始符号 (strt symol), 是一个非终结符 P 产生式 (production) 集合 产生式的形式 A, 有时用 A = 例 ( {, +,,, (, )}, {expr, op}, expr, P ) expr expr op expr expr (expr) expr expr expr op + op 3 简化表示 expr expr op expr (expr) expr op + 注 +, * 是 op 的选择 (lterntives) 简化表示 A ( ) A + 4 3.1 上下文无关文法 3.1 上下文无关文法 3.1.2 推导 (derivtion) 把产生式看成重写规则, 把符号串中的非终结符用其产生式右部的串来代替 例 + ( ) () ( + ) ( + ) ( + ) 上述代换序列称为从 到 -(+) 的推导 -(+) 是 的实例 记法 0 步或多步推导 S * 一步或多步推导 S + w 5 概念 上下文无关语言 由上下文无关文法 G 产生的语言 从开始符号 S 出发, 经 + 推导所能到达的所有仅由终结符组成的串 等价的文法 它们产生同样的语言 句型 (sententil form) S *,S 是开始符号, 是由终结符和 / 或非终结符组成的串, 则 是文法 G 的句型 句子 (sentence) 仅由终结符组成的句型 6
3.1 上下文无关文法 例 + ( ) 最左推导 (leftmost derivtion) 每步代换最左边的非终结符 lm lm () lm ( + ) lm ( + ) lm ( + ) 最右推导 (rightmost or cnonicl 规范推导 ) 每步代换最右边的非终结符 rm rm () rm ( + ) rm ( + ) rm ( + ) 3.1 上下文无关文法 3.1.3 分析树 (prse tree) 例 + ( ) -(+) 最左推导的分析树 7 8 3.1 上下文无关文法 3.1.3 分析树 (prse tree) 例 + ( ) -(+) 最左推导的分析树 3.1 上下文无关文法 3.1.3 分析树 (prse tree) 例 + ( ) -(+) 最左推导的分析树 ( ) ( ) + 9 10 3.1 上下文无关文法 3.1.3 分析树 (prse tree) 例 + ( ) -(+) 最左推导的分析树 3.1 上下文无关文法 3.1.3 分析树 (prse tree) 例 + ( ) -(+) 最左推导的分析树 ( ) ( ) + + 11 12
3.1 上下文无关文法 3.1.4 二义性 (miguity) 文法的某些句子存在不止一种最左 ( 最右 ) 推导, 或者不止一棵分析树, 则该文法是二义的 + + + + + + + + 两个不同的最左推导 13 3.1 上下文无关文法 3.1.4 二义性 + + + + + + + + 两棵不同的分析树 * + * + 14 文法的优点 3.2 语言和文法 文法给出了精确的 易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础来实现语言, 便于实现对语言的扩展和修改 文法的问题 文法只能描述编程语言的大部分语法, 不能描述语言中上下文有关的语法特征如, 语言要求变量先声明再使用 15 3.2 语言和文法 3.2.1 正规式和上下文无关文法的比较 正规式 ( ) * 开始 1 2 文法 可机械地由 NFA 变换而得, 为每个 NFA 状态引入一个非终结符 A 0 A 0 A 0 A 1 A 1 A 2 A 2 ( 该产生式并不必要 ) 0 16 3.2 语言和文法 3.2.2 分离词法分析器的理由 为什么要用正规式定义词法 词法规则非常简单, 不必用上下文无关文法 对于词法记号, 正规式描述简洁且易于理解 从正规式构造出的词法分析器效率高 3.2 语言和文法 从软件工程角度看, 词法分析和语法分析的分离有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强, 如输入字符集的特殊性等可以限制在词法分析器中处理 便于编译器前端的模块划分 17 18
3.2 语言和文法 能否把词法分析并入到语法分析中, 直接从字符流进行语法分析 3.2 语言和文法 3.2.3 验证文法产生的语言 G S (S) S L(G) = 配对的括号串的集合 若把词法分析和语法分析合在一起, 则必须将语言的注解和空白的规则反映在文法中, 文法将大大复杂 注解和空白由自己来处理的分析器, 比注解和空白符已由词法分析器删除的分析器要复杂得多 19 20 3.2 语言和文法 3.2.3 验证文法产生的语言 G S (S) S L(G) = 配对的括号串的集合 3.2 语言和文法 3.2.3 验证文法产生的语言 G S (S) S L(G) = 配对的括号串的集合 按推导步数进行归纳 推出的是配对括号串 归纳基础 (sis) S 归纳 (Induction) 假设 少于 n 步的推导都产生配对的括号串归纳步骤 n 步的最左推导如下 S (S)S * (x) S * (x) y 21 按串长进行归纳 配对括号串可由 S 推出 归纳基础 S 归纳假设 长度小于 2n 的配对的括号串都可以从 S 推导出来 归纳步骤 考虑长度为 2n(n 1) 的 w = (x) y S (S)S * (x) S * (x) y 22 3.2 语言和文法 3.2.4 适当的表达式文法 - 无二义性 用一种层次观点看待表达式 (+) + + 23 3.2 语言和文法 3.2.4 适当的表达式文法 用一种层次观点看待表达式 (+) + + (+) 文法 expr expr + term term term term fctor fctor fctor (expr) 24
3.2 语言和文法 expr expr + term term term term fctor fctor fctor (expr) expr term fctor term * expr term expr + term * fctor term term * fctor fctor fctor fctor + 分析树 25 分析树 3.2 语言和文法 3.2.5 消除二义性 (liminting miguity) stmt if expr then stmt if expr 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 26 3.2 语言和文法 3.2 语言和文法 无二义的文法 stmt mtched _stmt unmtched_stmt mtched_stmt if expr then mtched_stmt else mtched_stmt other unmtched_stmt if expr then stmt if expr then mtched_stmt else unmtched_stmt 27 3.2.6 消除左递归 (liminting left recursion) 文法左递归 A + A 自上而下的分析不能用于左递归文法 直接左递归 (immedite left recursion) A A, 不以 开头 串的特点 消除直接左递归 A A A A A A 28 3.2 语言和文法 3.2 语言和文法 例算术表达文法 + T T ( T + T + T ) T T F F ( F F F ) F ( ) 消除左递归后文法 T + T T FT T F T F ( ) 29 非直接左递归 S A A Sd 先变换成直接左递归 S A A Ad d 再消除左递归 S A A d A A A da 30
3.2 语言和文法 3.2.7 提左因子 (left fctoring) 有左因子的 (left -fctored) 文法 A 1 2 自上而下分析时, 不清楚应该用 A 的哪个选择来代换 提左因子 A A A 1 2 31 3.2 语言和文法 例悬空 else 的文法 stmt if expr then stmt else stmt if expr then stmt other 提左因子 stmt if expr then stmt optionl_else_prt other optionl_else_prt else stmt 32 3.2 语言和文法 3.2 语言和文法 3.2.8 非上下文无关的语言构造 L 1 = {wcw w 属于 ( ) * } 标识符的声明应先于其引用的抽象 C Jv 都不是上下文无关语言 L 2 = { n m c n d m n 0, m 0} 形参个数和实参个数应该相同的抽象 L 3 = { n n c n n 0} 早先排版描述的一个现象的抽象 e g i n5 个字母键,5 个回退键,5 个下划线键 33 L 1 = {wcw R w ( ) * } S S S c L 2 = { n m c m d n n 1, m 1} S Sd Ad A Ac c L 2 = { n n c m d m n 1,m 1} S A A A cd cd 34 3.2 语言和文法 3.2 语言和文法 L 3 ={ n n n 1} S S L 3 是不能用正规式描述的语言的一个范例 若存在接受 L 3 的 DFA D, 状态数为 k 个 设 D 读完,,,, k 分别到达状态 s 0, s 1,, s k 至少有两个状态相同, 例如是 s i 和 s j, 则 j i 属于 L 3 s 0 标记为 i 的路径 标记为 j i 的路径 s i 标记为 i 的路径 f 35 3.2.9 形式语言鸟瞰 文法 G = (V T, V N, S, P) 0 型文法,, (V N V T ) *, 1 36
3.2 语言和文法 3.2.9 形式语言鸟瞰 文法 G = (V T, V N, S, P) 0 型文法,, (V N V T ) *, 1 3.2 语言和文法 3.2.9 形式语言鸟瞰 文法 G = (V T, V N, S, P) 0 型文法,, (V N V T ) *, 1 1 型文法, 但 S 可以例外 短语文法 短语文法 37 38 3.2 语言和文法 3.2.9 形式语言鸟瞰 文法 G = (V T, V N, S, P) 0 型文法,, (V N V T ) *, 1 1 型文法, 但 S 可以例外 3.2 语言和文法 3.2.9 形式语言鸟瞰 文法 G = (V T, V N, S, P) 0 型文法,, (V N V T ) *, 1 1 型文法, 但 S 可以例外 2 型文法 A,A V N, (V N V T ) * 短语文法 上下文有关文法 短语文法 上下文有关文法 39 40 3.2 语言和文法 3.2.9 形式语言鸟瞰 文法 G = (V T, V N, S, P) 0 型文法,, (V N V T ) *, 1 1 型文法, 但 S 可以例外 2 型文法 A,A V N, (V N V T ) * 短语文法 上下文有关文法 上下文无关文法 41 3.2 语言和文法 3.2.9 形式语言鸟瞰 文法 G = (V T, V N, S, P) 0 型文法,, (V N V T ) *, 1 1 型文法, 但 S 可以例外 2 型文法 A,A V N, (V N V T ) * 3 型文法 A 或 A,A, V N, V T 短语文法 上下文有关文法 上下文无关文法 42
3.2 语言和文法 3.2.9 形式语言鸟瞰 文法 G = (V T, V N, S, P) 0 型文法,, (V N V T ) *, 1 1 型文法, 但 S 可以例外 2 型文法 A,A V N, (V N V T ) * 3 型文法 A 或 A,A, V N, V T 短语文法 上下文有关文法 上下文无关文法 正规文法 43 3.2 语言和文法 例 L 3 ={ n n c n n 1} 的上下文有关文法 S SC S C C C C c cc cc n n c n 的推导过程如下 S * n-1 S(C) n 1 用 S SC n-1 次 S + n (C) n 用 S C 1 次 S + n n C n 用 C C 交换相邻的 C S + n n 1 C n 用 1 次 S + n n C n 用 n-1 次 S + n n cc n-1 用 C c 1 次 S + n n c n 用 cc cc n-1 次 44 3.3.1 自上而下 (top-down) 分析的一般方法 为输入串寻找最左推导 试探 - 回溯 ( 效率低, 代价高 ) 例文法 S C C cd c 为输入串 w = c 建立分析树 S S S 不能处理左递归的例子 算术表达文法 + T T T T F F F ( ) + T + T C C C + T c 不能处理左递归 d c 45 46 3.3.2 LL(1) 文法 L-scnning from left to right; L- leftmost derivtion 对文法加什么样的限制可以保证没有回溯? 先定义两个和文法有关的函数 FIRST( ) = { *, V T } 特别是, * 时, 规定 FIRST( ) 对 A 的任何两个不同选择 i 和 j, 希望有 FIRST( i ) FIRST( j ) = 若 FIRST( i ) 或 FIRST( j ) 含, 还需增加条件 47 3.3.2 LL(1) 文法 对文法加什么样的限制可以保证没有回溯? 先定义两个和文法有关的函数 FIRST( ) = { *, V T } 特别是, * 时, 规定 FIRST( ) FOLLOW(A) = { S * A, V T } 如果 A 是某个句型的最右符号, 那么 $ 属于 FOLLOW(A) 48
计算 FIRST(X), X V T V N X V T, FIRST( X ) = {X} X V N 且 X Y 1 Y 2 Y k 加入 FIRST( X ), 如果 FIRST(Y i ) 且 在 FIRST(Y 1 ),, FIRST(Y i-1 ) 中 加入 FIRST(X), 如果 在 FIRST(Y 1 ),, FIRST(Y k ) 中 X V N 且 X 加入 FIRST(X) 49 计算 FIRST(X 1 X 2 X n ), X i V T V N, 它包含 FIRST(X 1 ) 中所有的非 符号 FIRST(X i ) 中所有的非 符号, 如果 在 FIRST(X 1 ),, FIRST(X i-1 ) 中, 如果 在 FIRST(X 1 ),, FIRST(X n ) 中 计算 FOLLOW(A), A V N $ 加入到 FOLLOW(S) 中 如果 A, 则 FIRST( ) 加入到 FOLLOW() 如果 A 或 A 且 FIRST( ), 则 FOLLOW(A) 的所有符号加入到 FOLLOW() 50 LL(1) 文法任何两个产生式 A 都满足下列条件 FIRST( ) FIRST( ) = 若 *, 那么 FIRST( ) FOLLOW(A) = LL(1) 文法任何两个产生式 A 都满足下列条件 FIRST( ) FIRST( ) = 若 *, 那么 FIRST( ) FOLLOW(A) = 例如, 对于下面文法, 面临 时, 第 2 步推导不知用 A 的哪个产生式选择 S A A FIRST() FOLLOW(A) C C 51 LL(1) 文法有一些明显的性质 没有公共左因子 不是二义的 不含左递归 52 例 T + T T FT T FT F () FIRST() = FIRST(T) = FIRST(F) = { (, } FIRST( ) = {+, } FRIST(T ) = {, } FOLLOW() = FOLLOW( ) = { ), $} FOLLOW(T) = FOLLOW(T ) = {+, ), $} FOLLOW(F) = {+,, ), $} 53 3.3.3 递归下降 (recursive-descent) 的预测分析 为每一个非终结符写一个分析过程 这些过程可能是递归的 例 type simple rry [simple] of type simple integer chr num dotdot num 54
一个辅助过程 vo mtch (terminl t) { if (lookhed == t) lookhed = nexttoken( ); else error( ); } 55 vo type( ) { if ( (lookhed == integer) (lookhed == chr) (lookhed == num) ) simple( ); else if ( lookhed == ) { mtch( ); mtch();} else if (lookhed == rry) { mtch(rry); mtch( [ ); simple( ); mtch( ] ); mtch(of ); type( ); } else error( ); } type simple rry [simple] of type 56 vo simple( ) { if ( lookhed == integer) mtch(integer); else if (lookhed == chr) mtch(chr); else if (lookhed == num) { mtch(num); mtch(dotdot); mtch(num); } else error( ); } simple integer chr num dotdot num57 3.3.4 非递归的预测分析 (nonrecursive predictive prsing) + $ 输入 栈 X Y Z $ 预测分析程序 分析表 M 输出 58 分析表 ( 表 3.1, P57) 的一部分 非终 输入 符号 结符 + T +T T T FT T T T FT F F 59 预测分析器接受输入 * + 的前一部分动作 栈输入输出 $ + $ 60
预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $ + $ $ T + $ T 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $ + $ $ T + $ T $ T F + $ T FT 61 62 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $ + $ $ T + $ T $ T F + $ T FT $ T + $ F 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $ + $ $ T + $ T $ T F + $ T FT $ T + $ F $ T + $ 63 64 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $ + $ $ T + $ T $ T F + $ T FT $ T + $ F $ T + $ $ T F + $ T FT 65 预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $ + $ $ T + $ T $ T F + $ T FT $ T + $ F $ T + $ $ T F + $ T FT $ T F + $ 66
预测分析器接受输入 * + 的前一部分动作 栈 输 入 输 出 $ + $ $ T + $ T $ T F + $ T FT $ T + $ F $ T + $ $ T F + $ T FT $ T F + $ $ T + $ F 67 3.3.5 构造预测分析表 (predictive prsing tle) (1) 对文法的每个产生式 A, 执行 (2) 和 (3) (2) 对 FIRST( ) 的每个终结符, 把 A 加入 M[A, ] (3) 如果 在 FIRST( ) 中, 对 FOLLOW(A) 的每个终结符 ( 包括 $), 把 A 加入 M[A, ] (4)M 中其它没有定义的条目都是 error 68 多重定义的条目 ( 若 G 左递归或二义 ) stmt if expr then stmt e_prt other e_prt else stmt expr 消去多重定义删去 e_prt, 这正好满足 else 和最近的 then 配对 LL(1) 文法 预测分析表没有多重定义的条目 非终结符 stmt e_prt expr 输入符号 other else stmt other e_prt else stmt e_prt expr 69 非终结符 stmt e_prt 输入符号 other else stmt other e_prt else stmt expr expr 70 3.3.6 预测分析的错误恢复 (error recovery) 1 先对编译器的错误处理做一个概述 词法错误, 如标识符 关键字或算符的拼写错 语法错误, 如算术表达式的括号不配对 语义错误, 如算符作用于不相容的运算对象 逻辑错误, 如无穷的递归调用 2 分析器对错误处理的基本目标 清楚而准确地报告错误的出现, 并尽量少出现伪错误 迅速地从每个错误中恢复过来, 以便诊断后面的错误 它不应该使正确程序的处理速度降低太多 71 72
3 非递归预测分析在什么场合下发现错误 栈顶的终结符和下一个输入符号不匹配 输入 + $ 3 非递归预测分析在什么场合下发现错误 栈顶是非终结符 A, 输入符号是, 而 M[A, ] 是空白 + $ 输入 栈 X Y Z $ 预测分析程序 分析表 M 输出 73 栈 X Y Z $ 预测分析程序 分析表 M 输出 74 4 非递归预测分析采用紧急方式 (pnic mode) 的错误恢复 发现错误时, 抛弃输入记号直到其属于某个指定的同步记号 (synchronizing tokens) 集合为止 5 同步 (synchronizing) 同步 词法分析器当前提供的记号流能够构成的语法构造, 正是语法分析器所期望的 不同步的例子语法分析器期望剩余的前缀构成过程调用语句, 而实际剩余的前缀形成的是赋值语句 75 6 同步记号集合的选择 把 FOLLOW(A) 的所有终结符放入非终结符 A 的同步记号集合 76 6 同步记号集合的选择 把 FOLLOW(A) 的所有终结符放入非终结符 A 的同步记号集合 if expr then stmt (then 和分号等记号是 expr 的同步记号 ) 6 同步记号集合的选择 把 FOLLOW(A) 的所有终结符放入非终结符 A 的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 77 78
6 同步记号集合的选择 把 FOLLOW(A) 的所有终结符放入非终结符 A 的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 = expr; if ( 语句的开始符号作为表达式的同步记号, 以免表达式出错又遗漏分号时忽略 if 语句等一大段程序 ) 79 6 同步记号集合的选择 把 FOLLOW(A) 的所有终结符放入非终结符 A 的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 把 FIRST(A) 的终结符加入 A 的同步记号集合 = expr;, if ( 语句的开始符号作为语句的同步符号, 以免多出一个逗号时会把 if 语句忽略了 ) 80 6 同步记号集合的选择 把 FOLLOW(A) 的所有终结符放入非终结符 A 的同步记号集合 把高层构造的开始符号加到低层构造的同步记号集合中 把 FIRST(A) 的终结符加入 A 的同步记号集合 如果出错时栈顶是存在有产生空串选择的非终结符, 则可以使用其推出空串的产生式选择 81 例栈顶为 T, 面临 时出错 非终 输 入 符 号 结符 + T +T T T FT T 出错 T T FT 82 T 可以产生空串, 报错并用 T 非终 输 入 符 号 结符 + T +T T T FT T 出错, T T FT 用 T 83 同步记号集合的选择 把 FOLLOW(A) 的所有终结符放入非终结符 A 的同步记号集合 把高层结构的开始符号加到低层结构的同步记号集合中 把 FIRST(A) 的终结符加入 A 的同步记号集合 如果出错时栈顶是存在有产生空串选择的非终结符, 则可以使用其推出空串的产生式选择 如果终结符在栈顶而不能匹配, 弹出此终结符 84
自下而上 (ottom-up) 的分析, 又称移进 - 归约 (shift-reduce) 分析 3.4.1 归约把输入串归约成文法的开始符号, 最右推导的逆过程 例 S Ae A Ac d 3.4.1 归约把输入串归约成文法的开始符号, 最右推导的逆过程 例 S Ae A Ac d cde( 读入 ) 寻找能匹配某产生式右部的子串 85 86 3.4.1 归约把输入串归约成文法的开始符号, 最右推导的逆过程 例 S Ae A Ac d cde Acde( 归约 ) A 3.4.1 归约 例 S Ae A Ac d cde Acde( 再读入 c) A c 87 88 3.4.1 归约 例 S Ae A Ac d cde Acde Ade( 归约 ) A A 3.4.1 归约 例 S Ae A Ac d cde Acde Ade( 再读入 d) A A c c d 89 90
3.4.1 归约 例 S Ae A Ac d cde Acde Ade Ae( 归约 ) A A c d 3.4.1 归约 例 S Ae A Ac d cde Acde Ade Ae( 再读入 e) A A c d e 91 92 3.4.1 归约 例 S Ae A Ac d cde Acde Ade Ae S( 归约 ) A A S c d 93 e 3.4.1 归约 例 S Ae A Ac S d cde Acde A Ade A Ae S c d e S rm Ae rm Ade rm Acde rm cde 94 3.4.2 句柄 (hndles) 句型的句柄是该句型中和某产生式右部匹配的子串, 并且把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步 S Ae A Ac d S rm Ae rm Ade rm Acde rm cde 句柄的右边仅含终结符如果文法二义, 那么句柄可能不唯一 95 例句柄不唯一 + ( ) 96
例句柄不唯一 + ( ) rm rm + rm rm rm 1 例句柄不唯一 + ( ) rm rm + rm + rm rm rm rm rm rm 1 rm 1 97 在右句型 中, 句柄不唯一 * 右句型 最右推导可得的句型 98 3.4.3 用栈实现移进 归约分析 栈输入动作 $ 先通过移进 归约分析器在分析输入串 1 时的动作序列来了解移进 归约分析的工作方式 99 100 栈输入动作 $ 101 102
$ 按 归约 要想很好地使用移进 归约方式, 尚需解决一些问题 如何决策是选择移进还是归约 进行归约时, 确定右句型中将要归约的子串 ( 即句柄 ) -- 总是出现在栈顶 进行归约时, 如何确定选择哪一个产生式 103 104 $ 按 归约 $ $ $ 按 归约 $ 105 106 $ 按 归约 $ $ $ $ 按 归约 $ $ 107 108
$ 按 归约 $ $ $ 2 $ $ 按 归约 $ $ $ 2 $ 按 归约 109 110 $ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ 按 归约 $ $ $ 2 $ 按 归约 $ 111 112 $ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ $ 按 归约 $ $ $ 2 $ 按 归约 $ $ 113 114
$ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ + 3 $ $ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ + 3 $ 按 归约 115 116 $ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ + 3 $ 按 归约 $ + $ $ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ + 3 $ 按 归约 $ + $ 按 + 归约 117 118 $ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ + 3 $ 按 归约 $ + $ 按 + 归约 $ $ 119 $ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ + 3 $ 按 归约 $ + $ 按 + 归约 $ $ 按 归约 120
$ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ + 3 $ 按 归约 $ + $ 按 + 归约 $ $ 按 归约 $ $ 121 $ 按 归约 $ $ $ 2 $ 按 归约 $ $ $ + 3 $ 按 归约 $ + $ 按 + 归约 $ $ 按 归约 $ $ 接受 122 3.4.4 移进 归约分析的冲突 1 移进 归约冲突 ( shift/reduce conflict) 例 stmt if expr then stmt if expr then stmt else stmt other 如果移进 归约分析器处于格局 (configurtion) 栈输入 if expr then stmt else $ 123 2 归约 归约冲突 (reduce/reduce conflict) stmt (prmeter_list) expr = expr prmeter_list prmeter_list, prmeter prmeter prmeter expr (expr_list) ( ) 是数组元素的引用 expr_list expr_list, expr expr 由 A(I, J) 开始的语句 栈 ( 归约成 expr 还是 prmeter? 输入, ) 124 2 归约 归约冲突 stmt (prmeter_list) expr = expr prmeter_list prmeter_list, prmeter prmeter prmeter expr (expr_list) expr_list expr_list, expr expr 本节介绍 LR(k) 分析技术 L-scnning from left to right; R- rightmost derivtion in reverse 特点 适用于一大类上下文无关文法 效率高 由 A(I, J) 开始的语句 ( 词法分析查符号表, 区分第一个 ) 栈输入 proc (, ) 需要修改上面的文法 125 主要介绍构造 LR 分析表的三种技术 简单的 LR 方法 ( 简称 SLR) 规范的 LR 方法 向前看的 LR 方法 ( 简称 LALR) 126
3.5.1 LR 分析算法 输入 1 i n $ 3.5.1 LR 分析算法 输入 1 i n $ 栈 s m X m s m-1 X m-1 s 0 LR 分析程序 ction goto LR 分析器的模型 输出 移进 - 归约分析器移进符号 LR 分析器移进状态和其相关的文法符号 (s0 除外 127) 栈 s m X m s m-1 X m-1 s 0 LR 分析程序 ction goto LR 分析器的模型 输出 s j 总结了栈中该状态以下的信息 ction[s m, i ] 移进 归约 接受 出错 goto[s m-r, A]=s j 移进 A 和 s j ( 归约后使用 128) 例 + T T si 移进当前输入符号和状态 i P69 T T F T rj 按第 j 个产生式进行归约 F ( ) F cc 接受 状态 动 作 转 移 + ( ) $ T F 0 s5 s4 1 2 3 1 s6 cc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 129 4 s5 s4 8 2 3 栈输入动作 0 + $ 130 栈输入动作 0 + 0 + 0 5 + $ 131 132
0 + 0 5 + $ 按 F 归约 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 133 134 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 + 0 5 + $ 按 F 归约 0 F 3 + $ 按 T F 归约 0 T 2 + $ 135 136 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 + $ 137 138
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 + $ 139 140 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 + $ 141 142 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 归约 143 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 归约 144
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 1 $ 145 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 1 $ 接受 146 3.5.2 LR 文法和 LR 分析方法的特点 1 概念活前缀 (vile prefix) 右句型的前缀, 该前缀不超过最右句柄的右端 S * rm A w rm w 的任何前缀 ( 包括 和 本身 ) 都是活前缀 w 仅包含终结符 3.5.2 LR 文法和 LR 分析方法的特点 1 概念活前缀 (vile prefix) 右句型的前缀, 该前缀不超过最右句柄的右端 2 定义 LR 文法 (LR grmmr) 我们能为之构造出所有条目都唯一的 LR 分析表 147 148 3 LR 分析方法的特点 栈中的文法符号总是形成一个活前缀 149 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 1 $ 接受 150
3 LR 分析方法的特点 栈中的文法符号总是形成一个活前缀 分析表的转移函数本质上是识别活前缀的 DFA 151 例 + T T 下表绿色部分构成 T T F T 识别活前缀 DFA 的 F ( ) F 状态转换表 状态 动作转移 + ( ) $ T F 0 s5 s4 1 2 3 1 s6 cc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 152 3 3 LR 分析方法的特点 栈中的文法符号总是形成一个活前缀 分析表的转移函数本质上是识别活前缀的 DFA 栈顶的状态符号包含了确定句柄所需要的一切信息 153 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 1 $ 接受 154 3 LR 分析方法的特点 栈中的文法符号总是形成一个活前缀 分析表的转移函数本质上是识别活前缀的 DFA 栈顶的状态符号包含了确定句柄所需要的一切信息 是已知的最一般的无回溯的移进 归约方法 能分析的文法类是预测分析法能分析的文法类的真超集 能及时发现语法错误 4 LR 分析方法和 LL 分析方法的比较 LR(1) 方法 LL(1) 方法 建立分析树的方式 自下而上 自上而下 手工构造分析表的工作量太大 155 156
4 LR 分析方法和 LL 分析方法的比较 LR(1) 方法 LL(1) 方法 建立分析树的方式 自下而上 自上而下 4 LR 分析方法和 LL 分析方法的比较 在下面的推导中, 最后一步用的是 A l 归约还是推导规范归约最左推导 S rm rm A w rm l w LL(1) 决定用该 157 产生式的位置 158 4 LR 分析方法和 LL 分析方法的比较 4 LR 分析方法和 LL 分析方法的比较 在下面的推导中, 最后一步用的是 A l LR(1) 方法 LL(1) 方法 LR(1) 决定用该产生式的位置 S rm rm A w rm l w LL(1) 决定用该 产生式的位置 159 建立分析树的方式 自下而上 自上而下 归约还是推导 规范归约 最左推导 决定使用产生式的时机 看见产生式右部推出的整个终结符串后, 才确定用哪个产生式进行归约 看见产生式右部推出的第一个终结符后, 便要确定用哪个产生式推导 160 4 LR 分析方法和 LL 分析方法的比较 4 LR 分析方法和 LL 分析方法的比较 LR(1) 方法 LL(1) 方法 LR(1) 方法 LL(1) 方法 对文法的显式限制 对文法没有限制无左递归 无公共左因子 对文法的显式限制 对文法没有限制无左递归 无公共左因子 分析表比较 状态 文法符号 分析表大 非终结符 终结符分析表小 161 162
4 LR 分析方法和 LL 分析方法的比较 4 LR 分析方法和 LL 分析方法的比较 LR(1) 方法 LL(1) 方法 LR(1) 方法 LL(1) 方法 对文法的显式限制 分析表比较 对文法没有限制无左递归 无公共左因子状态 文法符号非终结符 终结符分析表大分析表小 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 分析栈比较 状态栈, 通常状态比文法符号包含更多信息 文法符号栈 163 164 4 LR 分析方法和 LL 分析方法的比较 LR(1) 方法 LL(1) 方法 3.5.3 构造 SLR (simple LR) 分析表 术语 LR(0) 项目 ( 简称项目, item) 在右部的某个地方加点的产生式 确定句柄 语法错误 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 决不会将出错点后的符号移入分析栈 无句柄概念 和 LR 一样, 决不会读过出错点而不报错 165 166 3.5.3 构造 SLR (simple LR) 分析表 术语 LR(0) 项目 ( 简称项目, item) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 3.5.3 构造 SLR (simple LR) 分析表 术语 LR(0) 项目 ( 简称项目, item) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 expr expr + term 167 168
3.5.3 构造 SLR (simple LR) 分析表 术语 LR(0) 项目 ( 简称项目, item) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 expr expr + term term * fctor 3.5.3 构造 SLR (simple LR) 分析表 术语 LR(0) 项目 ( 简称项目, item) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 expr expr + term term * fctor 169 170 3.5.3 构造 SLR (simple LR) 分析表 术语 LR(0) 项目 ( 简称项目, item) 在右部的某个地方加点的产生式 加点的目的是用来表示分析过程中的状态 例 A XYZ 对应有四个项目 A XYZ A X YZ A XY Z A XYZ 例 A 只有一个项目和它对应 A 171 构造 SLR 分析表的两大步骤 1 从文法构造识别活前缀的 DFA 2 从上述 DFA 构造分析表 172 1 从文法构造识别活前缀的 DFA 1) 拓广文法 (ugmented grmmr) + T T T T F F F ( ) 1 从文法构造识别活前缀的 DFA 1) 拓广文法 + T T T T F F F ( ) 指示分析器何时停止分析并宣布接受输入 173 174
1 从文法构造识别活前缀的 DFA 2) 构造 LR(0) 项目集规范族 (cnonicl LR(0) collection) 1 从文法构造识别活前缀的 DFA 2) 构造 LR(0) 项目集规范族 求项目集的闭包 closure(i) P73 + T T 175 176 1 从文法构造识别活前缀的 DFA 2) 构造 LR(0) 项目集规范族 求项目集的闭包 closure(i) P73 + T T T T F T F 1 从文法构造识别活前缀的 DFA 2) 构造 LR(0) 项目集规范族 求项目集的闭包 closure(i) P73 + T T T T F T F F () F 177 178 1 从文法构造识别活前缀的 DFA 2) 构造 LR(0) 项目集规范族 ( 核心项目 kernel item) + T T ( 非核心项目 nonkernel item, T T F 可通过对核心项目求闭包 T F 而获得, 为节省存储项目集 F () 所需的存储空间, 可去之 ) F 核心项目 初始项目 ( ), 点不在最左端的项目 179 1 从文法构造识别活前缀的 DFA 2) 构造 LR(0) 项目集规范族 I 1 + T +T T T T F T F F () F 180
1 从文法构造识别活前缀的 DFA 2) 构造 LR(0) 项目集规范族 I 1 + T +T T T T F I 1 = goto (, ) T F F () F 1 从文法构造识别活前缀的 DFA 2) 构造 LR(0) 项目集规范族 I 1 + T +T T T T F I 2 T F T T F () T T F F 181 182 1 从文法构造识别活前缀的 DFA 2) 构造 LR(0) 项目集规范族 I 1 + T +T T T T F I 2 T F T T F () T T F F F I 3 T F 183 I 4 ( F ( ) + T T T T F T F F () F 184 I 4 ( F ( ) + T + T T T T T F T T F T F T F F () F () F F I 4 ( F ( ) + T + T T T T T F T T F T F T F F () F () F F I 5 F 185 186
I 1 I 1 I 1 + T T I 2 T I 2 F I 3 F I 3 ( I 4 ( I 4 187 I 5 I 5 188 I 1 I 1 + T I 1 I 1 I 2 + T T T T F T F ( I 2 I 3 I 4 + I 6 + T T T F T F F () F T F ( I 2 I 3 I 4 + I 6 + T T T F T F F () F I 5 189 I 5 190 I 1 I 1 I 2 + T T T T F I 1 I 3 T F 无状态转换 T F ( I 2 I 3 I 4 I 6 + I 7 + T T T F T T F F () T F F F () F T F ( I 2 I 3 I 4 I 5 191 I 5 192
T F ( I 1 I 2 I 3 I 4 I 4 F ( ) + T T T T F T F F ( ) F T F ( I 1 I 2 I 3 I 4 I 4 I 8 F ( ) F ( ) + T + T T T T F T F F ( ) F I 5 193 I 5 194 T F ( I 1 I 2 I 3 I 4 I 4 I 8 F ( ) F ( ) + T + T T T T F I 2 T F T T F ( ) T T F F T F ( I 1 I 2 I 3 I 4 I 4 I 8 F ( ) F ( ) + T + T T T T F I 2 T F T T F ( ) T T F F F I 3 T F I 5 195 I 5 196 T F ( I 1 I 2 I 3 I 4 I 5 I 4 I 8 F ( ) F ( ) + T + T T T T F I 2 T F T T F ( ) T T F F F I 3 T F ( I 4 F ( ) 197 T F ( I 1 I 2 I 3 I 4 I 5 I 4 I 8 F ( ) F ( ) + T + T T T T F I 2 T F T T F ( ) T T F F F I 3 T F ( I 4 I 5 F ( ) F 198
I 1 I 5 F 无状态转换 + I 1 I 6 T I 2 T * I 2 I 7 F I 3 F I 3 ( I 4 ( I 4 I 8 I 5 199 ( I 5 T F 指向 I 2 指向 I 3 200 + I 5 I 1 T I 6 I 9 F ( * 指向 I 7 指向 I 3 把所有状态都指向 I 4 作为接受状态 指向 I 5 这是一个 DFA T * F I 2 I 7 I 10 F ( I 指向 I 4 3 指向 I ( ) 5 +T I 4 I 8 I 11 + +T F ( T 指向 I 6 指向 I +T 2 F 指向 I 3 +T F 201 +T F 的所有前缀都可接受 + T T T T F T F F () F 也可以构造一个识别活前缀的 NFA N 202 也可以构造一个识别活前缀的 NFA N 每个项目一个状态 + T T T T F T F F () F 203 也可以构造一个识别活前缀的 NFA N 每个项目一个状态 + T T + T T T T F T F F () F 204
也可以构造一个识别活前缀的 NFA N 每个项目一个状态 + T T + T T T T F T F F () F 205 也可以构造一个识别活前缀的 NFA N 每个项目一个状态 + T T + T T T T F T F T T F T F F () F 206 也可以构造一个识别活前缀的 NFA N 每个项目一个状态 + T T + T T T T F T F T T F T F F () F 207 也可以构造一个识别活前缀的 NFA N 每个项目一个状态 + T T + T T T T F T F T T F T F F () F F () F 208 也可以构造一个识别活前缀的 NFA N 每个项目一个状态 + T T + T T T T F T F T T F T F F () F F () F 209 从文法构造的识别活前缀的 DFA 的一些特点 概念 有效项目 (vl item) 如果 S * rm Aw rm 1 2 w, 那么就说项目 A 1 2 对活前缀 1 是有效的 (1) 一个项目可能对好几个活前缀都是有效的 +T 对 和 ( 这两个活前缀都有效 +T (, 1 都为空 ) () (+T) ( = (, 1 为空 ) 该 DFA 读过 和 ( 后到达不同的状态, 那么项目 +T 就出现在对应的不同项目集中 210
从文法构造的识别活前缀的 DFA 的一些特点 概念 有效项目 (vl item) 如果 S * rm Aw rm 1 2 w, 那么就说项目 A 1 2 对活前缀 1 是有效的 (1) 一个项目可能对好几个活前缀都是有效的从项目 A 1 2 对活前缀 1 有效这个事实可以知道 如果 2, 应该移进 如果 2 =, 应该用产生式 A 1 归约 211 从文法构造的识别活前缀的 DFA 的一些特点 概念 有效项目如果 S * rm Aw rm 1 2 w, 那么就说项目 A 1 2 对活前缀 1 是有效的 (1) 一个项目可能对好几个活前缀都是有效的 (2) 一个活前缀可能有多个有效项目一个活前缀 的有效项目集是从这个 DFA 的初态出发, 沿着标记为 的路径到达的那个项目集 ( 状态 ) 212 例串 + T 是活前缀, 读完它后,DFA 处于状态 I 7 I 7 T T F, F ( ), F +T +T +T +T F +T F +T F +T +T ( ) +T +T F 构造 SLR 分析表的两大步骤 1 从文法构造识别活前缀的 DFA 2 从上述 DFA 构造分析表 213 214 2 从 DFA 构造 SLR 分析表 状态 i 从 I i 构造, 它的 ction 函数如下确定 如果 [A ] 在 I i 中, 并且 goto(i i, ) = I j, 那么置 ction[i, ] 为 sj 如果 [A ] 在 I i 中, 那么对 FOLLOW(A) 中的所有, 置 ction[i, ] 为 rj,j 是产生式 A 的编号 如果 [S S ] 在 I i 中, 那么置 ction[ i, $ ] 为接受 cc 如果出现动作冲突, 那么该文法就不是 SLR(1) 的 215 2 从 DFA 构造 SLR 分析表 状态 i 从 I i 构造, 它的 ction 函数如下确定 使用下面规则构造状态 i 的 goto 函数 对所有的非终结符 A, 如果 goto(i i, A) = I j, 那么 goto[i, A] = j 216
2 从 DFA 构造 SLR 分析表 状态 i 从 I i 构造, 它的 ction 函数如下确定 使用下面规则构造状态 i 的 goto 函数 不能由上面两步定义的条目都置为 error 分析器的初始状态是包含 [S S] 的项目集对应的状态 例 I 2 T T T F 因为 FOLLOW() = {$, +, )}, 所以 ction[2, $]=ction[2, +]=ction[2, )]=r2 ction[2, ] = s7 217 218 例 SLR(1) 文法的描述能力有限 S V = S V V V S S S V = S V V V = 是 的一个后继符 S $ V = $ = $ V I 2 S V = V 第一项目使得 ction[2, = ] = s6 第二项目使得 ction[2, = ] 为按 V 归约, 因为 = 是 的一个后继符 219 例 SLR(1) 文法的描述能力有限 S V = S V V V S S S V = S V V V 在所关注场合 的后继是 $ S $ V = $ = $ S $ $ V $ V I 2 S V = V 第一项目使得 ction[2, = ] = s6 第二项目使得 ction[2, = ] 为按 V 归约, 因为 = 是 的一个后继符 220 3.5.4 构造规范的 LR 分析表 LR(1) 项目 重新定义项目, 让它带上搜索符 (lookhed), 成为 [A, ] LR(1) 项目 [A, ] 对活前缀 有效 如果存在着推导 S * rm Aw rm w, 其中 = ; 是 w 的第一个符号, 或者 w 是 且 是 $ 221 例 S 从最右推导 S * rm rm 看出 [, ] 对活前缀 = 是有效的 对于项目 [A, ], 当 为空时, 是根据搜索符 来填表 ( 归约项目 ), 而不是根据 A 的后继符来填表 222
S S, $ S, $, /, / S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, /, /, / I 3 223,/ I 4 224 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, /, /, / I 3, / I 4 S, $ I 5, $, $, $ I 6, $ I 9, $ I 7, / I 8 225 构造规范的 LR 分析表 (1) 基于 LR(1) 项目来构造识别 G 活前缀的 DFA (2) 从 I i 构造分析器的状态 i, 状态 i 的 ction 函数如下确定 如果 [A, ] 在 I i 中, 且 goto(i i, ) = I j, 那么置 ction[i, ] 为 sj 如果 [A,] 在 I i 中, 且 A S, 那么置 ction[i, ] 为 rj 如果 [S S, $] 在 I i 中, 那么置 ction[i, $] = cc 如果用上面规则构造出现了冲突, 那么文法就不是 LR(1) 的 226 构造规范的 LR 分析表 (1) 基于 LR(1) 项目来构造识别 G 活前缀的 DFA (2) 从 I i 构造分析器的状态 i, 状态 i 的 ction 函数如下确定 (3) 状态 i 的 goto 函数如下确定 如果 goto(i i, A) = I j, 那么 goto[i, A] = j 构造规范的 LR 分析表 (1) 基于 LR(1) 项目来构造识别 G 活前缀的 DFA (2) 从 I i 构造分析器的状态 i, 状态 i 的 ction 函数如下确定 (3) 状态 i 的 goto 函数如下确定 (4) 用上面规则未能定义的所有条目都置为 error 227 228
构造规范的 LR 分析表 (1) 基于 LR(1) 项目来构造识别 G 活前缀的 DFA (2) 从 I i 构造分析器的状态 i, 状态 i 的 ction 函数如下确定 (3) 状态 i 的 goto 函数如下确定 (4) 用上面规则未能定义的所有条目都置为 error (5) 分析器的初始状态是包含 [S S, $] 的项目集对应的状态 229 先前基于 SLR(1) 有移进 - 归约冲突的例子, 在基于规范 LR(1) 时无冲突 S V = S V V V S S, $ S V =, $ S, $ V, =/$ V, =/$ V, $ V I 2 S V =, $ V, $ 230 3.5.5 构造 LALR 分析表 研究 LALR 的原因规范 LR 分析表的状态数偏多 LALR 特点 LALR 和 SLR 的分析表有同样多的状态, 比规范 LR 分析表要小得多 LALR 的能力介于 SLR 和规范 LR 之间 LALR 的能力在很多情况下已经够用 LALR 分析表构造方法 通过合并规范 LR(1) 项目集来得到 231 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2 S, $ I 5, $, $, $ I 6, /, /, $ I 9, / I 3, $ I 7, / I 4, / I 8 232 I 4 和 I 7 仅搜索符不一样 S S, $ S, $, /, / I 4 和 I 7 合并 S S S, $ I 1 S, $, $, $ I 2, /, /, / I 3, / I 4 S, $ I 5, $, $, $ I 6, $ I 9, $ I 7, / I 8 233 S S, $ S, $, /, / S 输入为 $ S S, $ I 1 S, $, $, $ I 2, /, /, / I 3, / I 4 S, $ I 5, $, $, $ I 6, $ I 9, $ I 7, / I 8 234
S S, $ S, $, /, / 输入为 $ S S S, $ I 1 S, $, $, $ I 2, /, /, / I 3, / I 4 S, $ I 5, $, $, $ I 6, $ I 9, $ I 7, / I 8 235 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2 S, $ I 5, $, $, $ I 6, /, /, $ I 9, / I 3, $ I 7, / I 4, / I 8 236 有三组同心集, 都合并 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, //$, //$, //$ I 36, //$ I 47 S, $ I 5, //$ I 89 237 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, //$, //$, //$ I 36, //$ I 47 S, $ I 5 栈输入 0 $, //$ I 89 238 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, //$, //$, //$ I 36, //$ I 47 S, $ I 5 栈 036 输入 $, //$ I 89 239 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, //$, //$, //$ I 36, //$ I 47 S, $ I 5 栈输入 03636 $, //$ I 89 240
S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, //$, //$, //$ I 36, //$ I 47 S, $ I 5 栈输入 0363647 $, //$ I 89 241 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, //$, //$, //$ I 36, //$ I 47 S, $ I 5 栈输入 0363689 $, //$ I 89 242 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, //$, //$, //$ I 36, //$ I 47 S, $ I 5 栈输入 03689 $, //$ I 89 243 S S, $ S, $, /, / S S S, $ I 1 S, $, $, $ I 2, //$, //$, //$ I 36, //$ I 47 S, $ I 5 栈输入 02 $ 报错, //$ I 89 244 1 合并同心项目集可能会引起冲突 同心的 LR(1) 项目集 略去搜索符后它们是相同的集合 1 合并同心项目集可能会引起冲突 同心集的合并不会引起新的移进 归约冲突 项目集 1 项目集 2 [A, ] [, ] 若合并后有冲突 245 246
1 合并同心项目集可能会引起冲突 同心集的合并不会引起新的移进 归约冲突 项目集 1 项目集 2 [A, ] [, ] [, c] [A, d] 则合并前就有冲突 247 1 合并同心项目集可能会引起冲突 同心集的合并不会引起新的移进 归约冲突 同心集的合并有可能产生新的归约 归约冲突 S S S Ad d e Ae A c c 对 c 有效的项目集 A c, d c, e 合并同心集后 A c, d/e c, d/e 对 c 有效的项目集 A c, e c, d 该文法是 LR(1) 的, 但不是 LALR(1) 的 248 2 构造 LALR(1) 分析表 (1) 构造 LR(1) 项目集规范族 C = {, I 1,, I n } (2) 寻找 LR(1) 项目集规范族中同心的项目集, 用它们的并集代替它们 (3) 按构造规范 LR(1) 分析表的方式构造分析表 下面文法是 LALR(1) 的, 因无同心集可合并 但不是 SLR(1) 的 S V = S V V V S S, $ S V =, $ S, $ V, =/$ V, =/$ V, $ V I 2 S V =, $ V, $ 249 250 3.5.6 非 LR 的上下文无关结构若自左向右扫描的移进 归约分析器能及时识别出现在栈顶的句柄, 那么相应的文法就是 LR 的 语言 L = {ww R w ( )*} 的文法 S S S 不是 LR 的 例为语言 L = { m n n > m 0 } 写三个文法, 它们分别是 LR(1) 的 二义的和非二义且非 LR(1) 的 LR(1) 文法 S A A A 语言 L = {wcw R w ( )*} 的文法 S S S c 是 LR 的 c 251 252
例为语言 L = { m n n > m 0 } 写三个文法, 它们分别是 LR(1) 的 二义的和非二义且非 LR(1) 的 LR(1) 文法 S A A A 非二义且非 LR(1) 的文法 S S 例为语言 L = { m n n > m 0 } 写三个文法, 它们分别是 LR(1) 的 二义的和非二义且非 LR(1) 的 LR(1) 文法 S A A A 非二义且非 LR(1) 的文法 S S 二义的文法 S S S 253 254 3.6 二义文法的应用 二义文法的特点 二义文法决不是 LR 文法 简洁 自然 例二义文法 + () 非二义的文法 + T T T T F F F () 该文法有单个非终结符为右部的产生式 255 3.6 二义文法的应用 二义文法的特点 二义文法决不是 LR 文法 简洁 自然 可以用文法以外的信息来消除二义 语法分析的效率高 ( 基于消除二义后得到的分析表 ) 256 3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例二义文法 + () 规定 优先级高于 +, 两者都是左结合 3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例二义文法 + () 规定 优先级高于 +, 两者都是左结合 LR(0) 项目集 I 7 + + 257 258
3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例二义文法 + () 规定 优先级高于 +, 两者都是左结合 3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例二义文法 + () 规定 优先级高于 +, 两者都是左结合 LR(0) 项目集 I 7 + + + + 面临 +, 归约 LR(0) 项目集 I 7 + + + + + 面临 +, 归约 面临, 移进 259 260 3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例二义文法 + () 规定 优先级高于 +, 两者都是左结合 3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例二义文法 + () 规定 优先级高于 +, 两者都是左结合 LR(0) 项目集 I 7 + + + + + 面临 +, 归约 面临, 移进 面临 ) 和 $, 归约 261 LR(0) 项目集 I 8 + 262 3.6 二义文法的应用 3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例二义文法 + () 规定 优先级高于 +, 两者都是左结合 3.6.1 使用文法以外信息来解决分析动作冲突 例二义文法 + () 规定 优先级高于 +, 两者都是左结合 LR(0) 项目集 I 8 + + 面临 +, 归约 LR(0) 项目集 I 8 + + 面临 +, 归约 面临, 归约 263 264
3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例二义文法 + () 规定 优先级高于 +, 两者都是左结合 LR(0) 项目集 I 8 + + 面临 +, 归约 面临, 归约 面临 ) 和 $, 归约 265 3.6 二义文法的应用 3.6.2 特殊情况产生式引起的二义性 su sup su sup {} c 266 3.6 二义文法的应用 3.6.2 特殊情况产生式引起的二义性 3.6 二义文法的应用 3.6.2 特殊情况产生式引起的二义性 su sup su sup {} c 从定义形式语言的角度说, 第一个产生式是多余的 su sup su sup {} c 联系到语义处理, 第一个产生式是必要的 267 268 3.6 二义文法的应用 3.6.2 特殊情况产生式引起的二义性 3.6 二义文法的应用 3.6.2 特殊情况产生式引起的二义性 su sup su sup {} c 对 su i sup 2, 需要下面第一种输出 2 i 2 i i 2 269 su sup I 11 su su sup sup sup {} c 按前面一个产生式归约 270
3.6 二义文法的应用 3.6.3 LR 分析的错误恢复 3.6 二义文法的应用 2 紧急方式错误恢复 1 LR 分析器在什么情况下发现错误 访问动作表时若遇到出错条目 访问转移表时它决不会遇到出错条目 决不会把不正确的后继移进栈 规范的 LR 分析器甚至在报告错误之前决不做任何无效归约 271 栈. s... A.. 发现错误 s C A A A s 1 C A A 272 3.6 二义文法的应用 3.6 二义文法的应用 2 紧急方式错误恢复 (1) 退栈, 直至出现状态 s, 它有预先确定的 A 的转移 2 紧急方式错误恢复 (1) 退栈, 直至出现状态 s, 它有预先确定的 A 的转移 (2) 抛弃若干输入符号, 直至找到, 它是 A 的合法后继 栈 ṣ... A.. 发现错误 s C A A A s 1 C A A 273 栈 ṣ... A.. s C A A A s 1 C A A 274 3.6 二义文法的应用 3.7 分析器的生成器 2 紧急方式错误恢复 (1) 退栈, 直至出现状态 s, 它有预先确定的 A 的转移 (2) 抛弃若干输入符号, 直至找到, 它是 A 的合法后继 (3) 再把 A 和状态 goto[s, A] 压进栈, 恢复正常分析 栈 s 1 s... A.. s C A A A s 1 C A A 275 3.7.1 分析器的生成器 Ycc Ycc 源程序 trnslte.y y.t.c 输入 Ycc 编译器 C 编译器.out y.t.c.out 输出 276
3.7 分析器的生成器 3.7.2 用 Ycc 处理二义文法 例简单计算器 输入一个表达式并回车, 显示计算结果 也可以输入一个空白行 3.7 分析器的生成器 %{ # include <ctype.h> # include <stdio.h > # define YYSTYP doule / 将栈定义为 doule 类型 / %} %token NUMR %left + %left / %right UMINUS %% 277 278 3.7 分析器的生成器 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 UMINUS {$$ = $2; } NUMR ; %% 279 3.7 分析器的生成器 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 UMINUS {$$ = $2; } NUMR ; %% -5+10 看成是 -(5+10), 还是 (-5)+10? 取后者 280 3.7 分析器的生成器 yylex ( ) { int c; while ( ( c = getchr ( ) ) == ); if ( ( c ==. ) (isdigit (c) ) ) { ungetc (c, stdin); scnf ( % lf, &yylvl); return NUMR; } return c; } 为了 C 编译器能准确报告 yylex 函数中错误的位置, 需要在生成的程序 y.t.c 中使用编译命令 #line 281 3.7 分析器的生成器 3.7.3 Ycc 的错误恢复 编译器设计者的工作 决定哪些 主要的 非终结符将有错误恢复与它们相关联 为各主要非终结符 A 加入形式为 A error 的错误产生式, 其中 是文法符号串 为这样的产生式配上语义动作 Ycc 把错误产生式当作普通产生式处理 282
3.7 分析器的生成器 遇到语法错误时 3.7 分析器的生成器 遇到语法错误时 从栈中弹出状态, 直到发现栈顶状态的项目集包含形为 A error 的项目为止 栈. s. A.. 发现错误 s C 1 A 2 A error error A s 1 C 1 A 2 s 2 A error 283 栈 ṣ. A.. 发现错误 s C 1 A 2 A error error A s 1 C 1 A 2 s 2 A error 284 3.7 分析器的生成器 遇到语法错误时 从栈中弹出状态, 直到发现栈顶状态的项目集包含形为 A error 的项目为止 把虚构的终结符 error 移进 栈 3.7 分析器的生成器 遇到语法错误时 从栈中弹出状态, 直到发现栈顶状态的项目集包含形为 A error 的项目为止 把虚构的终结符 error 移进 栈 忽略若干输入符号, 直至找到, 把 移进栈 栈 s 2 s. A.. 发现错误 s C 1 A 2 A error error A s 1 C 1 A 2 s 2 A error 285 栈 s 2 s. A.. s C 1 A 2 A error error A s 1 C 1 A 2 s 2 A error 286 3.7 分析器的生成器 遇到语法错误时 从栈中弹出状态, 直到发现栈顶状态的项目集包含形为 A error 的项目为止 把虚构的终结符 error 移进 栈 忽略若干输入符号, 直至找到, 把 移进栈 把 error 归约为 A, 恢复正常分析 s A 栈 C 1 A 2 A error s 1 s. A.. error s 1 C 1 A 2 s 2 A error 287 3.7 分析器的生成器 增加错误恢复的简单计算器 lines lines expr \n {printf ( %g \n, $2 ) } lines \n / / error \n {yyerror ( 重新输入上一行 ); yyerrok;} ; 288
本章要点 文法和语言的基本知识 自上而下的分析方法 预测分析, 非递归的预测分析,LL(1) 文法 自下而上的分析方法 SLR(1) 方法, 规范 LR(1) 方法和 LALR(1) 方法 LR 方法如何用于二义文法 语法分析的错误恢复方法 289 例题 1 下面的二义文法描述命题演算公式的语法, 为它写一个等价的非二义文法 S S nd S S or S not S p q (S) 非二义文法的产生式如下 or T T T T nd F F F not F ( ) p q 290 例题 1 下面的二义文法描述命题演算公式的语法, 为它写一个等价的非二义文法 S S nd S S or S not S p q (S) 非二义文法的产生式如下 or T T T T nd F F F not ( ) p q? not p nd q 有两种不同的最左推导 291 例题 1 下面的二义文法描述命题演算公式的语法, 为它写一个等价的非二义文法 S S nd S S or S not S p q (S) 非二义文法的产生式如下 or T T not p nd q T T nd F F not p nd q F not ( ) p q? not p nd q 有两种不同的最左推导 292 例题 2 设计一个文法 字母表 {, } 上 和 的个数相等的所有串的集合 二义文法 S S S S S S S S S 例题 2 设计一个文法 字母表 {, } 上 和 的个数相等的所有串的集合 二义文法 S S S S S 二义文法 S A A S A A S 293 294
例题 2 例题 3 设计一个文法 字母表 {, } 上 和 的个数相等的所有串的集合 二义文法 S S S S S 二义文法 S A A S A A S 非二义文法 S S A S A A A 295 S 试说明下面文法不是 LR(1) 的 L M L M L M M M L L L 句子 的分析树 296 例题 4 例题 5 下面的文法不是 LR(1) 的, 对它略做修改, 使之成为一个等价的 SLR(1) 文法 progrm egin declist ; sttement end declist d ; declist d sttement s ; sttement s 该文法产生的句子的形式是 egin d ; d ; ; d ; s ; s ; ; s end 修改后的文法如下 progrm egin declist sttement end declist d ; declist d ; sttement s ; sttement s 297 一个 C 语言的文件如下, 第四行的 if 误写成 fi long gcd(p,q) long p,q; { fi (p%q == 0) return q; else return gcd(q, p%q); } 基于 LALR(1) 方法的一个编译器的报错情况如下 prse error efore return ( line 5). 298 是否违反了 LR 分析的活前缀性质?