编译原理-语法分析-自下而上分析

自下而上分析 1

自下而上分析

自下而上分析的一个示例

可以看出自下而上分析的主要步骤是不断的用文法来“规约”，最后找到一种句型的表示

自下而上分析的基本思想

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

10.1.3 移进－归约分析示例

其中每一步的操作都可以构成语法树（分析树）的一部分。

可归约串：短语

短语与直接短语

短语

• 定义：令G是一个文法，S是文法的开始符号， 假定 α β δ 是文法G的一个句型，如果有 S =*=> α A δ 且 A =+=> β 则称 β 是句型 α β δ 相对于非终结符A的短语
• 如果有 A ⇒ β , 则称 β 是句型 α β δ 相对于规则 A → β 的 直接短语。

测试：短语和直接短语

10.3 分析过程描述

算符优先文法

算符优先文法

算符优先分析法:

• 按照算符的优先关系和结合性质进行语法分析
• 适合分析表达式

LR分析法:

• 规范归约：句柄作为可归约串

运算的优先级

四则运算的优先规则: 先乘除后加减, 同级从左到右

考虑文法G’(E)： E → i| E + E | E - E | E * E | E / E | ( E ) : 句子 i+i-i*(i+i) 有几种不同的归约 :

归约顺序不同，计算的顺序也不同，结果也不一样。

句子 i + i - i * ( i + i ) 的归约过程：

优先关系

任何两个可能相继出现的终结符a与b可能三种 优先关系 ：

• a ⋖ b a的优先级低于b
• a ≐ b a的优先级等于b （这里的点是在等号中间）
• a ⋗ b a的优先级高于b

算符优先关系与数学上的 <>= 不同 :

