第07章 自底向上LR分析法New.ppt

第7章自底向上LR分析法
编译原理
主讲教师:周时阳
1
本章研究自底向上的LR分析法,LR分析法是一类归约法的统称,主要介绍其中最基本的LR(0)、SLR(1)、LR(1)和LALR(1)四种分析法,重点讨论可归约前缀的作用、识别活前缀DFA的构造、分析表的构造、分析法适用条件和语法分析程序结构及其分析算法。
内容摘要
2
LR分析概述
LR(0)分析
SLR(1)分析
LR(1)分析
LALR(1)分析
重点讲解
小结
3
寻找句柄是根据向右查看输入串的K个符号,结合分析所处的“状态”,确定句柄是否出现在分析栈顶部。
LR分析法也称为LR(K)分析法。这里,L表示从左到右扫描输入串,R表示最右推导之逆过程(即规范归约),K表示向右查看输入串符号的个数。
这类自底向上的语法分析法,其总体框架可以划分为总控程序、分析栈和分析表三个组成部分,如下图所示。
目录
(符号栈)
(状态栈)
分析栈S
总控程序
x
·
·
·
#
a1a2 a3 a4···ai-1 ai ai+1 ··· an-1 an #
输入栈I
(ACTION)
q
·
·
·
q0
(GOTO)
分析表M
文法
(规则集)
LR分析概述
4
假设文法G[S]和分析表M,状态0为开始状态,;a为输入栈I栈顶元素,则总控程序的算法如下:
⑴初始化:“0#”进栈S;
⑵移进:[q,a]为sj,则将“ja”进栈S,输入栈I出栈,转到步骤⑵;
⑶归约:[q,a]为ri,则
() 令第i条规则为A→α。将︱α︱个状态和符号退出分析栈S;
() 令q′。[q′,A]为状态j,将“ja”进栈S,转到步骤⑵;[q′,A]为e k,转入出错处理ERROR();
⑷报错:[q,a]为e k,则转入出错处理ERROR();
⑸接受:[q,a],则输出“OK”,结束。
5
设文法G[S]定义如右,,其中表中空白出表示e k。试给出输入串abbcde的LR分析过程。
VT∪VN
G[S]:⑴ S→aAcBe
⑵ A→b
⑶ A→Ab
⑷ B→d
目录
6
LR(0)分析
可归前缀和活前缀
[S]为例,讨论LR分析法的基本原理,同时将提出可归前缀和活前缀重要概念。
目录
G[S]:⑴ S→aAcBe
⑵ A→b
⑶ A→Ab
⑷ B→d
G[S]:⑴ S→aAcBe[1]
⑵ A→b[2]
⑶ A→Ab[3]
⑷ B→d[4]
SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]
ab[2]b[3]cd[4]e[1]
aAb[3]cd[4]e[1]
aAcd[4]e[1]
aAcBe[1]
 S
如果使用分析栈实现这个过程,则方法也很简单:将输入串符号移进分析栈,直到遇到“编号”为止;这时,句柄出现在分析栈顶部,令编号代表的规则是A→α,将分析栈顶部︱α︱个符号出栈,A进栈便完成一次归约。重复这些步骤,直到归约出S。
7
即:尾符号恰好是句柄β尾符号的文法规范句型之前缀,称为可归前缀,可归约前缀之前缀称为活前缀。
G[S]:⑴ S→aAcBe
⑵ A→b
⑶ A→Ab
⑷ B→d
例如文法G[S],句型aAbcde的句柄为Ab,活前缀有:ε、a、aA和aAb,其中,aAb为可归前缀。
将符号串的任意含有头符号的子串称为前缀。特别地,空串ε为任意串的前缀。
设文法G[S],如果SαAωαβω是句型αβω的规范推导,则αβ称为可归前缀,αβ的前缀称为活前缀。
*
R
R
目录
8
假设事先知道文法所有规范句型可归前缀,使用分析栈实现分析的具体步骤修改为:
将输入串符号移进分析栈,直到分析栈出现“可归前缀”为止;这时,句柄出现在分析栈顶部,令可归前缀编号代表的规则是A→α,将分析栈顶部︱α︱个符号出栈,A进栈便完成一次归约。重复这些步骤,直到归约出S。显然不再需要输入串夹带着编号,也可以得到规范归约。
[S]的可归前缀如下:ab[2]、aAb[3]、aAcd[4]、aAcBe[1],使用分析栈实现abbcde的分析过程如下。
abbcde
aAbcde
aAcde
aAcBe
 S
SaAcBe[1]aAcd[4]