当前位置：文档之家 › 编译原理 六章 LR分析法

编译原理 六章 LR分析法

  • 格式：doc
  • 大小：247.50 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

第六章 LR分析法

第六章 LR分析法
四种分析法: – LR(0) SLR(1) LR(1) LALR(1)
3
6.1 LR分析概述
一个分析栈、一个驱动程序和一张分析表； 一个输入、一个输出。
输入
id+id*id#
状态栈 符号栈
im
Ym
im-1 Ym-1
…… i0 # 分析栈
LR驱动程序
输出
分
动作
转移 析
action goto
表
4
特殊性
#aAcd
e#
#aAcB
e#
#aAcBe
#
#S
#
动作 移进
移进 归约(A→b) 移进 归约(A→Ab) 移进 移进 归约(B→d) 移进
归约(S→aAcBe) 接受
注意：在分析 过程中,符号
S
栈内容连接剩
余输入串恰为
句型。
A
A
B
a b b c de
输出结果
文法G[S]： (1)S→aAcBe (2)A→b (3)A→Ab (4)B→d
ACTION[i,a]= 归约
接受
出错
7
-移进Shift:
表示:ACTION[i,a]=Sj 动作:状态j和输入符号a分别入符号
栈和状态栈，输入串向前进一字符。
-归约reduce:
表示:ACTION[i,a]=rk 其中: k表示第k个产生式。
动作:设第k个产生式右部长度为m, 左边非终结符为A,距状态栈栈顶m个 位置的状态为p。
造LR分析表。
17
拓广文法：
• 引入一新非终结符作为文法的新开始符，
添加一新产生式： S’→S :S’为新开始符，S为原来的开始符号。
• 拓展文法的目的： • 使文法只有一个以识别符号作为左部的产生

编译原理 第6章-LR分析-小结资料

