Download presentation
Presentation is loading. Please wait.
1
编 译 原 理 指导教师:杨建国 二零一零年三月
2
第七章 LR分析 第一节 LR分析概述 第二节 LR（0）分析 第三节 SLR（1）分析 第四节 LR（1）分析 第五节 LALR（1）分析
第七节 语法分析程序的自动构造工具YACC 第八节 典型例题及解答
3
知识结构
4
四种LR类型： LR(0) 、SLR(1) 、 LALR(1) 、 LR(1) 功能逐个增强 四种LR类型的文法是真包含关系 一个文法是LR(0)文法一定是LR(1)文法吗？
5
第七章 LR分析 7.1 LR分析概述 LR分析法： 它是给出一种能根据当前分析栈中的符号串（通常
它是给出一种能根据当前分析栈中的符号串（通常 以状态表示）和向右顺序查看输入串的k个(k≥0)符号就 可唯一地确定分析器的动作是移进还是归约和用哪个产 生式归约，因而也就能唯一地确定句柄 LR分析过程是一种规范归约过程 LR(k)分析方法是1965年Knuth提出的，括号中的k表 示向右查看输入串符号的个数
6
LR分析优点：对文法的限制很少、分析速度快、能准
确即时地指出出错位置 LR分析主要缺点：对于一个实用语言文法的分析器的 构造工作量相当大，k愈大构造愈复杂，实现比较困难
7
一个LR分析器的组成： （1）总控程序（驱动程序）：对所有的LR分析器是相同的 （2）分析表（分析函数）：动作表和状态转换表 （3）分析栈：文法符号栈和状态栈
8
LR分析器工作过程示意图如图7.1所示：
9
其中SP为栈指针，S[i]为状态栈，X[i]为文法符号栈
状态转换表内容按关系ACTION[Si，X]=Sj确定，该关系式 是指当栈顶状态为Si遇到当前文法符号为X时应转向状态Sj X为终结符或非终结符
![其中SP为栈指针，S[i]为状态栈，X[i]为文法符号栈](http://slidesplayer.com/slide/11352245/61/images/9/%E5%85%B6%E4%B8%ADSP%E4%B8%BA%E6%A0%88%E6%8C%87%E9%92%88%EF%BC%8CS%5Bi%5D%E4%B8%BA%E7%8A%B6%E6%80%81%E6%A0%88%EF%BC%8CX%5Bi%5D%E4%B8%BA%E6%96%87%E6%B3%95%E7%AC%A6%E5%8F%B7%E6%A0%88.jpg "状态转换表内容按关系ACTION[Si，X]=Sj确定，该关系式. 是指当栈顶状态为Si遇到当前文法符号为X时应转向状态Sj. X为终结符或非终结符.")
10
ACTION[Si，a]规定了栈顶状态为Si时遇到输入符号a应执
行的动作，动作有4种可能： （1）移进： 当Sj =ACTION[Si，a]成立，则把Sj移入到状态栈，把a移 入到文法符号栈。其中i，j表示状态号
![ACTION[Si，a]规定了栈顶状态为Si时遇到输入符号a应执](http://slidesplayer.com/slide/11352245/61/images/10/ACTION%5BSi%EF%BC%8Ca%5D%E8%A7%84%E5%AE%9A%E4%BA%86%E6%A0%88%E9%A1%B6%E7%8A%B6%E6%80%81%E4%B8%BASi%E6%97%B6%E9%81%87%E5%88%B0%E8%BE%93%E5%85%A5%E7%AC%A6%E5%8F%B7a%E5%BA%94%E6%89%A7.jpg "行的动作，动作有4种可能： （1）移进： 当Sj =ACTION[Si，a]成立，则把Sj移入到状态栈，把a移. 入到文法符号栈。其中i，j表示状态号.")
11
（2）归约： 当在栈顶形成句柄为β时，则用β归约为相应的非终结 符A，即当文法中有A β 产生式，而β的长度为r（ 即| β|=r），则从状态栈和文法符号栈中自栈顶向下去掉r个 符号，即栈指针SP减去r。并把A移入文法符号栈内，再把 满足Sj=GOTO[Si,A]的状态移进状态栈，其中Si为修改指针 后的栈顶状态
12
（3）接受acc： 当归约到文法符号栈中只剩文法的开始符号S时，并且 输入符号串已结束即当前输入符是#，则为分析成功
13
（4）报错： 当遇到状态栈顶为某一状态下出现不该遇到的文法符 号时，则报错，说明输入串不是该文法能接受的句子
14
7.2 LR（0）分析表的构造 构造LR(0)分析表方法一：（特例方法） 根据形式定义求出活前缀的正规表达式 然后由正规表达式构造NFA
再确定化为DFA 构造LR(0)分析表
15
构造LR(0)分析表方法二： 求出文法的所有项目 按一定规则构造识别活前缀的NFA 再确定化为DFA 构造LR(0)分析表
16
构造LR(0)分析表方法三：推荐 写出G的拓广文法G` 写出G`的LR(0)项目集 求出LR(0)项目集规范族C 构造识别文法全部活前缀的DFA 构造LR(0)分析表
17
例6.1 设文法G[S]： （1）S aAcBe （2）A b （3）A Ab （4）B d 对输入串abbcde＃进行分析，检查它是否是G[S]的句子： 最右推导为规范推导 自左向右的归约过程也称规范归约 对输入串abbcde的最右推导是： S aAcBe aAcde aAbcde abbcde
![例6.1 设文法G[S]： （1）S aAcBe. （2）A b. （3）A Ab. （4）B d. 对输入串abbcde＃进行分析，检查它是否是G[S]的句子： 最右推导为规范推导.](http://slidesplayer.com/slide/11352245/61/images/17/%E4%BE%8B6.1+%E8%AE%BE%E6%96%87%E6%B3%95G%5BS%5D%EF%BC%9A+%EF%BC%881%EF%BC%89S+aAcBe.+%EF%BC%882%EF%BC%89A+b.+%EF%BC%883%EF%BC%89A+Ab.+%EF%BC%884%EF%BC%89B+d.+%E5%AF%B9%E8%BE%93%E5%85%A5%E4%B8%B2abbcde%EF%BC%83%E8%BF%9B%E8%A1%8C%E5%88%86%E6%9E%90%EF%BC%8C%E6%A3%80%E6%9F%A5%E5%AE%83%E6%98%AF%E5%90%A6%E6%98%AFG%5BS%5D%E7%9A%84%E5%8F%A5%E5%AD%90%EF%BC%9A+%E6%9C%80%E5%8F%B3%E6%8E%A8%E5%AF%BC%E4%B8%BA%E8%A7%84%E8%8C%83%E6%8E%A8%E5%AF%BC..jpg "自左向右的归约过程也称规范归约. 对输入串abbcde的最右推导是： S aAcBe aAcde aAbcde abbcde.")
18
(1) # abbcde# 移进 (2) #a bbcde# 移进 (3) #ab bcde# 归约(A b) (4) #aA bcde#
步骤 符号栈 输入符号串 动作 (1) # abbcde# 移进 (2) #a bbcde# 移进 (3) #ab bcde# 归约(A b) (4) #aA bcde# 移进 (5) #aAb cde# 归约(A Ab) (6) #aA cde# 移进 (7) #aAc de# 移进 (8) #aAcd e# 归约(B d) (9) #aAcB e# 移进 (10) #aAcBe # 归约(S aAcBe) (11) #S # 接受
19
在表7.1中给出例6.1中文法G[S]的LR（0）分析表
ACTION GOTO a c e b d # S A B 1 2 3 4 5 6 7 8 9 S2 1 acc S4 3 S5 S6 r2 r2 r2 r2 r2 r2 S8 7 r3 r3 r3 r3 r3 r3 S9 r4 r4 r4 r4 r4 r4 r1 r1 r1 r1 r1 r1
![在表7.1中给出例6.1中文法G[S]的LR（0）分析表](http://slidesplayer.com/slide/11352245/61/images/19/%E5%9C%A8%E8%A1%A87.1%E4%B8%AD%E7%BB%99%E5%87%BA%E4%BE%8B6.1%E4%B8%AD%E6%96%87%E6%B3%95G%5BS%5D%E7%9A%84LR%EF%BC%880%EF%BC%89%E5%88%86%E6%9E%90%E8%A1%A8.jpg "ACTION. GOTO. a. c. e. b. d. # S. A. B S2. 1. acc. S4. 3. S5. S6. r2. r2. r2. r2. r2. r2. S8. 7. r3. r3. r3. r3. r3. r3. S9. r4. r4. r4. r4. r4. r4. r1. r1. r1. r1. r1. r1.")
20
在表7.2中给出对输入串abbcde＃的分析过程
步骤 状态栈 符号栈 输入串 ACTION GOTO (1) # abbcde# S2 (2) 02 #a bbcde# S4 (3) 024 #ab bcde# r2 3 (4) 023 #aA bcde# S6 (5) 0236 #aAb cde# r3 3 (6) 023 #aA cde# S5 (7) 0235 #aAc de# S8 (8) 02358 #aAcd e# r4 7 (9) 02357 #aAcB e# S9 (10) 023579 #aAcBe # r1 1 (11) 01 #S # acc
21
一.可归前缀和子前缀 为使最右推导和最左归约的关系看得更清楚，我们可以 在推导过程中加入一些附加信息。若对例6.1文法G[S]中的每 条产生式编上序号用[i]表示，并将其加在产生式的尾部，产 生式变为： S aAcBe [1] A b [2] A Ab [3] B d [4] 对输入串abbcde进行推导时把序号也带入，作最右推导：
![一.可归前缀和子前缀 为使最右推导和最左归约的关系看得更清楚，我们可以. 在推导过程中加入一些附加信息。若对例6.1文法G[S]中的每. 条产生式编上序号用[i]表示，并将其加在产生式的尾部，产.](http://slidesplayer.com/slide/11352245/61/images/21/%E4%B8%80.%E5%8F%AF%E5%BD%92%E5%89%8D%E7%BC%80%E5%92%8C%E5%AD%90%E5%89%8D%E7%BC%80+%E4%B8%BA%E4%BD%BF%E6%9C%80%E5%8F%B3%E6%8E%A8%E5%AF%BC%E5%92%8C%E6%9C%80%E5%B7%A6%E5%BD%92%E7%BA%A6%E7%9A%84%E5%85%B3%E7%B3%BB%E7%9C%8B%E5%BE%97%E6%9B%B4%E6%B8%85%E6%A5%9A%EF%BC%8C%E6%88%91%E4%BB%AC%E5%8F%AF%E4%BB%A5.+%E5%9C%A8%E6%8E%A8%E5%AF%BC%E8%BF%87%E7%A8%8B%E4%B8%AD%E5%8A%A0%E5%85%A5%E4%B8%80%E4%BA%9B%E9%99%84%E5%8A%A0%E4%BF%A1%E6%81%AF%E3%80%82%E8%8B%A5%E5%AF%B9%E4%BE%8B6.1%E6%96%87%E6%B3%95G%5BS%5D%E4%B8%AD%E7%9A%84%E6%AF%8F.+%E6%9D%A1%E4%BA%A7%E7%94%9F%E5%BC%8F%E7%BC%96%E4%B8%8A%E5%BA%8F%E5%8F%B7%E7%94%A8%5Bi%5D%E8%A1%A8%E7%A4%BA%EF%BC%8C%E5%B9%B6%E5%B0%86%E5%85%B6%E5%8A%A0%E5%9C%A8%E4%BA%A7%E7%94%9F%E5%BC%8F%E7%9A%84%E5%B0%BE%E9%83%A8%EF%BC%8C%E4%BA%A7..jpg "生式变为： S aAcBe [1] A b [2] A Ab [3] B d [4] 对输入串abbcde进行推导时把序号也带入，作最右推导：")
22
S aAcBe [1] aAcd [4] e [1] aAb [3] cd [4] e [1] ab [2] b [3] cd [4] e [1] 输入串abbcde是该文法的句子 它的逆过程－最左归约（规范归约）则为： ab [2] b [3] cd [4] e [1] 用产生式（2）归约 aAb [3] cd [4] e [1] 用产生式（3）归约 aAcd [4] e [1] 用产生式（4）归约 aAcBe [1] 用产生式（1）归约 S
![S aAcBe [1] aAcd [4] e [1] aAb [3] cd [4] e [1] ab [2] b [3] cd [4] e [1] 输入串abbcde是该文法的句子.](http://slidesplayer.com/slide/11352245/61/images/22/S+aAcBe+%5B1%5D+aAcd+%5B4%5D+e+%5B1%5D+aAb+%5B3%5D+cd+%5B4%5D+e+%5B1%5D+ab+%5B2%5D+b+%5B3%5D+cd+%5B4%5D+e+%5B1%5D+%E8%BE%93%E5%85%A5%E4%B8%B2abbcde%E6%98%AF%E8%AF%A5%E6%96%87%E6%B3%95%E7%9A%84%E5%8F%A5%E5%AD%90..jpg "它的逆过程－最左归约（规范归约）则为： ab [2] b [3] cd [4] e [1] 用产生式（2）归约. aAb [3] cd [4] e [1] 用产生式（3）归约. aAcd [4] e [1] 用产生式（4）归约. aAcBe [1] 用产生式（1）归约. S.")
23
每次归约前句型的前部依次为： ab [2] aAb [3] aAcd [4] aAcBe [1] 这正是在表7.2的分析过程中每次采取归约动作前符号栈 中的内容，把规范句型的这种前部称可归前缀 上述分析每个部分的前缀： ε,a,ab ε ,a,aA,aAb ε ,a,aA,aAc,aAcd ε ,a,aA,aAc,aAcB,aAcBe
![每次归约前句型的前部依次为： ab [2] aAb [3] aAcd [4] aAcBe [1] 这正是在表7.2的分析过程中每次采取归约动作前符号栈. 中的内容，把规范句型的这种前部称可归前缀.](http://slidesplayer.com/slide/11352245/61/images/23/%E6%AF%8F%E6%AC%A1%E5%BD%92%E7%BA%A6%E5%89%8D%E5%8F%A5%E5%9E%8B%E7%9A%84%E5%89%8D%E9%83%A8%E4%BE%9D%E6%AC%A1%E4%B8%BA%EF%BC%9A+ab+%5B2%5D+aAb+%5B3%5D+aAcd+%5B4%5D+aAcBe+%5B1%5D+%E8%BF%99%E6%AD%A3%E6%98%AF%E5%9C%A8%E8%A1%A87.2%E7%9A%84%E5%88%86%E6%9E%90%E8%BF%87%E7%A8%8B%E4%B8%AD%E6%AF%8F%E6%AC%A1%E9%87%87%E5%8F%96%E5%BD%92%E7%BA%A6%E5%8A%A8%E4%BD%9C%E5%89%8D%E7%AC%A6%E5%8F%B7%E6%A0%88.+%E4%B8%AD%E7%9A%84%E5%86%85%E5%AE%B9%EF%BC%8C%E6%8A%8A%E8%A7%84%E8%8C%83%E5%8F%A5%E5%9E%8B%E7%9A%84%E8%BF%99%E7%A7%8D%E5%89%8D%E9%83%A8%E7%A7%B0%E5%8F%AF%E5%BD%92%E5%89%8D%E7%BC%80..jpg "上述分析每个部分的前缀： ε,a,ab. ε ,a,aA,aAb. ε ,a,aA,aAc,aAcd. ε ,a,aA,aAc,aAcB,aAcBe.")
24
前缀a,aA,aAc是多个规范句型的前缀，因此把在规范句型
中形成可归前缀之前包括可归前缀在内的所有前缀都称 为活前缀。活前缀为一个或若干规范句型的前缀 在原文法G中增加产生式S` S，S为原文法G的开始符 号，所得的新文法称为G的拓广文法，以G`表示，S`为拓 广后文法G`的开始符号
25
对文法进行拓广的目的：是为了对某些右部含有开始符号
的文法，在归约过程中能分清是否已归约到文法的最初 开始符，还是在文法右部出现的开始符号，拓广文法的 开始符号S`只在左部出现，这样确保了不会混淆
26
R * 定义7.1 若S` αAw α βw是文法G的拓广文法G`中 的一个规范推导，符号串γ是α β的前缀，则称 γ是G的一个活前缀。也就是说γ是规范句型α βw 的前缀，但它的右端不超过该句型句柄的末端 R
27
二.识别活前缀的有限自动机 对例6.1的文法用拓广文法表示成： S` S [0] S aAcBe [1] A b [2] A Ab [3] B d [4]
![二.识别活前缀的有限自动机 对例6.1的文法用拓广文法表示成： S` S [0] S aAcBe [1] A b [2] A Ab [3] B d [4]](http://slidesplayer.com/slide/11352245/61/images/27/%E4%BA%8C.%E8%AF%86%E5%88%AB%E6%B4%BB%E5%89%8D%E7%BC%80%E7%9A%84%E6%9C%89%E9%99%90%E8%87%AA%E5%8A%A8%E6%9C%BA+%E5%AF%B9%E4%BE%8B6.1%E7%9A%84%E6%96%87%E6%B3%95%E7%94%A8%E6%8B%93%E5%B9%BF%E6%96%87%E6%B3%95%E8%A1%A8%E7%A4%BA%E6%88%90%EF%BC%9A+S%60+S+%5B0%5D+S+aAcBe+%5B1%5D+A+b+%5B2%5D+A+Ab+%5B3%5D+B+d+%5B4%5D.jpg "二.识别活前缀的有限自动机 对例6.1的文法用拓广文法表示成： S` S [0] S aAcBe [1] A b [2] A Ab [3] B d [4]")
28
现对句子abbcde的可归前缀列出： S [0] ab [2] aAb [3] aAcd [4] aAcBe [1] 构造识别其活前缀及可归前缀的有限自动机如图7.2：
![现对句子abbcde的可归前缀列出： S [0] ab [2] aAb [3] aAcd [4] aAcBe [1] 构造识别其活前缀及可归前缀的有限自动机如图7.2：](http://slidesplayer.com/slide/11352245/61/images/28/%E7%8E%B0%E5%AF%B9%E5%8F%A5%E5%AD%90abbcde%E7%9A%84%E5%8F%AF%E5%BD%92%E5%89%8D%E7%BC%80%E5%88%97%E5%87%BA%EF%BC%9A+S+%5B0%5D+ab+%5B2%5D+aAb+%5B3%5D+aAcd+%5B4%5D+aAcBe+%5B1%5D+%E6%9E%84%E9%80%A0%E8%AF%86%E5%88%AB%E5%85%B6%E6%B4%BB%E5%89%8D%E7%BC%80%E5%8F%8A%E5%8F%AF%E5%BD%92%E5%89%8D%E7%BC%80%E7%9A%84%E6%9C%89%E9%99%90%E8%87%AA%E5%8A%A8%E6%9C%BA%E5%A6%82%E5%9B%BE7.2%EF%BC%9A.jpg "现对句子abbcde的可归前缀列出： S [0] ab [2] aAb [3] aAcd [4] aAcBe [1] 构造识别其活前缀及可归前缀的有限自动机如图7.2：")
29
每一个终态都是句柄识别态，用 表示，仅有带*号的状
态既为句柄识别态又是句子识别态，句子识别态仅有唯一的一个 i
30
如果加一个开始状态并用ε弧和每个识别可归前缀的有限
自动机连接，则可变为：
31
将上图确定化并重新编号后变为： c
32
这是一种特例方法：构造识别文法活前缀的DFA
对文法G用拓广文法G`表示 对给定句子列出可归前缀 构造识别其活前缀及可归前缀的有限自动机 构造识别活前缀的NFA 再确定化为DFA
33
由例6.1文法对输入串abibcde#可以有如下推导：
S` S aAcBe aAcde aAbcde abibcde 其中i为任意正整数，该文法所描述的语言可用正规式 ab+cde表示 i
34
三.活前缀及其可归前缀的一般计算方法 定义7.2 设G=(VN,VT,P,S)是一个上下文无关文法，对于 A∈VN有 LC(A)={α|S` αAw, α∈V*,w ∈vt*} 其中S`是G的拓广文法G`的开始符号 R *
35
推论：若文法G中有产生式 B γAδ 则有：LC（A） LC（B）·｛γ｝ 因为对任一形如αBw的句型必有规范推导： S` αBw αγAδw R * R
36
由定义7.2推论和文法的产生式我们可以列出方程组，那
么例6.1文法可有方程： LC(S`)={ε} LC(S)= LC(S`)·{ε} ={ε} LC(A)= LC(S)·｛a｝∪ LC(A)· {ε}＝ ｛a｝ LC(B)= LC(S)·｛aAc｝＝{aAc} 用正规式来表示前缀集合，上述方程表示为： LC(S`)=ε LC(S)=ε LC(A)=a LC(B)=aAc
37
对LR（0）方法来说，包含句柄的活前缀计算非常简单，
只需把上面已求得的活前缀再加产生式的右部，可用如 下形式表示： 规定： LR（0）CONTEXT（A β）＝LC（A）·β， LR（0）CONTEXT（A β）可简写为 LR（0）C（A β）
38
这样对例6.1文法包含句柄的活前缀可有： LR(0)C（S` S）=S LR(0)C（S aAcBe）=aAcBe LR(0)C（A b）=ab LR(0)C（A Ab）=aAb LR(0)C（B d）=aAcd
39
例如文法G`为： S` E E aA E bB A cA A d B cB B d
40
求不包含句柄在内的活前缀方程组为： LC(S`)=ε LC(E)= LC(S`)·ε =ε LC(A)= LC(E)·a｜ LC(A)·c＝ ac* LC(B)= LC(E)·b｜ LC(B)·c＝ bc* 所以包含句柄的活前缀为： LR(0)C（S` E）=E LR(0)C（E aA）=aA LR(0)C（E bB）=bB LR(0)C（A cA）=ac*cA LR(0)C（A d）=ac*d LR(0)C（B cB）=bc*cB LR(0)C（B d）=bc*d
41
由此可构造以方法符号为字母表的识别活前缀（包含句柄
在内）的不确定有限自动机如图7.5：
42
对图7.5的不确定有限状态自动机可用子集法进行确定化结
果如图7.6：
43
这是第一种方法：构造识别文法活前缀的DFA
根据形式定义求出活前缀的正规表达式 然后由此正规表达式构造NFA 再确定化为DFA
44
四.LR（0）项目集规范族的构造 （1）LR（0）项目 在文法G中每个产生式右部适当位置添加一个圆点构成项目 圆点左部表示分析过程的某时刻用该产生式归约时句柄已识 别过的部分 圆点右部表示待识别的部分 项目个数一般为它的右部符号长度加１ 注意：A ℇ为A ·
45
例如，产生式S aAcBe对应有6个项目 [0]S ·aAcBe [1]S a·AcBe [2]S aA·cBe [3]S aAc·Be [4]S aAcB·e [5]S aAcBe·
![例如，产生式S aAcBe对应有6个项目 [0]S ·aAcBe. [1]S a·AcBe. [2]S aA·cBe. [3]S aAc·Be. [4]S aAcB·e.](http://slidesplayer.com/slide/11352245/61/images/45/%E4%BE%8B%E5%A6%82%EF%BC%8C%E4%BA%A7%E7%94%9F%E5%BC%8FS+aAcBe%E5%AF%B9%E5%BA%94%E6%9C%896%E4%B8%AA%E9%A1%B9%E7%9B%AE+%5B0%5DS+%C2%B7aAcBe.+%5B1%5DS+a%C2%B7AcBe.+%5B2%5DS+aA%C2%B7cBe.+%5B3%5DS+aAc%C2%B7Be.+%5B4%5DS+aAcB%C2%B7e..jpg "[5]S aAcBe·")
46
例中项目的编号用[]中的数字表示 第[0]个项目意味着希望用S的右部归约，当前输入串中符号 应为a 项目[1]表明用该产生式归约已与第一个符号a匹配过了，需 分析非终结符A的右部 项目[2]表明A的右部已分析完归约成A，目前希望遇到输入 串中的符号为c 以此类推直到项目[5]为S的右部都已分析完毕，则句柄已形 成可以进行归约
![例中项目的编号用[]中的数字表示 第[0]个项目意味着希望用S的右部归约，当前输入串中符号. 应为a. 项目[1]表明用该产生式归约已与第一个符号a匹配过了，需. 分析非终结符A的右部. 项目[2]表明A的右部已分析完归约成A，目前希望遇到输入.](http://slidesplayer.com/slide/11352245/61/images/46/%E4%BE%8B%E4%B8%AD%E9%A1%B9%E7%9B%AE%E7%9A%84%E7%BC%96%E5%8F%B7%E7%94%A8%5B%5D%E4%B8%AD%E7%9A%84%E6%95%B0%E5%AD%97%E8%A1%A8%E7%A4%BA+%E7%AC%AC%5B0%5D%E4%B8%AA%E9%A1%B9%E7%9B%AE%E6%84%8F%E5%91%B3%E7%9D%80%E5%B8%8C%E6%9C%9B%E7%94%A8S%E7%9A%84%E5%8F%B3%E9%83%A8%E5%BD%92%E7%BA%A6%EF%BC%8C%E5%BD%93%E5%89%8D%E8%BE%93%E5%85%A5%E4%B8%B2%E4%B8%AD%E7%AC%A6%E5%8F%B7.+%E5%BA%94%E4%B8%BAa.+%E9%A1%B9%E7%9B%AE%5B1%5D%E8%A1%A8%E6%98%8E%E7%94%A8%E8%AF%A5%E4%BA%A7%E7%94%9F%E5%BC%8F%E5%BD%92%E7%BA%A6%E5%B7%B2%E4%B8%8E%E7%AC%AC%E4%B8%80%E4%B8%AA%E7%AC%A6%E5%8F%B7a%E5%8C%B9%E9%85%8D%E8%BF%87%E4%BA%86%EF%BC%8C%E9%9C%80.+%E5%88%86%E6%9E%90%E9%9D%9E%E7%BB%88%E7%BB%93%E7%AC%A6A%E7%9A%84%E5%8F%B3%E9%83%A8.+%E9%A1%B9%E7%9B%AE%5B2%5D%E8%A1%A8%E6%98%8EA%E7%9A%84%E5%8F%B3%E9%83%A8%E5%B7%B2%E5%88%86%E6%9E%90%E5%AE%8C%E5%BD%92%E7%BA%A6%E6%88%90A%EF%BC%8C%E7%9B%AE%E5%89%8D%E5%B8%8C%E6%9C%9B%E9%81%87%E5%88%B0%E8%BE%93%E5%85%A5..jpg "串中的符号为c. 以此类推直到项目[5]为S的右部都已分析完毕，则句柄已形. 成可以进行归约.")
47
（2）构造识别活前缀的NFA 把文法的所有产生式的项目都列出，并使每个项目都作为 NFA的一个状态 以文法G`为例： S` E E aA|bB A cA|d B cB|d
48
该文法的项目有： 1.S` ·E 2.S` E· 3.E ·aA 4.E a·A 5.E aA· 6.A ·cA 7.A c·A 8.A cA· 9.A ·d 10.A d· 11.E ·bB 12.E b·B 13.E bB· 14.B ·cB 15.B c·B 16.B cB· 17.B ·d 18.B d·
49
由于S′仅在第一个产生式的左部出现，因此规定项目1为
初态 其余每个状态都为活前缀的识别态 圆点在最后的项目为句柄识别态 第一个产生式的句柄识别态为句子识别态
50
状态之间的转换关系确定方法如下： 若i项目为：X→X1X2…Xi-1·Xi…Xn j项目为：X→X1X2…Xi-1 Xi·Xi+1…Xn i项目和j项目出于同一个产生式，对应于NFA为状态j的圆 点只落后于状态i的圆点一个符号的位置，那么从状态i到 状态j连一条标记为Xi的箭弧 如果Xi为非终结符，则也会有以它为左部的有关项目及其 相应的状态
51
例如有项目形如： i X γ·Aδ k A ·β 则从状态i画标记为ε的箭弧到状态k，对于A的所有产 生式圆点在最左边的状态都连一条从i状态到该状态的箭弧， 箭弧上标记为ε
52
对文法G`的所有项目对应的状态构造出识别活前缀的NFA：
ε （0）S` E （1）E aA （2）E bB （3）A cA （4）A d （5）B cB （6）B d c A 8 6 7 ε a A ε 3 4 5 ε ε * E d 10 1 2 9 ε b B 13 11 12 ε d ε 18 17 ε c B 14 15 16 ε
53
对DFA如果把每个子集中所含状态集对应的项目写在新的状
态中，结果如图： A c I8:A→cA· I4: A→c·A A→·cA A→·d d I10:A→d· c d I2: E→a·E A→·cA A→·d A a I6:E→aA· I0:S`→·E E→·aA E→·bB E I1:S`→E· B b I7:E→bB· I3: E→b·B B→·cB B→·d d c d I11:B→d· I5: B→c·B B→·cB B→·d B I9:B→cB· c
54
这是第二种方法：构造识别文法活前缀的DFA
求出文法的所有项目 按一定规则构造识别活前缀的NFA 再确定化为DFA
55
（3）LR（0）项目集规范族的构造 CLOSURE(I)函数： I是G`的一个项目集，定义和构造CLOSURE（I）如下： ①I的项目均在CLOSURE（I）中 ②若A a·Bβ属于CLOSURE（I），则每一形如 B ·γ的项目也属于CLOSURE（I） ③重复②直到不出现新的项目为止
56
例如，考虑文法G[E]： E E+T|T T T*F|F F (E)|id 如果I={[E` ·E]}，CLOSURE(I)项目有哪些？ E` ·E E ·E+T E ·T T ·T*F T ·F F ·(E) F ·id
![例如，考虑文法G[E]： E E+T|T. T T*F|F. F (E)|id. 如果I={[E` ·E]}，CLOSURE(I)项目有哪些？ E` ·E E ·E+T.](http://slidesplayer.com/slide/11352245/61/images/56/%E4%BE%8B%E5%A6%82%EF%BC%8C%E8%80%83%E8%99%91%E6%96%87%E6%B3%95G%5BE%5D%EF%BC%9A+E+E%2BT%7CT.+T+T%2AF%7CF.+F+%28E%29%7Cid.+%E5%A6%82%E6%9E%9CI%3D%7B%5BE%60+%C2%B7E%5D%7D%EF%BC%8CCLOSURE%28I%29%E9%A1%B9%E7%9B%AE%E6%9C%89%E5%93%AA%E4%BA%9B%EF%BC%9F+E%60+%C2%B7E+E+%C2%B7E%2BT..jpg "E ·T T ·T*F. T ·F F ·(E) F ·id.")
57
GO（I，X）函数： 定义： GO(I，X)＝CLOSURE（｛所有形如[A αX·β] 的项目｜[A α ·Xβ] ∈I｝） I是一个LR（0）项目集 X是I中紧接“·”后的任一文法符号 圆点不在产生式右部最左边的项目称为核,但S` ·S除外
![GO（I，X）函数： 定义： GO(I，X)＝CLOSURE（｛所有形如[A αX·β] 的项目｜[A α ·Xβ] ∈I｝） I是一个LR（0）项目集. X是I中紧接 · 后的任一文法符号.](http://slidesplayer.com/slide/11352245/61/images/57/GO%EF%BC%88I%EF%BC%8CX%EF%BC%89%E5%87%BD%E6%95%B0%EF%BC%9A+%E5%AE%9A%E4%B9%89%EF%BC%9A+GO%28I%EF%BC%8CX%29%EF%BC%9DCLOSURE%EF%BC%88%EF%BD%9B%E6%89%80%E6%9C%89%E5%BD%A2%E5%A6%82%5BA+%CE%B1X%C2%B7%CE%B2%5D+%E7%9A%84%E9%A1%B9%E7%9B%AE%EF%BD%9C%5BA+%CE%B1+%C2%B7X%CE%B2%5D+%E2%88%88I%EF%BD%9D%EF%BC%89+I%E6%98%AF%E4%B8%80%E4%B8%AALR%EF%BC%880%EF%BC%89%E9%A1%B9%E7%9B%AE%E9%9B%86.+X%E6%98%AFI%E4%B8%AD%E7%B4%A7%E6%8E%A5+%C2%B7+%E5%90%8E%E7%9A%84%E4%BB%BB%E4%B8%80%E6%96%87%E6%B3%95%E7%AC%A6%E5%8F%B7..jpg "圆点不在产生式右部最左边的项目称为核,但S` ·S除外.")
58
例如，考虑文法G[E]： E E+T|T T T*F|F F (E)|id 如果I={[E E ·+T]}，GO(I,+)项目有哪些？ E E+·T T ·T*F T ·F F ·(E) F ·id 如果I={[E` E ·]}，GO(I,+)项目有哪些？
![例如，考虑文法G[E]： E E+T|T. T T*F|F. F (E)|id. 如果I={[E E ·+T]}，GO(I,+)项目有哪些？ E E+·T T ·T*F.](http://slidesplayer.com/slide/11352245/61/images/58/%E4%BE%8B%E5%A6%82%EF%BC%8C%E8%80%83%E8%99%91%E6%96%87%E6%B3%95G%5BE%5D%EF%BC%9A+E+E%2BT%7CT.+T+T%2AF%7CF.+F+%28E%29%7Cid.+%E5%A6%82%E6%9E%9CI%3D%7B%5BE+E+%C2%B7%2BT%5D%7D%EF%BC%8CGO%28I%2C%2B%29%E9%A1%B9%E7%9B%AE%E6%9C%89%E5%93%AA%E4%BA%9B%EF%BC%9F+E+E%2B%C2%B7T+T+%C2%B7T%2AF..jpg "T ·F F ·(E) F ·id. 如果I={[E` E ·]}，GO(I,+)项目有哪些？")
59
LR（0）项目集规范族： 定义：对于构成识别一个文法活前缀的DFA项目集（状态） 的全体 利用CLOSURE和GO（I，X）构造文法G`的LR（0）项目 集规范族C＝｛I0,I1,···｝
60
步骤如下： ①置项目S` ·S为初始集的核，然后对核求闭包， CLOSURE（｛ S` ·S ｝）得到初始的项目集 ②对初态集或其他所构造的项目集应用GO（I，X）＝ CLOSURE（J）求出新状态J的项目集 ③重复②直到不出现新的项目为止。
61
构造算法如下： Procedure ITEMS(G`); begin C:={I0=CLOSURE({S` ·S})}; repeat for C中每个项目集I和I中每个紧接“·”后的不同文法符号X do if go(I,X)非空且不属于C then 将go(I,X)加到C until C不再增大； end;
62
例如，考虑文法G[E]： E E+T|T T T*F|F F (E)|id I0: E` ·E E ·E+T E ·T T ·T*F T ·F F ·(E) F ·id
![例如，考虑文法G[E]： E E+T|T. T T*F|F. F (E)|id. I0: E` ·E E ·E+T. E ·T T ·T*F.](http://slidesplayer.com/slide/11352245/61/images/62/%E4%BE%8B%E5%A6%82%EF%BC%8C%E8%80%83%E8%99%91%E6%96%87%E6%B3%95G%5BE%5D%EF%BC%9A+E+E%2BT%7CT.+T+T%2AF%7CF.+F+%28E%29%7Cid.+I0%3A+E%60+%C2%B7E+E+%C2%B7E%2BT.+E+%C2%B7T+T+%C2%B7T%2AF..jpg "T ·F F ·(E) F ·id.")
63
I1: E` E · E E·+T I2: E T · T T·*F I3: T F ·
64
I4: F (· E) E · E+T E · T T · T*F T ·F F ·(E) F ·id I5: F id ·
65
I6: E E+·T T ·T*F T ·F F ·(E) F ·id I7: T T*·F
66
I8: F (E ·) E E·+T I9: E E+T· T T·*F I10: T T*F· I11: F (E)·
67
如果把这个项目集的每个项目集看做一个状态，那么这个项
目集族的GO函数可看做一个DFA M
68
这是第三种方法：构造识别文法活前缀的DFA
写出G的拓广文法G` 写出G`的LR(0)项目集 求出LR(0)项目集规范族C 构造识别文法全部活前缀的DFA
69
再举一个例子：
70
初始项目 接收项目 待约项目 规约项目 移进项目
71
Step1:
72
Step2:
74
Step3:
75
Step4:
76
A·
77
LR（0）项目集规范族的项目类型分为如下四种：
1）移进项目 A → • a 2）待约项目 A → • B 3）归约项目 A → • 4）接受项目 S`→ S • 一个项目集可能包含多种项目 a) 移进和归约项目同时存在（移进-归约冲突） b) 归约和归约项目同时存在（归约-归约冲突）
78
LR(0)文法： G`项目集规范族的每个项目集中不存在移进-归约，或 归约-归约冲突，称为LR(0)文法 注意：仅当一个文法是LR(0)文法时，才能构造出它的不 含冲突动作的LR(0)分析表，才能用LR(0)分析方法分析该文 法定义的符号串
79
（4）LR（0）分析表的构造 它可以用一个二维数组表示，行标为状态号，列标为文法符 号和# 分析表的内容的组成： 动作表：它表示当前状态下所面临输入符应做的工作是移进 、归约、接受或出错，动作表的行标只包含终结符和＃ 转换表：它表示在当前状态下面临文法符号时应转向的下一 个状态，相当于识别活前缀的有限自动机DFA的状态矩阵
80
构造LR（0）分析表的算法： 设一文法G`的项目集规范族C＝｛I0，I1，…，In｝， 令其中每个项目集Ii的下标作为分析器的状态，令包含 S` ·S项目的集合Ik的下标k为分析器的初态
81
则构造LR(0)分析表的步骤为： ①若A α·xβ∈Ii且GOTO(Ii,x)=Ij，x ∈VT,则置 ACTION[i,x] =Sj， x ∈VN,则置GOTO[i,x]=j ②若A α·∈Ii，则对∨x ∈ (VT∪{＃})，置ACTION[i,x] =rj，j为在文法G`中某产生式A α的序号 ③若S` S·∈Ik，则置ACTION[k,＃]=acc ④凡不能用上述方法填入分析表的元素，均置ERROR(空白)
![则构造LR(0)分析表的步骤为： ①若A α·xβ∈Ii且GOTO(Ii,x)=Ij，x ∈VT,则置. ACTION[i,x] =Sj， x ∈VN,则置GOTO[i,x]=j. ②若A α·∈Ii，则对∨x ∈ (VT∪{＃})，置ACTION[i,x]](http://slidesplayer.com/slide/11352245/61/images/81/%E5%88%99%E6%9E%84%E9%80%A0LR%280%29%E5%88%86%E6%9E%90%E8%A1%A8%E7%9A%84%E6%AD%A5%E9%AA%A4%E4%B8%BA%EF%BC%9A+%E2%91%A0%E8%8B%A5A+%CE%B1%C2%B7x%CE%B2%E2%88%88Ii%E4%B8%94GOTO%28Ii%2Cx%29%3DIj%EF%BC%8Cx+%E2%88%88VT%2C%E5%88%99%E7%BD%AE.+ACTION%5Bi%2Cx%5D+%3DSj%EF%BC%8C+x+%E2%88%88VN%2C%E5%88%99%E7%BD%AEGOTO%5Bi%2Cx%5D%3Dj.+%E2%91%A1%E8%8B%A5A+%CE%B1%C2%B7%E2%88%88Ii%EF%BC%8C%E5%88%99%E5%AF%B9%E2%88%A8x+%E2%88%88+%28VT%E2%88%AA%7B%EF%BC%83%7D%29%EF%BC%8C%E7%BD%AEACTION%5Bi%2Cx%5D.jpg "=rj，j为在文法G`中某产生式A α的序号. ③若S` S·∈Ik，则置ACTION[k,＃]=acc. ④凡不能用上述方法填入分析表的元素，均置ERROR(空白)")
82
例如，考虑文法G[E]： E E+T|T T T*F|F F (E)|id 在下表中给出文法G[E]的LR(0)分析表:
![例如，考虑文法G[E]： E E+T|T T T*F|F F (E)|id 在下表中给出文法G[E]的LR(0)分析表:](http://slidesplayer.com/slide/11352245/61/images/82/%E4%BE%8B%E5%A6%82%EF%BC%8C%E8%80%83%E8%99%91%E6%96%87%E6%B3%95G%5BE%5D%EF%BC%9A+E+E%2BT%7CT+T+T%2AF%7CF+F+%28E%29%7Cid+%E5%9C%A8%E4%B8%8B%E8%A1%A8%E4%B8%AD%E7%BB%99%E5%87%BA%E6%96%87%E6%B3%95G%5BE%5D%E7%9A%84LR%280%29%E5%88%86%E6%9E%90%E8%A1%A8%3A.jpg "例如，考虑文法G[E]： E E+T|T T T*F|F F (E)|id 在下表中给出文法G[E]的LR(0)分析表:")
83
S5 S4 1 2 3 S6 acc r2 r2 r2 S7 r2 r2 r2 r4 r4 r4 r4 r4 r4 S5 S4 8 2 3
ACTION GOTO id + * ( ) # E T F 1 2 3 4 5 6 7 8 9 10 11 S5 S4 1 2 3 S6 acc r2 r2 r2 S7 r2 r2 r2 r4 r4 r4 r4 r4 r4 S5 S4 8 2 3 r6 r6 r6 r6 r6 r6 S5 S4 9 3 S5 S4 10 S6 S11 r1 r1 r1 S7 r1 r1 r1 r3 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 r5
84
根据这种文法构造的LR（0）分析表不含多重定义时，称
这样的分析表为LR（0）分析表，能用LR（0）分析表的 分析器称为LR（0）分析器，能构造的LR（0）分析表的 文法称为LR（0）文法
85
如对文法G`的产生式编号如下： （0）S` E （1）E aA （2）E bB （3）A cA （4）A d （5）B cB （6）B d A c I8:A→cA· I4: A→c·A A→·cA A→·d d I10:A→d· c d I2: E→a·A A→·cA A→·d A I6:E→aA· I1:S`→E· E a B I7:E→bB· I3: E→b·B B→·cB B→·d b d I0:S`→·E E→·aA E→·bB c d I11:B→d· I5: B→c·B B→·cB B→·d B I9:B→cB· c
86
按上述算法构造这个文法的LR（0）分析表为表7.3：
87
（5）LR（0）分析器的工作过程 ① 若ACTION[S,a]＝Sj，a为终结符，则把a移入符号栈，j移入 状态栈 ② 若ACTION[S,a]＝rj，a为终结符或＃,则用第j个产生式归约, 并将两个栈的指针减去k，其中k为第j个产生式右部的符号 串长度,这时当前面面临符号为第j个产生式左部的非终结符, 不防设为A，归约后栈顶状态设为n，则再进行GOTO[n,A] ③ 若ACTION[S,a]＝acc，a为#，则为接受，表示分析成功
![（5）LR（0）分析器的工作过程 ① 若ACTION[S,a]＝Sj，a为终结符，则把a移入符号栈，j移入. 状态栈. ② 若ACTION[S,a]＝rj，a为终结符或＃,则用第j个产生式归约,](http://slidesplayer.com/slide/11352245/61/images/87/%EF%BC%885%EF%BC%89LR%EF%BC%880%EF%BC%89%E5%88%86%E6%9E%90%E5%99%A8%E7%9A%84%E5%B7%A5%E4%BD%9C%E8%BF%87%E7%A8%8B+%E2%91%A0+%E8%8B%A5ACTION%5BS%2Ca%5D%EF%BC%9DSj%EF%BC%8Ca%E4%B8%BA%E7%BB%88%E7%BB%93%E7%AC%A6%EF%BC%8C%E5%88%99%E6%8A%8Aa%E7%A7%BB%E5%85%A5%E7%AC%A6%E5%8F%B7%E6%A0%88%EF%BC%8Cj%E7%A7%BB%E5%85%A5.+%E7%8A%B6%E6%80%81%E6%A0%88.+%E2%91%A1+%E8%8B%A5ACTION%5BS%2Ca%5D%EF%BC%9Drj%EF%BC%8Ca%E4%B8%BA%E7%BB%88%E7%BB%93%E7%AC%A6%E6%88%96%EF%BC%83%2C%E5%88%99%E7%94%A8%E7%AC%ACj%E4%B8%AA%E4%BA%A7%E7%94%9F%E5%BC%8F%E5%BD%92%E7%BA%A6%2C.jpg "并将两个栈的指针减去k，其中k为第j个产生式右部的符号. 串长度,这时当前面面临符号为第j个产生式左部的非终结符, 不防设为A，归约后栈顶状态设为n，则再进行GOTO[n,A] ③ 若ACTION[S,a]＝acc，a为#，则为接受，表示分析成功.")
88
④ 若GOTO[S,A]＝j，A为非终结符，表明前一动作是用关
于A的产生式归约的，当前面临非终结符A应移入符号栈 ，j移入状态栈。对于终结符的GOTO[S,a]已和 ACTION[S,a]重合 ⑤若 ACTION[S,a]＝空白，则转向出错处理
![④ 若GOTO[S,A]＝j，A为非终结符，表明前一动作是用关](http://slidesplayer.com/slide/11352245/61/images/88/%E2%91%A3+%E8%8B%A5GOTO%5BS%2CA%5D%EF%BC%9Dj%EF%BC%8CA%E4%B8%BA%E9%9D%9E%E7%BB%88%E7%BB%93%E7%AC%A6%EF%BC%8C%E8%A1%A8%E6%98%8E%E5%89%8D%E4%B8%80%E5%8A%A8%E4%BD%9C%E6%98%AF%E7%94%A8%E5%85%B3.jpg "于A的产生式归约的，当前面临非终结符A应移入符号栈. ，j移入状态栈。对于终结符的GOTO[S,a]已和. ACTION[S,a]重合. ⑤若 ACTION[S,a]＝空白，则转向出错处理.")
89
例6.1 G[S]拓广为: S` S S aAcBe A b A Ab B d
![例6.1 G[S]拓广为: S` S S aAcBe A b A Ab B d](http://slidesplayer.com/slide/11352245/61/images/89/%E4%BE%8B6.1+G%5BS%5D%E6%8B%93%E5%B9%BF%E4%B8%BA%3A+S%60+S+S+aAcBe+A+b+A+Ab+B+d.jpg "例6.1 G[S]拓广为: S` S S aAcBe A b A Ab B d")
90
LR(0)分析表为:
91
对输入串abbcde#的分析过程: 说明abbcde#是例6.1文法G[S]的句子
![对输入串abbcde#的分析过程: 说明abbcde#是例6.1文法G[S]的句子](http://slidesplayer.com/slide/11352245/61/images/91/%E5%AF%B9%E8%BE%93%E5%85%A5%E4%B8%B2abbcde%23%E7%9A%84%E5%88%86%E6%9E%90%E8%BF%87%E7%A8%8B%3A+%E8%AF%B4%E6%98%8Eabbcde%23%E6%98%AF%E4%BE%8B6.1%E6%96%87%E6%B3%95G%5BS%5D%E7%9A%84%E5%8F%A5%E5%AD%90.jpg "对输入串abbcde#的分析过程: 说明abbcde#是例6.1文法G[S]的句子")
92
对输入串abbce#的分析过程 : 说明abbce#不是例6.1文法 G[S]的句子
![对输入串abbce#的分析过程 : 说明abbce#不是例6.1文法 G[S]的句子](http://slidesplayer.com/slide/11352245/61/images/92/%E5%AF%B9%E8%BE%93%E5%85%A5%E4%B8%B2abbce%23%E7%9A%84%E5%88%86%E6%9E%90%E8%BF%87%E7%A8%8B+%3A+%E8%AF%B4%E6%98%8Eabbce%23%E4%B8%8D%E6%98%AF%E4%BE%8B6.1%E6%96%87%E6%B3%95+G%5BS%5D%E7%9A%84%E5%8F%A5%E5%AD%90.jpg "对输入串abbce#的分析过程 : 说明abbce#不是例6.1文法 G[S]的句子")
93
7.3 SLR（1）分析 为什么要引进SLR(1)文法？ SLR（1）文法：其思想是基于容许LR（0）规范族中
有冲突的项目集（状态）用向前查看一个符号的办法 来进行处理，以解决冲突
94
假定LR（0）规范族中含有如下的项目集（状态）I
I＝｛X α·bβ,A γ·,B δ·｝ FOLLOW（A）∩FOLLOW（B）＝Ø FOLLOW（A）∩｛b｝＝Ø FOLLOW（B）∩｛b｝＝ Ø 那么，当在状态I时面临某输入符号为a时，则动作可由 以下规定决策： ①若a=b，则移进 ②若a∈FOLLOW(A)，则用产生式A γ进行归约 ③若a∈FOLLOW(B)，则用产生式B δ进行归约 ④此外，报错
95
假定项目集I （状态）中有m个移进项目： A1 α 1·a1β1， A2 α 2·a2β2，…， Am α m·amβm，同时含有n个归约项目为： B1 γ1·， B2 γ2·，…， Bn γn·， 只要集合｛a1，a2，…，am｝和FOLLOW（B1）， FOLLOW（B2），…， FOLLOW（Bn），两两交集都 为空，仍可用上述规则解决冲突即考查当前输入符号决定 动作：
96
①若a∈｛a1，a2，…，am｝，则移进 ②若a∈FOLLOW(Bi)，i＝1,2,…,n,则用Bi γ i进行归约 ③此外，报错 这种解决冲突动作的办法，称为SLR(1)解决办法，由 F.DeRemer于1971年提出
97
例如P140中G[E]的项目集规范族中的I2： E T · T T·*F 用SLR(1)解决，因为FOLLOW(E)={#,+,)},而移进项目 “·”后为“*”，当I2面临输入输入符号 +,),＃时,应使用产生式E T归约 *时，就移进* 面临其它符号时，则应报错 I1和I9中的冲突都可以按这种方法解决
![例如P140中G[E]的项目集规范族中的I2： E T · T T·*F. 用SLR(1)解决，因为FOLLOW(E)={#,+,)},而移进项目. · 后为 * ，当I2面临输入输入符号.](http://slidesplayer.com/slide/11352245/61/images/97/%E4%BE%8B%E5%A6%82P140%E4%B8%ADG%5BE%5D%E7%9A%84%E9%A1%B9%E7%9B%AE%E9%9B%86%E8%A7%84%E8%8C%83%E6%97%8F%E4%B8%AD%E7%9A%84I2%EF%BC%9A+E+T+%C2%B7+T+T%C2%B7%2AF.+%E7%94%A8SLR%281%29%E8%A7%A3%E5%86%B3%EF%BC%8C%E5%9B%A0%E4%B8%BAFOLLOW%28E%29%3D%7B%23%2C%2B%2C%29%7D%2C%E8%80%8C%E7%A7%BB%E8%BF%9B%E9%A1%B9%E7%9B%AE.+%C2%B7+%E5%90%8E%E4%B8%BA+%2A+%EF%BC%8C%E5%BD%93I2%E9%9D%A2%E4%B8%B4%E8%BE%93%E5%85%A5%E8%BE%93%E5%85%A5%E7%AC%A6%E5%8F%B7..jpg "+,),＃时,应使用产生式E T归约. *时，就移进* 面临其它符号时，则应报错. I1和I9中的冲突都可以按这种方法解决.")
98
改进的SLR（1）分析表的构造方法如下： ①若A α·xβ∈Ii且GOTO(Ii,x)=Ij，x ∈VT,则置 ACTION[i,x] =Sj， x ∈VN,则置GOTO[i,x]=j ②若A α·∈Ii，则对∨x ∈ (VT∪{＃})，且满足 x∈FOLLOW(A)时，置ACTION[i,x]=rj，j为在文法G`中某 产生式A α的序号 ③若S` S·∈Ii，则置ACTION[i,＃]=acc ④凡不能用上述方法填入分析表的元素，均置ERROR(空白)
![改进的SLR（1）分析表的构造方法如下： ①若A α·xβ∈Ii且GOTO(Ii,x)=Ij，x ∈VT,则置. ACTION[i,x] =Sj， x ∈VN,则置GOTO[i,x]=j. ②若A α·∈Ii，则对∨x ∈ (VT∪{＃})，且满足.](http://slidesplayer.com/slide/11352245/61/images/98/%E6%94%B9%E8%BF%9B%E7%9A%84SLR%EF%BC%881%EF%BC%89%E5%88%86%E6%9E%90%E8%A1%A8%E7%9A%84%E6%9E%84%E9%80%A0%E6%96%B9%E6%B3%95%E5%A6%82%E4%B8%8B%EF%BC%9A+%E2%91%A0%E8%8B%A5A+%CE%B1%C2%B7x%CE%B2%E2%88%88Ii%E4%B8%94GOTO%28Ii%2Cx%29%3DIj%EF%BC%8Cx+%E2%88%88VT%2C%E5%88%99%E7%BD%AE.+ACTION%5Bi%2Cx%5D+%3DSj%EF%BC%8C+x+%E2%88%88VN%2C%E5%88%99%E7%BD%AEGOTO%5Bi%2Cx%5D%3Dj.+%E2%91%A1%E8%8B%A5A+%CE%B1%C2%B7%E2%88%88Ii%EF%BC%8C%E5%88%99%E5%AF%B9%E2%88%A8x+%E2%88%88+%28VT%E2%88%AA%7B%EF%BC%83%7D%29%EF%BC%8C%E4%B8%94%E6%BB%A1%E8%B6%B3..jpg "x∈FOLLOW(A)时，置ACTION[i,x]=rj，j为在文法G`中某. 产生式A α的序号. ③若S` S·∈Ii，则置ACTION[i,＃]=acc. ④凡不能用上述方法填入分析表的元素，均置ERROR(空白)")
99
文法G[E]： (0)S` E (1)E E+T (2)E T (3)T T*F (4)T F (5)F (E) (6)F i G[E]的SLR（1）分析表如下：
![文法G[E]： (0)S` E. (1)E E+T. (2)E T. (3)T T*F.](http://slidesplayer.com/slide/11352245/61/images/99/%E6%96%87%E6%B3%95G%5BE%5D%EF%BC%9A+%280%29S%60+E.+%281%29E+E%2BT.+%282%29E+T.+%283%29T+T%2AF..jpg "(4)T F. (5)F (E) (6)F i. G[E]的SLR（1）分析表如下： .")
100
S5 S4 1 2 3 S6 acc r2 S7 r2 r2 r4 r4 r4 r4 S5 S4 8 2 3 r6 r6 r6 r6 S5
ACTION GOTO i + * ( ) # E T F 1 2 3 4 5 6 7 8 9 10 11 S5 S4 1 2 3 S6 acc r2 S7 r2 r2 r4 r4 r4 r4 S5 S4 8 2 3 r6 r6 r6 r6 S5 S4 9 3 S5 S4 10 S6 S11 r1 S7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5
101
G[E]的SLR（1）分析表如下：
![G[E]的SLR（1）分析表如下：](http://slidesplayer.com/slide/11352245/61/images/101/G%5BE%5D%E7%9A%84SLR%EF%BC%881%EF%BC%89%E5%88%86%E6%9E%90%E8%A1%A8%E5%A6%82%E4%B8%8B%EF%BC%9A.jpg "G[E]的SLR（1）分析表如下：")
102
根据这种文法构造的SLR分析表不含多重定义时，称这样
的分析表为SLR分析表，能用SLR分析表的分析器称为 SLR分析器，能构造SLR分析表的文法称为SLR文法
103
7.4 LR（1）分析 为什么要引进LR(1)文法？ 例如文法G`为： （0）S` S （1）S aAd （2）S bAc （3）S aec
（4）S bed （5）A e 识别G`的活前缀的有限自动机DFA，如下图所示，可以发 现在I5和I7中存在移进和归约冲突
104
例如文法G`的产生式如下： （0）S` S （1）S CC （2）C cC （3）C d I0：S` ·S,# S ·CC,＃ C ·cC,c/d C ·d,c/d
106
I5： S ae·c A e· I7： S be·d FOLLOW(A)={c,d} 在I5中，FOLLOW（A）∩｛c｝={c,d} ∩{c} ≠Ø 在I7中，FOLLOW（A）∩｛d｝={c,d} ∩{d} ≠Ø 因此，I5，I7中冲突不能用SLR（1）方法解决 所以我们引进LR(1)文法法解决
107
若[A α·Bβ] ∈I时 则[B ·γ]∈I（B γ为一产生式） 把FIRST（ β）作为用产生式B γ归约的搜索符， 称为向前搜索符，作为归约时查看的符号集合用以代替 SLR（1）分析中的FOLLOW集，把此搜索符号的集合 也放在相应项目的后面，这种处理方法即为LR（1）文法 [A` ·A,#] [A α·Bβ,a] [B ·γ,b] ，其中b ∈FIRST(βa) LR(1)组成：一部分和LR(0)项目相同(称它为心)，另一 部分为向前搜索符集合
![若[A α·Bβ] ∈I时 则[B ·γ]∈I（B γ为一产生式） 把FIRST（ β）作为用产生式B γ归约的搜索符， 称为向前搜索符，作为归约时查看的符号集合用以代替. SLR（1）分析中的FOLLOW集，把此搜索符号的集合.](http://slidesplayer.com/slide/11352245/61/images/107/%E8%8B%A5%5BA+%CE%B1%C2%B7B%CE%B2%5D+%E2%88%88I%E6%97%B6+%E5%88%99%5BB+%C2%B7%CE%B3%5D%E2%88%88I%EF%BC%88B+%CE%B3%E4%B8%BA%E4%B8%80%E4%BA%A7%E7%94%9F%E5%BC%8F%EF%BC%89+%E6%8A%8AFIRST%EF%BC%88+%CE%B2%EF%BC%89%E4%BD%9C%E4%B8%BA%E7%94%A8%E4%BA%A7%E7%94%9F%E5%BC%8FB+%CE%B3%E5%BD%92%E7%BA%A6%E7%9A%84%E6%90%9C%E7%B4%A2%E7%AC%A6%EF%BC%8C+%E7%A7%B0%E4%B8%BA%E5%90%91%E5%89%8D%E6%90%9C%E7%B4%A2%E7%AC%A6%EF%BC%8C%E4%BD%9C%E4%B8%BA%E5%BD%92%E7%BA%A6%E6%97%B6%E6%9F%A5%E7%9C%8B%E7%9A%84%E7%AC%A6%E5%8F%B7%E9%9B%86%E5%90%88%E7%94%A8%E4%BB%A5%E4%BB%A3%E6%9B%BF.+SLR%EF%BC%881%EF%BC%89%E5%88%86%E6%9E%90%E4%B8%AD%E7%9A%84FOLLOW%E9%9B%86%EF%BC%8C%E6%8A%8A%E6%AD%A4%E6%90%9C%E7%B4%A2%E7%AC%A6%E5%8F%B7%E7%9A%84%E9%9B%86%E5%90%88..jpg "也放在相应项目的后面，这种处理方法即为LR（1）文法. [A` ·A,#] [A α·Bβ,a] [B ·γ,b] ，其中b ∈FIRST(βa) LR(1)组成：一部分和LR(0)项目相同(称它为心)，另一. 部分为向前搜索符集合.")
108
一.LR（1）项目集族的构造 （1）构造LR（1）项目集的闭包函数 ①假定I是一个项目集，I的任何项目都属于CLOSURE（I） ②若A α·Bβ，a属于CLOSURE（I）,B γ是文法中的 产生式， β∈V*，b ∈FIRST(βa)，则B ·γ，b也属于 CLOSURE（I）中 ③重复②直到CLOSURE（I）不再增大为止
109
例如文法G`的产生式如下： （0）S` S （1）S CC （2）C cC （3）C d I0：S` ·S,# S ·CC,＃ C ·cC,c/d C ·d,c/d
110
（2）构造转换函数 GO（I，X）＝CLOSURE（J）其中I是LR（1）的项目 集，X是文法符号： J＝{任何形如[A α X·β,a]的项目|[A α ·Xβ,a] ∈I} 对文法G`的LR（1）项目集族的构造仍以[S` ·S,#]为 初态集的初始项目，然后对其求闭包和转换函数，直到 项目集不再增大
![（2）构造转换函数 GO（I，X）＝CLOSURE（J）其中I是LR（1）的项目. 集，X是文法符号： J＝{任何形如[A α X·β,a]的项目|[A α ·Xβ,a] ∈I} 对文法G`的LR（1）项目集族的构造仍以[S` ·S,#]为.](http://slidesplayer.com/slide/11352245/61/images/110/%EF%BC%882%EF%BC%89%E6%9E%84%E9%80%A0%E8%BD%AC%E6%8D%A2%E5%87%BD%E6%95%B0+GO%EF%BC%88I%EF%BC%8CX%EF%BC%89%EF%BC%9DCLOSURE%EF%BC%88J%EF%BC%89%E5%85%B6%E4%B8%ADI%E6%98%AFLR%EF%BC%881%EF%BC%89%E7%9A%84%E9%A1%B9%E7%9B%AE.+%E9%9B%86%EF%BC%8CX%E6%98%AF%E6%96%87%E6%B3%95%E7%AC%A6%E5%8F%B7%EF%BC%9A+J%EF%BC%9D%7B%E4%BB%BB%E4%BD%95%E5%BD%A2%E5%A6%82%5BA+%CE%B1+X%C2%B7%CE%B2%2Ca%5D%E7%9A%84%E9%A1%B9%E7%9B%AE%7C%5BA+%CE%B1+%C2%B7X%CE%B2%2Ca%5D+%E2%88%88I%7D+%E5%AF%B9%E6%96%87%E6%B3%95G%60%E7%9A%84LR%EF%BC%881%EF%BC%89%E9%A1%B9%E7%9B%AE%E9%9B%86%E6%97%8F%E7%9A%84%E6%9E%84%E9%80%A0%E4%BB%8D%E4%BB%A5%5BS%60+%C2%B7S%2C%23%5D%E4%B8%BA..jpg "初态集的初始项目，然后对其求闭包和转换函数，直到. 项目集不再增大.")
111
I1：S` S ·,# I2：S C ·C,# C ·cC,＃ C ·d,# I3：C c ·C,c/d C ·cC,c/d C ·d,c/d I4：C d ·,c/d I5：S CC ·,# I6：C c ·C,# C ·cC,# C ·d,#
112
I7：C d ·,# I8：C c C·,c/d I9：C c C ·, #
113
构造出的LR(1)项目集规范族C和GO函数如下图：
114
二.LR（1）分析表的构造 ①若[ A α ·aβ,b] ∈Ii，且GO(Ii,a)=Ij，a∈VT,则置 ACTION[i,a]=Sj。若GO(Ii,A)=Ij，A∈VN,则置GO[i,A]=j ②若[ A α ·,a] ∈Ii，则置ACTION[i,a]=rj。j为在文法 中对产生式A α的编号 ③若[ S` S·,#] ∈Ii，则置ACTION[i,#]=acc ④凡不能用上述方法填入分析表的元素，均置ERROR(空白)
![二.LR（1）分析表的构造 ①若[ A α ·aβ,b] ∈Ii，且GO(Ii,a)=Ij，a∈VT,则置. ACTION[i,a]=Sj。若GO(Ii,A)=Ij，A∈VN,则置GO[i,A]=j.](http://slidesplayer.com/slide/11352245/61/images/114/%E4%BA%8C.LR%EF%BC%881%EF%BC%89%E5%88%86%E6%9E%90%E8%A1%A8%E7%9A%84%E6%9E%84%E9%80%A0+%E2%91%A0%E8%8B%A5%5B+A+%CE%B1+%C2%B7a%CE%B2%2Cb%5D+%E2%88%88Ii%EF%BC%8C%E4%B8%94GO%28Ii%2Ca%29%3DIj%EF%BC%8Ca%E2%88%88VT%2C%E5%88%99%E7%BD%AE.+ACTION%5Bi%2Ca%5D%3DSj%E3%80%82%E8%8B%A5GO%28Ii%2CA%29%3DIj%EF%BC%8CA%E2%88%88VN%2C%E5%88%99%E7%BD%AEGO%5Bi%2CA%5D%3Dj..jpg "②若[ A α ·,a] ∈Ii，则置ACTION[i,a]=rj。j为在文法. 中对产生式A α的编号. ③若[ S` S·,#] ∈Ii，则置ACTION[i,#]=acc. ④凡不能用上述方法填入分析表的元素，均置ERROR(空白)")
115
例如文法G`的LR(1)分析表如下： s3 s4 1 2 acc s6 s7 5 s3 s4 8 r3 r3 r1 s6 s7 9 r3
ACTION GO c d # S C 1 2 3 4 5 6 7 8 9 s3 s4 1 2 acc s6 s7 5 s3 s4 8 r3 r3 r1 s6 s7 9 r3 r2 r2 r2
116
根据这种文法构造的LR（1）分析表不含多重定义时，称
这样的分析表为LR（1）分析表，能用LR（1）分析表的 分析器称为LR（1）分析器（规范的LR分析器），能构造 的LR（1）分析表的文法称为LR（1）文法
117
例给定文法： A A(A)| ε （1）构造LR（0）分析表，说明该文法是否为LR（0）文 法。如果不是指出分析表中存在的动作冲突； （2）构造SLR（1）分析表，说明该文法是否为SLR（1） 文法，为什么？ （3）构造LR（1）分析表，说明该文法是否为LR（1）文 法，为什么？
118
对文法进行拓广： （0）S A （1）A A(A) （2）A ε 构造识别活前缀的DFA： I0： S ·A A ·A(A) A · I1： S A · A A ·(A) I2： A A(·A) A ·A(A) A · A ( A ( I3： S A(A ·) A A ·(A) ) I4： A A(A)·
119
设计的LR(0)分析表如下： ACTION GO （ ） # A r2 1 s2 acc 2 3 s4 4 r1 由于构造出的LR(0)分析表不含多重入口，所以是LR(0)文法
120
设计的SLR(1)分析表如下： ACTION GO （ ） # A r2 1 s2 acc 2 3 s4 4 r1 由于构造出的SLR(1)分析表不含多重入口，所以是SLR(1)文法
121
构造LR(1)项目集规范族： I2： A A(·A),#/( A ·A(A),(/) A ·,(/) I0： S ·A,# A ·A(A),# A ·,# A ·A(A),( A ·,( I1： S A ·,# A A· (A),#/( A ( A ) I4： A A (A)·,#/( I3： A A (A·),#/( A A· (A),(/) ( I5： A A(·A),(/) A ·A(A),(/) A ·,(/) ) I7： A A (A·),(/) A A· (A),(/) A I6： A A (A)·,(/) (
122
设计的LR(1)分析表如下： ACTION GO （ ） # A r2 1 s2 acc 2 3 s5 s4 4 r1 5 7 6 s6 由于构造出的LR(1)分析表不含多重入口，所以是LR(1)文法
123
7.5 LALR（1）分析 为什么要引进LALR(1)文法？ 若文法G`为： （0）S` S （1）S BB （2）B aB （3）B b
124
LR(1)项目集和转换函数 : B
125
LR(1)分析表:
126
这个文法是LR(0)文法吗？ 分析这个LR(1)每个项目集的项目，可以发现，即使不考 查搜索符，它的任何项目集中都没有动作冲突，因此这 个文法是LR(0)文法 构造LR(0)项目集，它有几个状态？ ７个，而现在LR(1)有10个状态，为什么多３个？ 因为I3和I6,I4和I7,I8和I9分别为同心集 对于类似ALGOL一类的高级语言，处理它的LR分析表可 能要1000个状态，而用LALR分析器，只需要100个
127
LALR：向前看LR技术 介于规范LR分析器构造法和SLR分析器构造法之间的一 种方法 LALR分析表比规范LR分析表小很多,当然能力差一点， 但它却能处理一些SLR分析器难以处理的情况 LALR文法能描述大多数常用高级程序语言的语法结构 采用对LR（1）项目集规范族合并同心集的方法，若合 并同心集后不产生新的冲突，则为LALR（1）项目集
128
例如对图7.12合并同心集后为： I3，I6：B a·B,a/b/# B ·aB,a/b/# B ·b,a/b/# I4,I7: B b·,a/b/# I8,I9: B aB·,a/b/# 同心集合并后仍不包含冲突，因此该文法是LALR(1)
129
合并同心集有几个问题需要说明： （1）同心集是指心相同的项目集合并在一起，因此同心 集合并后心仍相同，只是超前搜索符集合为各同心集超 前搜索符集合的和集 （2）对于合并同心集后的项目集经转换函数所达仍为同 心集 （3）合并同心集后对某些错误发现的时间会产生推迟现 象，但错误的出现位置仍是准确的
130
（4）同心集合并后不会产生“移进-归约”冲突，但会
产生“归约-归约”冲突 {[A c·,d]， [B c·,e]} {[A c·,e]， [B c·,d]} 合并后，得到 A c·,d/e B c·,d/e
131
根据合并同心集后的项目集族构造该文法的LALR（1）
分析表，其构造步骤如下： (1)构造文法G的LR（1）项目集族，C＝{I0,I1,…,In} (2)合并所有的同心集，使C变为C`＝{J0,J1,…,Jm}，便是 LALR（1）的项目集 (3)据C`构造动作表，其方法与LR（1）分析表的构造相 同①②③④
132
例如文法G`的产生式如下： （0）S` S （1）S CC （2）C cC （3）C d
133
同心集：I3和I6 I4和I7 I8和I9 :
134
I0：S` ·S,# S ·CC,＃ C ·cC,c/d C ·d,c/d
135
I1：S` S ·,# I2：S C ·C,# C ·cC,＃ C ·d,# I3,6：C c ·C,c/d/# C ·cC,c/d/# C ·d,c/d/# I4,7：C d ·,c/d/# I5：S CC ·,# I8,9：C c C ·,c/d/#
136
合并同心集后项目集规范族和goto函数:
137
LALR分析表:
138
根据这种文法构造的LALR分析表不含多重定义时，称
这样的分析表为LALR分析表，能用LALR分析表的 分析器称为LALR分析器，能构造LALR分析表的文法称 为LALR文法
139
四种LR类型： LR(0) 、SLR(1) 、 LALR(1) 、 LR(1) 功能逐个增强 四种LR类型的文法是真包含关系 一个文法是LR(1)文法一定是LR(0)文法吗？
140
如何判断一个文法是哪一种文法呢？ 例：有文法G１（S`）的产生式如下： （0）S` S （1）S L＝R （2）S R （3）L *R （4）L i （5）R L 该文法的LR（0）项目集规范族为：
141
I0： S` ·S R ·L S ·L＝R L ·*R S ·R L ·i L ·*R I5： L i· L ·i I6： S L=·R R ·L R ·L I1： S` S · L ·*R I2： S L·=R L ·i R L· I7：L *R· I3: S R· I8：R L· I4： L *·R I9： S L=R· 在项目集I2中存在移进项目S L·＝R和归约项目 R L·，因此该文法不是LR（0）文法
142
由文法的产生式规则可求出FOLLOW（R）＝{#,=},所以
FOLLOW（R）∩{=} = {#,=} ∩{=} ≠Ø，因而在I2中存 在移进－归约冲突不能用SLR（1）方法解决，说明该文 法不是SLR（1）文法 上述文法的LR（1）项目集族及转换函数如下图所示：
143
S
144
合并同心集后的项目集分别是： I4,I11： L *·R,=/# R ·L,=/# L ·i,=/# L ·*R,=/# I5,I12: L i·,=/# I7,I13: L *R·,=/# I8,I10: R L·,=/# 进一步考察这些合并同心集后的项目集，发现它们仍 不含归约－归约冲突，因此我们可以判定该文法是LALR（ 1）文法,也是LR(1)方法,但却不是LR（0）和SLR（1）文法
145
相应的LALR（1）分析表：
146
例：有文法G２（S`）的产生式如下： （0）S` S （1）S aAd （2）S bBd （3）S aBe （4）S bAe （5）A c （6）B c
147
直接构造它的LR（1）项目集如下： I0： S` ·S,# I4： S aA·d ,# S ·aAd ,# I5： S aB·e ,# S ·bBd ,# I6： A c·,d S ·aBe ,# B c·,e S ·bAe,# I7： S bB·d ,# I1： S` S · ,# I8： S bA·e ,# I2： S a·Ad ,# I9： A c·,e S a·Be ,# B c·,d A ·c,d I10： S aAd· ,# B ·c,e I11： S aBe· ,# I3: S b·Bd ,# I13： S bBd· ,# S b·Ae ,# I14： S bAe· ,# B ·c,d A ·c,e
148
检查每个项目集Ii可知，在任一项目集中都不含移进－归
约冲突或归约－归约冲突。因此文法是LR（1）的，进一 步查看项目集可发现,I6和I9是同心集,若合并后则变为： I6,9： A c·,d/e B c·,e/d 这样就出现了新的归约－归约冲突，因而可判定该文法不 是LALR（1）文法，当然也不可能是SLR（1）和LR（0 ）方法
149
7.6 二义性文法在LR分析中的应用 LR文法是二义性的吗？ 为什么要介绍二义性文法的使用？
因为对某些二义性文法只要加进足够的无二义性规则，它 可以构造出比相应非二义性文法更优越的LR分析器 无二义性规则：为消除由于二义性引起冲突的规则 当“移进－归约”冲突，采用移进；当“归约－归约”冲突， 优先使用列在前面的产生式进行归约 归定优先性和结合性
150
例如：考虑文法： 0 S` S 1 S iSeS 2 S iS 3 S a 这个文法是二义性文法吗？ 它像程序语言中什么语句？ 它是“if-then-else”或“if-then”语句的抽象
151
它的LR(0)项目集规范族如图所示： I4: S iS·eS S iS· I0: S` ·S S ·iSeS S ·iS S ·a I1: S` S · S S i i e I2: S i·SeS S i·S S ·iSeS S ·a I5: S iSe·S S ·iSeS S ·iS S ·a i a a I3: S a· a S I6: S iSeS·
152
利用前面的规则（让else与最近的then匹配），构造出LR 分析表如下：
可以看出，I4存在“移进－归约”冲突 利用前面的规则（让else与最近的then匹配），构造出LR 分析表如下： 状态 ACTION GO i e a # S 1 2 3 4 5 6 s2 s3 1 acc s2 s3 4 r3 r3 s5 r2 s2 s3 6 r1 r1
153
利用这个分析器分析输入串iiaea的过程如下：
步骤 状态栈 符号栈 输入串 ACTION GO (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) # iiaea# s2 02 #i iaea# s2 s3 022 #ii aea# r3 0223 #iia ea# 4 s5 0224 #iiS ea# s3 02245 #iiSe a# r3 6 022453 #iiSea # #iiSeS r1 4 022456 # r2 1 024 #iS # acc 01 #S #
154
7.7 语法分析程序的自动构造工具YACC YACC（Yet Another Compiler -Compiler）是20世纪
70年代由Johnson等人在美国Bell实验室研制开发的一 个基于LALR（1）的语法分析程序的构造工具
155
YACC接受一个用BNF描述的上下文无关语言的语法规
则，且语法满足LALR（1）文法的要求，据其自动生 成相应的LALR（1）分析表，并与它的驱动程序和分 析栈结合构成一个LALR（1）分析器yyparse YACC仅是一个语法分析器的自动生成器，相应的语义 处理程序还需人工编写
156
YACC还可以处理某些二义性文法的规则 由YACC源程序得到语法分析器需要经过如图7.14两步 完成：
157
YACC与词法分析程序的接口称为yylex。
通常YACC和词法分析器的自动生成工具LEX联合应用是 一种较好的选择，其工作示意图7.15所示：
158
YACC源程序的组成： 说明部分： 用%{和}%括起的部分说明语义动作中使用的数据类型、 全局变量、语义值和联系类型等 用%开头的说明语法规则中的终结符及运算符的优先级 语法规则部分：由多个候选产生式组成 程序段部分：由完成语义动作的一些函数组成
159
对YACC源程序中由%{和%}括起的说明部分，{}内的语义
y.tab.c中，再经过C编译程序编译后才得到用YACC所生成 的语法分析器yyparse
160
现用为生成pl/o语法的子集spl/o解释器而使用LEX和YACC
编写的YACC源程序片段为例，了解YACC的使用：P157
161
7.8 典型例题及解答 例题1 文法G[S]为： S AB A aBa|ε B bAb| ε 1.该文法是SLR（1）的吗？
7.8 典型例题及解答 例题1 文法G[S]为： S AB A aBa|ε B bAb| ε 1.该文法是SLR（1）的吗？ 2.若是请构造它的分析表 3.给出输入串baab#的分析过程
![7.8 典型例题及解答 例题1 文法G[S]为： S AB A aBa|ε B bAb| ε 1.该文法是SLR（1）的吗？](http://slidesplayer.com/slide/11352245/61/images/161/7.8+%E5%85%B8%E5%9E%8B%E4%BE%8B%E9%A2%98%E5%8F%8A%E8%A7%A3%E7%AD%94+%E4%BE%8B%E9%A2%981+%E6%96%87%E6%B3%95G%5BS%5D%E4%B8%BA%EF%BC%9A+S+AB+A+aBa%7C%CE%B5+B+bAb%7C+%CE%B5+1.%E8%AF%A5%E6%96%87%E6%B3%95%E6%98%AFSLR%EF%BC%881%EF%BC%89%E7%9A%84%E5%90%97%EF%BC%9F.jpg "7.8 典型例题及解答. 例题1 文法G[S]为： S AB. A aBa|ε. B bAb| ε. 1.该文法是SLR（1）的吗？ 2.若是请构造它的分析表. 3.给出输入串baab#的分析过程.")
162
例题2 文法G[S]为： S S;M|M M MbD|D D D(S)| ε 1.证明G[S]是SLR（1）文法，并构造它的分析表 2.给出G[S]的LR（1）项目集规范族中的I0
![例题2 文法G[S]为： S S;M|M M MbD|D D D(S)| ε 1.证明G[S]是SLR（1）文法，并构造它的分析表 2.给出G[S]的LR（1）项目集规范族中的I0](http://slidesplayer.com/slide/11352245/61/images/162/%E4%BE%8B%E9%A2%982+%E6%96%87%E6%B3%95G%5BS%5D%E4%B8%BA%EF%BC%9A+S+S%3BM%7CM+M+MbD%7CD+D+D%28S%29%7C+%CE%B5+1.%E8%AF%81%E6%98%8EG%5BS%5D%E6%98%AFSLR%EF%BC%881%EF%BC%89%E6%96%87%E6%B3%95%EF%BC%8C%E5%B9%B6%E6%9E%84%E9%80%A0%E5%AE%83%E7%9A%84%E5%88%86%E6%9E%90%E8%A1%A8+2.%E7%BB%99%E5%87%BAG%5BS%5D%E7%9A%84LR%EF%BC%881%EF%BC%89%E9%A1%B9%E7%9B%AE%E9%9B%86%E8%A7%84%E8%8C%83%E6%97%8F%E4%B8%AD%E7%9A%84I0.jpg "例题2 文法G[S]为： S S;M|M M MbD|D D D(S)| ε 1.证明G[S]是SLR（1）文法，并构造它的分析表 2.给出G[S]的LR（1）项目集规范族中的I0")
163
例题3 文法G[S]为： S AdD| ε A aAd| ε D DdA|b| ε 1.证明G[S]不是LR（0）和SLR（1）文法 2.判断G[S]是否是LR（1）和LALA（1）文法 3.若2成立，请构造它们相应的分析表
![例题3 文法G[S]为： S AdD| ε. A aAd| ε. D DdA|b| ε. 1.证明G[S]不是LR（0）和SLR（1）文法. 2.判断G[S]是否是LR（1）和LALA（1）文法.](http://slidesplayer.com/slide/11352245/61/images/163/%E4%BE%8B%E9%A2%983+%E6%96%87%E6%B3%95G%5BS%5D%E4%B8%BA%EF%BC%9A+S+AdD%7C+%CE%B5.+A+aAd%7C+%CE%B5.+D+DdA%7Cb%7C+%CE%B5.+1.%E8%AF%81%E6%98%8EG%5BS%5D%E4%B8%8D%E6%98%AFLR%EF%BC%880%EF%BC%89%E5%92%8CSLR%EF%BC%881%EF%BC%89%E6%96%87%E6%B3%95.+2.%E5%88%A4%E6%96%ADG%5BS%5D%E6%98%AF%E5%90%A6%E6%98%AFLR%EF%BC%881%EF%BC%89%E5%92%8CLALA%EF%BC%881%EF%BC%89%E6%96%87%E6%B3%95..jpg "3.若2成立，请构造它们相应的分析表.")
164
【本章小结】 LR分析的特征是： ◇ 归约过程是规范的： ◇符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)。 ◇ 分析决策依据栈顶状态和现行输入符号是什么来决定的。 ◇为构造LR分析表，可先构造识别活前缀和句柄的DFA。 ◇ LR分析器的关键部分是分析表的构造, 对一个文法能判断是否是LR类文法，能构造相应的LR分析表，并能对给定的输入串进行分析以决定该输入串是否为所给文法的句子 ◇ 四种LR类型： LR(0) SLR(1) LALR(1) LR(1) 功能逐个增强
165
◇ 四种LR类型的文法是真包含关系 ◇ 四种LR类分析器的作用 ◇ LR类型文法是无二义的 ◇ 某些二义性文法，人为地给出优先性和结合性的规定，可能构造出比相应非二义性文法更优越的LR分析器。
166
第7章 作业题 P165： 1. 3. 6. 16.
Similar presentations
