编译原理 第五章 语法分析——自下而上分析 编译原理.

Presentation on theme: "编译原理 第五章 语法分析——自下而上分析 编译原理."— Presentation transcript:

1 编译原理 第五章 语法分析——自下而上分析 编译原理

2 第五章 语法分析——自下而上分析 自上而下分析法(Top-down) 自下而上分析法(Bottom-up) 编译原理

3 语法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down)
基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序 优点：直观、简单和宜于手工实现。 编译原理

4 语法分析的方法： 自下而上分析法(Bottom-up)
基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约 编译原理

5 E E + E E * E i i i G(E)： E  i| E+E | E-E | E*E | E/E | (E) i*i+i
编译原理

6 5.1.1 归约 采用“移进－归约”思想进行自下而上分析。
基本思想：用一个寄存符号的先进后出栈， 把输入符号一个一个地移进到栈里，当栈顶 形成某个产生式的候选式时，即把栈顶的这 一部分替换成(归约为)该产生式的左部符 号。 编译原理

7 e abbcde de cde bbcde bcde bcde cde e
例：设文法G(S)： (1) S  aAcBe (2) A  b (3) A  Ab (4) B  d 试对abbcde进行“移进－归约”分析。 d c A a e abbcde S c A a de e B c A a A a cde a bbcde b a bcde A a bcde b A a cde B c A a e 编译原理

8 编译原理

9 自下而上分析过程：边输入单词符号，边归约。 核心问题：识别可归约串
S a A c B e A b d b 分析树和语法树不一定一致。 自下而上分析过程：边输入单词符号，边归约。 核心问题：识别可归约串 编译原理

10 5.1.2 规范归约 定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且
则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。 编译原理

11 考虑文法G(E)： E  T | E+T T  F | T*F F  (E) | i 和句型i1*i2+i3：
E  E+T  E+F  E+i3  T+i3  T*F+i3  T*i2+i3  F*i2+i3  i1*i2+i3 短语： i1，i2，i3， i1*i2， i1*i2+i3 直接短语： i1，i2，i3 句柄： i1 编译原理

12 E F T i1 + * i3 i2 在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。 编译原理

13 可用句柄来对句子进行归约 句型 归约规则 abbcde (2) A  b aAbcde (3) A  Ab
句型 归约规则 abbcde (2) A  b aAbcde (3) A  Ab aAcde (4) B  d aAcBe (1) S  aAcBe S 编译原理

14 定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 
2 0为文法的开始符号，即0=S 3 对任何i，0  i  n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。 编译原理

15 规范归约是关于是一个最右推导的逆过程 最左归约 规范推导 把上例倒过来写，则得到：
S  aAcBe aAcde  aAbcde  abbcde 显然这是一个最右推导。 规范归约是关于是一个最右推导的逆过程 最左归约 规范推导 由规范推导推出的句型称为规范句型。 编译原理

16 b d a c e S A B d b a c e S A B d a c e S A B a c e S A B 编译原理

17 5.1.3 符号栈的使用和分析树的表示 栈是语法分析的一种基本数据结构。’#’作为栈底符号 考虑文法G(E)： E  T | E+T
T  F | T*F F  (E) | i 输入串为i1*i2+i3 ，分析步骤为： 编译原理

18 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用F→i
G(E)： E  T | E+T T  F | T*F F  (E) | i 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用F→i #T *i2+i3# 归，用T→F 4 #T* i2+i3# 进 编译原理

19 步骤 符号栈 输入串 动作 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 6 #T*F +i3# 归，用F→i
G(E)： E  T | E+T T  F | T*F F  (E) | i 步骤 符号栈 输入串 动作 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 6 #T*F +i3# 归，用F→i 7 #T +i3# 归，用T→T*F 8 #E +i3# 归，用E→T 9 #E+ i3# 进 编译原理

20 步骤 符号栈 输入串 动作 9 #E+ i3# 进 10 #E+i3 # 进 11 #E+F # 归，用F→i
G(E)： E  T | E+T T  F | T*F F  (E) | i 步骤 符号栈 输入串 动作 #E i3# 进 10 #E+i3 # 进 11 #E+F # 归，用F→i 12 #E+T # 归，用T→F 13 #E # 归，用E→E+T 14 #E # 接受 编译原理

21 回顾 语法分析的方法： 自下而上分析法(Bottom-up)
基本思想：从输入串开始，逐步进行“归 约”，直到文法的开始符号。即从树末端开始， 构造语法树。所谓 归约 ，是指根据文法的产 生式规则，把产生式的右部替换成左部符号。 编译原理

22 归约 采用“移进－归约”思想进行自下而上分析。
基本思想：用一个寄存符号的先进后出栈，把输 入符号一个一个地移进到栈里，当栈顶形成某个 产生式的候选式时，即把栈顶的这一部分替换成 (归约为)该产生式的左部符号。 编译原理

23 规范归约 定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且 则称是句型相对于非终结符A的短语。
特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。 编译原理

24 定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 
2 0为文法的开始符号，即0=S 3 对任何i，0  i  n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。 编译原理

25 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用F→i
G(E)： E  T | E+T T  F | T*F F  (E) | i 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用F→i #T *i2+i3# 归，用T→F 4 #T* i2+i3# 进 编译原理

26 步骤 符号栈 输入串 动作 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 6 #T*F +i3# 归，用F→i
G(E)： E  T | E+T T  F | T*F F  (E) | i 步骤 符号栈 输入串 动作 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 6 #T*F +i3# 归，用F→i 7 #T +i3# 归，用T→T*F 8 #E +i3# 归，用E→T 9 #E+ i3# 进 编译原理

27 步骤 符号栈 输入串 动作 9 #E+ i3# 进 10 #E+i3 # 进 11 #E+F # 归，用F→i
G(E)： E  T | E+T T  F | T*F F  (E) | i 步骤 符号栈 输入串 动作 #E i3# 进 10 #E+i3 # 进 11 #E+F # 归，用F→i 12 #E+T # 归，用T→F 13 #E # 归，用E→E+T 14 #E # 接受 编译原理

28 G(E)： E  i| E+E|E-E|E*E|E/E|(E)
5.2 算符优先分析 四则运算的优先规则： 先乘除后加减，同级从左到右 考虑二义文法文法G(E)： G(E)： E  i| E+E|E-E|E*E|E/E|(E) 它的句子有几种不同的规范规约。 归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。 如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。 编译原理

