第五章 语法分析——自下而上分析 自上而下分析法(Top-down) 自下而上分析法(Bottom-up) 国防科技大学计算机系602教研室.

Presentation on theme: "第五章 语法分析——自下而上分析 自上而下分析法(Top-down) 自下而上分析法(Bottom-up) 国防科技大学计算机系602教研室."— Presentation transcript:

1 第五章 语法分析——自下而上分析 自上而下分析法(Top-down) 自下而上分析法(Bottom-up) 国防科技大学计算机系602教研室

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

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

4 E E + E E * E i i i G(E)： E  i| E+E | E-E | E*E | E/E | (E) i*i+i
国防科技大学计算机系602教研室

5 5.1.1 归约 采用“移进－归约”思想进行自下而上分析。
基本思想：用一个寄存符号的先进后出栈， 把输入符号一个一个地移进到栈里，当栈顶 形成某个产生式的候选式时，即把栈顶的这 一部分替换成(归约为)该产生式的左部符号。 国防科技大学计算机系602教研室

6 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 国防科技大学计算机系602教研室

7 国防科技大学计算机系602教研室

8 自下而上分析过程：边输入单词符号，边归约。 核心问题：识别可归约串
S a A c B e A b d b 分析树和语法树不一定一致。 自下而上分析过程：边输入单词符号，边归约。 核心问题：识别可归约串 国防科技大学计算机系602教研室

9 5.1.2 规范归约 定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且
则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。 国防科技大学计算机系602教研室

10 考虑文法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 国防科技大学计算机系602教研室

11 E F T i1 + * i3 i2 在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。 国防科技大学计算机系602教研室

12 可用句柄来对句子进行归约 句型 归约规则 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 国防科技大学计算机系602教研室

13 定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 
2 0为文法的开始符号，即0=S 3 对任何i，0  i  n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。 国防科技大学计算机系602教研室

14 S  aAcBe aAcde  aAbcde  abbcde 显然这是一个最右推导。 规范归约是关于是一个最右推导的逆过程
把上例倒过来写，则得到： S  aAcBe aAcde  aAbcde  abbcde 显然这是一个最右推导。 规范归约是关于是一个最右推导的逆过程 最左归约 规范推导 由规范推导推出的句型称为规范句型。 国防科技大学计算机系602教研室

15 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
国防科技大学计算机系602教研室

16 5.1.3 符号栈的使用和分析树的表示 栈是语法分析的一种基本数据结构。’#’作为栈底符号 考虑文法G(E)： E  T | E+T
5.1.3 符号栈的使用和分析树的表示 栈是语法分析的一种基本数据结构。’#’作为栈底符号 考虑文法G(E)： E  T | E+T T  F | T*F F  (E) | i 输入串为i1*i2+i3 ，分析步骤为： 国防科技大学计算机系602教研室

17 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用F→i
步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用F→i #T *i2+i3# 归，用T→F 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 6 #T*F +i3# 归，用F→i 7 #T +i3# 归，用T→T*F 国防科技大学计算机系602教研室

18 步骤 符号栈 输入串 动作 8 #E +i3# 归，用E→T 9 #E+ i3# 进 10 #E+i3 # 进
步骤 符号栈 输入串 动作 8 #E +i3# 归，用E→T 9 #E+ i3# 进 10 #E+i3 # 进 11 #E+F # 归，用F→i 12 #E+T # 归，用T→F 13 #E # 归，用E→E+T 14 #E # 接受 国防科技大学计算机系602教研室

19 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) 它的句子有几种不同的规范规约。 归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。 如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。 国防科技大学计算机系602教研室

20 例如：句子i+i-i*(i+i) E i ( ) * + - 国防科技大学计算机系602教研室

21 E i ( ) * + - 返回 国防科技大学计算机系602教研室

22 句子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 国防科技大学计算机系602教研室

23 起决定作用的是相邻的两个算符之间的优先关系。 所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。
国防科技大学计算机系602教研室

24 首先必须定义任何两个可能相继出现的终结符a与b的优先关系 三种关系
a  b a的优先级低于b a  b a的优先级等于b a  b a的优先级高于b 注意：与数学上的<>=不同，a  b并不意味着b  a 国防科技大学计算机系602教研室

