编译原理ch5 语法分析3

本文主要内容包括自底向上分析概述、LR分析法概述、LR（0）分析及分析表构造

自底向上分析概述

自底向上的语法分析

从分析树的底部(叶节点)向顶部(根节点)方向构造分析树，可以看成是将输入串w归约到文法开始符号S的过程
自顶向下的语法分析采用最左推导方式
自底向上的语法分析采用最左归约方式（反向构造最右推导）

自底向上语法分析的通用框架：移入-归约分析(Shift-Reduce Parsing)

文法
① E → E+E
② E → E*E
③ E → (E)
④ E → id 

栈 			剩余输入 		动作
$ 			id+(id+id) $
$ id 		+(id+id) $ 		移入
$ E 		+(id+id) $ 		归约: E→id
$ E+ 		(id+id) $ 		移入
$ E+( 		id+id) $ 		移入
$ E+(id 	+id) $ 			移入
$ E+(E 		+id) $ 			归约: E→id
$ E+(E+ 	id) $ 			移入
$ E+(E+id 	) $ 			移入
$ E+(E+E 	) $ 			归约: E→id
$ E+(E 		) $ 			归约: E→E+E
$ E+(E) 	$ 				移入
$ E+E 		$ 				归约: E→(E)
$ E 		$ 				归约: E→E+E

每次归约的符号串称为“句柄”

栈内符号串 + 剩余输入 =“规范句型”

移入-归约分析的工作过程

1. 在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串β进行归约为止

2. 然后，它将符号串β归约为某个产生式的左部

3. 语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析)为止

移入-归约分析器可采取的4种动作

1. 移入：将下一个输入符号移到栈的顶端

2. 归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串

3. 接收：宣布语法分析过程成功完成

4. 报错：发现一个语法错误，并调用错误恢复子例程

移入-归约分析中存在的问题

造成错误的原因：错误地识别了句柄

句柄：句型的最左直接短语

自底向上分析的关键问题 是如何正确识别句柄。

LR分析法

LR文法(Knuth, 1963) 是最大的、可以构造出相应移入-归约语法分析器的文法类

1. L: 对输入进行从左到右的扫描

2. R: 反向构造出一个最右推导序列

LR(k)分析: 需要向前查看k个输入符号的LR分析

当省略(k)时，表示k =1

LR分析表结构

符号a进入符号栈中，状态n进入状态栈中。

LR 分析器的工作过程

初始化（状态栈中只有s0，符号栈中只有$，输入缓冲区中符号串为a1a2…an）

s0
$				a1a2…an $ 

一般情况下

s0s1… sm
$X1…Xm				aiai+1…an $ 

1. 如果ACTION [sm, ai]= Sx， 那么格局变为：

s0s1… sm x
$X1…Xm ai 			ai+1…an $

---

理解：如果符号栈栈顶sm，遇到输入缓冲区ai，查表对应项为移入动作Sx，

则ai进入符号栈，x进入状态栈，当前状态变为状态x

---

2. 如果ACTION[sm , ai]= rx 表示用第x个产生式A→Xm-(k-1)…Xm
   进行归约，那么格局变为：

s0s1… sm-k
$X1…Xm-k A 		aiai+1…an $

---

理解：如果符号栈栈顶sm，遇到输入缓冲区ai，查表对应项为规约动作rx，表示用第x个产生式A→Xm-(k-1)…Xm进行归约 ，

则符号栈顶k个符号Xm-(k-1)…Xm出栈，产生式左部A入栈（未完）

---

接下来检查状态S(m-k)遇到规约的非终结符A如何进行状态转移，如果GOTO[sm-k , A]=y，那么格局变为：

s0s1… sm-k y
$ X1…Xm-k A 			aiai+1…an $

---

理解：必须检查状态栈顶状态遇到新规约的非终结符A如何进行状态转移，如果GOTO[sm-k , A]=y，则状态y进入状态栈

---

3. 如果ACTION[sm , ai]=acc，那么分析成功
4. 如果ACTION[sm , ai]=err ，那么出现语法错误

如何构造给定文法的LR分析表

不同分析法对应LR分析表构成方法不同

LR(0)分析
SLR分析
LR(1)分析
LALR分析

LR(0)分析

LR（0）项目

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）

S→bBB

S → ·bBB （ .后面为终结符，称移进项目 ）
S → b·BB （ .后面为非终结符，称待约项目 ）
S → bB·B
S → bBB· （ .在最后，称归约项目 ）

产生式A→ε 只生成一个项目A→ ·

项目描述了句柄识别的状态

增广文法 (Augmented Grammar)

如果G 是一个以S为开始符号的文法，则G的增广文法 G’ 就是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态

LR(0)自动机

把等价的项目组成一个项目集(I) ，称为项目集闭包(Closure of Item Sets)>，

每个项目集闭包对应着自动机的一个状态

LR（0）分析表构造算法

LR(0) 分析过程中的冲突

LR(0)分析表含有移进/归约冲突

移进/归约冲突和归约/归约冲突

不是所有CFG都能用LR(0)方法进行分析，也就是说， CFG不总是LR(0)文法

赏

谢谢你请我吃糖果

支付宝

微信