编译原理与技术 第3章 语法分析 14学时

内容提要 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个记号 源程序 分析树 前端的 3 语法分析 内容提要 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个记号 源程序 分析树 前端的 其余部分 语 法 中间表示 符号表

编译原理与技术 第3章 语法分析 3.1 上下文无关文法 0.5学时

正规式能定义一些简单的语言，能表示给定结构的固定次数 的重复或者没有指定次数的重复 例：a (ba)5, a (ba) 3.1 上下文无关文法 3.1.1 上下文无关文法的定义 正规式能定义一些简单的语言，能表示给定结构的固定次数 的重复或者没有指定次数的重复 例：a (ba)5, a (ba) 正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw | w是a和b的串}

例 ( {id, +, , -, (, )}, {expr, op}, expr, P ) 3.1 上下文无关文法 上下文无关文法是四元组（VT , VN , S, P） VT : 终结符集合 VN : 非终结符集合 S : 开始符号，非终结符中的一个 P : 产生式集合， 产生式形式 : A  α 以下简称“文法” 例 ( {id, +, , -, (, )}, {expr, op}, expr, P ) expr  expr op expr expr  (expr) expr  - expr expr  id op  + op  

符号的约定 终结符 非终结符 其它 3.1 上下文无关文法 字母表前面的小写字母，如a, b, c, … 词法分析中约定的记号，如id, num, if, while, … 数字0, 1, 2, … , 9 标点符号，如逗号，句号，… 运算符号，如+, -, , <, >, =, … 非终结符 字母表前面的大写字母，如A, B, C, … 字母S，通常代表开始符号 小写字母组成的名字，如expr, op, stmt, … 其它 字母表后面的大写字母，如X, Y, Z, 代表文法符号，包括非终结符或 终结符 字母表后面的小写字母，如u, v, w, …, z，代表终结符号串 小写希腊字母，如α, β, γ, …，代表文法符号串

expr  expr op expr expr  (expr) expr  - expr expr  id 3.1 上下文无关文法 expr  expr op expr expr  (expr) expr  - expr expr  id op  + op   简化表示 expr  expr op expr | (expr) | - expr | id op  + |  E  E A E | (E ) | -E | id A  + | 

把产生式看成重写规则，把符号串中的非终结符用其产生式右 部的串来代替 3.1 上下文无关文法 3.1.2 推导 把产生式看成重写规则，把符号串中的非终结符用其产生式右 部的串来代替 例：E  E + E | E  E | (E ) | -E | id E  -E  -(E)  -(E + E)  -(id + E)  -(id + id) 概念 上下文无关语言、等价的文法、句型 记号 S  α、 S + w

例如 E  E + E | E  E | (E ) | -E | id 最左推导 3.1 上下文无关文法 例如 E  E + E | E  E | (E ) | -E | id 最左推导 E lm -E lm -(E) lm -(E + E) lm -(id + E) lm -(id + id) 最右推导（规范推导） E rm -E rm -(E) rm -(E + E) rm -(E + id) rm -(id + id)

例如 E  E + E | E  E | (E ) | -E | id 3.1 上下文无关文法 3.1.3 分析树 例如 E  E + E | E  E | (E ) | -E | id E  -E  -(E)  -(E + E)  -(id + E)  -(id + id) E  E ( E ) E + E id id

3.1.4 二义性 E  E  E E  E + E  id  E  E  E +E 3.1 上下文无关文法 3.1.4 二义性 E  E  E E  E + E  id  E  E  E +E  id  E + E  id  E + E  id  id + E  id  id + E  id  id + id  id  id + id 两个不同的最左推导 两棵不同的语法树 E  + id

编译原理与技术 第3章 语法分析 3.2 语言和文法 2学时

文法只能描述编程语言的大部分语法，不能描述语言中 上下文有关的语法特征 3.2 语言和文法 文法的优点 文法给出了精确的，易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改 文法的问题 文法只能描述编程语言的大部分语法，不能描述语言中 上下文有关的语法特征

3.2.1 正规式和上下文无关文法的比较 正规式 (a|b)ab 文法（由正规式构造文法） 开始 a 3.2 语言和文法 3.2.1 正规式和上下文无关文法的比较 正规式 (a|b)ab 文法（由正规式构造文法） A0  aA0 | bA0 | aA1 A1  bA2 A2  ε 1 2 开始 a b

从软件工程角度看，词法分析和语法分析的分离有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分 3.2 语言和文法 3.2.2 分离词法分析器理由 为什么要用正规式定义词法 词法规则非常简单，不必用上下文无关文法 对于词法记号，正规式描述简洁且易于理解 从正规式构造出的词法分析器效率高 从软件工程角度看，词法分析和语法分析的分离有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分

能否把词法分析并入到语法分析中，直接从字符流进行语法 分析 3.2 语言和文法 能否把词法分析并入到语法分析中，直接从字符流进行语法 分析 若把词法分析和语法分析合在一起，则必须将语言的注 解和空白的规则反映在文法中，文法将大大复杂 注解和空白由自己来处理的分析器，比注解和空格已由 词法分析器删除的分析器要复杂得多

G : S  (S) S | ε L(G) = 配对的括号串的集合 按推导步数进行归纳：推出的是配对括号串 归纳基础： S  ε 3.2 语言和文法 3.2.3 验证文法产生的语言 G : S  (S) S | ε L(G) = 配对的括号串的集合 按推导步数进行归纳：推出的是配对括号串 归纳基础： S  ε 归纳假设：少于n步的推导都产生配对的括号串 归纳步骤：n步的最左推导如下： S  (S)S  (x) S  (x) y 按串长进行归纳：配对括号串可由S推出 归纳假设：长度小于2n的都可以从S推导出来 归纳步骤：考虑长度为2n(n ≥ 1)的w = (x) y

id  id  (id+id) + id  id + id 3.2 语言和文法 3.2.4 适当的表达式文法 用一种层次观点看待表达式 id  id  (id+id) + id  id + id 文法 expr  expr + term | term term  term  factor | factor factor  id | (expr)

term  term  factor | factor factor  id | (expr) 3.2 语言和文法 expr  expr + term | term term  term  factor | factor factor  id | (expr) expr id term factor  expr + id factor term  id  id  id 分析树 id + id  id 分析树

| if expr then stmt else stmt | other 3.2 语言和文法 3.2.5 消除二义性 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

matched_stmt  if expr then matched_stmt else matched_stmt | other 3.2 语言和文法 无二义的文法 stmt  matched _stmt | unmatched_stmt matched_stmt  if expr then matched_stmt else matched_stmt | other unmatched_stmt  if expr then stmt | if expr then matched_stmt else unmatched_stmt

stmt  if expr then stmt | matched_stmt 3.2 语言和文法 例题 下面的条件语句文法仍存在二义，请证明 stmt  if expr then stmt | matched_stmt matched_stmt  if expr then matched_stmt else stmt | other if  then　　　　　　　　　　　　　else  if  then  else  if  then 

3.2.6 消除左递归 文法左递归 A + Aα 直接左递归 A  Aα | β 串的特点 βα . . . α 消除直接左递归 3.2 语言和文法 3.2.6 消除左递归 文法左递归 A + Aα 直接左递归 A  Aα | β 串的特点 βα . . . α 消除直接左递归 A  βA' A'  αA' | ε

例题 例 算术表达文法 E  E + T | T ( T + T . . . + T ) 3.2 语言和文法 例题 例 算术表达文法 E  E + T | T ( T + T . . . + T ) T  T  F | F ( F  F . . .  F ) F  ( E ) | id 消除左递归后文法 E  T E' E'  + T E' | ε T  F T' T'   F T' | ε