25 5.2.1 算符优先文法及优先表构造 一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：
算符优先文法及优先表构造 一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部： …QR… 则我们称该文法为算符文法。 约定： a、b代表任意终结符； P、Q、R代表任意非终结符； ‘…’代表由终结符和非终结符组成的任意序列，包括空字。 国防科技大学计算机系602教研室

26 假定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是一个算符优先文法。 国防科技大学计算机系602教研室

27 例:考虑下面的文法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)和(3)，可得*↑； 由(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。 国防科技大学计算机系602教研室

28 优先关系表 国防科技大学计算机系602教研室

29 通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。 确定满足关系和的所有终结符对：
首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)： 国防科技大学计算机系602教研室

30 有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。
假定有个产生式的一个候选形为 …aP… 那么，对任何bFIRSTVT(P)，有 ab。 …Pb… 那么，对任何aLASTVT(P)，有 ab。 国防科技大学计算机系602教研室

31 首先讨论构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)：
1. 若有产生式P→a…或P→Qa…，则 aFIRSTVT(P)； 2. 若aFIRSTVT(Q)，且有产生式P→Q…， 则aFIRSTVT(P)。 国防科技大学计算机系602教研室

32 数据结构： 布尔数组F[P，a]，使得F[P，a]为真的条件是， 当且仅当aFIRSTVT(P)。开始时，按上述的 规则(1)对每个数组元素F[P，a]赋初值。 栈STACK，把所有初值为真的数组元素F[P， a]的符号对(P，a)全都放在STACK之中。 国防科技大学计算机系602教研室

33 运算： 如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如 P→Q…
的产生式，若F[P，a]为假，则变其值为真且将(P，a)推进STACK栈。 上述过程必须一直重复，直至栈STACK拆空为止。 国防科技大学计算机系602教研室

34 如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：
PROCEDURE INSERT(P，a)； IF NOT F[P，a] THEN BEGIN F[P，a]:=TRUE； 把(P，a)下推进STACK栈 END； 国防科技大学计算机系602教研室

35 主程序： 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 国防科技大学计算机系602教研室

36 FIRSTVT(P)＝{a | F[P，a]=TRUE}
这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。 FIRSTVT(P)＝{a | F[P，a]=TRUE} 同理，可构造计算LASTVT的算法。 使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是： 国防科技大学计算机系602教研室

37 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 国防科技大学计算机系602教研室

38 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是算符优先文法吗? 国防科技大学计算机系602教研室

39 国防科技大学计算机系602教研室

40 G的算符优先关系表 结论: G是算符优先文法 国防科技大学计算机系602教研室

41 5.2.2 算符优先分析算法 可归约串，句型，短语，直接短语，句柄，规范归约。
算符优先分析算法 可归约串，句型，短语，直接短语，句柄，规范归约。 一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。 最左素短语是指处于句型最左边的那个素短语。 国防科技大学计算机系602教研室

42 考虑下面的文法G(E)： 句型：T+F*P+i 短语：T+F*P+i, T, F， P, F*P, i, T+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, T, F， P, F*P, i, T+F*P 直接短语：T, F, P, i 句柄：T 素短语： F*P, i 最左素短语： F*P 国防科技大学计算机系602教研室

43 算符优先文法句型(括在两个＃之间)的一般形式写成： #N1a1N2a2…NnanNn+1#
其中，每个ai都是终结符，Ni是可有可无的非终结符。 定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 Njaj…NiaiNi+1， aj-1aj aj aj+1，…，ai-1ai aiai+1 国防科技大学计算机系602教研室

44 使用一个符号栈S，用它寄存终结符和非终结符，k代表符号栈S的使用深度。
算符优先分析算法 使用一个符号栈S，用它寄存终结符和非终结符，k代表符号栈S的使用深度。 1 k:=1; S[k]:=‘#’; 2 REPEAT 把下一个输入符号读进a中； IF S[k]VT THEN j:=k ELSE j:=k-1; WHILE S[j]a DO BEGIN REPEAT Q:=S[j]; IF S[j-1]VT THEN j:=j-1 ELSE j:=j-2 UNTIL S[j]Q; 国防科技大学计算机系602教研室

