编译原理Ch5

第五章 自下而上的语法分析

一、自下而上分析的基本问题

1.自下而上分析方法的关键

找出当前句型的可归约串，然后根据产生式判别将它归约成什么样的非终结符

2.规范规约基本概念

(1)短语

G为文法，S为开始符号，假定αβδ是G的一个句型，如果
$$
S\overset*{\Rightarrow}αβδ且A\overset+{\Rightarrow}β
$$
则称β是句型αβδ相对于非终结符A的短语。
使用语法树来表示：
针对某一非终结符，以该终结符为根的，高度大于等于2的子树的，所有叶子结点，组成了该终结符的短语。

(2)直接短语

若$ A {\Rightarrow} β $，则β是非终结符A的直接短语。
使用语法树来表示：
针对某一非终结符，以其为根节点的，高度等于2的树的叶子结点，是该非终结符的直接短语。

(3)句柄

最左直接短语。
使用语法树来表示：
一棵语法树的最左边的高度为2的子树的叶子节点。

(4)规范规约

从句子到开始符号的归约序列，如果每一步都是把句柄替换为相应产生式的左部符号而得到的，则称为规范归约。规范归约是最右推导（规范推导）的逆过程。

3.自下而上的分析过程

考虑文法

$G(E)：E→E+T|T$
$T→T*F | F$
$F→i| (E)$
$并假定输入串为(i+i)*i，考察自下而上的分析过程$

答案：

二、LR分析法

1.LR分析表工作过程

(1)初始化

状态栈：$S_0$
符号栈：#
输入串：$a_1a_2a_3…a_n$

(2)一般情况下

状态栈：$S_0S_1…S_m$
符号栈：#$X_1X_2…X_m$
输入串：$a_ia_{i+1}…a_n$#

(3)$ACTION[S_m,a_i]=S_x$移入动作

表示当前状态栈顶是状态$m$，输入串头为$a_i$，此时让$x$入状态栈，让$a_i$入符号栈，变为：
状态栈：$S_0S_1…S_mx$
符号栈：#$X_1X_2…X_ma_i$
输入串：$a_{i+1}…a_n$#

(4)$ACTION[S_m,a_i]=R_x$归约动作

表示当前状态栈顶是状态$m$，输入串头为$a_i$，此时，状态栈和符号栈顶k个元素出栈，并用产生式$x(A→X_{m-(k-1)}…X_m)$对符号栈出栈元素进行规约。（k表示被规约了k个字母）变为：
状态栈：$S_0S_1…S_{m-k}$
符号栈：#$X_1X_2…X_{m-k}A$
输入串：$a_ia_{i+1}…a_n$#
并且此时，若
$$
GOTO[S_{m-k},A]=y,
$$
则跳转到状态y，y入状态栈顶，格局变为：
状态栈：$S_0S_1…S_{m-k}y$
符号栈：#$X_1X_2…X_{m-k}A$
输入串：$a_ia_{i+1}…a_n$#

(5)$ACTION[S_m,a_i]=acc$

分析成功

(6)$ACTION[S_m,a_i]=空白$

出现语法错误

2.LR分析算法

• 输入：串w和LR语法分析表，该表描述了文法G的ACTION函数和GOTO函数
• 输出：如果w在L(G)中，则输出w的自底向上语法分析过程中的规约步骤；否则给出一个错误提示。
• 方法：初始时，语法分析器栈中的内容为初始状态$S_0$，输入缓冲区中的内容为w#。然后，语法分析器执行下面的程序：
  

3.LR分析器的逻辑结构

三、LR(0)分析

1.LR(0)项目

• 把右部某位置有圆点的产生式称为相应文法的一个LR(0)项目，简称项目。
  $$
  A→a_1·a_2
  $$
  例如，

$S→·bBB(1)$
$S→b·BB(2)$
$S→bB·B(3)$
$S→bBB·(4)$

• 项目描述了句柄识别的状态
• 产生式1是移进项目，·后跟着终结符
• 产生式2/3是待约项目，·后跟着非终结符
• 产生式4是规约项目，·后为空

2.增广文法

• 如果G是一个以S为开始符号的文法，则G的增广文法是在G中加上新开始符号S’和产生式S’→S而得到的文法
• 目的是使得文法的开始符号仅出现在一个产生式的左边，从而使得分析器只有有一个接受状态

3.项目闭包closure(I)

• I是一个LR(0)项目，表示为$I→I_0…I_i·I_{i+1}…I_n，closure(I)$表示为：
  • $I$本身
  • 若形如$K→α·Aβ$的项目属于$I$，且$A→µ$是文法的一个产生式，任何形如$A→·µ$的项目也应加到$closure(I)$中
  • 重复上述过程，直到$closure(I)$不变