非直接左递归 S  Aa | b A  Sd | ε 先变换成直接左递归 A  Aad | bd | ε 再消除左递归 3.2 语言和文法 非直接左递归 S  Aa | b A  Sd | ε 先变换成直接左递归 A  Aad | bd | ε 再消除左递归 A  bd A' | A' A'  adA' | ε

3.2 语言和文法 3.2.7 提左因子 有左因子的文法 A  αβ1 | αβ2 提左因子 A  αA' A'  β1 | β2

stmt  if expr then stmt else stmt | if expr then stmt | other 3.2 语言和文法 例题 例 悬空else的文法 stmt  if expr then stmt else stmt | if expr then stmt | other 提左因子 stmt  if expr then stmt optional_else_part optional_else_part  else stmt | ε

3.2.8 非上下文无关的语言构造 L1 = { wcw | w ∈ (a | b)} 3.2 语言和文法 3.2.8 非上下文无关的语言构造 L1 = { wcw | w ∈ (a | b)} 标识符的声明应先于其引用的抽象 L2 = { anbmcndm | n ≥ 0, m ≥ 0} 形参个数和实参个数应该相同的抽象 L3 = { anbncn | n ≥ 0} 早先排版描述的一个现象的抽象 b e g i n：5个字母键，5个回退键，5个下划线键

L1' = { wcwR | w ∈ (a|b)} S  aSa | bSb | c 3.2 语言和文法 L1' = { wcwR | w ∈ (a|b)} S  aSa | bSb | c L2' = { anbmcmdn | n ≥ 1, m ≥ 1} S  aSd | aAd A  bAc | bc L2" = { anbncmdm | n ≥ 1，m ≥ 1} S  AB A  aAb | ab B  cBd | cd

设读完ε, a, aa, …, ak 分别到达状态s0, s1, …, sk 3.2 语言和文法 L3' ={ anbn | n ≥ 1} S  aSb | ab L3' 是不能用正规式描述的语言的一个范例 若存在接受L3' 的DFA，状态数为k个 设读完ε, a, aa, …, ak 分别到达状态s0, s1, …, sk 至少有两个状态相同，例如是 si 和 sj，则 ajbi 属于L3' 标记为aj  i的路径 … si … f s0 标记为ai的路径 标记为bi的路径

0型文法：αβ，α,β∈(VN∪VT), |α|≥1 短语文法 3.2 语言和文法 3.2.9 形式语言鸟瞰 文法 G = (VT , VN , S , P) 0型文法：αβ，α,β∈(VN∪VT), |α|≥1 短语文法 1型文法：|α|≤|β|，但 Sε 可以例外 上下文有关文法 2型文法：Aβ，A∈VN , β∈(VN∪VT) 上下文无关文法 3型文法：AaB 或 Aa，A,B∈VN , a∈VT 正规文法

例 L3＝{ anbncn | n≥1 }的上下文有关文法 S  aSBC S  aBC CB  BC 3.2 语言和文法 例题 例 L3＝{ anbncn | n≥1 }的上下文有关文法 S  aSBC S  aBC CB  BC aB  ab bB  bb bC  bc cC  cc anbncn 的推导过程如下： S  an-1S(BC)n-1 用S  aSBC n-1次 + an(BC)n 用S  aBC 1次 + anBnCn 用CB  BC n(n-1)/2次 + anbBn-1Cn 用aB  ab 1次 + anbnCn 用bB  bb n-1次 + anbncCn-1 用bC  bc 1次 + anbncn 用cC  cc n-1次

编译原理与技术 第3章 语法分析 3.3 自上而下分析 3学时

3.3.1 自上而下分析的一般方法 例 文法 S  aCb C  cd | c 为输入串 acb 建立分析树 S a C b S a C 3.3 自上而下分析 3.3.1 自上而下分析的一般方法 例 文法 S  aCb C  cd | c 为输入串 acb 建立分析树 S a C b S a C b c d S a C b c 复杂的回溯技术 回溯导致语义工作推倒重来 难以报告出错的确切位置 效率低 不能处理左递归

不能处理左递归的例子：算术表达文法 E  E + T | T T  T  F | F F  ( E ) | id E E + T E 3.3 自上而下分析 不能处理左递归的例子：算术表达文法 E  E + T | T T  T  F | F F  ( E ) | id E E + T E + T E + T … … …

FIRST(α) = {a | α  a…, a∈VT} 特别当 α  ε 时，规定 ε ∈ FIRST(α) 3.3 自上而下分析 3.3.2 LL(1)文法 对文法加什么样的限制可以保证没有回溯？ 先定义两个和文法有关的函数 FIRST(α) = {a | α  a…, a∈VT} 　特别当 α  ε 时，规定 ε ∈ FIRST(α) FOLLOW(A) = {a | S  …Aa…，a∈VT} 　如果A是某个句型的最右符号，那么$属于FOLLOW(A)

若B  ε， FIRST(α)  FIRST(A) A  ε ε∈FIRST(A) $∈FOLLOW(S) B  αAβ 3.3 自上而下分析 FIRST 、FOLLOW计算规则： A  aα a∈FIRST(A) A  Bα FIRST(B)  FIRST(A) 若B  ε， FIRST(α)  FIRST(A) A  ε ε∈FIRST(A) $∈FOLLOW(S) B  αAβ FIRST(β)  FOLLOW(A) 若β  ε， FOLLOW(B)  FOLLOW(A)

FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E') = {+, ε} 3.3 自上而下分析 例题 例 E  TE' E'  + TE' | ε T  FT' T'   FT' | ε F  (E) | id FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(E') = {+, ε} FIRST(T') = {, ε} FOLLOW(E) = FOLLOW(E') = { ), $} FOLLOW(T) = FOLLOW (T') = {+, ), $} FOLLOW(F) = {, +, ), $}

任何两个产生式A  α | β 都满足下列条件： FIRST(α) ∩ FIRST(β) = Ø 3.3 自上而下分析 LL(1)文法： 任何两个产生式A  α | β 都满足下列条件： FIRST(α) ∩ FIRST(β) = Ø 若 β  ε，那么FIRST(α) ∩ FOLLOW(A) = Ø 例如，对于下面文法，面临a…时，第2步推导不知用哪个产 生式 S  A B A  a b | ε a ∈ FIRST(ab) ∩ FOLLOW(A) B  a C C  …

1代表在分析过程中执行每一步推导都要向前查看一个输 入符号——当前正在处理的输入符号 3.3 自上而下分析 LL(1)文法 第一个L代表从左向右扫描输入符号串； 第二个L代表产生最左推导； 1代表在分析过程中执行每一步推导都要向前查看一个输 入符号——当前正在处理的输入符号 LL(1)文法有一些明显的性质 没有公共左因子 不是二义的 不含左递归

| array [simple] of type 3.3 自上而下分析 3.3.3 递归下降的预测分析 为每一个非终结符写一个分析过程 这些过程可能是递归的 例 simple  integer | char | num dotdot num type  simple | ↑ id | array [simple] of type

void match (terminal t) { 3.3 自上而下分析 一个辅助过程 void match (terminal t) { if (lookahead == t) lookahead = nextToken( ); else error( ); }

if ( lookahead == integer) match(integer); 3.3 自上而下分析 void 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

| array [simple] of type 3.3 自上而下分析 void type( ) { if ( (lookahead == integer) || (lookahead == char) || (lookahead == num) ) simple( ); else if ( lookahead == '↑' ) { match( '↑' ); match(id);} else if (lookahead == array) { match(array); match( '[' ); simple( ); match( ']' ); match(of ); type( ); } else error( ); type  simple |  id | array [simple] of type

else if (M[X,a]是出错入口) error; else if (M[X,a]=XY1Y2…Yk) { 3.3 自上而下分析 3.3.4 非递归的预测分析 输入 预测分析程序 分析表M 输出 栈 a + b $ X Y Z while(X!=$ ) { if ( X==a) X出栈, 指针推进; else if (X是终结符) error; else if (M[X,a]是出错入口) error; else if (M[X,a]=XY1Y2…Yk) { X出栈; 输出产生式; Yk…Y1入栈; }

分析表的例子 E  TE' T  FT' F  (E) | id E'  +TE' | ε T'  FT' | ε 教材表3.1 3.3 自上而下分析 分析表的例子 E  TE' T  FT' F  (E) | id E'  +TE' | ε T'  FT' | ε 教材表3.1 非终 结符 输 入 符 号 id +  ( ) $ E E  TE E E  +TE E'   T T  FT T T   T  FT T'   F F  id F  (E)

预测分析器接受输入 id  id + id 的前一部分动作 栈 输 入 输 出 3.3 自上而下分析 例题 预测分析器接受输入 id  id + id 的前一部分动作 栈 输 入 输 出 $ E id  id + id$ $ E T id  id + id$ E  TE $ E T F id  id + id$ T  FT $ E T id id  id + id$ F  id $ E T  id + id$ $ E T F   id + id$ T  FT $ E T F id + id$ $ E T id id + id$ F  id $ E T + id$

例题 栈 输 入 输 出 $ E + id$ T   $ E T + + id$ E  +TE $ E T id$ 3.3 自上而下分析 例题 栈 输 入 输 出 $ E + id$ T   $ E T + + id$ E  +TE $ E T id$ $ E T F id$ T  FT $ E T id id$ F  id $ E T $ $ E $ T   $ E  

3.3 自上而下分析 例题 输出构成分析树： E T E' F T' id   +

(1) 对文法的每个产生式 A  α ，执行(2)和(3) (2) 对FIRST(α)的每个终结符a， 把 A  α 加入M[A, a] 3.3 自上而下分析 3.3.5 构造预测分析表 (1) 对文法的每个产生式 A  α ，执行(2)和(3) (2) 对FIRST(α)的每个终结符a， 把 A  α 加入M[A, a] (3) 如果 ε 在FIRST(α)中，对FOLLOW(A)的每个终结符b（包 括$）, 把 A  α 加入M[A, b] (4) M中其它没有定义的条目都是error

FIRST(TE') = FIRST(FT') = { ( , id } FOLLOW(E') = { ), $} 3.3 自上而下分析 分析表的构造 E  TE' T  FT' F  (E) | id E'  +TE' | ε T'  FT' | ε FIRST(TE') = FIRST(FT') = { ( , id } FOLLOW(E') = { ), $} FOLLOW (T') = {+, ), $} 非终 结符 输 入 符 号 id +  ( ) $ E E  TE E E  +TE E'   T T  FT T T   T  FT T'   F F  id F  (E)

stmt  if expr then stmt e_part | other e_part  else stmt |  非终 结符 3.3 自上而下分析 多重定义的条目 stmt  if expr then stmt e_part | other e_part  else stmt |  非终 结符 输 入 符 号 other b else . . . stmt stmt  other e_part e_part else stmt e_part   expr expr  b 消除方法： 修改文法，消除二义性 根据语法约定消去多重定义

词法错误，如标识符、关键字或算符的拼写错 语法错误，如算术表达式的括号不配对 语义错误，如算符作用于不相容的运算对象 3.3 自上而下分析 3.3.6 预测分析的错误恢复 (1) 先对编译器的错误处理做一个概述 词法错误，如标识符、关键字或算符的拼写错 语法错误，如算术表达式的括号不配对 语义错误，如算符作用于不相容的运算对象 逻辑错误，如无穷的递归调用 (2) 分析器对错误处理的基本目标 清楚而准确地报告错误的出现，并尽量少出现伪错误 迅速地从每个错误中恢复过来，以便诊断后面的错误 它不应该使正确程序的处理速度降低太多

栈顶是非终结符A，输入符号是a，但M[A , a]是空白 3.3 自上而下分析 (3) 非递归预测分析在什么场合下发现错误 栈顶是终结符，但和输入符号不匹配 栈顶是非终结符A，输入符号是a，但M[A , a]是空白 输入 预测分析程序 分析表M 输出 栈 a + b $ X Y Z

(4) 非递归预测分析：采用紧急方式的错误恢复 发现错误时，分析器每次抛弃一个输入记号，直到输入记号 属于某个指定的同步记号集合为止 3.3 自上而下分析 (4) 非递归预测分析：采用紧急方式的错误恢复 发现错误时，分析器每次抛弃一个输入记号，直到输入记号 属于某个指定的同步记号集合为止 (5) 同步 词法分析器当前提供的记号流能够构成的语法构造，正是语 法分析器所期望的 不同步的例子 语法分析器期望剩余的前缀构成过程调用语句，而实际剩余的前缀 形成赋值语句

把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 3.3 自上而下分析 (6) 同步记号集合的选择 把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合 例如： if expr then stmt then和分号等记号是expr的同步记号 把高层构造的开始符号加到低层构造的同步记号集合中 例如：a = expr; if … 语句的开始符号作为表达式的同步记号，以免表达式出错又遗漏分 号时忽略 if 语句等一大段程序 把FIRST(A)的终结符加入A的同步记号集合 例如：a = expr; , if … 语句的开始符号作为语句的同步符号，以免多出一个逗号时会把 if 语句忽略了 如果终结符在栈顶而不能匹配，弹出此终结符 如果非终结符可以产生空串，若出错时栈顶是这样的非终结 符，则可以使用推出空串的产生式

例：栈顶为T'，面临id时出错（例如：a20d+5） 非终 结符 输 入 符 号 3.3 自上而下分析 例题 例：栈顶为T'，面临id时出错（例如：a20d+5） 非终 结符 输 入 符 号 id +  ( ) $ E E  TE E E  +TE E'   T T  FT T err T   T  FT T'   F F  id F  (E) err, T T 可以产生空串，报错并用 T。 相当于丢弃了一个输入

编译原理与技术 第3章 语法分析 3.4 自下而上分析 1.5学时

S rm aABe rm aAde rm aAbcde rm abbcde 3.4 自下而上分析 3.4.1 归约 例 S  aABe 输入abbcde A  Abc | b B  d abbcde（读入ab） aAbcde（归约） aAbcde（读入bc） aAde（归约） aAde（读入d） aABe（归约） aABe(读入e) S（归约） S A B A a b b c d e S rm aABe rm aAde rm aAbcde rm abbcde

句型的句柄是和某产生式右部匹配的子串，并且，把它归约 成该产生式左部的非终结符代表了最右推导过程的逆过程的 一步 3.4 自下而上分析 3.4.2 句柄 句型的句柄是和某产生式右部匹配的子串，并且，把它归约 成该产生式左部的非终结符代表了最右推导过程的逆过程的 一步 S  aABe A  Abc | b B  d S rm aABe rm aAde rm aAbcde rm abbcde 句柄的右边仅含终结符 如果文法二义，那么句柄可能不唯一

例 句柄不唯一 E  E + E | E  E | (E ) | id 句子 id1  id2 + id3 3.4 自下而上分析 例 句柄不唯一 E  E + E | E  E | (E ) | id 句子 id1  id2 + id3 在句型 E  E + id3 中，句柄不唯一 E rm E  E rm E  E + E rm E  E + id3 rm E  id2 + id3 rm id1  id2 + id3 E rm E + E rm E + id3 rm E  E + id3 rm E  id2 + id3 rm id1  id2 + id3

先通过例子 id1  id2 +id3 了解移进—归约分析的工作方式 栈 输 入 动 作 3.4 自下而上分析 3.4.3 用栈实现移进—归约分析 先通过例子 id1  id2 +id3 了解移进—归约分析的工作方式 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $id1  id2 + id3$ 按 E  id 归约 $E  id2 + id3$ 移进 $E id2 + id3$ 移进 $Eid2 + id3$ 按 E  id 归约 $EE + id3$ 移进 $EE+ id3$ 移进 $EE+id3 $ 按 E  id 归约 $EE+E $ 按 E  E+E 归约 $EE $ 按 E  EE 归约 $E $ 接受

要想很好地使用移进—归约方式，尚需解决一些问题 如何决策选择移进还是归约 进行归约时，确定右句型中将要归约的子串 3.4 自下而上分析 要想很好地使用移进—归约方式，尚需解决一些问题 如何决策选择移进还是归约 进行归约时，确定右句型中将要归约的子串 进行归约时，如何确定选择哪一个产生式

| if expr then stmt else stmt | other 3.4 自下而上分析 3.4.4 移进—归约分析的冲突 （1）移进—归约冲突 例 stmt  if expr then stmt | if expr then stmt else stmt | other 如果移进—归约分析器处于格局 栈 输入 … if expr then stmt else … $ 解决方法：消除二义性 归约? 移进?

stmt  id (parameter_list) | expr = expr 3.4 自下而上分析 （2）归约—归约冲突 例 stmt  id (parameter_list) | expr = expr parameter_list  parameter_list, parameter | parameter parameter  id expr  id (expr_list) | id expr_list  expr_list, expr | expr 由A(I, J)开始的语句 栈 输入 … id ( id , id )… 解决方法：查符号表，区分第一个id。上下文有关文法 procid 归约成expr还是parameter ? procid

编译原理与技术 第3章 语法分析 3.5 LR分析器 6学时

本节介绍LR(k)分析技术 特点 适用于一大类上下文无关文法 效率高 主要介绍构造LR分析表的三种技术 简单的LR方法（简称SLR） 向前看的LR方法（简称LALR）

3.5.1 LR分析算法 输入 … ai an $ a1 Xm Xm-1 … sm sm-1 s0 LR分析程序 输出 栈 action goto LR分析器的模型

3.5 LR分析器 LR分析程序： 栈顶状态为s0；a指向第一个符号； while(1) { s=栈顶状态 if ( action[s,a] == 移进t) { 把a和t入栈; a取下一个输入符号; } else if ( action[s,a] == 归约 Aβ) { 栈顶退掉2|β|个符号; 把A和goto[s,A]入栈; 输出产生式 Aβ; } else if (action[s,a] == 接受) break; else 调用错误恢复例程； }

例题 例 E  E + T | T T  T  F | F F  (E ) | id 教材表3.7 3.5 LR分析器 si: 移进，状态i进栈 rj: 按产生式(j)归约 acc: 表示接受 i: 转移到状态i (1) E  E + T (2) E  T (3) T  T  F (4) T  F (5) F  (E ) (6) F  id 教材表3.7 状态 动 作 action 转 移 goto id +  ( ) $ E T F s5 s4 1 2 3 s6 acc r2 s7 r4 4 8 …

例题 3.5 LR分析器 栈 输 入 动 作 id  id + id $ A[0,id]=s5 移进 0 id 5  id + id $ 输 入 动 作 id  id + id $ A[0,id]=s5 移进 0 id 5  id + id $ A[5,]=r6 归约 Fid，M[0,F]=3 0 F 3  id + id $ A[3,]=r4 归约 TF，M[0,T]=2 0 T 2  id + id $ A[2,]=s7 移进 0 T 2  7 id + id $ A[7,id]=s5 移进 0 T 2  7 id 5 + id $ A[5,+]=r6 归约 Fid，M[7,F]=10 0 T 2  7 F 10 + id $ A[10,+]=r3 归约 TTF，M[7,T]=2 0 T 2 + id $ A[2,+]=r2 归约 ET，M[0,E]=1 0 E 1 + id $ A[1,+]=s6 移进 0 E 1 + 6 id $ A[6,id]=s5 移进 0 E 1 + 6 id 5 $ A[5,$]=r6 归约 Fid，M[6,F]=3 0 E 1 + 6 F 3 $ A[3,$]=r4 归约 TF，M[6,$]=9 0 E 1 + 6 T 9 $ A[9,$]=r1 归约 EE+T, M[0,E]=1 0 E 1 $ A[1,$]=acc 接受

活前缀：右句型的前缀，该前缀不超过最右句柄的右端 S rm γAw rm γβw γβ的任何前缀（包括 ε 和 γβ 本身）都是活前缀 3.5 LR分析器 3.5.2 LR文法和LR分析方法的特点 （1）概念 活前缀：右句型的前缀，该前缀不超过最右句柄的右端 S rm γAw rm γβw γβ的任何前缀（包括 ε 和 γβ 本身）都是活前缀 （2）定义 LR文法：我们能为之构造出所有条目都唯一的LR分析表

3.5 LR分析器 （3）LR分析方法的特点 栈中的文法符号总是形成一个活前缀

3.5 LR分析器 栈 输 入 动 作 id  id + id $ A[0,id]=s5 移进 0 id 5  id + id $ A[5,]=r6 归约 Fid，M[0,F]=3 0 F 3 A[3,]=r4 归约 TF，M[0,T]=2 0 T 2 A[2,]=s7 移进 0 T 2  7 id + id $ A[7,id]=s5 移进 0 T 2  7 id 5 + id $ A[5,+]=r6 归约 Fid，M[7,F]=10 0 T 2  7 F 10 A[10,+]=r3 归约 TTF，M[7,T]=2 A[2,+]=r2 归约 ET，M[0,E]=1 0 E 1 A[1,+]=s6 移进 0 E 1 + 6 id $ A[6,id]=s5 移进 0 E 1 + 6 id 5 $ A[5,$]=r6 归约 Fid，M[6,F]=3 0 E 1 + 6 F 3 A[3,$]=r4 归约 TF，M[6,$]=9 0 E 1 + 6 T 9 A[9,$]=r1 归约 EE+T, M[0,E]=1 A[1,$]=acc 接受

分析表的转移函数本质上是识别活前缀的DFA 3.5 LR分析器 （3）LR分析方法的特点 栈中的文法符号总是形成一个活前缀 分析表的转移函数本质上是识别活前缀的DFA

绿色部分构成识别活前缀DFA的状态转换表 3.5 LR分析器 E  E + T | T T  T  F | F F  (E ) | id 绿色部分构成识别活前缀DFA的状态转换表 教材表3.7 状态 动 作 action 转 移 goto id +  ( ) $ E T F s5 s4 1 2 3 s6 acc r2 s7 r4 4 8 …

分析表的转移函数本质上是识别活前缀的DFA 栈顶的状态符号包含了确定句柄所需要的一切信息 3.5 LR分析器 （3）LR分析方法的特点 栈中的文法符号总是形成一个活前缀 分析表的转移函数本质上是识别活前缀的DFA 栈顶的状态符号包含了确定句柄所需要的一切信息

3.5 LR分析器 栈 输 入 动 作 id  id + id $ A[0,id]=s5 移进 0 id 5  id + id $ A[5,]=r6 归约 Fid，M[0,F]=3 0 F 3 A[3,]=r4 归约 TF，M[0,T]=2 0 T 2 A[2,]=s7 移进 0 T 2  7 id + id $ A[7,id]=s5 移进 0 T 2  7 id 5 + id $ A[5,+]=r6 归约 Fid，M[7,F]=10 0 T 2  7 F 10 A[10,+]=r3 归约 TTF，M[7,T]=2 A[2,+]=r2 归约 ET，M[0,E]=1 0 E 1 A[1,+]=s6 移进 0 E 1 + 6 id $ A[6,id]=s5 移进 0 E 1 + 6 id 5 $ A[5,$]=r6 归约 Fid，M[6,F]=3 0 E 1 + 6 F 3 A[3,$]=r4 归约 TF，M[6,$]=9 0 E 1 + 6 T 9 A[9,$]=r1 归约 EE+T, M[0,E]=1 A[1,$]=acc 接受

分析表的转移函数本质上是识别活前缀的DFA 栈顶的状态符号包含了确定句柄所需要的一切信息 是已知的最一般的无回溯的移进—归约方法 3.5 LR分析器 （3）LR分析方法的特点 栈中的文法符号总是形成一个活前缀 分析表的转移函数本质上是识别活前缀的DFA 栈顶的状态符号包含了确定句柄所需要的一切信息 是已知的最一般的无回溯的移进—归约方法 能分析的文法类是预测分析法能分析的文法类的真超集 能及时发现语法错误 手工构造分析表的工作量太大

看见产生式右部推出的整个终结符串后，才确定用哪个产生式进行归约 看见产生式右部推出的第一个终结符后，便要确定用哪个产生式推导 3.5 LR分析器 （4）LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上 自 上 而 下 归约还是推导 规 范 归 约 最 左 推 导 决定使用产生式的时机 看见产生式右部推出的整个终结符串后，才确定用哪个产生式进行归约 看见产生式右部推出的第一个终结符后，便要确定用哪个产生式推导

在下面的推导中，最后一步用的是 A  a β S +rm γ A b w +rm γ a β b w LR(1)决定用该 产生式的位置 LL(1)决定用该 产生式的位置

根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 3.5 LR分析器 LR(1)方 法 LL(1)方 法 对文法的显式限制 对文法没有限制 无左递归、无公共左因子 分析表比较 状态×文法符号 分析表大 非终结符×终结符 分析表小 分析栈比较 状态栈，通常状态比文法符号包含更多信息 文法符号栈 确定句柄 根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 语法错误 决不会将出错点后的符号移入分析栈 和LR一样，决不会读过出错点而不报错

• 3.5.3 构造SLR(1)分析表 术语：LR(0)项目（简称项目） 在右部的某个地方加点的产生式 用加点来表示分析过程中的状态 例：AXYZ对应有四个项目 A  •XYZ A  X•YZ A  XY•Z A  XYZ• 例：Aε只对应一个项目 A  • expr  expr + •term term  •term  factor term  term • factor expr + term •  term factor

3.5 LR分析器 构造SLR分析表的两大步骤 （1）从文法构造识别活前缀的DFA （2）从上述DFA构造分析表

（1）从文法构造识别活前缀的DFA 1）拓广文法 E'  E E  E + T | T T  T  F | F 3.5 LR分析器 （1）从文法构造识别活前缀的DFA 1）拓广文法 E'  E E  E + T | T T  T  F | F F  ( E ) | id

（1）从文法构造识别活前缀的DFA 2）构造LR(0)项目集规范族 I0： E'  •E (核心项目） E  •E + T (非核心项目，通过对核心 E  •T 项目求闭包而获得) T  •T  F T  •F F  •( E ) F  •id E'  E E  E + T | T T  T  F | F F  ( E ) | id

goto ( I0, E ) = I1 I5： I0： F  id• E'  •E id I1： E  •E + T E 3.5 LR分析器 goto ( I0, E ) = I1 I5： F  id• I0： E'  •E E  •E + T E  •T T  •T  F T  •F F  •( E ) F  •id id I1： E'  E• E  E •+ T E I4： F  ( •E ) E  •E + T E  •T T  •T  F T  •F F  •( E ) F  •id T I2： E  T• T  T • F ( F E'  E E  E + T | T T  T  F | F F  ( E ) | id I3： T  F•

E + I0 I1 I6 I1： E'  E• E  E •+ T + T I6： I2 E  E + •T T  •T  F 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I1： E'  E• E  E •+ T + I6： E  E + •T T  •T  F T  •F F  •( E ) F  •id E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I2： E  T• T  T • F  I7： 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I2： E  T• T  T • F  I7： T  T  •F F  •( E ) F  •id I7  E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I3： T  F• 无转换 E'  E 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I3： T  F• 无转换 E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I4： F  ( •E ) E  •E + T 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I4： F  ( •E ) E  •E + T E  •T T  •T  F T  •F F  •( E ) F  •id I8： F  ( E •) E  E •+ T E T I2 F I3 I4 ( I5 id I8 E ( id 指向I2 T E'  E E  E + T | T T  T  F | F F  ( E ) | id 指向I3 F

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 T 指向I3 F 指向I4 ( 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 T 指向I3 F 指向I4 ( 指向I5 id I6： E  E + •T T  •T  F T  •F F  •( E ) F  •id I9： E  E + T• T  T • F T F I3 E'  E E  E + T | T T  T  F | F F  ( E ) | id I5 id I4 (

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10： 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10： T  T  F• F I7： T  T  •F F  •( E ) F  •id I10 F 指向I4 ( 指向I5 id I5 id I4 ( E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11： F  ( E )• ) I8： F  ( E •) E  E •+ T I6 + I11 ) 指向I6 + E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6  指向I7 I9： E  E + T• T  T • F I7  E'  E E  E + T | T T  T  F | F F  ( E ) | id

I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 3.5 LR分析器 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 所有状态都作为接受状态 这是一个判断活前缀的DFA E  E  E+T  E+T  F  E+T  id  E+T  F  id E+TF 的所有前缀都可接受

也可以构造一个识别活前缀的NFA 每个项目作为一个状态 E'  E E  E + T | T T  T  F | F 3.5 LR分析器 也可以构造一个识别活前缀的NFA 每个项目作为一个状态 E'  E E  E + T | T T  T  F | F F  ( E ) | id E E'  •E E'  E• ε ε ε ε E  •E + T E  •T ε ε ε ε T  •T  F T  •F ε ε F  •( E ) F  •id

从文法构造的识别活前缀的DFA的一些特点 概念：有效项目 3.5 LR分析器 从文法构造的识别活前缀的DFA的一些特点 概念：有效项目 如果S'rm αAw rm αβ1β2w，那么就说项目Aβ1•β2对 活前缀 αβ1 是有效 （1）一个项目可能对好几个活前缀都是有效的 E  •E+T 对 ε 和 ( 这两个活前缀都有效 E'  E  E+T (α，β1都为空) E'  E  (E)  (E+T) (α =“(”， β1为空) 该DFA读过 ε 和 ( 后到达不同的状态，那么项目 E•E+T 就出现在对应的不同项目集中

从文法构造的识别活前缀的DFA的一些特点 概念：有效项目 3.5 LR分析器 从文法构造的识别活前缀的DFA的一些特点 概念：有效项目 如果S'rm αAw rm αβ1β2w，那么就说项目Aβ1•β2对 活前缀 αβ1 是有效 （1）一个项目可能对好几个活前缀都是有效的 从项目 Aβ1•β2 对活前缀 αβ1 有效这个事实可以知道 如果 β2 ≠ ε，应该移进 如果 β2 = ε，应该用产生式 Aβ1 归约 （2）一个活前缀可能有多个有效项目 一个活前缀 γ 的有效项目集就是从这个DFA的初态出发， 沿着标记为 γ 的路径到达的那个项目集（状态）

例 串 E + T  是活前缀，读完它后，DFA处于状态I7 3.5 LR分析器 例 串 E + T  是活前缀，读完它后，DFA处于状态I7 E'  E E'  E E'  E  E+T  E+T  E+T  E+T  F  E+T  F  E+T  F  E+T  id  E+T  ( E )  E+T  id  E+T  F  id I7： T  T  •F F  •( E ) F  •id

（2）从识别活前缀的DFA构造SLR分析表 状态 i 由项目集 Ii 构造，它的action函数如下确定： 如果 Ii 中包含 [Aα•aβ]，并且 goto(Ii, a ) = Ij，那么 置action[i, a]为sj 如果 Ii中包含 [Aα•]，那么对 FOLLOW(A) 中的所有a， 置 action[i, a] 为rj，j是产生式 Aα 的编号 如果 Ii中包含 [S'S•]，那么置 action[i, $]为接受acc 如果出现动作冲突，那么该文法就不是SLR(1)的 使用下面规则构造状态i的goto函数： 如果 goto(Ii, A) = Ij, 那么置goto[i, A] = j 不能由上面两步定义的条目都置为error 分析器的初始状态是包含[S'•S]的项目集对应的状态

action[2, $]=action[2, +]=action[2, )]=r2 E'  E E  E + T | T 3.5 LR分析器 例题 例 I2: 因为FOLLOW(E) = {$, +, )}, 所以 action[2, ] = s7 action[2, $]=action[2, +]=action[2, )]=r2 E'  E E  E + T | T T  T  F | F F  ( E ) | id I2： E  T• T  T • F

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 •id + id  id  id 栈： E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id •+ id  id  id 栈： 0 id 5 0 F 3 0 T 2 0 E 1 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + •id  id  id 栈： 0 E 1 + 6 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id • id  id 栈： 0 E 1 + 6 id 5 0 E 1 + 6 F 3 0 E 1 + 6 T 9 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id  •id  id 栈： 0 E 1 + 6 T 9  7 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id  id • id 栈： 0 E 1 + 6 T 9  7 id 5 0 E 1 + 6 T 9  7 F 10 0 E 1 + 6 T 9 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id  id  •id 栈： 0 E 1 + 6 T 9  7 E'  E E  E + T | T T  T  F | F F  ( E ) | id

例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 3.5 LR分析器 例题 I1 I0 E I3 I2 I4 I5 T F ( id + I6 I7  I8 指向I3 指向I2 I9 指向I4 指向I5 I10 I11 ) 指向I6 指向I7 id + id  id  id• 栈： 0 E 1 + 6 T 9  7 id 5 0 E 1 + 6 T 9  7 F 10 0 E 1 + 6 T 9 0 E 1 acc E'  E E  E + T | T T  T  F | F F  ( E ) | id

action[2, = ] =r5，因为"="是E的一个后继符 该文法不是SLR(1)的 例：带指针的计算、赋值语句 (1) S  V = E (2) S  E (3) V   E (4) V  id (5) E  V I0 : S   •S S  •V = E S  •E V  • E V  •id E  •V I2 : S  V •= E E  V• V 第一项目使得 action[2, = ] = s6 第二项目使得 action[2, = ] =r5，因为"="是E的一个后继符 该文法不是SLR(1)的 S $  V = E $ 移进的场合 S $  E $  V $ 规约的场合

重新定义项目，让它带上搜索符，成为如下形式 [Aα • β, a] 3.5 LR分析器 3.5.4 构造规范的LR分析表 LR(1)项目： 重新定义项目，让它带上搜索符，成为如下形式 [Aα • β, a] LR(1)项目[Aβ1•β2, a]对活前缀 αβ1 有效： 如果存在着推导 S rm αAw rm αβ1β2w，其中： a 是 w 的第一个符号，或者 w 是 ε 且 a 是 $

从最右推导S rm bbBba rm bbbBba看出： [B  b•B, b]对活前缀 bbb 是有效的 3.5 LR分析器 例 S  BB B  bB | a 从最右推导S rm bbBba rm bbbBba看出： [B  b•B, b]对活前缀 bbb 是有效的 对于项目[A  α•β, a]，当 β为空时，是根据搜索符a来填表 （归约项目），而不是根据A的后继符来填表

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a B 3.5 LR分析器 I5 : S BB•, $ B I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I6 : B b•B, $ B •bB, $ B •a, $ b I2 : S B•B, $ B •bB, $ B •a, $ B I3 : B b•B, b/a B •bB, b/a B •a, b/a b I4 : B a•, b/a a b a I9 : B bB•, $ B I7 : B a•, $ a b I8 : B bB•, b/a B a

(1) 基于LR(1)项目来构造识别 G' 活前缀的DFA (2) 状态 i 由项目集 Ii 构造，它的action函数如下确定： 如果 Ii 中包含 [Aα•aβ, b]，并且 goto(Ii, a ) = Ij，那 么置action[i, a]为sj 如果 Ii中包含 [Aα•, a]，且A≠S，那么置 action[i, a] 为rj，j是产生式 Aα 的编号 如果 Ii中包含 [S'S•, $]，那么置 action[i, $]为接受acc 如果出现动作冲突，那么该文法就不是SLR(1)的 使用下面规则构造状态i的goto函数： 如果 goto(Ii, A) = Ij，那么置goto[i, A] = j 不能由上面两步定义的条目都置为error 分析器的初始状态是包含 [S'•S, $] 的项目集对应的状态

先前基于SLR(1)有移进-归约冲突的例子，在基于规范LR(1) 时无冲突 (1) S  V = E (2) S  E (3) V   E (4) V  id (5) E  V I0 : S   •S, $ S  •V = E, $ S  •E, $ V  • E, =/$ V  •id, =/$ E  •V, $ I2 : S  V •= E, $ E  V•, $ V

LALR和SLR的分析表有同样多的状态，比规范LR分析表 要小得多 LALR的能力介于SLR和规范LR之间

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I4 : B a•, b/a a I3 : B b•B, b/a b I5 : S BB•, $ I6 : B b•B, $ I7 : B a•, $ I8 : B bB•, b/a I9 : B bB•, $ I4和I7仅搜索符不一样 I4和I7合并

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I4 : B a•, b/a a I3 : B b•B, b/a b I5 : S BB•, $ I6 : B b•B, $ I7 : B a•, $ I8 : B bB•, b/a I9 : B bB•, $ 有三组同心集，都合并

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I47 : B a•, b/a/$ a I36 : B b•B, b/a/$ B •bB, b/a/$ B •a, b/a/$ b I5 : S BB•, $ I89 : B bB•, b/a/$ 有三组同心集，都合并

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I4 : B a•, b/a a I3 : B b•B, b/a b I5 : S BB•, $ I6 : B b•B, $ I7 : B a•, $ I8 : B bB•, b/a I9 : B bB•, $ 03132432 831802 6162762 961925 201 03132432 831802 error 输入为bbabba$ 输入为bba$

I5 : S I1 : I0 : S BB•, $ S S•, $ S •S, $ S •BB, $ B •bB, b/a 3.5 LR分析器 I0 : S •S, $ S •BB, $ B •bB, b/a B •a, b/a I1 : S S•, $ S I2 : S B•B, $ B •bB, $ B •a, $ B I47 : B a•, b/a/$ a I36 : B b•B, b/a/$ B •bB, b/a/$ B •a, b/a/$ b I5 : S BB•, $ I89 : B bB•, b/a/$ 036136247 36289361 8902error 输入为bbabba$ 输入为bba$

同心的LR(1)项目集：略去搜索符后它们是相同的集合 同心集的合并不会引起新的移进—归约冲突 若合并后有冲突，则合并前就有冲突。例如： （1）合并同心项目集可能会引起冲突 同心的LR(1)项目集：略去搜索符后它们是相同的集合 同心集的合并不会引起新的移进—归约冲突 若合并后有冲突，则合并前就有冲突。例如： 项目集1 项目集2 [A  α•, a] [B  β•aγ, b] [B  β•aγ, c] [A  α•, d] . . . . . .

同心集的合并有可能产生新的归约—归约冲突 3.5 LR分析器 （1）合并同心项目集可能会引起冲突 同心集的合并有可能产生新的归约—归约冲突 S  S S  aAd | bBd | aBe | bAe A  c B  c 对ac有效的项目集 对bc有效的项目集 A  c•, d B  c•, e A  c•, e B  c•, d 合并同心集后 该文法是LR(1)的， 但不是LALR(1)的 A  c•, d/e B  c•, d/e

1）构造LR(1)项目集规范族C = {I0, I1, …, In} （2）构造LALR(1)分析表 1）构造LR(1)项目集规范族C = {I0, I1, …, In} 2）寻找LR(1)项目集规范族中同心的项目集，用它们的并集代 替它们 3）按构造规范LR(1)分析表的方式构造分析表

下面文法是LALR(1)的，因无同心集可合并 但不是SLR(1)的 S  V = E S  E V   E V  id E  V I0 : S   •S S  •V = E S  •E V  • E V  •id E  •V I2 : S  V •= E E  V• V

若自左向右扫描的移进—归约分析器能及时识别出现在栈顶 的句柄，那么相应的文法就是LR的 语言L = {wwR| w ∈ (a | b)*}的文法 S  aSa | bSb | ε 不是LR的 ababbbbaba 语言L = {wcwR| w ∈ (a | b)*}的文法 S  aSa | bSb | c 是LR的 ababbcbbaba

例：为语言L = { ambn | n > m ≥ 0 }写三个文法,它们分别是 LR(1)的、二义的和非二义且非LR(1)的 例题1 例：为语言L = { ambn | n > m ≥ 0 }写三个文法,它们分别是 LR(1)的、二义的和非二义且非LR(1)的 LR(1)文法：S  AB A  aAb | ε B  Bb | b 非二义且非LR(1)的文法：S  aSb | B B  Bb | b 二义的文法：S  aSb | Sb | b a a a b b b b b a a a b b b b b a a a b b b b b

例题2 例：试说明下面文法不是LR(1)的： L  M L b | a M  ε M b L a  句子abbb的分析树

例：下面的文法不是LR(1)的，对它略做修改，使之成为 一个等价的SLR(1)文法 例题3 例：下面的文法不是LR(1)的，对它略做修改，使之成为 一个等价的SLR(1)文法 program  begin declist ; statement end declist  d ; declist | d statement  s ; statement | s 该文法产生的句子的形式是 begin d ; d ; … ; d ; s ; s ; … ; s end 修改后的文法如下： program  begin declist statement end declist  d ; declist | d ;

3.5 LR分析器 例题4 例：一个C语言的文件如下，第四行的if误写成fi： long gcd(p,q) long p,q; { fi (p%q == 0) return q; else return gcd(q, p%q); } 基于LALR(1)方法的一个编译器的报错情况如下： parse error before ‘return’ ( line 5). 是否违反了LR分析的活前缀性质？

编译原理与技术 第3章 语法分析 3.6 二义文法的应用 1学时

例：二义文法 E  E + E | E  E | (E) | id 非二义的文法： E  E + T | T 3.6 二义文法的应用 二义文法的特点： 二义文法决不是LR文法 简洁、自然 例：二义文法 E  E + E | E  E | (E) | id 非二义的文法： E  E + T | T T  T  F | F F  (E) | id 该文法有单个非终结符为右部的产生式 可以用文法以外的信息来消除二义 语法分析的效率高（基于消除二义后得到的分析表）

例 二义文法 E  E + E | E  E | (E) | id 规定：  优先级高于 +，两者都是左结合 3.6 二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突 例 二义文法 E  E + E | E  E | (E) | id 规定：  优先级高于 +，两者都是左结合

I0 E'  •E E  •E + E E  •E  E E  •(E) E  •id I1 E'  E• 3.6 二义文法的应用 I0 E'  •E E  •E + E E  •E  E E  •(E) E  •id I1 E'  E• E  E •+ E E  E • E E I2 E  ( •E) ( I3 E  id• id I4 E  E + •E I5 E  E  •E I6 E  (E •) I7 E  E + E• I8 E  E  E• I9 E  (E)• +  )

state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 7 5 8 s9 3.6 二义文法的应用 state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 7 5 8 s9 s4/r1 s5/r1 r1 s4/r2 s5/r2 r2 9 r3

LR(0)项目集I7 I7 id + id + id 面临+，归约 E  E + E• id + id  id 面临，移进 3.6 二义文法的应用 LR(0)项目集I7 id + id + id 面临+，归约 id + id  id 面临，移进 面临 ) 和$，归约 LR(0)项目集I8 id  id + id 面临+，归约 id  id  id 面临，归约 I7 E  E + E• E  E •+ E E  E • E I8 E  E  E• E  E •+ E E  E • E

state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 7 5 8 s9 3.6 二义文法的应用 state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 7 5 8 s9 r1 r2 9 r3

从定义形式语言的角度说，第一个产生式是多余的 联系到语义处理，第一个产生式是必要的 对a sub i sup 2，需要下面第一种输出 3.6 二义文法的应用 3.6.2 特殊情况产生式引起的二义性 例：E  E sub E sup E E  E sub E E  E sup E E  {E} E  c 从定义形式语言的角度说，第一个产生式是多余的 联系到语义处理，第一个产生式是必要的 对a sub i sup 2，需要下面第一种输出 可归约可移进时，移进 I11: E  E sub E sup E· E  E sup E· . . . 按前面一个产生式归约

规范的LR分析器甚至在报告错误之前决不做任何无效归约 3.6 二义文法的应用 3.6.3 LR分析的错误恢复 （1）LR分析器在什么情况下发现错误 访问动作表时若遇到出错条目 访问转移表时它决不会遇到出错条目 决不会把不正确的后继移进栈 规范的LR分析器甚至在报告错误之前决不做任何无效归约

（2）紧急方式错误恢复 例如，在分析非终结符A时发现错误 3.6 二义文法的应用 （2）紧急方式错误恢复 例如，在分析非终结符A时发现错误 s . 栈 . . . . . . . . a . . A 发现错误 s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ b

1) 退栈，直至出现状态s, 它有预先确定的A的转移 3.6 二义文法的应用 （2）紧急方式错误恢复 例如，在分析非终结符A时发现错误 1) 退栈，直至出现状态s, 它有预先确定的A的转移 s . 栈 . . . . . . . . a . . A 发现错误 s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ b

3.6 二义文法的应用 （2）紧急方式错误恢复 例如，在分析非终结符A时发现错误 1) 退栈，直至出现状态s, 它有预先确定的A的转移 2) 抛弃若干输入符号，直至找到a, 它是A的合法后继 s . 栈 . . . . . . . . a . . A s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ b

3.6 二义文法的应用 （2）紧急方式错误恢复 例如，在分析非终结符A时发现错误 1) 退栈，直至出现状态s, 它有预先确定的A的转移 2) 抛弃若干输入符号，直至找到a, 它是A的合法后继 3) 再把A和状态goto[s, A]压进栈，恢复正常分析 s A . s1 栈 . . . . . . . . a . . s : C α•Aβ A •bγ . . . s1 : C αA •β Ab·γ b

