第七章 LR分析.ppt.ppt

文档介绍：第七章 LR分析
第一节 LR分析概述
第二节 LR(0)分析
第三节 SLR(1)分析
第四节 LR(1)分析
第五节 LALR(1)分析
第六节二义性文法在LR分析中的应用
第七节
第八节典型例题及解答
知识结构
四种LR类型:
LR(0) 、SLR(1) 、 LALR(1) 、 LR(1) 功能逐个增强
四种LR类型的文法是真包含关系
一个文法是LR(0)文法一定是LR(1)文法吗?
LR分析概述
LR分析法:
它是给出一种能根据当前分析栈中的符号串(通常
以状态表示)和向右顺序查看输入串的k个(k≥0)符号就
可唯一地确定分析器的动作是移进还是归约和用哪个产
生式归约,因而也就能唯一地确定句柄
LR分析过程是一种规范归约过程
LR(k)分析方法是1965年Knuth提出的,括号中的k表
示向右查看输入串符号的个数
第七章 LR分析
LR分析优点:对文法的限制很少、分析速度快、能准
确即时地指出出错位置
LR分析主要缺点:对于一个实用语言文法的分析器的
构造工作量相当大,k愈大构造愈复杂,实现比较困难
一个LR分析器的组成:
(1)总控程序(驱动程序):
(2)分析表(分析函数):动作表和状态转换表
(3)分析栈:文法符号栈和状态栈
:
其中SP为栈指针,S[i]为状态栈,X[i]为文法符号栈
状态转换表内容按关系GOTO[Si,X]=Sj确定,该关系式
是指当栈顶状态为Si遇到当前文法符号为X时应转向状态Sj
X为终结符或非终结符
ACTION[Si,a]规定了栈顶状态为Si时遇到输入符号a应执
行的动作,动作有4种可能:
(1)移进:
当Sj =GOTO[Si,a]成立,则把Sj移入到状态栈,把a移
入到文法符号栈。其中i,j表示状态号
(2)归约:
当在栈顶形成句柄为β时,则用β归约为相应的非终结
符A,即当文法中有A Β产生式,而β的长度为r(
即| β|=r),则从状态栈和文法符号栈中自栈顶向下去掉r个
符号,即栈指针SP减去r。并把A移入文法符号栈内,再把
满足Sj=GOTO[Si,A]的状态移进状态栈,其中Si为修改指针
后的栈顶状态