45 15 IF S[j]a OR S[j]a THEN 16 BEGIN k:=k+1;S[k]:=a END
11 把S[j+1]…S[k]归约为某个N； 12 k:=j+1; 13 S[k]:=N 14 END OF WHILE; 15 IF S[j]a OR S[j]a THEN BEGIN k:=k+1;S[k]:=a END 17 ELSE ERROR /*调用出错诊察程序*/ 18 UNTIL a=‘#’ 国防科技大学计算机系602教研室

46 在算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：# N #。
算法的第11行中的N是指那样一个产生式的左部符号，此产生式的右部和S[j+1]…S[k] 构成如下一一对应关系：自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。 国防科技大学计算机系602教研室

47 算符优先分析一般并不等价于规范归约。 E F + * T i P E + * i T P 国防科技大学计算机系602教研室

48 算符优先分析法是一种广为应用、行之 有效的方法。
算符优先分析法特点： 优点: 简单，快速 缺点: 可能错误接受非法句子，能力有限. 算符优先分析法是一种广为应用、行之 有效的方法。 用于分析各类表达式 ALGOL 60 国防科技大学计算机系602教研室

49 5.2.3 优先函数 把每个终结符与两个自然数f()与g()相对应，使得 优点:便于比较，节省空间；
缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。 国防科技大学计算机系602教研室

50 文法G(E) (1) E→E+T | T (2) T→T*F | F (3) F→P  F | P (4) P→(E) | i
的优先函数如下表 国防科技大学计算机系602教研室

51 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) 如果优先函数存在，则不唯一(无穷多) 国防科技大学计算机系602教研室

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

53 现在必须证明：若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的情形，只须证明其一。 国防科技大学计算机系602教研室

54 如果ab，则有从fa到gb的弧。也就是，gb能到达的任何结fa也能到达。因此，f(a) g(b)。
我们将指出，如果f(a)＝g(b)，则根本不存在优先函数。假若f(a)＝g(b)，那么必有如下的回路： 国防科技大学计算机系602教研室

55 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。 国防科技大学计算机系602教研室

56 例:取前面文法G(E) (1) E→E+T | T (2) T→T*F | F (3) F→P  F | P (4) P→(E) | i
国防科技大学计算机系602教研室

57 f+ f* f fi g+ g* g gi 国防科技大学计算机系602教研室

58 5.3 LR分析法 LR分析法：1965年 由Knuth提出 产生分析表 分析表产生器 分析表 文法 LR分析器工作 LR分析总 控程 序
输入 输出 国防科技大学计算机系602教研室

59 主要介绍 1. 总控程序(LR分析器)的处理思想 2. LR分析表的构造方法及原理 国防科技大学计算机系602教研室

60 5.3.1 LR分析器 规范归约的关键问题是寻找句柄. “历史”：已移入符号栈的内容 “展望”：根据产生式推测未来可能遇到的输入符号
“现实”：当前的输入符号 国防科技大学计算机系602教研室

61 LR分析方法：把"历史"及"展望"综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作
a1a2ai  an# 输入串 状态 符号 分析栈 LR分析 程 序 输出 action goto LR分析表 国防科技大学计算机系602教研室

62 LR分析器的核心是一张分析表： ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作.
GOTO[s，X]：状态s面对文法符号X时，下一状态是什么 国防科技大学计算机系602教研室

63 每一项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. 报错 国防科技大学计算机系602教研室