例 二义文法 E  E + E | E  E | (E) | id 规定： 优先级高于+，两者都是左结合 3.6 二义文法的应用 例 例 二义文法 E  E + E | E  E | (E) | id 规定： 优先级高于+，两者都是左结合 LR(0)项目集I4 I4 E  E + •E E  •E + E E  •E  E E  •(E) E  •id + . 栈 . . . id +  . . 4 本例无需退栈， 也无需丢弃符号 报错：缺少运算对象 将E和I7入栈

state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 e7 7 5 8 3.6 二义文法的应用 state action goto id +  ( ) $ E s3 s2 1 s4 s5 acc 2 6 3 r4 4 e7 7 5 8 s9 r1 r2 9 r3

3.6 二义文法的应用 （3）短语级恢复 删除或插入符号，纠正局部错误

state action goto id +  ( ) $ E s3 e1 s2 d 1 e4 s4 s5 acc 2 e6 6 3 r4 3.6 二义文法的应用 state action goto id +  ( ) $ E s3 e1 s2 d 1 e4 s4 s5 acc 2 e6 6 3 r4 4 e7 7 5 e8 8 s9 e9 r1 r2 9 r3

I0 E'  •E E  •E + E E  •E  E E  •(E) E  •id I1 E'  E• 3.6 二义文法的应用 I0 E'  •E E  •E + E E  •E  E E  •(E) E  •id I1 E'  E• E  E •+ E E  E • E E I2 E  ( •E) ( I3 E  id• id I4 E  E + •E I5 E  E  •E I6 E  (E •) I7 E  E + E• I8 E  E  E• I9 E  (E)• +  )

