自底向上的语法分析 4.5.

Presentation on theme: "自底向上的语法分析 4.5."— Presentation transcript:

1 自底向上的语法分析 4.5

2 1. 移进归约的概念

3 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d

4 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde（读入ab） a b

5 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde（归约） a A

6 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde（再读入bc）

7 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde
aAde（归约） a b A c

8 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde
aAde（再读入d） a b A d c

9 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde

10 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde
aABe(再读入e) e a b A d c B

11 4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde

12 S rm aABe rm aAde rm aAbcde rm abbcde
4.4 自下而上分析 4.4.1 归约 例 S  aABe A  Abc | b B  d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde S e a b A d c B

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

14 4.4 自下而上分析 例 句柄不唯一 E  E + E | E  E | (E ) | id

15 4.4 自下而上分析 例 句柄不唯一 E  E + E | E  E | (E ) | id E rm E  E rm E  E + E rm E  E + id3 rm E  id2 + id3 rm id1  id2 + id3

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

17 2. 用栈实现移进归约

18 用栈实现移进归约分析 移进 归约 接受 报错 把下一个输入符号移进栈
分析器知道句柄的右端已在栈顶，然后确定句柄的左端在栈中的位置，再决定用什么样的非终结符代替句柄 接受 分析器宣告分析成功 报错 分析器发现语法错误，调用错误恢复例程

19 4.4 自下而上分析 4.4.3 用栈实现移进归约分析 先通过 来了解移进归约分析的工作方式
移进归约分析器在分析输入串id1  id2 + id3时的动作序列 来了解移进归约分析的工作方式

20 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$

21 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进

22 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$

23 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约

24 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E

25 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E

26 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$

27 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$

28 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$

29 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$

30 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE

31 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE

32 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$

33 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$

34 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3

35 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3

36 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E

37 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约

38 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约

39 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约

40 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约

41 4.4 自下而上分析 栈 输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$
输 入 动 作 $ id1  id2 + id3$ 移进 $ id1  id2 + id3$ 按E  id归约 $E $E id2 + id3$ $Eid2 + id3$ $EE $EE+ id3$ $EE+id3 $EE+E 按E  E+E归约 按E  EE归约 接受

42 3. 移进归约的冲突

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

44 4.4 自下而上分析 4.4.4 移进归约分析的冲突 1、移进归约冲突 例 stmt  if expr then stmt | if expr then stmt else stmt | other 如果移进归约分析器处于格局 栈 输入 … if expr then stmt else … $

45 4.4 自下而上分析 2、归约归约冲突 由A(I, J)开始的语句 栈 输入 … id ( id , id )… 归约成expr还
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 )… 归约成expr还 是parameter ?

46 4.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) 栈 输入 … procid ( id , id )… 需要修改上面的文法

47 4.4 自下而上分析 2、归约归约冲突 stmt  procid (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) 栈 输入 … procid ( id , id )…

48 4. LR分析器

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

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

51 LR语法分析 LR语法分析算法实例：图4.37 (1) E  E + T (2) E  T
(3) T  T  F (4) T  F (5) F  ( E ) (6) F  id si：表示移进并将状态i压栈。 rj：表示按照编号为j的产生式进行归约。 Acc：表示接受。 空白：表示出错。

52 LR语法分析

53 可行前缀：右句型的前缀，该前缀不超过最右句柄的右端
4.5 LR分析器 4.5.2 LR文法和LR分析方法的特点 1、概念 可行前缀：右句型的前缀，该前缀不超过最右句柄的右端 S *rm  A w rm   w  的任何前缀（包括和 本身）都是可行前缀

54 4.5 LR分析器 4.5.2 LR文法和LR分析方法的特点 1、概念 可行前缀：右句型的前缀，该前缀不超过最右句柄的右端 2、定义 LR文法：我们能为之构造出所有条目都唯一的LR分析表

55 4.5 LR分析器 3、LR分析方法的特点 栈中的文法符号总是形成一个可行前缀

56 4.5 LR分析器 栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约
输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 0 F 3 按T  F归约 0 T 2 0 T 2  7 id + id $ 0 T 2  7 id 5 + id $ 0 T 2  7 F 10 按T  TF归约 . . . 0 E 1 $ 接受

57 4.5 LR分析器 3、LR分析方法的特点 栈中的文法符号总是形成一个可行前缀 分析表的转移函数本质上是识别可行前缀的DFA

58 4.5 LR分析器 例 E  E + T | E  T 下表绿色部分构成 T  T  F | T  E 识别可行前缀DFA的
F  (E ) | F  id 状态转换表 状态 动 作 转 移 id  ( ) $ E T F s s4 1 s acc 2 r2 s r2 r2 3 r4 r r4 r4 4

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

60 4.5 LR分析器 栈 输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约
输 入 动 作 id  id + id $ 移进 0 id 5  id + id $ 按F  id归约 0 F 3 按T  F归约 0 T 2 0 T 2  7 id + id $ 0 T 2  7 id 5 + id $ 0 T 2  7 F 10 按T  TF归约 . . . 0 E 1 $ 接受

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

62 4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上
自 上 而 下

63 4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 建立分析树的方式 自 下 而 上
自 上 而 下 归约还是推导 规 范 归 约 最 左 推 导

64 4.5 LR分析器 4、LR分析方法和LL分析方法的比较 在下面的推导中，最后一步用的是A l S rm …  rm  A b w  rm  l  b w LR(1)决定用该 产生式的位置 LL(1)决定用该 产生式的位置

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

66 4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 对文法的显式限制 对文法没有限制
无左递归、无公共左因子

67 4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 对文法的显式限制 对文法没有限制
无左递归、无公共左因子 分析表比较 状态×文法符号 分析表大 非终结符×终结符 分析表小

68 4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 对文法的显式限制 对文法没有限制
无左递归、无公共左因子 分析表比较 状态×文法符号 分析表大 非终结符×终结符 分析表小 分析栈比较 状态栈，通常状态比文法符号包含更多信息 文法符号栈

69 4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 确定句柄
根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念

70 4.5 LR分析器 4、LR分析方法和LL分析方法的比较 LR(1)方 法 LL(1)方 法 确定句柄
根据栈顶状态和下一个符号便可以确定句柄和归约所用产生式 无句柄概念 语法错误 决不会将出错点后的符号移入分析栈 和LR一样，决不会读过出错点而不报错