64 (s0 s1  sm ，# X1  Xm ，aiai+1  an #)
分析开始时: 状态 已归约串 输入串 (s0， #， a1a2  an #) 以后每步的结果可以表示为: (s0 s1  sm ，# X1  Xm ，aiai+1  an #) 国防科技大学计算机系602教研室

65 (s0 s1  sm ，# X1  Xm ，aiai+1  an #)
分析器根据ACTION(sm , ai)确定下一步动作 1. 若ACTION(sm , ai)为移进，且s，则三元式格局变为: (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)为"报错"，则三元式变化过程终止，报告错误. 国防科技大学计算机系602教研室

66 LR分析器示例： 文法G(E)： (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i (1) E→E＋T
国防科技大学计算机系602教研室

67 其LR分析表为: 国防科技大学计算机系602教研室

68 假定输入串为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# (6) #T*i +i# (7) #T*F +i# (8) 02 #T +i# (9) 01 #E +i# (10) 016 #E+ i# 国防科技大学计算机系602教研室

69 E * T + F i 步骤 状态 符号 输入串 (11) 0165 #E+i # (12) 0163 #E+F #
步骤 状态 符号 输入串 (11) #E+i # (12) #E+F # (13) #E+T # (14) 01 #E # (15) 接受 E * T + F i 国防科技大学计算机系602教研室

70 定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为LR文法。
定义：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法. 非LR结构 LR文法不是二义的，二义文法肯定不会是LR的。 S  iCtS | iCtSeS 栈 输入 …iCtS e…# 国防科技大学计算机系602教研室

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

72 指导思想——目标驱动 踢足球 “如果你不知道怎样踢球，就往球门方向踢 ” ——施拉普纳 LR分析
“如果你不知道怎样分析，就保证栈中总是活前缀” 国防科技大学计算机系602教研室

73 文法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) 称为"待约项目". 国防科技大学计算机系602教研室

74 文法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· 国防科技大学计算机系602教研室

75 状态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确定化。 构成识别一个文法活前缀的DFA的项目集 (状态)的全体称为文法的LR(0)项目集规范 族。 国防科技大学计算机系602教研室

76 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 国防科技大学计算机系602教研室

77 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 国防科技大学计算机系602教研室

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

79 结论: 若项目A .B对活前缀=是有 效的且B  是一个产生式，则项目B  .对=也是有效的。
设 ，那么 所以，B  .对=也是有效的。 国防科技大学计算机系602教研室

80 文法G(S) 考虑： 项目：B  c.B B  . cB B  . d 活前缀：bc S’ E  bB  bcB
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 国防科技大学计算机系602教研室

81 LR(0)项目集规范族的构造 假定文法G是一个以S为开始符号的文法，我们构造一个G，它包含了整个G，但它引进了一个不出现在G中的非终结符S，并加进一个新产生式S→S，而这个S是G的开始符号。那么，我们称G是G的拓广文法。这样，便会有一个仅含项目S→S.的状态，这就是唯一的“接受”态。 国防科技大学计算机系602教研室

82 假定I是文法G的任一项目集，定义和构造I的闭包CLOSURE(I)如下： 1. I的任何项目都属于CLOSURE(I)；
2. 若A→·B属于CLOSURE(I)，那么，对任何关于B的产生式B→，项目B→·也属于CLOSURE(I)； 3. 重复执行上述两步骤直至CLOSURE(I) 不再增大为止。 国防科技大学计算机系602教研室

83 为了识别活前缀，我们定义一个状态转换函数GO是一个状态转换函数。I是一个项目集，X是一个文法符号。函数值GO(I，X)定义为：
GO(I，X)＝CLOSURE(J) 其中 J＝{任何形如A→X·的项目| A→ · X属于I}。 直观上说，若I是对某个活前缀  有效的项目集，那么，GO(I，X)便是对 X 有效的项目集。 国防科技大学计算机系602教研室

84 文法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 国防科技大学计算机系602教研室

85 构造文法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转换图. 国防科技大学计算机系602教研室

86 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 国防科技大学计算机系602教研室

87 LR(0)分析表的构造 假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况：
1) 既含移进项目又含归约项目， 2) 含有多个归约项目 则称G是一个LR(0)文法。 国防科技大学计算机系602教研室

88 构造LR(0)分析表的算法 令每个项目集Ik的下标k作为分析器的状态，包含项目S→·S的集合Ik的下标k为分析器的初态。
国防科技大学计算机系602教研室

89 分析表的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填入信息的空白格均置上“报错标志”。 国防科技大学计算机系602教研室

90 LR(0)分析表为 国防科技大学计算机系602教研室

91 例: 按上表对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 # 国防科技大学计算机系602教研室

92 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. 此外，报错。 国防科技大学计算机系602教研室

93 冲突性动作的这种解决办法叫做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)解决办法。 国防科技大学计算机系602教研室

94 首先把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为分析器的初态。 国防科技大学计算机系602教研室

95 分析表的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填入信息的空白格均置上“出错标志”。 国防科技大学计算机系602教研室