例：下面的二义文法描述命题演算公式的语法，为它写一个 等价的非二义文法 3.6 二义文法的应用 例题1 例：下面的二义文法描述命题演算公式的语法，为它写一个 等价的非二义文法 S  S and S | S or S | not S | p | q | (S) 非二义文法的产生式如下 E  E or T | T T  T and F | F F  not E | ( E) | p | q ? not p and q有两种不同的最左推导 not p and q not p and q F  not F | ( E) | p | q

例：设计一个文法：字母表{a, b}上a和b的个数相等的所有 串的集合 3.6 二义文法的应用 例题2 例：设计一个文法：字母表{a, b}上a和b的个数相等的所有 串的集合 二义文法：S  a S b S | b S a S | ε aabbabab aabbabab S S S S 二义文法：S  a B | b A | ε A  a S | b A A B  b S | a B B aabbabab aabbabab aabbabab B B B B B B

例：设计一个文法：字母表{a, b}上a和b的个数相等的所有 串的集合 3.6 二义文法的应用 例题2 例：设计一个文法：字母表{a, b}上a和b的个数相等的所有 串的集合 非二义文法：S  a B S | b A S | ε A  a | b A A B  b | a B B a abb abab a B S b, abb, aabbb, ababb,

编译原理与技术 第3章 语法分析 3.7 语法分析器的生成器 

