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

Presentation on theme: "编译原理与技术 第3章 语法分析 14学时."— Presentation transcript:

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

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

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

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

5 例 ( {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  

6 符号的约定 终结符 非终结符 其它 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，代表终结符号串 小写希腊字母，如α, β, γ, …，代表文法符号串

7 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  + | 

8 把产生式看成重写规则，把符号串中的非终结符用其产生式右 部的串来代替
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

9 例如 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)

10 例如 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

11 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

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

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

14 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

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

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

17 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

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

19 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 分析树

20 | 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

21 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

22 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 

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

24 例题 例 算术表达文法 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' | ε

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

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

27 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 | ε

28 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个下划线键

29 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

30 设读完ε, 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的路径

31 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 正规文法

32 例 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次

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

34 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 复杂的回溯技术 回溯导致语义工作推倒重来 难以报告出错的确切位置 效率低 不能处理左递归

35 不能处理左递归的例子：算术表达文法 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 … … …

36 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)

37 若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)

38 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) = {, +, ), $}

39 任何两个产生式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  …

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

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

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

43 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

44 | 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

45 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入栈; }

46 分析表的例子 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)

47 预测分析器接受输入 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$

48 例题 栈 输 入 输 出 $ 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  

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

50 (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

51 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)

52 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 消除方法： 修改文法，消除二义性 根据语法约定消去多重定义

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

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

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

56 把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 语句忽略了 如果终结符在栈顶而不能匹配，弹出此终结符 如果非终结符可以产生空串，若出错时栈顶是这样的非终结 符，则可以使用推出空串的产生式

57 例：栈顶为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。 相当于丢弃了一个输入

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

59 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

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

61 例 句柄不唯一 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

62 先通过例子 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 $ 接受

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

64 | 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 … $ 解决方法：消除二义性 归约? 移进?

65 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

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

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

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

69 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 调用错误恢复例程； }

70 例题 例 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 …

71 例题 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 id 5 $ A[5,$]=r6 归约 Fid，M[6,F]=3 0 E F 3 $ A[3,$]=r4 归约 TF，M[6,$]=9 0 E T 9 $ A[9,$]=r1 归约 EE+T, M[0,E]=1 0 E 1 $ A[1,$]=acc 接受

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

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

74 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 id 5 $ A[5,$]=r6 归约 Fid，M[6,F]=3 0 E F 3 A[3,$]=r4 归约 TF，M[6,$]=9 0 E T 9 A[9,$]=r1 归约 EE+T, M[0,E]=1 A[1,$]=acc 接受

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

76 绿色部分构成识别活前缀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 …

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

78 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 id 5 $ A[5,$]=r6 归约 Fid，M[6,F]=3 0 E F 3 A[3,$]=r4 归约 TF，M[6,$]=9 0 E T 9 A[9,$]=r1 归约 EE+T, M[0,E]=1 A[1,$]=acc 接受

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

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

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

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

83 • 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

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

85 （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

86 （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

87 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•

88 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

89 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

90 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

91 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

92 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 (

93 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

94 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

95 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

96 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 的所有前缀都可接受

97 也可以构造一个识别活前缀的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

98 从文法构造的识别活前缀的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 就出现在对应的不同项目集中

99 从文法构造的识别活前缀的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的初态出发， 沿着标记为 γ 的路径到达的那个项目集（状态）

100 例 串 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

101 （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]的项目集对应的状态

102 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

103 例题 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

104 例题 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

105 例题 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

106 例题 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 id 5 0 E F 3 0 E T 9 E'  E E  E + T | T T  T  F | F F  ( E ) | id

107 例题 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 T 9  7 E'  E E  E + T | T T  T  F | F F  ( E ) | id

108 例题 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 T 9  7 id 5 0 E T 9  7 F 10 0 E T 9 E'  E E  E + T | T T  T  F | F F  ( E ) | id

109 例题 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 T 9  7 E'  E E  E + T | T T  T  F | F F  ( E ) | id

110 例题 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 T 9  7 id 5 0 E T 9  7 F 10 0 E T 9 0 E 1 acc E'  E E  E + T | T T  T  F | F F  ( E ) | id

111 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 $ 规约的场合

112 重新定义项目，让它带上搜索符，成为如下形式 [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 是 $

113 从最右推导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的后继符来填表

114 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

115 (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, $] 的项目集对应的状态

116 先前基于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

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

118 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合并

119 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•, $ 有三组同心集，都合并

120 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/$ 有三组同心集，都合并

121 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$

122 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$

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

124 同心集的合并有可能产生新的归约—归约冲突
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

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

126 下面文法是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

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

128 例：为语言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

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

130 例：下面的文法不是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 ;

131 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分析的活前缀性质？

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

133 例：二义文法 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 该文法有单个非终结符为右部的产生式 可以用文法以外的信息来消除二义 语法分析的效率高（基于消除二义后得到的分析表）

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

135 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)• +  )

136 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

137 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

138 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

139 从定义形式语言的角度说，第一个产生式是多余的 联系到语义处理，第一个产生式是必要的 对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· . . . 按前面一个产生式归约

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

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

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

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

144 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

145 例 二义文法 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入栈

146 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

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

148 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

149 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)• +  )

150 例：下面的二义文法描述命题演算公式的语法，为它写一个 等价的非二义文法
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

151 例：设计一个文法：字母表{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

152 例：设计一个文法：字母表{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,

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

154 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 输入 输出

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

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

157 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

158 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，指示编译后代码行号

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

160 遇到语法错误时 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 

161 从栈中弹出状态，直到发现栈顶状态的项目集包含形为 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

162 从栈中弹出状态，直到发现栈顶状态的项目集包含形为 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 •α 

163 从栈中弹出状态，直到发现栈顶状态的项目集包含形为 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 

164 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;} ;

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

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

167 习题 文法和语言基础 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）

168 习题 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）