编译原理课件chap06(陈火旺)

第六章语法分析——LR分析——LR

第六章 语法分析--LR分析

第五章我们学过自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法与第5章介绍的算符优先分析一样，LR方法也是通过求句柄逐步归约进行语法分析。在运算符优先分析中，句柄是通过运算符的优先关系而求得，LR方法中句柄是通过求可归前缀而求得。

第六章 语法分析--LR分析

LR分析概述

LR（k）分析是根据当前分析栈中的符号串和向右顺序查看输入串的k(k≥0)个符号就可以唯一确定分析的动作是移进还是归约以及用哪个产生式归约。从左到右扫描(L)自底向上进行规约(R)

(是规范规约）

第六章 语法分析--LR分析

LR分析的优缺点

1)适合文法类足够大,适用于大多数上下文无关文法 2)分析效率高 3)报错及时

4)手工实现工作量大5)可以自动生成

美国Bell实验室推出的编译程序自动构造工具——YACC：能接受一个用BNF描述的满足LALR（1）上下文无关文法并对其自动构造出LALR（1）分析器。

第六章 语法分析--LR分析

第六章 LR分析法

一、LR分析概述（基本构造原理与方法）二、LR(0)分析三、SLR(1)分析四、LR(1)分析五、LALR (1)分析

第六章 语法分析--LR分析

LR分析器模型栈 S1 Xm总控程序…… S1 X1 S0#状态文法符号

Input#

output

ACTION GOTO LR分析表

产生式表

第六章语法分析--LR分析

2、LR分析方法的逻辑结构

逻辑上说，一个LR分析器由3个部分组成：

(1) 总控程序，也可以称为驱动程序。对所有的LR分析器 (1)(1)

总控程序都是相同的。

(2) 分析表或分析函数，不同的文法分析表将不同，同一 (2)(2)

个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。

(3) 分析栈，包括文法符号栈和相应的状态栈，它们均是 (3)

先进后出栈。

分析器的动作就是由栈顶状态和当前输入符号所决定。

第六章 语法分析--LR分析

总控程序根据不同的分析表来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法是根据具体文法的分析表对输入串进行分析处理。

LR分析过程的思想是在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法及当前输入符号，按分析表完成相应的分析工作。

第六章 语法分析--LR分析

LR分析过程的思想：

记住历史：记住已移进和归约的整个符号串。（即栈中的内容）立足现实：输入串读头下的符号

展望未来：根据所用的产生式推测未来可能碰到的输入符号。（也通过栈识别）

第六章 语法分析--LR分析

分析表的组成：(1)

分析动作表Action符号状态 S0 S1… Sn

a1action[S0, a1] action[S1, a1]… Sn, a1] action[ action[S

a2action[S0, a2] action[S1, a2]… Sn, a2] action[ action[S

……………

ataction[S0, at] action[S1, at]… S n, a t] action[ action[S

第六章语法分析--LR分析

Si,aj]为二维数组，指出当前 表中action[action[S

栈顶为状态Si，输入符号为aj是所执行的动作。其动作有四种可能，分别为移进(S)、归约(r)、接受(acc)、出错(error)。

(2) 状态转换表goto

第六章 语法分析--LR分析

符号状态 S0 S1… Sn

x1goto[S0, x1] goto[S1,x1]… goto[Sn, x1] goto[

x2goto[S0, x2] goto[S1, x2]… goto[Sn, x2] goto[

……………

xtgoto[S0, xt] goto[S1, xt]… goto[Sn, xt] goto[

[Si,xj]指出栈顶状态为Si,文法符表中goto goto[号为xj时应转到的下一状态。第六章语法分析--LR分析

分析表种类的不同决定使用不同的LR分析方法

a‘) LR（0）分析表

a) SLR分析表(简单LR分析表)

构造简单,最易实现,大多数上下文无关文法都 可以构造出SLR分析表,所以具有较高的实用 价值。使用SLR分析表进行语法分析的分析器 叫SLR分析器

b) LR（1）分析表(规范LR分析表)

适用文法类最大,大多数上下文无关文法都能 构造出LR分析表,但其分析表体积太大.暂时实 用价值不大.

13

第六章 语法分析--LR分析

c) LALR分析表(超前LR分析表)这种表适用的文法类及其实现上难易在上面两种之间,在实用上很吸引人.使用LALR分析表进行语法分析的分析器叫LALR分析器。例：YACC

文法规则文件 YACC源文件

YACC

某语言的 LALR分析器

第六章语法分析--LR分析

几点说明

1.四种分析表对应四类文法

2.一个SLR文法必定是LALR文法和LR（1）文法

第六章 语法分析--LR分析

15

3、LR分析过程：

LR分析步骤：

(a) 将初始状态S0和句子的左界符#分别进分析栈。 (a)

(b) 根据栈顶状态和当前输入符号查动作表，进 (b)

行如下的工作。 ※ 移进：当前输入符号进符号栈，根据状态转换表新的状态进状态栈，继续扫描，从而下一输入符号变成当前输入符号。 ※ 归约： (1)按某个产生式进行归约，若产生式的右端长度为n，则符号栈顶和状态顶n个元素同时相应退栈。(2)归约后的文法符号进符号栈，(3)查第六章 语法分析--LR分析