• 此时，$closure(I)$中的所有项目互相称为等价项目，$closure(I)$集合视为一个状态。

4.构建LR(0)自动机

5.构造LR(0)分析表

• 行标为状态编号
• ACTION表列标为终结符+#，GOTO函数列标为规约时使用过的非终结符
• ACTION表中，若LR(0)自动机中的项目为移进项目，则ACTION=sn，n为下一个状态的编号
• ACTION表中，若LR(0)自动机中的项目为规约项目，则ACTION=rn，n为使用产生式规约的编号
• GOTO表中，若LR(0)自动机中的项目为待约项目，则GOTO=n，n为下一个状态的编号
• 例：
  

6.LR(0)分析过程的冲突

(1)移进/规约冲突

• $I_2$的第一条表示，无论后边是什么字符，都要采取规约动作，但$I_2$的第二条表示，如果下一个读入字符是*，则采取移进操作。
• 此时，自动机不知道到底是用移进还是规约动作。
• 同理$I_9$也有同样的问题。
  
• 如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)文法
• 不是所有CFG【上下文无关文法】都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法

(2)规约/规约冲突

• 对于某一个状态，接受某个终极符后既可执行规约动作1，也可执行规约动作2，如图中的B和T，同时图中也有移进规约冲突。

7.SLR分析

(1)思想

• 可以解决一些冲突。移进/规约冲突例中，若下一个输入符号是*，即使我们选择规约出E，但*并不在E的FOLLOW集中，而在T的FOLLOW集中，因此我们要选择移进动作。
  

(2)算法

• 理解：下一个输入符号是a，先查看所有移进项目，圆点后边如果有a，则选择移进a，如果a在规约项目左部的FOLLOW集中，则选择规约。

(3)与LR(0)对比

• LR(0)在分析时向前看0个符号，也就是不向前看，在分析表中，若遇到ACTION=r，则一行全都是规约动作；SLR分析时向前查看一个符号，当输入符号不在FOLLOW集中，才采取规约动作。
  

(4)SLR分析遇到的冲突

• 此例中，等号在R的FOLLOW集中，发生了冲突。

四、LR(1)分析法

1.LR(1)项目

• 将一般形式为$[A→αβ,a]$的项称为$LR(1)$项，其中$A→αβ$是一个产生式
• a是一个终结符（包括#），他的含义是，在当前状态下，A后面要求紧跟的终结符，称为该项的展望符(lookahead)
• 也就是说，只有在A后面是a时，才使用这个项目。
• LR(1)中的1指二元组第二个项。
• 在形如$[A→α·β,a]$且$ β≠ \varepsilon $的项中，展望符a没有任何作用。
• 但是一个形如$[A→α,a]$的项在只有在下一个输入符号是a时才可以按照A→α进行规约。
  • 这样的a的集合总是FOLLOW(A)的子集，而且它通常是一个真子集。

2.LR(1)等价项目

• 对于待约项目$[A→α·Bβ,a]$，若$B→γ$，则等价项目是$[B→·γ,b]$
• $b∈FIRST(βa)$

3.构建LR(1)自动机

• 如果除展望符外，两个LR(1)项目集是相同的，则称这两个LR(1)项目集是同心的，如$I_8$和$I_10$、$I_4$和$I_11$

4.LR(1)项目集闭包计算算法

• 对于I中的每一项$[A→α·β,a]$
• 对于增广文法中的每一个产生式$[B→·γ,b]$
• 对于$FIRST[βa]$中的每一个符号b
• 将$[B→·γ,b]$加到集合I中
• 直到集合I没有变化为止

5.LR(1)分析表的构造算法

五、LALR分析法

1.为何被提出？

• LR(1)分析法占用的空间多，因为状态多，有很多同心项：
  
  

2.可能出现的问题

(1)可能会产生归约/规约冲突

• 不会产生移进规约冲突

  因为同心项目中，“心”是相同的，即每一项的产生式部分相同，合并的是展望符，而展望符只在归约时起作用，在移进时不起作用。
  因此，只要合并前无移进/归约冲突，合并后就没有。

(2)推迟错误的发现

• 会晚发现错误，不会放过错误

3.LALR(1)特点

• 形式上与LR(1)相同
• 大小上与LR(0)/SLR相当
• 分析能力介于SLR和LR(1)之间
  $$
  SLR<LALR(1)<LR(1)
  $$
• 合并后的展望符的集合依旧是FOLLOW集的子集