96 按上述方法构造出的ACTION与GOTO表如果不含多重入口，则称该文法为SLR(1)文法。
使用SLR表的分析器叫做一个SLR分析器。 每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的. 国防科技大学计算机系602教研室

97 例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 国防科技大学计算机系602教研室

98 这个文法的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· 国防科技大学计算机系602教研室

99 I1、I2和I9都含有“移进－归约”冲突。 FOLLOW(E)＝{#, ), +}， I0 I1 I2 I3 I4 I5 I6 I7 I8
T * i F ( ) 国防科技大学计算机系602教研室

100 其分析表如下: 国防科技大学计算机系602教研室

101 非SLR文法示例：考虑如下文法： 计算FOLLOW集合所得到的超前符号集合可能大于实际能出现的超前符号集。 (0) S→S
(2) S→R (3) L→*R (4) L→i (5) R→L 国防科技大学计算机系602教研室

102 这个文法的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· 国防科技大学计算机系602教研室

103 国防科技大学计算机系602教研室

104 如上例，当状态2显现于栈顶而且面临输入符号为‘=’时，实际上不能用对栈顶L进行归约，因为这个文法不含“R=”为前缀的规范句型。
SLR在方法中,如果项目集Ii含项目A.而且下一输入符号aFOLLOW(A),则状态i面临a时,可选用“用A归约”动作。但在有些情况下,当状态i显现于栈顶时,栈里的活前缀未必允许把归约为A，因为可能根本就不存在一个形如“Aa”的规范句型。因此，在这种情况下，用“ A ”归约不一定合适。 如上例，当状态2显现于栈顶而且面临输入符号为‘=’时，实际上不能用对栈顶L进行归约，因为这个文法不含“R=”为前缀的规范句型。 国防科技大学计算机系602教研室

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

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

107 为构造有效的LR(1)项目集族我们需要两个函数CLOSURE和GO。
国防科技大学计算机系602教研室

108 证明：若项目[A→·B, a]对＝有效， 则有规范推导
[A→·B, a]对活前缀＝是有效的，则对于每个形如B的产生式， 对任何bFIRST(a)，[B→·, b]对也是有效的。 证明：若项目[A→·B, a]对＝有效， 则有规范推导 ζ [zi:tə] η [i:tə] ξ [ksai] φ [fai] χ [kai] ψ [psai] 国防科技大学计算机系602教研室

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

110 令I是一个项目集，X是一个文法符号，函数GO(I，X)定义为： GO(I，X)＝CLOSURE(J) 其中
J＝{任何形如[A→X·, a]的项目 | [A→·X, a]I} 国防科技大学计算机系602教研室

111 文法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 国防科技大学计算机系602教研室

112 构造LR(1)分析表的算法。 令每个Ik的下标k为分析表的状态，令含有[S→·S, #]的Ik的k为分析器的初态。
国防科技大学计算机系602教研室

113 动作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填入信息的空白栏均填上“出错标志”。 国防科技大学计算机系602教研室

114 按上述算法构造的分析表，若不存在多重定义的入口(即，动作冲突)的情形，则称它是文法G的一张规范的LR(1)分析表。
具有规范的LR(1)分析表的文法称为一个LR(1)文法。 LR(1)状态比SLR多， LR(0)SLR  LR(1) 无二义文法 国防科技大学计算机系602教研室

115 例5.13 (5.10)的拓广文法G( S) (0) S→S (1) S→BB (2) B→aB (3) B→b
国防科技大学计算机系602教研室

116 LR(1)的项目集C和函数GO S I0: S’•S, # S•BB, # B•aB, a/b B •b, a/b
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 国防科技大学计算机系602教研室

117 LR(1)分析表为: 国防科技大学计算机系602教研室

118 例: 按上表对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 国防科技大学计算机系602教研室

119 例: 按上表对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 国防科技大学计算机系602教研室

120 基本概念 定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且 则称是句型相对于非终结符A的短语。
特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。 国防科技大学计算机系602教研室

121 定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 
2 0为文法的开始符号，即0=S 3 对任何i，0  i  n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。 国防科技大学计算机系602教研室

122 作业 P133—1，2，3 P134—5 (1)，(2)，(3), (4) P134—8(选作) 国防科技大学计算机系602教研室