编译原理 第6章-LR分析-小结资料
LR(0)项目集规范族; 对LR(1)或 LALR(1)分析表，构造 LR(1)项目集规范族。
Compiler Construction Principles
(2)构造识别文法规范句型活前缀的DFA。 (3)将DFA转换成相应的LR分析表。
四种分析表的构造基本相同，仅对含 归约项目的项目集构造分析表元素不同。
构造该文法的LR(0)项目集族和转换函 数如下图所示。
I0:
S′→·S S →·(S)
S
S →·
(
S
I2:SS S
→(·S) →·(S) →·
(
I1: S'→S.
I3: S →(S·) )
I4: S →(S)·
0. S' →S 1. S →(S) 2. S →ε
见表
该文法不是LR(0)文法。因为I0，I2中 含有移进—归约的冲突。
)
I6: S→S(S·), )/(
2. S → ε S →· , )/(
S →S·(S), )/(
Compiler Construction Principles
所有的LR(1)项目集中没有移进—归约 的冲突,所以该文法为LR(1)文法 或该文法为SLR(1)文法, 任何SLR(1)文 法都是LR(1)或LALR(1)文法
3 S2 S4
4 r1 r1 r1
FOLLOW(S) ={ #, (, ) }
Compiler Construction Principles
步骤 栈中状态
10
2 01
3 012
4 0123
5 01232
6
012323
7 0123234
8 0123
9 01234

编译原理 第06章_LR分析法(3)

编译原理 第06章_LR分析法(3)
同
的。将同心集合并为： I5,12: L→i•, =/# I4,11: L→*•R, =/# R→•L, =/# I7,13: L→*R•, =/# L→•*R, =/# I8,10: R→L•, =/# L→•i, =/#
6.4 LALR(1)分析法
我们看到合并同心集后的项目集其核心 部分不变，仅搜索符合并。对合并同心集后 的项目集的转换函数为GO(I,X)自身的合并， 这是因为相同的心之转换函数仍属同心集， 例如： GO(I4,11, i)=GO(I4, i)∪GO(I11, i)= I5,12 GO(I4,11, R)=GO(I4, R)∪GO(I11, R)= I7,13 GO(I4,11, *)=GO(I4, *)∪GO(I11, *)= I4,11
0. S' →S 1. S →L=R
2. S →R 3. L →*R
4. L →i 5. R →L
6.4 LALR(1)分析法
3. 若LALR(1)项目集族中不存在归约一 归约冲突，则该文法是LALR(1)文法。对例 中的文法，由于合并同心集后不存在归约— 归约冲突，所以该文法是LALR(1)文法。
S'→•S,# I0: R→•L,# S→•L=R,# L I :R→L•,# L→• * R,# S→•R,# 10 L I2:S→L•=R,# L→•i,# L→•*R,=/# L R→L•,# * i L→•i,=/# i R I11: L→*•R,# R→•L,# I3: S→R•,# I12: L→i•,# R→•L,# * i L→• * R,# R L→ * •R,=/# I4: I13:L→*R•,# L→•i,# R→•L,=/# I5: L→i•,=/# L→•*R,=/# R * i I7: L→*R•,=/# L→•i,=/#

《编译原理LR分析》ppt课件

《编译原理LR分析》ppt课件

a
– aAb[3]
a,aA
– aAcd[4]
a,aA,aAc
– aAcBe[1]
a,aA,aAc,aAcB
ＬＲ分析程序
LR 文法 对于一个cfg 文法, 假如可以构造一张 LR 分析表, 使得它的每一个入口均是唯一的 〔Sj,rj,acc,空白〕，那么称该 cfg 是LR 文法．
ＬＲ分析
特征: – ．标准的 – ．符号栈中的符号是标准句型的前缀，
动作
移进 移进 归约(A→b) 移进 归约(A→Ab) 移进 移进 归约(B→d) 移进 归约 承受
对输入串abbcde#的移进-规约分析过程
符号串abbcde是否是G[S]的子
S aAcBe aAcde aAbcde abbcde
步骤 符号栈 输入符号串 动作
状态栈 ACTION GOTO
1〕 #
LR〔0〕LC〔Ab〕=ab
LR〔0〕LC〔AAb〕=aAb
LR〔0〕LC〔Bd〕=aAcd 的正规式
〔 =VnVt〕上
x
0 S①
2
a 3
b④
5
a
A 6
7
b
⑧
9
a
A
c
10
11
12
d⒀
a
A
c
14 15
16
17
B 18 e ⒆
DFA
a
A
b
x
2
3
6
S
b
1
4
c
B
e
5
7
9
d
8
构造LR〔0〕工程集标准族
活前缀与句柄的关系：
G[S]:
R
=>αβω

编译原理-清华大学-第6章-LR分析法(2+1,2+1)

编译原理-清华大学-第6章-LR分析法(2+1,2+1)
出错。
r1 5
三、LR分析算法
状态/符号
Sm Xm Sm-1Xm-1 …… …… …… S1 X1
0#
输入缓冲区 a1…ai…an#
LR主控 程序
动作表 转移表 action goto
产生式 序列
分析表
置ip指向输入串w的第一个符号；
状态0和符号#分别进分析栈；
令S为状态栈的栈顶状态；a是ip指向的符号；
作为DFA的初始状态。
21
3）定义状态转换函数GO (产生新的项目集）
GO(I,X)定义为CLOSURE(J)，其中I,J都是项目集， X(VN∪VT), J={AX•|当A•XI}。
J 的构造方法类似于词法分析的 MOVE函数
GO(I,X)类似于 CLOSURE（ MOVE（I，X））
4）构造LR(0)项目集规范族的算法
2、S′S• 称为句子识别态或接受项目；
3、转换关系：项目i为XX1…Xi-1•Xi…Xn, 项目j为XX1…Xi • Xi＋1…Xn， 则从项目i画一弧线射向j，标记为Xi；
4、若项目i为X•A，其中A是非终结符，则从i项目画 弧射向所有A•的项目，V*
5、规约项目为终态用双圈表示，双圈外有*号者为接受态 18
(最左规约，规范规约)
ab[2]b[3]cd[4]e[1]
(用[2]归约)
<= aAb[3]cd[4]e[1]
<= aAcd[4]e[1] <= aAcBe[1]
(用[3]归约) (用[4]归约) (用[1]归约)
<= S
其中<=表示规约
问题:在归约过程中,那些是可归前缀?
13
4、活前缀：G=(Vn,Vt,P,S'), 若有规范推导 S′* αAωαβω,

编译原理-LR分析法 PPT

编译原理-LR分析法 PPT
EE+T | T TT*F | F F (E) | id
并用SLR(1)方法分析id*id+id∈L(G[E]) ?
G的拓广文法G[E]：
(0) E E
(4) TF
(1) EE+T
(5) F (E)
(2) ET
(6) F id
(3) TT*F
I0:E.E E.E+T E.T T.T*F T.F F.(E) F.id
Q = G的LR(0)项目集规范族, q0 = closure( {S.S} )， F = 所有含归约项目的有效项目集组成的集合， = go(I,X) )。
若将所有状态均视为终态，则识别活前缀的自动 机DFA M= ( = VTVN,
Q = G的LR(0)项目集规范族, q0 = closure({S.S})， F = Q， = go (I,X) )。
I8: (I4,A) AcA.
I9: (I5,B) BcB.
I10: (I4,d) Ad.
I11: (I3,d) Bd.
识别文法 活前缀的DFA
c
a
S.S
start S.aA
S
S.bB
I0
b
c
Ac.A A.cA A.d
I4 c
Sa.A A.cA A.d
I2
Sb.B B.cB B.d
J ={A X . | A . X I }
称函数go(I, X)为转移函数。
项目A X . 称为项目A . X后继。
二、识别句柄和活前缀的自动机
若文法G = ( VT, VN, S, P)，则识别G的句柄的自动 机为DFA M = ( = VTVN，
B 是产生式，则项目 B . 对活前缀 = 1 也是 有效的。

第六章编译原理


1. 分析栈中的文法符号+栈外余留输入串 规范句型 2. 规约实质：不断进栈，等待栈顶形成当前句型的句柄 3 句柄一定是产生式的右部候选式
关键：找出当前句型的“可归约串x”
最左素短语 算符优先分析法
句柄
L(R)文法 如何找当前句柄归约？
1.
引入一个新的状态栈来表示符号栈中的符 号目前状态 用LR分析表来表示不同状态下对于各输入 符号应采取的动作
对符号串＃a，b＃的分析过程 步骤 1 2 3 4 5 6 状态栈 符号栈 余留符号 产生式 ACTION/GOTO
S0
S0 S3 S0 S2 S0 S2 S5
#
#a #B #B,
a,b#
,b# ,b# b# # # # # B→b A→B A→B,A B→a
S3
γ S5 S4 γ γ γ
4， 2 2 ，6 3 ，2
1
2
3
8
2 9
3 3 10
6
7 8 9 10 11
6.4 SLR 分析表的构造
为了解决LR(0)中一个项目集合中存在“移进—归约”和“归 约—归约“冲突，而产生的。
例 6.2 P102 的LR(0) 分析表
解决冲突的办法: 对于一个状态Si的项目集: Si={A→α △β ,B→γ △,C→δ △} 其中, α , γ , δ ∈V* First(β )∈VT 存在“移进—归约” “归约—归约”冲突 若Follow(B)∩Follow(C)∩First(β )=ф 则 当输入符号为a时,(a∈VT∪’#’)
则C→△γ ∈CLOSURE(I) b. 重复b,直到CLOSURE(I)不再增加为止.
论述： 1 .把G[
S
]第一个项目 S →△S作为初始状态项目集的核

编译原理 第6章课件

第6章ＬＲ分析法教学要求:１．掌握：活前缀的概念，２．理解：LR （0 ）, SLR （1）, LR(1)和LALR(1)分析过程，各类分析表的构造３．了解：二义性文法在LR 分析中的应用目录 6.1 LR 分析概述6.2 LR (0) 分析6.3 SLR(1) 分析6.4 LR （1）分析6.5 LALR(1)分析6.6 二义性文法在LR 分析中的应用强调算符之间的优先关系的唯一性，这使得它的适应面比较窄算法在发现最左素短语的尾时，需要回头寻找对应的头LR(k)分析法可分析LR(k)文法产生的语言– L ：从左到右扫描输入符号，– R ：最右推导对应的最左归约(反序完成最右推导)– k ：向前读入k 个符号，以便确定归约用的产生式LR 分析法正是给出一种能根据当前分析栈中的符号串和向右顺序查看输入串的K 个（ K ≥0）符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。

LR 分析法的归约过程是规范推导的逆过程，所以LR 分析过程是一种规范归约过程。

6.1 ＬＲ分析概述Ｌ：从左到右扫描输入串R ： 最右推导的逆过程分析器模型和分析算法• ＬＲ分析特征讨论说明：S[i] 为状态栈， X[i]为文法符号栈。

状态转换表用GOTO[S i ,X]= S j 表示，规定当栈顶状态为S i ，遇到当前文法符号为X 时应转向状态S j ，X 为终结符号或非终结符号。

ACTION[S i ,a]规定了栈顶状态为S i ，遇到输入符号为a 应执行的动作。

动作有如下四种： 移进： S j = GOTO[S i ,a]移入状态栈，a 移入到文法符号栈。

归约： 栈顶形成句柄为β时，文法有产生式 A →β，若 β的长度为r ，则从两个栈顶去掉r 个符号，把A 移入符号栈，S j =GOTO[S i ,A] 移入状态栈。

接受acc 报错LR 分析算法 置ip 指向输入串w 的第一个符号 令S 为栈顶状态 a 是ip 指向的符号 重复 begin if ACTION[S,a]=S j then begin PUSH j,a(进栈)ip 前进(指向下一输入符号) end else if ACTION[S,a]=r j (第j 条产生式为A →β)then beginpop |β| 项令当前栈顶状态为S’push GOTO[S’,A]和A(进栈)end else if ACTION[s,a]=accthen return (成功）else errorend.重复LR 文法:对于一个上下文无关文法（Context Free Grammar)-cfg 文法, 如果能 够构造一张 LR 分析表, 使得它的每一个入口均是唯一的（Sj,rj,acc,空白）， 则称该 cfg 是LR 文法．ＬＲ分析:特征:规范的符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)分析决策依据:栈顶状态和现行输入符号．• 四种技术 LR(0) SLR(1) LR(1) LALR(1)6.2 LR(0) 分析LR(0)文法--------能力最弱，理论上最重要:存在FA 识别活前缀识别活前缀的DFA 如何构造（LR(0)项目集规范族的构造）LR(0)分析表的构造一、可归约前缀和子前缀最右推导过程（每条产生式尾部加上编号）S ⇒aAcBe[1] ⇒aAcd[4]e[1] ⇒aAb[3]cd[4]e[1]⇒ab[2]b[3]cd[4]e[1]归约时在栈里的句型的前缀 归约前可在栈里的规范句型(不含句柄) 的前缀 ab[2] aaAb[3] a,aAaAcd[4] a,aA,aAcaAcBe[1] a,aA,aAc,aAcB可归约前 子前缀活前缀（viable prefixes ）G=(Vn,Vt,P,S),若有S’ ⇒ αA ω ⇒ αβω,γ是αβ的前缀,则称是文法G 的活 前缀. 其中S’是对原文法扩充(S’→S)增加的非终结符.? 为使S’不出现在任何产生式的右部.活前缀是规范句型（右句型)的前缀，但不超过句柄移进归约分析的栈中出现的内容加上余留输入构成规范句型二、识别活前缀的FA启示:可以把非终结符号和终结符号都看成一个FA 的输入符号，每把一个符号 进栈时看成已识别过了该符号，而状态进行转换，当识别到可归约前缀 时，相当于在栈顶形成了句柄，则认为达到了识别句柄的终态。

编译原理LR分析法

编译原理LR分析法
编译原理是研究如何将高级语言程序转换成等价的低级机器语言程序的学科， LR分析法是其中一种重要的语法分析方法。
何为编译原理
编译原理是计算机科学的一个分支，研究将高级语言程序转换为等价的底层机器代码的过程。它涉及词法分析、 语法分析、语义分析、优化和代码生成等多个阶段。
LR分析法的概述
LR分析法的步骤
1
1. 构建LR项集族
基于文法的产生式，生成LR(0)项集族，
2. 构建LR分析表
2
包括起始项集和其它项集。
根据LR项集族和文法的终结符和非终结
符，构建LR分析表，包括移进、规约和
接受操作。Leabharlann 33. 进行语法分析
使用构建的LR分析表，对输入的符号串 进行逐步解析，直到接受或出错。
构建LR分析表
项集的闭包
通过对项集进行闭包运算，计算 出项集中的所有项。
项集的转移
根据项目集的状态和接收符号， 进行项集的状态转移。
规约项的处理
确定规约的产生式和规约动作， 构建规约表。
LR分析表的使用
使用构建的LR分析表，可进行能够解析输入符号串的自底向上语法分析。它 根据输入符号和栈顶符号，执行移进、规约或接受操作来推导和验证语法结 构。
优缺点和应用
优点
具有广泛适用性，支持大多 数上下文无关文法。解析效 率高，能够快速生成语法树。
缺点
对于某些复杂的语法，可能 需要构建大型的分析表。编 写LR分析器的难度较高。
应用
LR分析法被广泛用于编译器 设计、解析器生成器和语法 分析工具的开发中。
LR分析法是一种自底向上的语法分析方法，用于构建一个确定性的有限状态 自动机（LR自动机）以解析各种语法结构。它具有广泛的应用，包括编译器 设计和语法分析工具的开发。

编译原理chapter6

3、接受
宣布分析成功，退出总控程序。
第六章 LR分析法及分析程序构造 第二节 LR分析器 三、LR分析器的总控程序
4、报错
报告输入串含有错误，调用相应错误错误 处理程序。
注：1)不管哪一类分析程序，总控程序的动作 都一样。
2)LR分析器的动作情况也可以描述成机器内 部的格局间转换。
例：根据表达式文法的LR分析表分析输入串 i*i＋i的LR动作过程。
状态栈
符号栈
输入串
动作
0
#
i*i+i#
05
#i
*i+i#
移进
03
#F
*i+i#
R6 归约
02
#T
027
#T*
*i+i#
R4 归约
i+i#
移进
0275
#T*i
+i#
移进
02710
#T*F
+i#
R6 归约
02
#T
+i#
R3 归约
01
#E
+i#
016
#E+
i#
R2 归约 移进
0165
#E+i
#
移进
0163
（2）与普通不带回溯的自上而下预测技术相比 也要好些。
（3）在自左向右扫描输入串时就能发现其中 的错误，并能准确地指出出错位置，其他分析 方法无法比拟。
第六章 LR分析法及分析程序构造 第一节 引言 三、LR分析法的缺点
若用手工构造分析程序，则工作量太大， 而且容易出错，因此，必须使用自动产生这种 分析程序的产生器。
4、若项目i为X•A，其中A是非终结符，则从 i项目画弧射向所有A• 的项目，V*
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第六章 LR分析法在第5章中已经讨论过，自底向上分析方法是一种移进归约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是分析过程中如何确定句柄。

LR分析法正是给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K≥0）符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。

LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。

LR（K）分析方法是1965年Knuth先生提出的，括号中的K表示向右查看输入串符号的个数。

这种方法比起自顶向下的LL（K）分析方法和自底向上的优先分析方法对文法的限制要少得多，也就是说对于大多数用无二义性上下文无关的文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置。

但是，由于它的主要缺点是对于一个实用语言文法的分析器的构造工作量相当大，K愈大构造愈复杂，实现相当困难。

因此，目前对于真正实用的编译程序，所采用的LR分析器都是借助于美国Bell实验室1974年推出的“一个编译器的编译器—YACC”来实现的。

它能接受一个用BNF描述的满足LALR（1）的上下文无关文法并将自动构造出LALR（1）语法分析器。

本章将主要介绍LR分析的基本思想和当K≤1时LR分析器的基本构造原理和方法。

其中LR （0）分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，对绝大多数高级语言的语法分析器是不能适用的，然而，它是构造其它LR类分析器的基础。

当K=1是，已能满足当前绝大多数高级语言编译程序的需要。

其中SLR（1）和LALR（1）分别是LR（0）和LR（1）的一种改进。

本章重点：LR（0）、SLR（1）第一节 LR分析概述（一）LR（1）分析器的逻辑结构及工作过程Array在逻辑上，一个LR（1）分析器的结构如图6-1-1（a）所示。

它有一个输入符号串，一个下推分析栈，以及一个总控程序和分析表。

LR（1）分析器在总控程序的控制下自左至右扫视输入串中的各个符号，并根据当前分析栈中所存放之文法符号的状况及正扫描之输入符号，按分析表的指示完成相应的分析动作。

在分析的每一时刻，分析栈中记录了迄今为止的分析历程。

因此，为了方便，对于分析过程的每一步，我们可将迄今的分析历程用一种“状态”来刻画，并将此状态名置于分析栈的栈顶，如图6-1-1（b）所示。

分析刚开始时，栈中仅有一个句子的左界符号#，此时分析器处于初始状态S O。

此S O不仅刻画了分析栈中当前仅有一个符号#这一事实，而且还预示着：即将扫视的输入符号，应正好是可作为句子首符号的那些符号。

类似地，状态S1刻画了分析栈中已存有符号#X1的情况，S2刻画了栈中存有符号串 # X1X2的情况，…，栈顶状态S m刻出了栈中已存有符号串 # X1X2…X m，等等。

此外，根据分析栈栈顶状态，还可对当前可能遇到的输入符号进行预测。

例如，对于前面所述的文法G[E]，设分析栈中已移进和归约出的符号串为 # E+T 时的栈顶状态为S i，则S i不仅表征了迄今所扫描过的输入符号业已被归约成# E+T，而且由S i还可作这样的预测：若输入符号串无语法错误，则当前可遇到的输入符号，仅能是（+，*，），或#。

显然，对于上述栈顶状态S i，若当前所扫视到的符号为*，则应将*移入栈中；当扫视到的符号为+、）或#时，则应将符号串E+T归约为E；若扫视到的不是上述四种符号之一，则应按语法错误处理。

由此可见，知道了栈顶状态S m和正扫视到的输入符号a i，就知道了当前所需的全部有用信息，从而也就可唯一地确定当前分析器所应完成的动作。

所以，在具体实现时，并不需要将已归约出的文法符号串也记入分析栈中。

作为LR（1）分析器核心的分析表由两个子表组成：其一是分析动作表，另一个为状态转换表，分别如图6-1-2（a ）和6-1-2（b ）所示。

其中：S 1，S 2，…S n 为分析器的各个状态；a 1，a 2，…，a e 为文法的全部终结符号或句子的界符；X 1，X 2，…X 为文法字汇表中的全部文法符号。

分析表中的每一元素ACTION[S m ，a i ]指明，当栈顶状态为S m 且扫视到的输入符号为a i 时应完成的动作。

状态转移表中的元素GOTO[S m ，X i ]则指明，当栈顶状态为S m 且面临文法符号Xi 时所应转移到的下一状态。

图6-1-2（a）分析动作表图6-1-2（b ）状态转移表LR （1）分析器在总控程序的控制下进行工作，其过程如下（为书写方便，我们将分析栈按顺时针旋转九十度）：第一步 分析开始时，首先将初始状态S O 及句子左界符#推入分析栈中。

第二步则以栈顶的状态及正扫视的输入符号ai 组成符号对（S m ，a i ）去查分析动作表，并根据表元ACTION[S m ，a i ，]的指示完成相应的分析动作。

每一分析表元所规定的动作，仅能是下列四种动作之一：（1）若ACTION[S m ，a i ]=“移进”，这表明句柄尚未在栈顶部形成，此时正期待继续移进输入符号以形成句柄，故将当前的输入符号推入栈中，即有：然后，以符号对（S m ，a i ）查状态转移表，设相应的表元GOTO [S m ，a i ]= S m +1，再将此新的状态（即要转移到的下一状态）推入栈中，则有如下的格局：（2）若m i j j A →X m -r+1 X m -r+2…X m 进行归约。

这表明栈顶部的符号串X m -r+1 X m -r+2…X m 已是当前句型（相对于非终结符号A ）的句柄。

按第j 个产生式进行归约，也就是将分析栈从顶向下的r 个符号（因为该产生式右部符号串的长度为r ）退出，然后再将文法符号A 推入栈中，此时分析栈的格局为然后，以（S m -r ，A ）查状态转移表，设GOTO [S m -r ，A]=S l ，将此新状态推入栈中，则有如下的格局：（3）若ACTION[S m ，a i ]=“接受”，则表明当前的输入串已被成功地分析完毕，应中止分析器的工作。

（4）若ACTION[S m ，a i ]=ERROR ，则表明当前的输入串中有语法错误，也应中止分析器的工作。

第三步 重复上述第二步的工作，直到在分析的某一步，栈顶出现“接受状态”或“出错状态”为止。

对于前者，分析栈的最终格局应为：其中，Z 为文法的开始符号，S e 则为使ACTION[S α，#]=“接受”的唯一状态（即接受状态）。

上述所列的三个步骤，实质上是对LR （1）分析器总控程序的一个非形式的描述，它对任何不同的LR （1）分析表都是适用的。

第二节 LR （0）分析LR （0）分析表构造的思想和方法是构造其它LR 分析表的基础。

我们回顾在第5章曾给出例1文法G[S]为：（1）S →aAcBe （2）A →b （3）A →Ab （4）B →d对输入串abbcde#用自底向上归约的方法进行分析，当归约到第5）步时栈中符号串为#aAb ，我们采用了产生式（3）进行归约而不是产生式（2）归约，而在第3）步归约时栈中符号串为#ab 时却用产生式（2）归约，虽然在第2）步和第5）步归约前栈顶号都为b ，但归约所用产生式却不同，其原因在于已分析过的部分在栈中的前缀不同，也就是我们在LR 分析中引进的状态栈的栈顶状态不同，为了说明这个问题我们先在表6-2-1中给出例1文法G[S]的LR（0）分析表，在表6-2-2给出利用LR 分析法对输入串abbcde#的分析过程。

表6-2-1 例1文法的LR（0）分析表表6-2-2 对输入串abbcde#的分析过程一、可归前缀和前缀在表6-2-2分析中，每次归约前句型的前部分依次为：abaAbaAcdaAcBe这正是我们在表6-2-2的分析过程中每次采取归约动作前符号栈中的内容，即分别对应步骤3）、5）、8）10）时符号栈中的符号串，我们把规范句型的这种前部分串称可归前缀。

我们再来分析上述归约时规范句型的前缀：ε,a,abε,a,aA,aAbε,a,aA,aAc,aAcdε,a,aA,aAc,aAcB,aAcBe不难发现前缀a,aA,aAc都不只是某一个规范句型的前缀，因此我们把形成可归前缀之前包括可归前缀在内所有规范句型的前缀都称为活前缀。

活前缀为一个或若干规范句型的前缀。

在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，则表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。

二、LR（0）项目集规范族构造1、LR（0）项目在一个规范句型的活前缀中，决不会含有句柄右边的任何符号。

这是因为一旦句型的句柄在栈的顶部形成，将会立即被归约之故。

因此，活前缀与句柄间的关系不外下述三种情况：（1）活前缀中已含有句柄的全部符号（句柄的最右符号即为其最右符号）；（2）活前缀中含句柄的一部分符号（句柄开头的若干符号与活前缀最右的若干个符号一致）；（3）活前缀中全然不包含句柄的任何符号。

第一种情况表明，此时某一产生式A→β的右部符号串β已出现在栈顶，因此相应的分析动作应当是用此产生式进行归约。

第二种情况意味着形如A→β1β2的产生式的右部子串β1已出现在栈顶，正期待着从余留输入串中看到能由β2推出的符号串。

而第三种情况则意味着，期望从余留输入串中能看到由某一产生式A→α右部，即α所推出的符号串，为了刻画在分析过程中，文法的一个产生式右部符号串已有多大一部分被识别，我们可在该产生式的右部的某处加上一个圆点“·”来指示位置。

例如，对于上述三处情况，标有圆点的产生式分别为A→β·，A→β1·β2以及A→·α。

我们把右部某位置上标有圆点的产生式称为相应文法的一个LR（0）项目，特别对形如A→ε的产生式，相应的LR（0）项目为A→·。

显然，不同的LR（0）项目，反映了分析过程中栈顶的不同情况。

在文法G中的每个产生式的右部适当位置添加一个圆点构成一个LR（0）项目例如，产生式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·一个产生式可对应的项目为它的右部符号长度加1。

A→ε的产生式，相应的LR（0）项目为A→·下面我们就会看到，文法的全部LR（0）项目将是构造识别它的所有活前缀的有限自动机的基础。

2、构造识别活前缀的NFA如果把文法的所有产生式的项目都引出，每个项目都为NFA的一个状态。

仍以文法G′为例S′→EE→aA|bBA→cA|dB→cB|d该文法的项目有：1、S′→·E 10、A →d·2、S′→E·11、E →·bB3、E→·aA 12、E →b·B4、E→a·A 13、E →bB·5、E→aA·14、B→·cB6、A→·cA 15、B→c·B7、A→c·A 16、B→c B·8、A→cA·17、B →·d9、A →·d 18、B →d·由于S′仅在第一产生式的左部出现，因此规定项目1为初态，其余每个状态都为活前缀的识别态，圆点在最后的项目为句柄识别态，第一个产生式的句柄识别态为句子识别态。