• + ⋖ +
• a ⋖ b 并不意味着 b ⋗ a 如 ( ⋖ + 和 + ⋖ (

算符文法

一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含 … Q R … 形式的产生式右部，则我们称该文法为算符文法。

约定：

• a、b代表任意终结符
• P、Q、R代表任意非终结符
• ‘ … ’代表由终结符和非终结符组成的任意序列，包括空字

算符优先文法

示例：算符优先文法：

对应的优先关系表：

构造优先关系表

构造优先关系表的算法——FIRSTVT和LASTVT集合

根据FIRSTVT和LASTVT集合，检查每个产生式的候选式，确定满足关系 ⋖ 和 ⋗ 的所有终结符对 ：

• 假定有个产生式的一个候选形为…aP…，那么，对 任何 b ∈ FIRSTVT( P ) ，有 a ⋖ b
• 假定有个产生式的一个候选形为…Pb…，那么，对 任何 a ∈ LASTVT ( P ) ，有 a ⋗ b

构造集合FIRSTVT的算法

反复使用下面两条规则构造集合 FIRSTVT( P ) :

• 若有产生式 P → a … 或 P → Q a … ，则 a ∈ FIRSTVT( P )
• 若 a ∈ FIRSTVT(Q) ，且有产生式 P → Q … ，则 a ∈ FIRSTVT( P )

算法的一种实现:

• 布尔数组F[P，a] ，使得F[P，a]为真的条件是，当且 仅当 a ∈ FIRSTVT。开始时，按上述的规则1对每个数组元素F[P，a]赋初值。
• 栈STACK ，把所有初值为真的数组元素F[P，a]的符 号对(P，a)全都放在STACK之中。
• 若栈STACK不空，就将栈顶项弹出，记此项为 (Q， a) 。对于每个形如 P → Q… 的产生式，若F[P，a]为假， 则变其值为真且将 (P， a) 推进STACK栈。
• 上述过程一直重复，直至栈STACK为空为止。

算法的工作结果得到一个二维数组F，从它可得 任何非终结符 P 的FIRSTVT FIRSTVT( P ) ＝ { a ∣ F[P，a] = TRUE }

10.5.3 构造集合LASTVT的算法

同样的思想：

反复使用下面两条规则构造集合LASTVT

• 若有产生式 P → … a 或 P → … a Q ，则 a ∈ LASTVT( P )
• 若 a ∈ LASTVT( Q ) ，且有产生式 P→…Q，则 a ∈ LASTVT( P )

FIRSTVT和LASTVT集合计算示例

构造优先关系表的算法

• 通过检查G的每个产生式的每个候选式，可找 出所有满足a ≐ b 的终结符对。
• 根据 FIRSTVT 和 LASTVT 集合，检查每个产生式 的候选式，确定满足关系 ⋖ 和 ⋗ 的所有终结符对
  • 假定有个产生式的一个候选形为 … a P … ，那么，对任何 b ∈ FIRSTVT( P ) ，有 a⋖b
  • 假定有个产生式的一个候选形为 … P b … ，那么，对任何 a ∈ LASTVT( P ) ，有 a ⋗ b

示例：构造优先关系表

没有任何两个终结符之间是有多个关系的，所以该文法是一个算符优先文法。

算符优先分析算法

最左素短语

• 可归约串，句型，短语
• 一个文法G的句型的 素短语 是指这样一个短语， 它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语
• 最左素短语 是指处于句型左边的那个素短语
  

最左素短语定理

• 算符优先文法句型(括在两个＃之间)的一般形式: # N1 a1 N2 a2 … Nn an Nn+1 # 其中，ai 都是终结符， Ni 是可有可无的非终结符。
• 定理：一个算符优先文法G的任何句型的左素短语是满足如下条件的左子串 Nj aj … Ni ai Ni+1 ，且：
  • aj−1 ⋖ aj
  • aj ≐ aj+1 , … , ai−1 ≐ ai
  • ai ⋗ a i+1

算符优先分析算法

• 使用一个符号栈S，用它寄存终结符和非终结符， k代表符号栈S的使用深度
• 在正确的情况下，算法工作完毕时，符号栈S应 呈现：# N #

整个算法的执行如下：

根据上面的规约那一部分的算法可知：对于文法的句子来说，它的算符优先分析的结果 不一定 就是语法树，所以语法树和分析树要分开指代，这章一开始便已强调：

算符优先分析程序构成

• 总控程序 ，根据现行栈顶符号和当前输入符号， 执行动作
• 优先关系表 ，用于指导总控程序进行移进-归约
• 分析栈STACK ，用于存放文法符号

10.6.5 算符优先分析法

特点:

• 优点: 简单，快速
• 缺点: 可能错误接受非法句子

使用广泛,用于分析各类表达式 如，ALGOL 60

第11章 自下而上分析2

LR分析法概述

LR分析法

• 1965年由Knuth提出
• L：从左到右扫描输入串
• R：自下而上进行归约

工作框架

句柄和规范归约

短语、直接短语和句柄

• 短语
• 直接短语
• 句柄 :一个句型的左直接短语称为该句型的句柄。

用句柄归约

可用句柄来对句子进行归约:

规范归约

定义：假定 α 是文法G的一个句子，我们称序列 αn​，αn−1​，…，α0 是 α 的一个规范归约，如果此序列满足：

• αn ​= α
• α0​ 为文法的开始符号，即 α0 ​= S
• 对任何 i ， 0 ≤ i ≤ n ， αi−1是从 αi​ 经把句柄替换成为相应产生式左部符号而得到的

算符优先分析vs. 规范归约

11.2.5 规范句型

• 规范归约 是最左归约
• 规范归约的逆过程就是右推导 S ⇒ aAcBe ⇒ aAcde ⇒ aAbcde ⇒ abbcde
• 右推导也称为 规范推导
• 由规范推导推出的句型称为 规范句型

LR分析法

规约的关键

规范归约的关键问题是寻找句柄.

• 历史 ：已移入符号栈的内容
• 展望 ：根据产生式推测未来可能遇到的输入符号
• 现实 ：当前的输入符号

LR分析器的结构

LR分析方法：把 "历史" 及 "展望" 综合抽象成状态 ；由栈顶的 状态 和 现行的输入符号 唯一确定每一步工作:

LR分析表

LR分析器的核心是一张分析表:

• ACTION[s，a] ：当状态s面临输入符号a时，应采取什么动作.
• GOTO[s，X] ：状态s面对文法符号X时，下一状态是什么

11.3.4 LR分析过程

• 分析开始时：

• 以后每步的结果可以表示为:

LR分析示例

LR分析器的性质

• 栈内的符号串和扫描剩下的输入符号串构成了一个规范句型
• 一旦栈的顶部出现可归约串(句柄)，则进行规约

对于句子，在规范归约过程中，栈内的符号串 和扫描剩下的输入符号串构成了一个规范句型， 下面哪种格局不会出现：

LR文法

LR文法

• 定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这 个文法就称为 LR文法 。
• 定义：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这 个文法就称为 LR(k)文法 。

LR文法与二义文法

• LR文法不是二义的，二义文法肯定不会是LR的

• LR文法⊂无二义文法

• 非LR结构:

  

第12章 自下而上分析3

活前缀

字的前缀、活前缀

• 字的前缀 ：是指字的任意首部，如字 abc 的前缀有: ε， a ， ab ， abc
• 活前缀 ：是指 规范句型 的一个前缀，这种前缀不含 句柄 之后的任何符号。即，对于规范句型 α β δ ，β 为句柄，如果 αβ = u1 ​u2​ … ur​，则符号串 u1 ​u2 ​… ui ​(1≤i≤r) 是 α β δ 的 活前缀 。( δ 必为终结符串)
• 规范归约过程中，保证分析栈中总是 活前缀 ， 就说明分析采取的移进/归约动作是正确的

对于一个文法G, 可以构造一个DFA, 它能识别G 的所有活前缀。

构造识别活前缀的DFA

文法的拓广

将文法G( S ) 拓广为 G′ ( S ) :

• 构造文法 G′ ，它包含了整个 G ，并引进不出现在 G 中的非终结符 S′ 、以及产生式 S′ → S , S′ 是 G′ 的开始符号
• 称 G′ 是 G 的拓广文法

LR(0)项目

• LR( 0 )项目: 在每个产生式的右部添加一个圆点，表示我们在分析过程中看到了产生式多大部分
• 例如： A → XYZ 有四个项目：A → •XYZ , A → X•YZ , A → XY•Z , A → XYZ•
• A → α• 称为 "归约项目" （把点看成识别的指针，识别到产生的末表示可以用这个产生式的左部代替）
• 归约项目 S′ → α• 称为 "接受项目"（表示识别到文法的拓广文法的开始，也就是当前读入的单词被识别到）
• A → α • a β ( a ∈ VT ) 称为 "移进项目"
• A → α • B β ( B ∈ VN ) 称为 "待约项目"

示例：

构造识别文法所有活前缀的DFA

对于上面那个文法的一个 NFA 就是：

然后按照前面的套路将 NFA 变为 DFA ：

LR(0)项目集规范族

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

如上图中的每一个状态中的一些项目组成的集合就是一个个项目集规范族：

通过计算项目集规范族构造识别活前缀的DFA

有效项目

项目 A → β1 • β2 对活前缀 αβ1 是有效的，其条件是存在规范推导: S′=*=>R ​αAω=*=>R​αβ1​β2​ω

在任何时候，分析栈中的活前缀 X1 ​X2 ​… Xm​ 的有效项目集正是从识别活前缀的 DFA 的初态出发，读出 X1 ​X2 ​… Xm​ 后到达的那个项目集(状态)。

（应该可以理解为当一个活前缀的后缀是某个项目的前缀时，就称这个项目是这个活前缀的一个有效项目，因为只要当活前缀的后缀加上一定的后续的读入就可以规约到这个项目的左部）

有效项目的性质

若项目 A→α•Bβ 对活前缀 η = δα 是有效的且 B→γ 是一个产生式，则项目 B→•γ 对 η = δα 也是有效的。

证明：

LR(0)项目集规范族的构造

将文法G(S)拓广为G′(S′)：

• 构造文法G′ ，它包含了整个G，并引进不出现在G中的非终结符S′，以及产生式 S′→S ，S′ 是 G′ 的开始符号
• G′ 唯一的“接受”态：仅含项目S′→S•的状态

项目集的闭包CLOSURE

状态转换函数

为了识别活前缀，我们定义一个状态转换函数GO。I 是一个项目集，X 是 一个文法符号。函数值 GO(I，X) 定义为：GO(I，X) ＝ CLOSURE( J ) 其中 J ＝ { 任 何 形 如 A → α X • β 的 项 目 ∣ A → α • X β 属 于 I } 。

直观上说，若 I 是对某个活前缀 γ 有效的项目集， 那么，GO(I，X) 便是对 γX 有效的项目集

示例：项目集的转移函数计算

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

两种构造识别活前缀的DFA的方法

• 1.项目→ NFA → DFA
• 2.Closure → GO → DFA

构造LR(0)分析表

LR(0)分析表的构造

假若一个文法G的拓广文法G′的活前缀识别自动机中的每个状态(项目集)不存在下述情况：

• 既含移进项目又含归约项目；
• 含有多个归约项目

则称G是一个LR(0)文法。

构造LR(0)分析表的算法

• 令每个项目集 Ik​ 的下标 k 作为分析器的状态，包含项目 S′→•S 的集合 Ik​ 的下标 k 为分析器的初态。
• 构造 LR(0) 分析表的 ACTION 和 GOTO 子表

LR(0)分析表的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 填入信息的空白格均置上 “报错标志”。

示例：LR(0)分析表的构造

LR(0)分析示例

第13章 自下而上分析4

SLR(1)分析法

一个非LR(0)文法

从这个文法的DFA可以看出，某些状态既是规约态，也是移进态，这样就是一个非LR(0)文法：

I1、I2和I9都含有“移进－归约”冲突，可以看出冲突的项目集中的项目的 FOLLOW集合是相交的。

冲突解决办法

• 假定一个LR(0)规范族含有如下的一个项目集 (状态) I ＝ { X → α • b β ， A → α • ， B → α • } I＝\{\color{blue}{X→α•bβ}，\color{red}{A→α•}，\color{fuchsia}{B→α•}\color{black}{\}} I＝{X→α•bβ，A→α•，B→α•}
• F O L L O W ( A ) \color{red}{FOLLOW(A)} FOLLOW(A) 和 F O L L O W ( B ) \color{fuchsia}{FOLLOW(B)} FOLLOW(B) 的交集为 ∅ ∅ ∅ ，且不包含 b \color{blue}{b} b
• 当状态 I I I 面临任何输入符号 a a a 时，可以:
  • 1. 若 a = b ， 则 移 进 ； \color{blue}{1.若a=b，则移进；} 1.若a=b，则移进；
  • 2. 若 a ∈ F O L L O W ( A ) ， 用 产 生 式 A → α 进 行 归 约 ； \color{red}{2.若a∈FOLLOW(A)，用产生式A→α进行归约； } 2.若a∈FOLLOW(A)，用产生式A→α进行归约；
  • 3. 若 a ∈ F O L L O W ( B ) ， 用 产 生 式 B → α 进 行 归 约 ； \color{fuchsia}{3.若a∈FOLLOW(B)，用产生式B→α进行归约； } 3.若a∈FOLLOW(B)，用产生式B→α进行归约；
  • 4.此外，报错。

SLR(1)冲突解决办法

假定LR(0)规范族的一个项目集 I = { A 1 → α • a 1 β 1 ， A 2 → α • a 2 β 2 ， … ， A m → α • a m β m ， B 1 → α • ， B 2 → α • ， … ， B n → α • } I=\{\color{blue}{A_1→α•a_1β_1， A2→α•a_2β_2，…，A_m→α•a_mβ_m}，\color{red}{B_1→α•，B_2→α•，…， B_n→α•} \color{black}{\}} I={A1​→α•a1​β1​，A2→α•a2​β2​，…，Am​→α•am​βm​，B1​→α•，B2​→α•，…，Bn​→α•} 如果集合 { a 1 ， … ， a m } \color{blue}{\{a_1，…，a_m}\} {a1​，…，am​}， F O L L O W ( B 1 ) ， … ， F O L L O W ( B n ) \color{red}{FOLLOW(B_1)，…， FOLLOW(B_n)} FOLLOW(B1​)，…，FOLLOW(Bn​)两两不相交(包括不得有两个FOLLOW集 合有#)，则当状态I面临任何输入符号a时：

• 1. 若 a 是 某 个 a i ， i = 1 , 2 , … , m ， 则 移 进 ； \color{blue}{1. 若a是某个ai，i=1,2,…,m，则移进；} 1.若a是某个ai，i=1,2,…,m，则移进；
• 2. 若 a ∈ F O L L O W ( B i ) ， i = 1 , 2 , … , n ， 则 用 产 生 式 B i → α 进 行 归 约 ； \color{red}{2. 若a∈FOLLOW(B_i)，i=1,2,…,n，则用产生式Bi→α 进行归约； } 2.若a∈FOLLOW(Bi​)，i=1,2,…,n，则用产生式Bi→α进行归约；
• 3. 此 外 ， 报 错 。 \color{black}{3. 此外，报错。 } 3.此外，报错。

SLR(1)解决办法：S-Simple，1-最多向前看一个单词

构造SLR(1)分析表的方法

• 把G拓广为G′
• 对G′构造
  • LR(0)项目集规范族C
  • 活前缀识别自动机的状态转换函数GO
• 使用C和GO，构造SLR分析表
  • 令每个项目集Ik的下标k作为分析器的状态，包含项 目S′→•S的集合Ik的下标k为分析器的初态。
  • 构造分析表的ACTION和GOTO子表

SLR(1)分析表的ACTION和GOTO子表构造

• 1.若项目 A → α • a β A→α•aβ A→α•aβ 属于 I k I_k Ik​ 且 G O ( I k , a ) = I j GO(I_k,a)=I_j GO(Ik​,a)=Ij​ ， a a a 为终结符，则置
  A C T I O N [ k , a ] = s j ACTION[k,a] = s_j ACTION[k,a]=sj​；
• 2.若项目 A → α • A→α• A→α• 属于 I k I_k Ik​ ，那么，对任何终结符 a ∈ F O L L O W ( A ) \color{red}{a∈FOLLOW(A)} a∈FOLLOW(A) ，置 A C T I O N [ k , a ] ACTION[k,a] ACTION[k,a] 为“ r j r_j rj​ ”；其中，假定 A → α A→α A→α 为文法 G ′ G’ G′ 的第 j j j 个产生式；
• 3.若项目 S ′ → S • S’→S• S′→S• 属于 I k I_k Ik​ ，则置 A C T I O N [ k , # ] 为 “ a c c ” ACTION[k,\#]为“acc” ACTION[k,#]为“acc”;
• 4.若 G O ( I k , A ) ＝ I j GO(I_k,A)＝I_j GO(Ik​,A)＝Ij​ ， A A A 为非终结符，则置 G O T O [ k , A ] = j GOTO[k,A]=j GOTO[k,A]=j；
• 5.分析表中凡不能用规则1至4填入信息的空白格均置上 “报错标志” 。

SLR(1)和LR(0)分析表构造方法的对比

可以看出，SLR处理冲突的解决方法就是将以前分析表中规约的一行缩小成为FOLLOW的字符，减少冲突的可能（显然这样也不是最优的，也可能产生冲突的）

SLR(1)文法

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

SLR(1)分析表构造示例

对于上面那个会产生冲突的LR(0)文法，更改其中产生 规约 步骤的分析表产生规则，使用FOLLOW来代替：

一个非SLR(1)文法

对于这样一个文法，它的SLR分析表是会产生冲突的：

SLR冲突消解存在的问题

• SLR在方法中，如果项目集 I i I_i Ii​ 含项目 A → α • \color{#08f}{A→α•} A→α• 而且下一输入符号 a ∈ F O L L O W ( A ) \color{#08f}{a∈FOLLOW(A)} a∈FOLLOW(A) ，则状态 i i i 面临 a a a 时，可选用“用 A → α A→α A→α 归约”动作
• 但在有些情况下，当状态i显现于栈顶时，当前单词是a， 栈里的 活前缀 β α \color{#08f}{β}\color{purple}{α} βα 未必允许把 α \color{purple}{α} α 归约为 A \color{purple}{A} A ，因为可能根本 就不存在一个形如“ β A a \color{#08f}{β}\color{purple}{A}\color{#0f5}{a} βAa ”的规范句型
• 在这种情况下，用“A→α”归约不一定合适
• 原因是： FOLLOW集合提供的信息太泛 F O L L O W ( A ) = { α ∣ S ⇒ ∗ … A α … , α ∈ V T } FOLLOW(A)=\{\alpha|S⇒^*…A\alpha \dots, \alpha∈V_T\} FOLLOW(A)={α∣S⇒∗…Aα…,α∈VT​}

LR(1)分析表的构造

构造LR(1)分析表的方法

• 把G拓广为G′
• 对G′构造LR(1)项目集规范族C和活前缀识别自 动机的状态转换函数GO
• 使用C和GO，构造LR(1)分析表

LR(k)项目

• LR(k)项目 ：扩展LR(0)项目，附带有k个终结符 [ A → α • β , a 1 a 2 … a k ] [A→α•β, a_1a_2…a_k] [A→α•β,a1​a2​…ak​] a 1 a 2 … a k a_1a_2…a_k a1​a2​…ak​ 称为 向前搜索符串(或展望串) 。
• 归约项目 [ A → α • ， a 1 a 2 … a k ] [A→α•，a_1a_2…a_k] [A→α•，a1​a2​…ak​] 的意义：当它所属的状态呈现在栈顶且后续的k个输入符号为 a 1 a 2 … a k a_1a_2…a_k a1​a2​…ak​ 时，才可以把栈顶上的α归约为A
• 对于任何 移进 或 待约项目 [ A → α • β , a 1 a 2 … a k ] , β ≠ ε [A→α•β, a_1a_2…a_k] , β≠ε [A→α•β,a1​a2​…ak​],β​=ε ，搜索符串 a 1 a 2 … a k a_1a_2…a_k a1​a2​…ak​ 没有直接作用

有效项目

形式上我们说一个LR(1)项目 [ A → α • β , a ] [\color{red}{A}→\color{#08f}{α}•\color{#0f8}{β} \color{black}{,} \color{purple}{a}] [A→α•β,a] 对于活前缀 γ \color{#08f}{γ} γ 是 有效的 ，如果存在规范推导 : S ′ ⇒ R ∗ δ A ω ⇒ R ∗ δ α β ω S’⇒^_R \color{#08f}{\delta} \color{red}{A} \color{purple}{\omega} \color{black}{⇒^_R} \color{#08f}{\delta} \color{#08f}{α} \color{#0f8}{β} \color{purple}{\omega} S′⇒R∗​δAω⇒R∗​δαβω
其中，1) γ ＝ δ α \color{#08f}{γ＝δα} γ＝δα ；2) a \color{purple}{a} a 是 ω \color{purple}{ω} ω 的第一个符号，或者 a \color{purple}{a} a 为#而 ω \color{purple}{ω} ω 为ε。

有效项目的性质

LR(1)项目集规范族

• 闭包函数CLOSURE
• 转换函数GO

项目集的闭包CLOSURE

假定I是文法G′的任一项目集，定义和构造I的闭 包CLOSURE(I)如下：

• 1.I的任何项目都属于 C L O S U R E ( I ) CLOSURE(I) CLOSURE(I) 。
• 2.若项目 [ A → α • B β , a ] [A→α•Bβ, a] [A→α•Bβ,a] 属于 C L O S U R E ( I ) CLOSURE(I) CLOSURE(I) ， B → ξ B→ξ B→ξ 是一个产生式，那么，对于 F I R S T ( β a ) FIRST(βa) FIRST(βa) 中的每个 终结符b，如果 [ B → • ξ , b ] [B→•ξ, b] [B→•ξ,b] 原来不在 C L O S U R E ( I ) CLOSURE(I) CLOSURE(I) 中，则把它加进去。
• 3.重复执行步骤2，直至 C L O S U R E ( I ) CLOSURE(I) CLOSURE(I) 不再增大为止。

项目集的转换函数GO

令I是一个项目集，X是一个文法符号，函数 GO(I，X)定义为： G O ( I ， X ) ＝ C L O S U R E ( J ) GO(I，X)＝CLOSURE(J) GO(I，X)＝CLOSURE(J) ,其中 J ＝ { 任 何 形 如 [ A → α X • β , a ] 的 项 目 ∣ [ A → α • X β , a ] ∈ I } J＝\{ 任何形如[ A→αX•β, a]的项目 | [ A→α•Xβ, a]∈I \} J＝{任何形如[A→αX•β,a]的项目∣[A→α•Xβ,a]∈I}

LR(1)项目集规范族的构造算法

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

LR(1)分析表的构造算法

• 把G拓广为G′
• 对G′构造LR(1)项目集规范族C和活前缀识别自 动机的状态转换函数GO
• 使用C和GO，构造LR(1)分析表
  • 令每个Ik的下标k为分析表的状态，令含有[S′→•S, #] 的Ik的k为分析器的初态
  • 构造LR(1)分析表的ACTION和GOTO子表

LR(1)分析表的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填入信息的空白栏 均填上“出错标志”。

LR(1)和SLR(1)分析表构造方法的对比

可以看出，与SLR相比，在规约中更加缩小了可规约的情况，使得冲突减小

LR(1)分析表和LR(1)文法

• 按上述算法构造的分析表，若不存在多重定义 的入口(即，动作冲突)的情形，则称它是文法G 的一张规范的LR(1)分析表。
• 具有规范的LR(1)分析表的文法称为一个LR(1)文法。
• 使用LR(1)分析表的分析器叫做一个规范的LR分析器。
• LR(1)状态比SLR(1)多
• L R ( 0 ) ⊂ S L R ( 1 ) ⊂ L R ( 1 ) ⊂ 无 二 义 文 法 LR(0) ⊂SLR(1) ⊂LR(1) ⊂无二义文法 LR(0)⊂SLR(1)⊂LR(1)⊂无二义文法

LR(1)分析表构造示例

分析器产生工具

分析器产生器——YACC

YACC——Yet AnotherCompiler Compiler

• LALR(1)分析
• GNU Bison：基本兼容Yacc，与flex一起使用
• The Lex & YaccPage http://dinosaur.compilertools.net/

参考

学习所用，参考自[CSDN 博主 pi31415926535x ][https://blog.csdn.net/pi31415926535x/article/details/105299131]