关于 SLR,LR(1)
SLR,LR(1)
SLR,LR(1)
SLR,LR(1) 及 LALR(1)
LALR(1)
LALR(1)
LALR(1) 在实践中的
效率及状态集规模的探讨
学校：哈尔滨工业大学
学院：软件学院
姓名：吴海文
学号： 1083710406
1083710406
1083710406
1083710406
目录
关于
SLR,LR(1)
及
LALR(1)
在实践中的效率及状态集规模的探讨 ..................................................
1
目录 ...................................................................................................................................................
2
摘要： ...............................................................................................................................................
2
一、功能简介 ...................................................................................................................................
4
1
．
LR
语法分析器。 ..........................................................................................................
4
2
．
LR(0)
语法分析器。 .......................................................................................................
4
3
．
LR(1)
语法分析器。 .......................................................................................................
5
4
．
LALR
文法（
Look Ahead LR
）即向前看
LR
语法分析器。 .........................................
6
二、项目集合状态数对比 ...............................................................................................................
7
1
． 简单文法。 ...................................................................................................................
7
2
． 中等复杂文法 ...............................................................................................................
8
3
． 大型文法 .......................................................................................................................
9
4
． 简化的
C
文法 .............................................................................................................
11
5
． 标准
C
语言文法 .........................................................................................................
13
三、结论 .........................................................................................................................................
14
四、参考文献： .............................................................................................................................
15
摘要：
编译器的构造中 ， 语法分析是一个非常关键也是较难的部分之一 ， 虽然现在
已经有非常成熟的语法分析器的生成器 ， 但是真正大的编译器设计者还是会选择
自己处理语法分析 。 其中 ， 自顶向下的方法有递归下降分析 ， 非递归预测分析等
，
但是前者递归无法满足程序嵌套的深入 ， 很容易形成栈溢出 ； 后者手工构造对于
稍微大的文法无法显得捉襟见肘。
幸运的是 ： 自底向上分析能够很好的解决上述问题 。 其中 LR(0) ， LR(1) 以 及
LALR(1) 对程序设计语言语法分析提供了很好的解决方案 。 但是他们三者的性能如
何，到底实际中适和使用哪种分析方法？很多书都提出 LALR 分析方法同时拥有
了前两者的优点，所以是最提倡的。
据笔者所知 ， YACC(Yet Another Compiler- Compiler ) 语法分析器生成器所使用
的方法正是 LALR 分析法。
本文旨在用程序证明 LALR 语法分析方法的最优性以及 LR(1) 方法的不可行
性。
作者此次正好利用编译原理论文的机会，和大家一起去实践的证明一下吧 ！
关键词： LR(0) ； LR(1) ； LALR(1) ；语法分析；规模；效率；论证 YACC
一、功能简介
在本次论证中 ， 自顶向下语法分析方法因为其简单性和实际操作中的不可行行 ， 不属于
本文的重点 。 首先我们简单了解一下自底向上的语法分析 。 下面的论证都以简单文法
1
为基
础：
文法
1
1
1
1
S
S
S
S ->
->
->
-> C
C
C
C C
C
C
C
C
C
C
C ->
->
->
-> c
c
c
c C
C
C
C |
|
|
| d
d
d
d
表 1.1 文法 1
我们知道，在 LR(0) ， LR(1) 及 LALR(1) 语法分析方法中，三者有主要有一下特点：
1 ． LR
LR
LR
LR 语法分析器。 它首先构造出各个可行前缀的有效项的项集，我们称为
状态如下图 1.1 ，并且在语法分析栈中跟踪这些状态的转变。
图 1.1 LR 状态
这些有效项目集可以引导我们进行移入归约决定 ， 如果项目集中某个有效项的点在
产生式的最右端 （ 图 1 中的状态 1 ） ， 则我们就进行归约 ； 如果下一个输入符号出现
在某个有效项的点的右边（如图 1 中的状态 2 ） ，我们就会把向前看符号移入栈中 。
2 ． LR(0)
LR(0)
LR(0)
LR(0) 语法分析器。 又称为简单 LR 语法分析器。在一个 SLR 语法分析器
中 ， 我们按照某个点在最右边进行归约的条件是 ： 向前看符号能够在某个句型中跟
在该有效项对应的产生式的头部符号的后面 ， 如果没有语法分析动作冲突 ， 那这个
文法就是 SLR 的，就可以应用这个方法。如下图所示（文法使用表 1 ） ：
文法 2
2
2
2
S
S
S
S –
–
–
– >
>
>
> L
L
L
L =
=
=
= R
R
R
R
S
S
S
S ->
->
->
-> R
R
R
R
L
L
L
L ->
->
->
-> *R
*R
*R
*R
L
L
L
L ->
->
->
-> id
id
id
id
R
R
R
R –
–
–
– >
>
>
> L
L
L
L
表 1.2 文法 2
文法 2 产生的状态如下图 2 ：
图 1.2 SLR 状态集
3 ． LR(1)
LR(1)
LR(1)
LR(1) 语法分析器 。 又称为规范 LR
LR
LR
LR 语法分析器 。 相比 SLR 更复杂 。 它使
用的项中增加了一个向前看符号集合 。 当应用这个产生式进行归约时 ， 下一个输入
符号必须在这个集合中 。 只有当存在一个点的最右端的有效项 ， 并且当前向前看符
号是这个向前符号之一时，我们才觉得按照这个产生式进行归约，如下图 1.3 所示
（使用文法 1 ） ：
- 1
- 2
- 3
前往页