3.7.1 分析器的生成器Yacc Yacc源程序 Yacc y.tab.c translate.y 编译器 C a.out 输出 输入 3.7 语法分析器的生成器 3.7.1 分析器的生成器Yacc Yacc 编译器 Yacc源程序 translate.y y.tab.c C a.out 输入 输出

3.7 语法分析器的生成器 3.7.2 用Yacc处理二义文法 例：简单计算器 输入一个表达式并回车，显示计算结果 也可以输入一个空白行

3.7 语法分析器的生成器 %{ # include <ctype .h> # include <stdio.h > # define YYSTYPE double / 将栈定义为double类型 / %} %token NUMBER %left ‘+’ ‘-’ %left ‘’ ‘/ ’ %right UMINUS %%

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; } | NUMBER %% -5+10看成是 (-5)+10

3.7 语法分析器的生成器 yylex ( ) { int c; while ( ( c = getchar ( ) ) == ' ' ); if ( ( c == '.' ) | | (isdigit (c) ) ) { ungetc (c, stdin); scanf ( "% lf", &yylval); return NUMBER; } return c; 为了C编译器能准确报告yylex函数中错误的位置，需要在生成 的程序y.tab.c中使用编译命令#line，指示编译后代码行号

决定哪些“主要的”非终结符将有错误恢复与它们相关 联 3.7 语法分析器的生成器 3.7.3 Yacc的错误恢复 编译器设计者的工作 决定哪些“主要的”非终结符将有错误恢复与它们相关 联 为各主要非终结符A加入形式为 A  error α 的错误产 生式，其中 α 是文法符号串 为这样的产生式配上语义动作 Yacc把错误产生式当作普通产生式处理

遇到语法错误时 s . 栈 . . . . . . . . . . . A 发现错误 s : C  β1 •Aβ2 3.7 语法分析器的生成器 遇到语法错误时 s . 栈 . . . . . . . . . . . A 发现错误 s : C  β1 •Aβ2 A  •error α . . . s1 : C  β1A •β2 s2 : A  error •α error 

从栈中弹出状态，直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 3.7 语法分析器的生成器 遇到语法错误时 从栈中弹出状态，直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 s . 栈 . . . . . . . . . . . A 发现错误 s : C  β1 •Aβ2 A  •error α . . . s1 : C  β1A •β2 s2 : A  error •α error  error

从栈中弹出状态，直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 3.7 语法分析器的生成器 遇到语法错误时 从栈中弹出状态，直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 忽略若干输入符号，直至找到 α，把 α 移进栈 s error . α 栈 . . . . . . . . . . . A s : C  β1 •Aβ2 A  •error α . . . s1 : C  β1A •β2 s2 : A  error •α 

从栈中弹出状态，直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 3.7 语法分析器的生成器 遇到语法错误时 从栈中弹出状态，直到发现栈顶状态的项目集包含形为 A  •error α 的项目为止 把虚构的终结符 error“移进”栈 忽略若干输入符号，直至找到 α，把 α 移进栈 把 error α 归约为A，恢复正常分析 s s1 . 栈 . . . . . . . . . . . A s : C  β1 •Aβ2 A  •error α . . . s1 : C  β1A •β2 s2 : A  error •α error 

lines : lines expr '\n' {printf ( "%g \n", $2 ) } | lines '\n' 3.7 语法分析器的生成器 增加错误恢复的简单计算器 lines : lines expr '\n' {printf ( "%g \n", $2 ) } | lines '\n' | / ε / | error '\n' {yyerror ( "重新输入上一行"); yyerrok;} ;

0型文法（短语文法）、1型文法（上下文有关文法）、2 型文法（上下文无关文法）、3型文法（正规文法） 推导、最左推导、最右推导、分析树 3 语法分析 本章要点 文法和语言的基本知识 0型文法（短语文法）、1型文法（上下文有关文法）、2 型文法（上下文无关文法）、3型文法（正规文法） 推导、最左推导、最右推导、分析树 二义性的消除、左递归的消除、提左因子的方法 从正规式构造文法、从语言构造文法 自上而下分析（无左递归，无公共左因子） FIRST集合和FOLLOW集合的计算，LL(1)文法的条件及 判断 递归下降预测分析（函数形式） 非递归预测分析：预测分析表的编写，多重定义的消除

句柄、活前缀、项目与项目集、拓广文法、搜索符 识别活前缀的DFA构造 SLR(1)分析：分析表的编写 规范LR(1)分析：分析表的编写 3 语法分析 本章要点 自下而上分析 句柄、活前缀、项目与项目集、拓广文法、搜索符 识别活前缀的DFA构造 SLR(1)分析：分析表的编写 规范LR(1)分析：分析表的编写 LALR(1)分析：同心项目集的合并 二义文法：移进-归约冲突、归约-归约冲突 非SLR/LR/LALR文法的判定：寻找冲突 语法分析的错误恢复方法

习题 文法和语言基础 3.2 3.4(b)(c) 3.6(a)(b)(c) 自上而下分析、LL(1) 3.8 3.10 3 语法分析 习题 文法和语言基础 3.2 3.4(b)(c) 3.6(a)(b)(c) 自上而下分析、LL(1) 3.8 3.10 3.15（第二版3.14） 自下而上分析 3.16（第二版3.15）

习题 SLR(1) 3.19(a) （第二版3.18(a)） 3.21 (a) （第二版3.20 (a)） LR(1) 3 语法分析 习题 SLR(1) 3.19(a) （第二版3.18(a)） 3.21 (a) （第二版3.20 (a)） LR(1) 3.30（第二版3.28） LALR(1) 3.22（第二版3.21） 3.24（第二版3.23）