29 例如：句子i+i-i*(i+i) E i ( ) * + - 编译原理

30 E i ( ) * + - 返回 编译原理

31 句子i+i-i*(i+i)的归约过程是： (1) i+i-i*(i+i) (2) E+i-i*(i+i) (3) E+E-i*(i+i)
(6) E-E*(E+i) (7) E-E*(E+E) (8) E-E*(E) (9) E-E*E (10) E-E (11) E 编译原理

32 起决定作用的是相邻的两个算符之间的优先关系。 所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。
编译原理

33 首先必须定义任何两个可能相继出现的终结符a与b的优先关系 三种关系
a  b a的优先级低于b a  b a的优先级等于b a  b a的优先级高于b 注意：与数学上的<>=不同 +  + a  b并不意味着b  a，如 (  + 和 +  ( 编译原理

34 5.2.1 算符优先文法及优先表构造 一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：
算符优先文法及优先表构造 一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部： …QR… 则我们称该文法为算符文法。 约定： a、b代表任意终结符； P、Q、R代表任意非终结符； ‘…’代表由终结符和非终结符组成的任意序列，包括空字。 编译原理

35 假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：
1. ab 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式； 2. ab 当且仅当G中含有形如P→…aR…的产生式， 而R b…或R Qb…； 3. ab 当且仅当G中含有形如P→…Rb…的产生式，而 R …a或R …aQ。 如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一： ab，ab， ab 则称G是一个算符优先文法。 编译原理

36 例:考虑下面的文法G(E)： (1) E→E+T | T (2) T→T*F | F (3) F→P  F | P
(4) P→(E) | i 由第(4)条规则，有 ‘(’‘)’； 由规则E→E＋T和TT*F， 有 ＋*； 由(2) T→T*F 和(3) F→P  F ，可得*↑； 由(1)E→E＋T和E  E+T，可得++； 由(3)F→PF和F  PF，可得↑↑。 由(4)P→(E)和 EE+TT+TT*F+TF*F+T P↑F*F+Ti↑F*F+T 有 (+、(*、(↑和(i。 编译原理

37 优先关系表 编译原理

38 通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。
1. ab 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式； 确定满足关系和的所有终结符对： 2. ab 当且仅当G中含有形如P→…aR…的产生式， 而R b…或R Qb…； 3. ab 当且仅当G中含有形如P→…Rb…的产生式，而 R …a或R …aQ。 编译原理

39 通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。 确定满足关系和的所有终结符对：
首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)： ab 当且仅当G中含有形如P→…aR…的产生式， 而R b…或R Qb…； 编译原理

40 通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。 确定满足关系和的所有终结符对：
首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)： 3. ab 当且仅当G中含有形如P→…Rb…的产生式，而 R …a或R …aQ。 编译原理

41 通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。 确定满足关系和的所有终结符对：
首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)： 比较 比较 编译原理

42 有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。
假定有个产生式的一个候选形为 …aP… 那么，对任何bFIRSTVT(P)，有 ab。 …Pb… 那么，对任何aLASTVT(P)，有 ab。 编译原理

43 首先讨论构造集合FIRSTVT(P)的算法。 按其定义，可用下面两条规则来构造集合FIRSTVT(P)：
1. 若有产生式P→a…或P→Qa…，则 aFIRSTVT(P)； 2. 若aFIRSTVT(Q)，且有产生式P→Q…， 则aFIRSTVT(P)。 编译原理

44 数据结构： 布尔数组F[P，a]，使得F[P，a]为真的条件是， 当且仅当aFIRSTVT(P)。开始时，按上述的 规则(1)对每个数组元素F[P，a]赋初值。 栈STACK，把所有初值为真的数组元素F[P， a]的符号对(P，a)全都放在STACK之中。 编译原理

45 运算： 如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如 P→Q…
的产生式，若F[P，a]为假，则变其值为真且将(P，a)推进STACK栈。 上述过程必须一直重复，直至栈STACK拆空为止。 编译原理

46 如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：
PROCEDURE INSERT(P，a)； IF NOT F[P，a] THEN BEGIN F[P，a]:=TRUE； 把(P，a)下推进STACK栈 END； 编译原理

47 主程序： BEGIN FOR 每个非终结符P和终结符a DO F[P，a]:=FALSE；
FOR 每个形如P→a…或P→Qa…的产生式 DO INSERT(P，a)； WHILE STACK 非空 DO 把STACK的顶项，记为(Q，a)，上托出去； FOR 每条形如P→Q…的产生式 DO END OF WHILE； END 编译原理

48 FIRSTVT(P)＝{a | F[P，a]=TRUE}
这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。 FIRSTVT(P)＝{a | F[P，a]=TRUE} 同理，可构造计算LASTVT的算法。 编译原理

49 按其定义，可用下面两条规则来构造集合LASTVT(P)：
1. 若有产生式P→… a或P→ … aQ，则a LASTVT(P)； 2. 若a LASTVT(Q)，且有产生式P→… Q ， 则a LASTVT(P)。 编译原理

50 使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：
编译原理

51 IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符
FOR 每条产生式P→X1X2…Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2； IF Xi为终结符而Xi+1为非终结符 THEN FOR FIRSTVT(Xi+1)中的每个a DO 置 Xia； IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END 编译原理

52 1. 计算文法G的FIRSTVT和LASTVT; 2. 构造优先关系表; 3. G是算符优先文法吗?
例: 考虑下面的文法G(E)： (1) E→E+T | T (2) T→T*F | F (3) F→P  F | P (4) P→(E) | i 1. 计算文法G的FIRSTVT和LASTVT; 2. 构造优先关系表; 3. G是算符优先文法吗? 编译原理

53 编译原理

54 G的算符优先关系表 结论: G是算符优先文法 编译原理

55 回顾 定义任何两个可能相继出现的终结符a与b的优先关系 三种关系 注意：与数学上的<>=不同，a  b并不意味着b  a
编译原理

56 假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：
1. ab 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式； 2. ab 当且仅当G中含有形如P→…aR…的产生式， 而R b…或R Qb…； 3. ab 当且仅当G中含有形如P→…Rb…的产生式，而 R …a或R …aQ。 如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一： ab，ab， ab 则称G是一个算符优先文法。 编译原理

57 通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。 确定满足关系和的所有终结符对：
首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)： 比较 比较 编译原理

58 有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。
假定有个产生式的一个候选形为 …aP… 那么，对任何bFIRSTVT(P)，有 ab。 …Pb… 那么，对任何aLASTVT(P)，有 ab。 编译原理

59 首先讨论构造集合FIRSTVT(P)的算法。 按其定义，可用下面两条规则来构造集合FIRSTVT(P)：
1. 若有产生式P→a…或P→Qa…，则 aFIRSTVT(P)； 2. 若aFIRSTVT(Q)，且有产生式P→Q…， 则aFIRSTVT(P)。 编译原理

60 按其定义，可用下面两条规则来构造集合LASTVT(P)：
1. 若有产生式P→… a或P→ … aQ，则a LASTVT(P)； 2. 若a LASTVT(Q)，且有产生式P→… Q ， 则a LASTVT(P)。 编译原理

61 使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：
编译原理

62 IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符
FOR 每条产生式P→X1X2…Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2； IF Xi为终结符而Xi+1为非终结符 THEN FOR FIRSTVT(Xi+1)中的每个a DO 置 Xia； IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END 编译原理

63 5.2.2 算符优先分析算法 可归约串，句型，短语，直接短语，句柄，规范归约。
算符优先分析算法 可归约串，句型，短语，直接短语，句柄，规范归约。 一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。 最左素短语是指处于句型最左边的那个素短语。 编译原理

64 考虑下面的文法G(E)： 句型：T+F*P+i 短语： 直接短语： 句柄： 素短语： 最左素短语： T , F , P , i , F*P,
(1) E→E+T | T (2) T→T*F | F (3) F→P  F | P (4) P→(E) | i 句型：T+F*P+i 短语： 直接短语： 句柄： 素短语： 最左素短语： T , F , P , i , F*P, T+F*P , T+F*P+i T , F , P , i T F*P , i F*P 编译原理

65 算符优先文法句型(括在两个＃之间)的一般形式写成： #N1a1N2a2…NnanNn+1#
其中，每个ai都是终结符，Ni是可有可无的非终结符。 定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 Njaj…NiaiNi+1， aj-1aj aj aj+1，…，ai-1ai aiai+1 编译原理

66 使用一个符号栈S，用它寄存终结符和非终结符，k代表符号栈S的使用深度。
算符优先分析算法 使用一个符号栈S，用它寄存终结符和非终结符，k代表符号栈S的使用深度。 编译原理

67 IF S[k]VT THEN j:=k ELSE j:=k-1; WHILE S[j]a DO BEGIN Q:=S[j];
REPEAT 把下一个输入符号读进a中； IF S[k]VT THEN j:=k ELSE j:=k-1; WHILE S[j]a DO BEGIN Q:=S[j]; IF S[j-1]VT THEN j:=j-1 ELSE j:=j-2 UNTIL S[j]Q; 把S[j+1]…S[k]归约为某个N； k:=j+1; S[k]:=N END OF WHILE; IF S[j]a OR S[j]a THEN BEGIN k:=k+1;S[k]:=a END ELSE ERROR /*调用出错诊察程序*/ UNTIL a=‘#’ 自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。 N → X X … Xk-j ↕ ↕ ↕ S[j+1] S[j+2] … S[k] 编译原理

68 在算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：# N #。
编译原理

69 算符优先分析一般并不等价于规范归约。 E F + * T i P E + * i T P 考虑下面的文法G(E)：
(1) E→E+T | T (2) T→T*F | F (3) F→P  F | P (4) P→(E) | i 的句子i+i*i+i 编译原理

70 算符优先分析法是一种广为应用、行之 有效的方法。
算符优先分析法特点： 优点: 简单，快速 缺点: 可能错误接受非法句子，能力有限. 算符优先分析法是一种广为应用、行之 有效的方法。 用于分析各类表达式 ALGOL 60 编译原理

71 5.2.3 优先函数 把每个终结符与两个自然数f()与g()相对应，使得 优点:便于比较，节省空间；
缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。 编译原理

72 文法G(E) (1) E→E+T | T (2) T→T*F | F (3) F→P  F | P (4) P→(E) | i
的优先函数如下表 编译原理

73 f(a)=g(a)，f(a)>g(b)， f(b)=g(a)，f(b)=g(b) 导致如下矛盾:
有许多优先关系表不存在优先函数，如： 不存在对应的优先函数f和g 假定存在f和g，则有 f(a)=g(a)，f(a)>g(b)， f(b)=g(a)，f(b)=g(b) 导致如下矛盾: f(a) > g(b) = f(b) = g(a) = f(a) 如果优先函数存在，则不唯一(无穷多) 编译原理

74 如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数:
1 对于每个终结符a，令其对应两个符号fa和ga，画一以所有符号和为结点的方向图。如果ab，则从fa画一条弧至gb，如果ab，则画一条弧从gb至fa 。 2 对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)，赋给ga的数作为g(a)。 3 检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数。 编译原理

75 现在必须证明：若ab，则f(a)＝g(b)；若ab，则f(a)< g(b)；若ab，则f(a)> g(b)。
1 对于每个终结符a，令其对应两个符号fa和ga，画一以所有符号和为结点的方向图。如果ab，则从fa画一条弧至gb，如果ab，则画一条弧从gb至fa 。 现在必须证明：若ab，则f(a)＝g(b)；若ab，则f(a)< g(b)；若ab，则f(a)> g(b)。 第一个关系可从函数的构造直接获得。因为，若ab，则既有从fa到gb的弧，又有从gb到fa的弧。所以，fa和gb所能到达的结是全同的。 至于ab和ab的情形，只须证明其一。 编译原理

76 如果ab，则有从fa到gb的弧。也就是，gb能到达的任何结fa也能到达。因此，f(a) g(b)。
我们将指出，如果f(a)＝g(b)，则根本不存在优先函数。假若f(a)＝g(b)，那么必有如下的回路： 编译原理

77 f’(a)> g’(b) f’(a1) g’(b1) …  f’(am) g’(bm) f’(a)
因此有 ab, a1b, a1b1, …, ambm, abm 对任何优先函数f’和g’来说，必定有 f’(a)> g’(b) f’(a1) g’(b1) …  f’(am) g’(bm) f’(a) 从而导致f’(a)> f’(a)，产生矛盾。因此，不存在优先函数f和g。 编译原理

78 例:取前面文法G(E) (1) E→E+T | T (2) T→T*F | F (3) F→P  F | P (4) P→(E) | i
编译原理

79 f+ f* f fi g+ g* g gi 编译原理

80 回顾 语法分析的方法： 算符优先分析法：按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 自下而上分析法(Bottom-up)
基本思想：从输入串开始，逐步进行“归约”， 直到文法的开始符号。即从树末端开始，构造语 法树。所谓归约，是指根据文法的产生式规则， 把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合 性质进行语法分析。适合分析表达式。 优先关系表的构造：FIRSTVT, LASTVT 优先函数 算符优先分析法 编译原理

81 规范归约 定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且 则称是句型相对于非终结符A的短语。
特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。 编译原理

82 定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 
2 0为文法的开始符号，即0=S 3 对任何i，0  i  n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。 编译原理

83 5.3 LR分析法 LR分析法：1965年 由Knuth提出 产生分析表 分析表产生器 分析表 文法 LR分析器工作 LR分析总 控程 序
输入 输出 编译原理

84 主要介绍 1. 总控程序(LR分析器)的处理思想 2. LR分析表的构造方法及原理 编译原理

85 5.3.1 LR分析器 规范归约的关键问题是寻找句柄. “历史”：已移入符号栈的内容 “展望”：根据产生式推测未来可能遇到的输入符号
“现实”：当前的输入符号 编译原理

86 LR分析方法：把"历史"及"展望"综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作
a1a2ai  an# 输入串 状态 符号 分析栈 LR分析 程 序 输出 action goto LR分析表 编译原理

87 LR分析器的核心是一张分析表： ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作.
GOTO[s，X]：状态s面对文法符号X时，下一状态是什么 编译原理

88 每一项ACTION[s，a]所规定的四种动作:
1. 移进 把(s，a)的下一状态s’和输入符号a推进栈，下一输入符号变成现行输入符号. 2. 归约 指用某产生式A进行归约. 假若的长度为r， 归约动作是， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s’=GOTO[sm-r, A]和文法符号A推进栈. 3. 接受 宣布分析成功，停止分析器工作. 4. 报错 编译原理

89 (s0 s1  sm ，# X1  Xm ，aiai+1  an #)
分析开始时: 状态 已归约串 输入串 (s0， #， a1a2  an #) 以后每步的结果可以表示为: (s0 s1  sm ，# X1  Xm ，aiai+1  an #) 编译原理

90 (s0 s1  sm ，# X1  Xm ，aiai+1  an #)
分析器根据ACTION(sm , ai)确定下一步动作 1. 若ACTION(sm , ai)为移进，且s=GOTO(sm, ai),，则三元式格局变为: (s0 s1  sms ，# X1  Xm ai，ai+1  an #)) 2. 若ACTION(sm , ai)为按A归约，三元式变为: (s0 s1  sm-rs ，# X1  Xm-rA ，aiai+1  an #)) 此处, s=GOTO(sm-r, A), r为的长度, = Xm-r+1 Xm 3. 若ACTION(sm , ai)为"接受"，则三元式不再变化，变化过程终止，宣布分析成功. 4. 若ACTION(sm , ai)为"报错"，则三元式变化过程终止，报告错误. (s0 s1  sm-r sm-r+1  sm ，# X1  Xm-r Xm-r+1  Xm ，aiai+1  an #) (s0 s1  sm-r ，# X1  Xm-r，aiai+1  an #)) (s0 s1  sm-rs ，# X1  Xm-rA ，aiai+1  an #)) 编译原理

91 LR分析器示例： 文法G(E)： (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i (1) E→E＋T
编译原理

92 其LR分析表为: 编译原理

93 假定输入串为i*i+i， LR分析器的工作过程:
步骤 状态 符号 输入串 (1) 0 # i*i+i# (2) 05 #i *i+i# (3) 03 #F *i+i# (4) 02 #T *i+i# (5) 027 #T* i+i# T * F i 编译原理

94 假定输入串为i*i+i， LR分析器的工作过程:
步骤 状态 符号 输入串 (5) 027 #T* i+i# (6) #T*i +i# (7) #T*F +i# (8) 02 #T +i# (9) 01 #E +i# (10) 016 #E+ i# E + T * T F i F i 编译原理

95 E E + T T F * T F i F i i 步骤 状态 符号 输入串 (10) 016 #E+ i#
步骤 状态 符号 输入串 (10) 016 #E+ i# (11) #E+i # (12) #E+F # (13) #E+T # (14) 01 #E # (15) 接受 E E + T T F * T F i F i i 编译原理

96 定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为LR文法。
定义：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法. 非LR结构 LR文法不是二义的，二义文法肯定不会是LR的。 S  iCtS | iCtSeS 栈 输入 …iCtS e…# 编译原理

97 5.3.2 LR(0)项目集族和LR(0)分析表的构造 假定是文法G的一个句子，我们称序列 n， n-1， ，0
是的一个规范归约，如果此序列满足： 1 n=  2 0为文法的开始符号，即0=S 3 对任何i，0  i  n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。 编译原理

98 5.3.2 LR(0)项目集族和LR(0)分析表的构造 栈内永远不会出现句柄之后的符号！ 规范归约过程中
栈内的符号串和扫描剩下的输入符号串构成了一个规范句型 栈内的如果出现句柄，句柄一定在栈的顶部 X • a• 句柄 • 柄 句 • a• • • • 柄 句 a• • • 句 • 柄• • • 栈内永远不会出现句柄之后的符号！ 编译原理

99 5.3.2 LR(0)项目集族和LR(0)分析表的构造 字的前缀：是指字的任意首部，如字abc的前缀有，a，ab，abc
活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型，为句柄，如果=u1u2…ur，则符号串u1u2…ui(1ir)是的活前缀。(必为终结符串) 对于一个文法G, 可以构造一个DFA,它能识别G的所有活前缀. 编译原理

100 指导思想——目标驱动 踢足球 “如果你不知道怎样踢球，就往球门方向踢 ” ——施拉普纳 LR分析
“如果你不知道怎样分析，就保证栈中总是活前缀” 一个语言都有哪些活前缀? 那些字符串是活前缀? 能不能构造一个DFA来识别活前缀? 编译原理

101 文法G的每个产生式的右部添加一个圆点称为G的LR(0)项目 如:AXYZ有四个项目：
A.XYZ AX.YZ AXY.Z AXYZ. A . 称为"归约项目" 归约项目 S’ . 称为"接受项目" A .a (aVT) 称为"移进项目" A .B (BVN) 称为"待约项目". 编译原理

102 文法G(S) 该文法的项目有： S→E E→aA|bB A→cA|d B→cB|d
1. S→·E S→E· E→·aA E→a·A E→aA· A→·cA 7. A→c·A A→cA· A→·d A→d· E→·bB 12. E→b·B 13. E→bB· 14. B→·cB 15. B→c·B B→cB· 17. B→·d B→d· 编译原理

103 状态j为XX1 … Xi-1Xi .Xi+1 … Xn ， 则从状态i画一条标志为Xi的有向边到状态j；
构造识别文法所有活前缀的NFA方法 1. 若状态i为XX1 … Xi-1.Xi … Xn ， 状态j为XX1 … Xi-1Xi .Xi+1 … Xn ， 则从状态i画一条标志为Xi的有向边到状态j； 2. 若状态i为X .A ，A为非终结符， 则从状态i画一条边到所有状态A.。 把识别文法所有活前缀的NFA确定化。 编译原理

104 6 7 8 9 10 4 5 3 1 2 11 12 13 14 15 16 18 17  a A E b B c d 识别活前缀的NFA 编译原理

105 A c a E b d B 识别活前缀的DFA 8: A→cA· 4: A→c·A A→·cA A→·d 10: A→d· 2: E→a·A
0: S→·E E→·aA E→·bB 4: A→c·A A→·cA A→·d 2: E→a·A 1: S→E· 3: E→b·B B→·cB B→·d 5: B→c·B 11: B→d· 9: B→cB· 7: E→bB· 10: A→d· 6: E→aA· 8: A→cA· c b E a d A B 识别活前缀的DFA 编译原理

106 构成识别一个文法活前缀的DFA的项目集 (状态)的全体称为文法的LR(0)项目集规范 族。
编译原理

107 有效项目 我们说项目A 1.2对活前缀1是有效的，其条件是存在规范推导
在任何时候，分析栈中的活前缀X1X2 … Xm的有效项目集正是栈顶状态Sm所代表的那个集合。也正是从识别活前缀的DFA的初态出发，读出X1X2 … Xm后到达的那个项目集(状态)。 ζzeta ηeta θtheta ξxi ψpsi φphi 编译原理

108 结论: 若项目A .B对活前缀=是有 效的且B  是一个产生式，则项目B  .对=也是有效的。
设 ，那么 所以，B  .对=也是有效的。 编译原理

109 项目A 1.2对活前缀1是有效的，其条件是存在规范推导 文法G(S)
S→E E→aA|bB A→cA|d B→cB|d 考虑： 项目：B  c.B B  . cB B  . d 活前缀：bc S’ E  bB  bcB S’ E  bB  bcB bccB S’ E  bB  bcB  bcd 编译原理

110 LR(0)项目集规范族的构造 假定文法G是一个以S为开始符号的文法，我们构造一个G，它包含了整个G，但它引进了一个不出现在G中的非终结符S，并加进一个新产生式S→S，而这个S是G的开始符号。那么，我们称G是G的拓广文法。这样，便会有一个仅含项目S→S.的状态，这就是唯一的“接受”态。 编译原理

111 假定I是文法G的任一项目集，定义和构造I的闭包CLOSURE(I)如下： 1. I的任何项目都属于CLOSURE(I)；
2. 若A→·B属于CLOSURE(I)，那么，对任何关于B的产生式B→，项目B→·也属于CLOSURE(I)； 3. 重复执行上述两步骤直至CLOSURE(I) 不再增大为止。 2. 若状态i为X .A ，A为非终结符， 则从状态i画一条边到所有状态A.。 P50：NFA确定化 设I是的状态集的一个子集，定义I的-闭包-closure(I)为: i) 若sI，则s-closure(I)； ii) 若sI，则从s出发经过任意条弧而能到达的任何状态s’都属于-closure(I) -closure(I)=I{s’|从某个sI出发经过任意条弧能到达s’} 编译原理

112 为了识别活前缀，我们定义一个状态转换函数GO是一个状态转换函数。I是一个项目集，X是一个文法符号。函数值GO(I，X)定义为：
GO(I，X)＝CLOSURE(J) 其中 J＝{任何形如A→X·的项目| A→ · X属于I}。 直观上说，若I是对某个活前缀  有效的项目集，那么，GO(I，X)便是对 X 有效的项目集。 P50：设a是中的一个字符，定义 Ia= -closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。 编译原理

113 文法G(S) S→E E→aA|bB A→cA|d B→cB|d I0={S→·E, E→·aA, E→·bB}
GO(I0, E)= closure(J)=closure({S’→E·}) = {S’→E·} = I1 GO(I0, a)= closure(J)=closure({E→a·A}) ={ E→a·A, A→·cA, A→·d} )=I2 GO(I0, b)= closure(J)=closure ({E →b.B}) ={E →b.B, B→.cB, B→.d}= I3 编译原理

114 构造文法G的拓广文法G的LR(0)项目集规范族算法：
PROCEDURE ITEMSETS(G)； BEGIN C:={CLOSURE({S·S})}； REPEAT FOR C中每个项目集I和G的每个符号X DO IF GO(I，X)非空且不属于C THEN 把GO(I，X)放入C族中; UNTIL C 不再增大 END 转换函数GO把项目集连接成一个DFA转换图. 编译原理

115 c A d c d a A E B b d c d B c 8: A→cA· 4: A→c·A A→·cA A→·d 10: A→d·
2: E→a·A A→·cA A→·d a 6: E→aA· A 0: S→·E E→·aA E→·bB E 1: S→E· 3: E→b·B B→·cB B→·d B b 7: E→bB· c d 11: B→d· 5: B→c·B B→·cB B→·d d 9: B→cB· B c 编译原理

116 回顾：规范归约 定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且
则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。 编译原理

117 定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 
2 0为文法的开始符号，即0=S 3 对任何i，0  i  n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。 编译原理

118 5.3 LR分析法 LR分析法：1965年 由Knuth提出 产生分析表 分析表产生器 分析表 文法 LR分析器工作 LR分析总 控程 序
输入 输出 编译原理

119 LR分析方法：把"历史"及"展望"综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作
a1a2ai  an# 输入串 状态 符号 分析栈 LR分析 程 序 输出 action goto LR分析表 编译原理

120 LR分析器的核心是一张分析表： ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作.
GOTO[s，X]：状态s面对文法符号X时，下一状态是什么 编译原理

121 每一项ACTION[s，a]所规定的四种动作:
1. 移进 把(s，a)的下一状态s’和输入符号a推进栈，下一输入符号变成现行输入符号. 2. 归约 指用某产生式A进行归约. 假若的长度为r， 归约动作是， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s’=GOTO[sm-r, A]和文法符号A推进栈. 3. 接受 宣布分析成功，停止分析器工作. 4. 报错 编译原理

122 (s0 s1  sm ，# X1  Xm ，aiai+1  an #)
分析开始时: 状态 已归约串 输入串 (s0， #， a1a2  an #) 以后每步的结果可以表示为: (s0 s1  sm ，# X1  Xm ，aiai+1  an #) 编译原理

123 (s0 s1  sm ，# X1  Xm ，aiai+1  an #)
分析器根据ACTION(sm , ai)确定下一步动作 1. 若ACTION(sm , ai)为移进，且s=GOTO(sm, ai),，则三元式格局变为: (s0 s1  sms ，# X1  Xm ai，ai+1  an #)) 2. 若ACTION(sm , ai)为按A归约，三元式变为: (s0 s1  sm-rs ，# X1  Xm-rA ，aiai+1  an #)) 此处, s=GOTO(sm-r, A), r为的长度, = Xm-r+1 Xm 3. 若ACTION(sm , ai)为"接受"，则三元式不再变化，变化过程终止，宣布分析成功. 4. 若ACTION(sm , ai)为"报错"，则三元式变化过程终止，报告错误. (s0 s1  sm-r sm-r+1  sm ，# X1  Xm-r Xm-r+1  Xm ，aiai+1  an #) (s0 s1  sm-r ，# X1  Xm-r，aiai+1  an #)) (s0 s1  sm-rs ，# X1  Xm-rA ，aiai+1  an #)) 编译原理

124 5.3.2 LR(0)项目集族和LR(0)分析表的构造 栈内永远不会出现句柄之后的符号！ 规范归约过程中
栈内的符号串和扫描剩下的输入符号串构成了一个规范句型 栈内的如果出现句柄，句柄一定在栈的顶部 X • a• 句柄 • 柄 句 • a• • • • 柄 句 a• • • 句 • 柄• • • 栈内永远不会出现句柄之后的符号！ 编译原理

125 5.3.2 LR(0)项目集族和LR(0)分析表的构造 字的前缀：是指字的任意首部，如字abc的前缀有，a，ab，abc
活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型，为句柄，如果=u1u2…ur，则符号串u1u2…ui(1ir)是的活前缀。(必为终结符串) 对于一个文法G, 可以构造一个DFA,它能识别G的所有活前缀. 编译原理

126 构造识别文法所有活前缀的NFA方法 1. 若状态i为XX1 … Xi-1.Xi … Xn ，
状态j为XX1 … Xi-1Xi .Xi+1 … Xn ， 则从状态i画一条标志为Xi的有向边到状态j； 2. 若状态i为X .A ，A为非终结符， 则从状态i画一条边到所有状态A.。 把识别文法所有活前缀的NFA确定化。 编译原理

127 文法G(S) 该文法的项目有： S→E E→aA|bB A→cA|d B→cB|d
1. S→·E S→E· E→·aA E→a·A E→aA· A→·cA 7. A→c·A A→cA· A→·d A→d· E→·bB 12. E→b·B 13. E→bB· 14. B→·cB 15. B→c·B B→cB· 17. B→·d B→d· 编译原理

128 6 7 8 9 10 4 5 3 1 2 11 12 13 14 15 16 18 17  a A E b B c d 识别活前缀的NFA 编译原理

129 A c a E b d B 识别活前缀的DFA 8: A→cA· 4: A→c·A A→·cA A→·d 10: A→d· 2: E→a·A
0: S→·E E→·aA E→·bB 4: A→c·A A→·cA A→·d 2: E→a·A 1: S→E· 3: E→b·B B→·cB B→·d 5: B→c·B 11: B→d· 9: B→cB· 7: E→bB· 10: A→d· 6: E→aA· 8: A→cA· c b E a d A B 识别活前缀的DFA 编译原理

130 LR(0)项目集规范族的构造 假定文法G是一个以S为开始符号的文法，我们构造一个G，它包含了整个G，但它引进了一个不出现在G中的非终结符S，并加进一个新产生式S→S，而这个S是G的开始符号。那么，我们称G是G的拓广文法。这样，便会有一个仅含项目S→S.的状态，这就是唯一的“接受”态。 编译原理

131 假定I是文法G的任一项目集，定义和构造I的闭包CLOSURE(I)如下： 1. I的任何项目都属于CLOSURE(I)；
2. 若A→·B属于CLOSURE(I)，那么，对任何关于B的产生式B→，项目B→·也属于CLOSURE(I)； 3. 重复执行上述两步骤直至CLOSURE(I) 不再增大为止。 2. 若状态i为X .A ，A为非终结符， 则从状态i画一条边到所有状态A.。 P50：NFA确定化 设I是的状态集的一个子集，定义I的-闭包-closure(I)为: i) 若sI，则s-closure(I)； ii) 若sI，则从s出发经过任意条弧而能到达的任何状态s’都属于-closure(I) -closure(I)=I{s’|从某个sI出发经过任意条弧能到达s’} 编译原理

132 为了识别活前缀，我们定义一个状态转换函数GO是一个状态转换函数。I是一个项目集，X是一个文法符号。函数值GO(I，X)定义为：
GO(I，X)＝CLOSURE(J) 其中 J＝{任何形如A→X·的项目| A→ · X属于I}。 直观上说，若I是对某个活前缀  有效的项目集，那么，GO(I，X)便是对 X 有效的项目集。 P50：设a是中的一个字符，定义 Ia= -closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。 编译原理

133 文法G(S) S→E E→aA|bB A→cA|d B→cB|d I0={S→·E, E→·aA, E→·bB}
GO(I0, E)= closure(J)=closure({S’→E·}) = {S’→E·} = I1 GO(I0, a)= closure(J)=closure({E→a·A}) ={ E→a·A, A→·cA, A→·d} )=I2 GO(I0, b)= closure(J)=closure ({E →b.B}) ={E →b.B, B→.cB, B→.d}= I3 编译原理

134 构造文法G的拓广文法G的LR(0)项目集规范族算法：
PROCEDURE ITEMSETS(G)； BEGIN C:={CLOSURE({S·S})}； REPEAT FOR C中每个项目集I和G的每个符号X DO IF GO(I，X)非空且不属于C THEN 把GO(I，X)放入C族中; UNTIL C 不再增大 END 转换函数GO把项目集连接成一个DFA转换图. 编译原理

135 c A d c d a A E B b d c d B c 8: A→cA· 4: A→c·A A→·cA A→·d 10: A→d·
2: E→a·A A→·cA A→·d a 6: E→aA· A 0: S→·E E→·aA E→·bB E 1: S→E· 3: E→b·B B→·cB B→·d B b 7: E→bB· c d 11: B→d· 5: B→c·B B→·cB B→·d d 9: B→cB· B c 编译原理

136 LR(0)分析表的构造 假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况：
1) 既含移进项目又含归约项目， 2) 含有多个归约项目 则称G是一个LR(0)文法。 编译原理

137 构造LR(0)分析表的算法 令每个项目集Ik的下标k作为分析器的状态，包含项目S→·S的集合Ik的下标k为分析器的初态。 编译原理

138 分析表的ACTION和GOTO子表构造方法：
1. 若项目A→·a属于Ik且GO(Ik, a)＝Ij，a为终结符，则置ACTION[k,a] 为“sj”。 2. 若项目A→·属于Ik，那么，对任何终结符a(或结束符#)，置ACTION[k,a]为 “rj”(假定产生式A→是文法G的第j个产生式)。 3. 若项目S→S·属于Ik，则置ACTION[k,#]为 “acc”。 4. 若GO(Ik,A)＝Ij，A为非终结符，则置GOTO[k,A]=j。 5. 分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。 编译原理

139 文法G(S) S→E E→aA|bB A→cA|d B→cB|d 编译原理

140 A c a E b d B 识别活前缀的DFA 8: A→cA· 4: A→c·A A→·cA A→·d 10: A→d· 2: E→a·A
0: S→·E E→·aA E→·bB 4: A→c·A A→·cA A→·d 2: E→a·A 1: S→E· 3: E→b·B B→·cB B→·d 5: B→c·B 11: B→d· 9: B→cB· 7: E→bB· 10: A→d· 6: E→aA· 8: A→cA· c b E a d A B 识别活前缀的DFA 编译原理

141 LR(0)分析表为 编译原理

142 例: 按上表对acccd进行分析 步骤 状态 符号 输入串 1 0 # acccd# 2 02 #a cccd#
步骤 状态 符号 输入串 1 0 # acccd# #a cccd# #ac ccd# #acc cd# #accc d# #acccd # #acccA # #accA # #acA # #aA # #E # 编译原理

143 5.3.3 SLR分析表的构造 LR(0)文法太简单，没有实用价值.
假定一个LR(0)规范族中含有如下的一个项目集(状态)I＝{X→·b，A→·，B→·}。FOLLOW(A)和FOLLOW(B)的交集为，且不包含b，那么，当状态I面临任何输入符号a时，可以: 1. 若a=b，则移进； 2. 若aFOLLOW(A)，用产生式A→进行归约； 3. 若aFOLLOW(B)，用产生式B→进行归约； 4. 此外，报错。 编译原理

144 冲突性动作的这种解决办法叫做SLR(1)解决办法。
假定LR(0)规范族的一个项目集I={A1→·a11，A2→·a22，…，Am→·amm，B1→·，B2→·，…，Bn→·} 如果集合{a1，…，am}，FOLLOW(B1)，…，FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集合有#)，则： 1. 若a是某个ai，i=1,2,…,m，则移进； 2. 若aFOLLOW(Bi)，i=1,2,…,n，则用产生式Bi→进行归约； 3. 此外，报错。 冲突性动作的这种解决办法叫做SLR(1)解决办法。 编译原理

145 首先把G拓广为G，对G构造LR(0)项目 集规范族C和活前缀识别自动机的状态转 换函数GO.
构造SLR(1)分析表方法: 首先把G拓广为G，对G构造LR(0)项目 集规范族C和活前缀识别自动机的状态转 换函数GO. 然后使用C和GO，按下面的算法构造SLR分析表： 令每个项目集Ik的下标k作为分析器的状态，包含项目S→·S的集合Ik的下标k为分析器的初态。 编译原理

146 分析表的ACTION和GOTO子表构造方法：
1. 若项目A→·a属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTION[k,a]为 “sj”； 2. 若项目A→·属于Ik，那么，对任何终结符a，aFOLLOW(A)，置ACTION[k,a]为 “rj”；其中，假定A为文法G的第j个产生式； 3. 若项目S→S·属于Ik，则置ACTION[k,#]为“acc”; 4. 若GO(Ik,A)＝Ij，A为非终结符，则置GOTO[k,A]=j； 5. 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。 编译原理

147 按上述方法构造出的ACTION与GOTO表如果不含多重入口，则称该文法为SLR(1)文法。
使用SLR表的分析器叫做一个SLR分析器。 每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的. 编译原理

148 例5.11 考察下面的拓广文法： (0) S→E (1) E→E+T (2) E→T (3) T→T*F (4) T→F
例5.11 考察下面的拓广文法： (0) S→E (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i 编译原理

149 这个文法的LR(0)项目集规范族为： I0: S→·E E→·E+T E→·T T→·T*F T→·F F→· (E) F→·i
I4: F→(·E) E→·E+T E→·T T→·T*F T→·F F→· (E) F→·i I7: T→T*·F F→·(E) F→·i I8: F→(E·) E→E·+T I9: E→E+T· T→T·*F I5 : F→i· I1: S→E· E→E·+T I6: E→E+·T T→·T*F T→·F F→·(E) F→·i I10: T→T*F· I2: E→T· T→T·*F I11: F→(E)· I3: T→F· 编译原理

150 I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 I10 I11 E + T * i F ( )
编译原理

151 I1、I2和I9都含有“移进－归约”冲突。 FOLLOW(E)＝{#, ), +}， I1: S→E· E→E·+T I2: E→T·
T→T·*F I9: E→E+T· T→T·*F 编译原理

152 其分析表如下: 编译原理

153 非SLR文法示例：考虑如下文法： 计算FOLLOW集合所得到的超前符号集合可能大于实际能出现的超前符号集。 (0) S→S
(2) S→R (3) L→*R (4) L→i (5) R→L 编译原理

154 这个文法的LR(0)项目集规范族为： I6：S→L=·R R→·L L→·*R L→·i I0：S→·S S→·L=R S→·R
I3：S→R· I4：L→*·R R→·L L→·*R L→·i I7：L→*R· I1：S→S· I8：R→L· I9：S→L=R· I5：L→i· 编译原理

155 编译原理

156 I2含有“移进－归约”冲突。 FOLLOW(R)＝{#, =}， I2：S→L·=R R→L· 编译原理

157 当状态2显现于栈顶而且面临输入符号为‘=’时，实际上不能用对栈顶L进行归约。 不含“R=”为前缀的规范句型 有含“*R=”为前缀的规范句型
考虑如下文法： (0) S→S (1) S→L=R (2) S→R (3) L→*R (4) L→i (5) R→L 当状态2显现于栈顶而且面临输入符号为‘=’时，实际上不能用对栈顶L进行归约。 不含“R=”为前缀的规范句型 有含“*R=”为前缀的规范句型 I2：S→L·=R R→L· 编译原理

158 SLR在方法中,如果项目集Ii含项目A
SLR在方法中,如果项目集Ii含项目A.而且下一输入符号aFOLLOW(A),则状态i面临a时,可选用“用A归约”动作。但在有些情况下,当状态i显现于栈顶时,栈里的活前缀未必允许把归约为A，因为可能根本就不存在一个形如“Aa”的规范句型。因此，在这种情况下，用“ A ”归约不一定合适。 FOLLOW集合提供的信息太泛！ 编译原理

159 规范LR分析表的构造 我们需要重新定义项目，使得每个项目都附带有k个终结符。每个项目的一般形式是[A→·, a1a2…ak] ，这样的一个项目称为一个LR(k)项目。项目中的 a1a2…ak 称为它的向前搜索符串(或展望串)。 向前搜索符串仅对归约项目[A→·，a1a2…ak]有意义。对于任何移进或待约项目[A→·, a1a2…ak], ，搜索符串 a1a2…ak 没有作用。 编译原理

160 我们只对k1的情形感兴趣，向前搜索(展望)一个符号就多半可以确定“移进”或“归约”。
归约项目[A→·, a1a2…ak]意味着：当它所属的状态呈现在栈顶且后续的k个输入符号为 a1a2…ak 时，才可以把栈顶上的归约为A。 我们只对k1的情形感兴趣，向前搜索(展望)一个符号就多半可以确定“移进”或“归约”。 形式上我们说一个LR(1)项目[A→·, a]对于活前缀是有效的，如果存在规范推导 其中，1) ＝；2) a是的 第一个符号，或者a为#而为。 编译原理

161 为构造有效的LR(1)项目集族我们需要两个函数CLOSURE和GO。
编译原理

162 证明：若项目[A→·B, a]对＝有效， 则有规范推导
[A→·B, a]对活前缀＝是有效的，则对于每个形如B的产生式， 对任何bFIRST(a)，[B→·, b]对也是有效的。 证明：若项目[A→·B, a]对＝有效， 则有规范推导 ζ [zi:tə] η [i:tə] ξ [ksai] φ [fai] χ [kai] ψ [psai] 编译原理

163 项目集I 的闭包CLOSURE(I)构造方法：
2. 若项目[A→·B, a]属于CLOSURE(I)，B→ 是一个产生式，那么，对于FIRST(a) 中的每个终结符b，如果[B→·, b]原来不在CLOSURE(I)中，则把它加进去。 3. 重复执行步骤2，直至CLOSURE(I)不再增大为止。 编译原理

164 令I是一个项目集，X是一个文法符号，函数GO(I，X)定义为： GO(I，X)＝CLOSURE(J) 其中
J＝{任何形如[A→X·, a]的项目 | [A→·X, a]I} 编译原理

165 文法G的LR(1)项目集族C的构造算法：
BEGIN C:={CLOSURE({[S→·S，#]})}; REPEAT FOR C中每个项目集I和G的每个符号X DO IF GO(I，X)非空且不属于C，THEN 把GO(I，X)加入C中 UNTIL C不再增大 END 编译原理

166 构造LR(1)分析表的算法。 令每个Ik的下标k为分析表的状态，令含有[S→·S, #]的Ik的k为分析器的初态。 编译原理

167 动作ACTION和状态转换GOTO构造如下：
1. 若项目[A→·a, b]属于Ik且GO(Ik, a)＝Ij， a为终结符，则置ACTION[k, a]为 “sj”。 2. 若项目[A→·，a]属于Ik，则置ACTION[k, a]为 “rj”；其中假定A→为文法G的第j个产生式。 3. 若项目[S→S·, #]属于Ik，则置ACTION[k, #]为 “acc”。 4. 若GO(Ik，A)＝Ij，则置GOTO[k, A]=j。 5. 分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。 编译原理

168 按上述算法构造的分析表，若不存在多重定义的入口(即，动作冲突)的情形，则称它是文法G的一张规范的LR(1)分析表。
具有规范的LR(1)分析表的文法称为一个LR(1)文法。 LR(1)状态比SLR多， LR(0)SLR  LR(1) 无二义文法 编译原理

169 例 (5.10)的拓广文法G( S) (0) S→S (1) S→BB (2) B→aB (3) B→b 编译原理

170 LR(1)的项目集C和函数GO I0: S’•S, # S•BB, # B•aB, a B•aB, b B •b, a
I5: SBB•, # B a B I2: SB • B, # B•aB, # B •b, # I6: Ba•B, # B•aB, # B •b, # a a b I4: B b •, a/b b b B b a I3: Ba•B, a/b B•aB, a/b B •b, a/b I7: B b •, # I9: B aB•, # B LR(1)的项目集C和函数GO I8: B aB•, a/b 编译原理

171 LR(1)分析表为: 编译原理

172 例: 按上表对aabab进行分析 步骤 状态 符号 输入串 0 0 # aabab# 1 03 #a abab#
步骤 状态 符号 输入串 0 0 # aabab# #a abab# #aa bab# #aab ab# #aaB ab# #aB ab# #B ab# #Ba b# #Baa # #BaB # #BB # #S # acc 编译原理

173 例: 按上表对abab进行分析 步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab#
步骤 状态 符号 输入串 0 0 # abab# #a bab# #ab ab# #aB ab# #B ab# #Ba b# #Bab # #BaB # #BB # #S # acc 编译原理