第六章 LR分析法
在第5章中已经讨论过，自底向上分析方法是一种移进归约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K≥0）符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。
LR（K）分析方法是1965年Knuth先生提出的，括号中的K表示向右查看输入串符号的个数。这种方法比起自顶向下的LL（K）分析方法和自底向上的优先分析方法对文法的限制要少得多，也就是说对于大多数用无二义性上下文无关的文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置。但是，由于它的主要缺点是对于一个实用语言文法的分析器的构造工作量相当大，K愈大构造愈复杂，实现相当困难。因此，目前对于真正实用的编译程序，所采用的LR分析器都是借助于美国Bell实验室1974年推出的“一个编译器的编译器—YACC”来实现的。它能接受一个用BNF描述的满足LALR（1）的上下文无关文法并将自动构造出LALR（1）语法分析器。
本章将主要介绍LR分析的基本思想和当K≤1时LR分析器的基本构造原理和方法。其中LR（0）分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，对绝大多数高级语言的语法分析器是不能适用的，然而，它是构造其它LR类分析器的基础。当K=1是，已能满足当前绝大多数高级语言编译程序的需要。其中SLR（1）和LALR（1）分别是LR（0）和LR（1）的一种改进。
本章重点：LR（0）、SLR（1）
第一节 LR分析概述
（一）LR（1）分析器的逻辑结构及工作过程在逻辑上，一个LR（1）分析器的结构如图6-1-1（a）所示。它有一个输入符号串，一个下推分析栈，以及一个总控程序和分析表。LR（1）分析器在总控程序的控制下自左至右扫视输入串中的各个符号，并根据当前分析栈中所存放之文法符号的状况及正扫描之输入符号，按分析表的指示完成相应的分析动作。
第7章LR分析法
伍春香
武汉大学计算机学院优先分析法回顾
优先分析法的效率问题。问题：
算符优先分析法：文法不含ε规则。简单优先分析法：不允许文法有相同的产生式右部。
——不是严格的从左到右
——每一次比较都需要(重新)查优先关系矩阵/函数
LR(k)分析法
学习目标
掌握
LR方法的基本原理
构造以LR(0)项目集为状态的识别规范句型活前缀的DFA
构造以LR(1)项目集为状态的识别规范句型活前缀的DFA
LR(0)、SLR(1)分析表的构造
LR(1)、LALR(1)分析表的构造
二义性文法的LR分析LR分析法和LR分析程序
LR分析程序的结构
LR分析表
LR分析过程
7.1 LR分析法和LR分析程序
1．LR分析程序的逻辑结构
包括两部分：一个总控(驱动)程序和一张分析表。
总控程序
分析表7.1 LR分析法和LR分析程序
1．LR分析程序的逻辑结构
设置一个栈，每个元素包含两部分：状态与文法符号。
q
0q
1 q
2 ……q
m
# X
1 X
2 ……X
m符号栈状态栈
总控程序
分析表
7.1 LR分析法和LR分析程序
1．LR分析程序的逻辑结构
输入符号串，总控程序根据分析表分析并给出判断结果。
符号栈状态栈
a
ka
k+1……a
n#q
0q
1 q
2 ……q
m
# X
1 X
2 ……X
m输入串
总控程序
分析表7.1 LR分析法和LR分析程序
1．LR分析程序的逻辑结构
输入符号串，总控程序根据分析表分析并给出判断结果。
符号栈状态栈
a
ka
k+1……a
n#q
0q
1 q
2 ……q
m
# X
1 X
2 ……X
m输入串
句型
规范句型
7.1 LR分析法和LR分析程序
1．LR分析程序的逻辑结构——分析表
分析表是LR分析程序的核心部分，它有“动作”
(ACTION) 和“状态转换”(GOTO) 两部分。
ACTION和GOTO都是二维数组：
ACTION[q, a]——状态q面临输入符号a时应采取的动作
GOTO[q, X]——状态q面对文法符号X时下一状态状
《编译原理》LR分析法与构造LR（1）分析表的步骤-例题解析
《编译原理》LR 分析法与构造 LR(1) 分析表的步骤 - 例题解析
笔记
直接做题是有⼀些特定步骤，有技巧。但也必须先了解⼀些基本概念，本篇会通过例题形式解释概念，会容易理解和记忆，以及解决类似问题。
如果只想做题可以直接下拉⾄习题部分。
（⼀）关于状态
对于产⽣式 A→aBcD，就可以分解为下⾯⼏个不同的识别状态：
（1）A→.aBcD
（2）A→a.BcD
（3）A→aB.cD
（4）A→aBc.D
（5）A→aBcD.
“.” 的左部符号表⽰已被识别出来的那部分句柄符号
状态（1）表⽰：处于句柄的头
状态（2）表⽰：已经识别出字符 a，等待 形成以 B 为产⽣式左部的右部
状态（3）表⽰：刚刚进⾏了⼀次规约，即把关于 B 的产⽣式右部规约成 B
状态（4）表⽰：已经识别出字符 c，等待 形成以 D 为产⽣式左部的右部
状态（5）表⽰：已经到达句柄的尾巴，可以把 aBcD 规约为产⽣式左部的符号 A
（⼆）什么是 LR(k) 分析法？
字⾯意思理解：
字符含义
L表⽰ 从左到右 扫描输⼊串
R表⽰利⽤ 最右分析⽅法 来识别句⼦，即构造⼀个 最右推导的逆过程
k表⽰向右查看输⼊串符号的个数
LR 分析过程是规范归约的过程
规范规约是最右推导的逆过程，最右推导是规范推导，所以 最左规约是规范规约。
LR 分析法根据当前分析栈中的符号串和向右顺序查看输⼊串的 k 个符号就可以唯⼀确定分析器的动作是移进还是归约、利⽤那个产⽣式进⾏归约。
当没有指明 k 是⼏的时候，默认为 1
（三）⽂法的拓⼴？
⽂法的拓⼴是对现有⽂法，添加⼀个 S'，并对⽂法进⾏展开。
例如：
对于⽂法 G[E]:
E → E+T|T
T → T*F|F
F → i|(E)
可以把它拓⼴为
⽂法 G[E']:
E' → E
E → E+T|T
T → T*F|F
F → i|(E)
此时可能会有疑问，不就是加了个开始符号，有什么意义呢？为什么要再加个开始符号呢？
实验三 LR(1)分析法
一、实验目的
构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
二、实验内容
对下列文法，用LR（1）分析法对任意输入的符号串进行分析：
（1）E- E+T
（2）E- E—T
（3）T- T*F
（4）T- T/F
（5）F- (E)
（6）F- i
三、LR（1）分析法实验设计思想及算法
(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。
(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
LR分析器由三个部分组成：
其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：
(1)移进：
action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。
(2)归约：
action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。
(3)接受acc:
当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。
