【编译原理系列】自下而上分析法与 LR(1) 文法

亦凉 2023-01-10 11:49 482阅读 0赞

# 自下而上分析 #

从句子ω开始，**从左到右扫描ω**，**反复用产生式的左部替换产生式的右部（句型中的句柄）**、谋求对ω的匹配，**最终**得到文法的**开始符号**，**或者发现**一个**错误**：规范归约—剪句柄—移进/归约分析—SLR(1)分析器

# 规范规约 #

设αβδ是文法G的一个**句型，**

*  若 存在S =\*>αAδ，A =+>β，
 *  则 称β是句型αβδ相对于A的**短语**，
 *  特别的，若 有A→β，则 称β是句型αβδ相对于产生式A→β的**直接短语**
 *  一个句型的**最左直接短语**被称为**句柄**

如：句型：id1+id2\*id3，短语：id1+id2\*id3、id2\*id3、id1、id2、id3，直接短语：id1、id2、id3，句柄：id1

*  **句型**：存在的一个**子树**；
 *  **短语**：以非终结符为根子树中**所有**从左到右的**叶子**；
 *  **直接短语**：**只有父子关系的树中所有**从左到右排列的**叶子（树高为2）**；
 *  **句柄**：**最左边**父子关系树中所有从左到右排列的叶子（**句柄是唯一的**）
    
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70][]

## 最左规约 ##

若 α是文法G的句子且满足下述条件，则 称序列αn，αn-1，…，α0是α的一个最左归约。

1.   α n = α α\_n=α αn=α
2.   α 0 = S α\_0=S α0=S（S是G 的开始符号）
3.  对任何i(0<i<=n)， α i − 1 α\_\{i-1\} αi−1是将 α i α\_i αi中**句柄**替换为相应产生式左部非终结符得到的

**最左归约**的**逆过程**是一个**最右推导**，分别称最右推导和最左归约为**规范推导**和**规范归约**

*  推导`=>`；归约`<=`（剪句柄的过程）

# 移进-归约分析器 #

也有驱动器指向输入记号流的向上的箭头的！！！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1][]

格局：

*  栈中内容，当前剩余输入

改变格局的动作：

1.  **移进(shift)：** 输入序列中的终结符进栈。(匹配终结符)
2.  **归约(reduce)：** 将栈顶句柄替换为对应非终结符(最左归约)
3.  **接受(accept)：** 宣告分析成功
4.  **报错(error)：** 发现语法错误，调用错误恢复例程

注意

1.  **句柄**总是在**栈顶**形成(最左归约)
2.  **栈中保留**的总是一个**右句型**的前缀(加上若干终结符形成句型)，称为**活前缀**
3.  **最左归约**是逻辑上从下到上构造一棵分析树，或从下到上为分析树剪句柄

## 规约过程 ##

特点：

1.  采用最一般的**无回溯**移进-归约方法
2.  **可分析的文法**是**LL文法的真超集**
3.  能够**及时发现错误**，快到从左到右扫描输入序列的最大可能；
4.  **分析表较复杂**，难以手工构造

规约过程：

初始格局为：（#0，ω#， 移进），其中0是初态
    ip指向ω#中的第一个终结符，top指向栈顶初始状态；
    loop  s:=top^; a:=ip^;
       case action[s，a] is
    	 shift s': push(a); push(s'); next(ip); -- 移进
    	 reduce by A→β:
    		pop(2*|β|);	 -- 弹出句柄和相应状态
    		s' := top^; -- 暴露出当前栈顶状态s'
    		push(A);     	 -- 产生式左部符号进栈
    		push(goto(s'，A)); -- 新栈顶状态进栈
    		write(A→β);      -- 完成归约，跟踪分析轨迹
    	 accept:  return; 		-- 成功返回
    	 others:  error;  		-- 出错处理
       end case;
    end loop;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2][]

## 活前缀与项目 ##

出现在移进-归约分析器**栈中**的**右句型的前缀**，被称为文法G的**活前缀**（viable prefix）

*  `活前缀＋若干剩余输入（不在栈中）＝>右句型`
 *  若存在最右推导S’=\*>αAω=>αβ1β2ω，则称**项目\[A→β1.β2\] 对活前缀αβ1有效**

一个**LR(0)项目**(简称项目)是这样一个产生式，在它右部的某个位置**有一个点“.”**。对于A→ε，它**仅有**一个项目A→.

*  一个产生式右部若有n个文法符号，则该产生式有n+1个LR(0)项目
 *  每个产生式是一个识别活前缀的NFA；每个**项目**是NFA的一个**状态**
 *  项目A→α.β显示了分析过程中看到(移进)了产生式的多少；β**不为空**的项目称为**可移进项目**，β**为空**的项目称为**可归约项目**

项目A→β1.β2对活前缀αβ1有效，具有两层含意：

1.  从文法开始符号，**经αβ1**可到达**该项目**(项目所在**状态**)
2.  在当前活前缀的情况下，该项目**可指导下一步分析动作**(αAω=>αβ1β2ω)

### 活前缀与项目的关系 ###

① 一个**项目**可能对**若干个活前缀**有效，项目A→β1.β2对所有从初态出发可以到达此项目的路径上的标记均有效（一个路径标记是一个活前缀）

② **若干个项目**可能对**同一个活前缀**有效，项目集中的所有项目对同一活前缀均有效

综合①②可知：

*  **同一项目集**中的**所有项目**，对此项目集的**所有活前缀**均有效，即项目集中的每个项目均有同等权利指导下一步动作（*即一个对某活前缀有效，则整个项目集对他都有效*）
 *  这里的**活前缀的DFA**也要每一种可能分行写，而且不可以用`|`连接，对于`.`后面的非终结符，展开要完全，比如项目集中已经存在部分，也要补全，然后每个还要标序号，为了清晰可见，可以不连接到，而只是箭头和标号，同时注意如果给出的不是拓广文法，要先变成拓广文法，然后给出识别活前缀的DFA

③ 有效项目的意义

1.  到目前为止分析是正确的；
2.  指导下一步的分析：  
    A→β1.β2（可移进项）：移进β2中第一个终结符  
    B→β.（可归约项）：按产生式B→β归约

④ 项目集中的冲突和解决冲突的简单方法：SLR(1)

*  当一个项目集中同时存在：
    
     *  A→β1.β2和B→β1. ：**既可移进又可归约**，**移进/归约冲突**
     *  A→α.和B→α. ：**均可指导下一步分析**，**归约/归约冲突**
 *  解决方法：**简单向前看一个终结符：**
    
     *  移进/归约冲突：若**FIRST(β2)∩FOLLOW(B)=Φ**，冲突可解决
     *  归约/归约冲突：若**FOLLOW(A)∩FOLLOW(B)=Φ**，冲突可解决

## 活前缀 DFA ##

SLR(1)分析器（即简单LR(1)） 构造过程：

*  首先构造一个可以识别文法G中**所有活前缀的DFA**，然后根据**DFA**和简单的**向前看**信息**构造SLR分析表**
 *  在移进-归约分析中，只要保证已扫描过的输入序列**可以归约为一个活前缀**，则**分析到目前为止没有错误**

### 拓广文法 ###

拓广文法 G ’ = G ∪ \{ S ’ → S \} G’ = G∪\\\{S’→S\\\} G’=G∪\{ S’→S\}

*  写拓广文法的时候，每一个一行，然后要写`(i)`，对于同一个非终结符展开成多个用`|`连接的时候，每一种选择也必须分行写
 *  其中：`S'→.S`是识别S的初态，`S'→S.`是识别S的终态。
 *  目的是使最终构造的DFA状态集中具有**唯一的初态和终态**

### 活前缀 DFA 构造 ###

*  NFA（项目）→DFA（项目集）

词法分析器－“子集法” ：

*  ① ε\_闭包(I)：从**状态集I**不经任何**字符**能到达的**状态**全体
 *  ② smove（I，a）：所有从I经**字符a**能**直接**到达的**状态**全体

活前缀 DFA 类似的两个过程：

*  ① closure(I)：从项目集I不经任何**文法符号**到达的**项目**全体
 *  ② goto(I，x)：所有从I经**文法符号x**能**直接**到达的**项目**全体

项目集I的闭包closure(I)是这样一个项目集

1.  I中的所有项目属于closure(I)；
2.  若A→α.Bβ属于closure(I)，则所有**形如B→.γ的项目**属于closure(I)；
3.  其它任何项目不属于closure(I)

即若`.`后面是一个非终结符B，则需要将B展开成`B→.γ`的形式

closure(I)的计算

function closure（I） is
    begin   J := I；
        for J中每个项目[A→α.Bβ]和G中每个产生式B→γ
        loop 
            if   B→.γ不在J中  
            then 加入[B→.γ]到J;
            end  if；
            exit when 再没有项目可以被加入到J中；
        end loop；    
        return（J）；
    end closure；

对所有属于项目集I、且形如\[A→α.Xβ\]的项目（X∈N∪T），goto(I，X)是所有**形如\[A→αX.β\]的项目**

*  设J=goto(I，X)，K=closure(J)，K中项目A→α.β分为两类：

1.  J： α非空，因为至少有一个X；**均是核心项目**
2.  K-J： α=ε，即 "."在产生式右部最左边（想到新增加的都是`B→.γ`这类）；可由某个J计算而来（K-J=closure(J)-J）；**均是非核心项目**

**项目\[S’→.S\]和所有“.”不在产生式右部最左边**的项目称为**核心项目**(kernel items)，其它“.”在产生式右部**最左边**的项目(不包括\[S’→.S\])称为**非核心项目**(nonkernel items)

比较：

*  项目A→α.β显示了分析过程中看到(移进)了产生式的多少；
 *  β**不为空**的项目称为**可移进项目**，β**为空**的项目称为**可归约项目**

**构造过程**：

构造文法G的、基于LR(0)项目的、识别活前缀的DFA
    加入closure(S’→.S)到C中，作为唯一未标记状态; -- 初态
    while C中还有未标记状态I   -- 考察所有未标记状态
    loop 标记I;
    	for I状态下的每个文法符号x   -- 考察所有x
    	loop if J:=closure(goto(I,x))非空  --有下一状态
    		 then 	Dtran[I,x]:= J;  -- 记录下一状态转移
    			if J不在C中	           -- 新状态待考察
    			then 不标记加入J到C；
    			end if;
    		  end if;
    	end loop;
    end loop;

### 活前缀 DFA 冲突 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3]

#### 证明是LR(0)文法 ####

若上述构造的**DFA中没有冲突**，则**文法是LR(0)的**

*  即：如果某某项目集既有可移进项目又有可归约项目，产生了移进/归约冲突，那么该文法不是LR(0)文法

#### 证明是SLR(1)文法 ####

若**冲突可以解决**，则称文法为**SLR(1)文法**，构造的分析表为SLR(1)分析表

*  SLR文法分析过程**可以解决归约-归约冲突**，但是**不一定能解决移进-归约冲突**。
 *  如果规约式的 follow 集和移进的下一个元素相交为空，则为 SLR文法，反之不是。

> F->Y·+B  
> F->Y·  
> 如果 FOLLOW(F) = \{a, b, +\}，那当我们遇到 + 符号时，就无法确定到底是选择移进操作得到F->Y+·B，还是归约F。  
> SLR不能完全解决reduce-shift conflict. 这就是为什么我们要选择LR(1) / LALR(1)了

#### 证明是LR(1)文法 ####

若**冲突不可以解决**，则称文法为**LR(1)文法**，构造的分析表为LR(1)分析表

*  向前搜索符的过程: 当我们看到一条 `A->b∙C,d` 时
    
     *  意思是: 我们正在解析一个A->bC的式子,此时我们已经读过了b, 紧接着会读C, 当我们读完整个A->bC后面接着的是d.
 *  举个例子：存在产生式 `A->bCd` , `C->e` ，并且某个项目集内（即某个状态内）有`A->b∙Cd,#`
    
     *  根据规则可以生成 `C->∙e,d` 此处的d是来自于在第一条式子中C后面字串的FIRST, 即FIRST(d,\#),
     *  若此时有FIRST集中有多个项, 需要将每一个项都加入
 *  注意：这里的 **该产生式后面的 first 集是对于整个产生式的，并不取决于’ ∙ ’ 的位置**（在构造一个状态项目集（即构造闭包）时，发生替换时确定，以后不再变化）
    
     *  例如下图：S-> L=R 在起始产生式（S’ -> S）通过求闭包得到后，就确定了其后面式子的 first 集，此后不管 ’ ∙ ’ 怎么移动，其 first 集都不再变  
        ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 4][]

#### 非SLR(1)文法 ####

**二义文法不是SLR(1)文法**

所以非SLR(1)文法分为两类

*  非二义文法：可以增加向前看终结符个数解决冲突
 *  二义文法：无论向前看多少个终结符，也无法解决二义性

## LR 分析表 ##

与预测分析表不同的是LR分析表的列既有终结符也有非终结符的部分

**动作表**

*  action\[s, **a**\]确定改变格局的动作

**转移表**

*  goto\[s, **A**\]指示非终结符的**状态转移**

若为文法G构造的移进-归约分析表中**不含多重定义**的条目，则称G为LR(k)文法，分析器被称为是LR(k)分析器，它所识别的语言被称为LR(k)语言。

*  L表示**从左到右扫描**输入序列，R表示**逆序的最右推导**
 *  k表示为确定下一动作**向前看的终结符个数**，一般情况下k<=1。当k=1时，简称LR
 *  有LR(0)、SLR(1)、LALR(1)和LR(1)分析器，它们功能的强弱和构造的难度依次递增；
    
     *  当k>1后，分析器的构造趋于复杂，一般情况下并不构造k>1的LR(k)分析器

### 构造SLR分析表 ###

输入: 基于G的LR(0)项目集的、识别活前缀的DFA=(C, Dtran)

if   DFA中有不能解决的移进/归约和归约/归约冲突
    then error;
    else for 每个状态转移Dtran[i,x]=j
    	   loop if x∈T 
                then action[i,x]:=Sj; 
                else goto[i,x]:=j; 
                end if;
           end loop;
           for  状态i的每个可归约项A→α.
           loop  if   S'→ S. 
                 then action[i, #]:=acc;
                 else for 每个a∈FOLLOW(A) 
                      loop action[i,a]:=Rk; end loop; --k代表当时给表达式的标号
                 end if;
           end loop;
       end if;
    2. DFA的初态（S'→.S所在的状态），是分析表的开始状态

# LR(0) 与 SLR(1) 示例 #

## 构造 DFA ##

对产生式进行编号并画出 DFA

(0)  S' → E
    (1)  E → aA
    (2)  E → bB
    (3)  A → cA
    (4)  A → d
    (5)  B → cB
    (6)  B → d

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 5][]

## 由 DFA 填分析表 ##

1、根据 DFA 的项目集确定分析器状态，写出分析表的行下标（行首）。

*  并根据分析表的要求写出 ACTION、GOTO 子表的列下标（列首）。
 *  ACTION 表列下标是所有的终结符，GOTO 表的列下标是除了拓广文法新加入的非终结符之外的所有其他非终结符

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 6][]

2、填写表格内容——实际上就是把 DFA 中的各个转移的边都挪进来。具体就是要逐个去看

2.1 对于移进项目：

*  从初始的 0 状态出发，有一条标记为 a 的边连接到 2 状态。
 *  这就说明，进行语法分析的过程中，当栈顶为 0 状态且剩余输入为 a 时，就需要执行移进动作——将 a 移进栈，并紧接着将 DFA 的状态转移到 2。因此，0 行 a 列填入 s2。
 *  同理，0 行 b 列填入 s3。  
    ![20210124003446123.png][]

2.2 对于待约项目：

*  对标记为非终结符的边，填写 GOTO 表 。
 *  例如，次栈顶为 0、栈顶为 E 时，语法分析器会转移到 1 状态。因此将 1 填写在第 0 行 E 列的位置上。

![20210124003640413.png][]

2.3 对于接收状态。

*  接受状态时输入序列全部读完，所以剩余输入是 \# 。
 *  即，当前栈顶为 1 状态且剩余输入为 \# 时可以执行接收动作，因此第 1 行 \# 列填入 acc。  
    ![20210124003713716.png][]

2.4 对于规约项。

*  用状态 6 举例。当到达状态 6 时，无论剩余输入字符是什么终结符，都可以进行规约了。
 *  对于状态 6 中项目所描述的 E → aA.，显然可以用产生式 `(1) E → aA`进行规约。因此，ACTION 表中第 6 行的所有列均填入 r1

用上面四点的规则填写整张表，最后得到完成的 LR(0) 分析表如下图所示  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 7][]

## SLR 分析表改造 ##

准备工作部分，与 LR(0) 分析表的构造差不多：

*  同样使用每个项目集的状态编号作为分析器的状态编号，也就同样用作行下标；
 *  同样使用拓广文法产生式作为 0 号产生式。

填表也和 LR(0) 类似，唯一的不同体现在对规约项的处理方法上：

*  如果当前状态有项目 A → α.aβ 和 A → α. ，而次栈顶此时是 α 且读写头读到的是 a，那么当且仅当 a∈FOLLOW(A) 时，我们才会用 A → α 对 α 进行规约。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 8][]

如果构造出来的表的每个入口都不含多重定义（也就是如上图中表格那样的，每个格子里面最多只有一个动作），那么该表就是该文法的 SLR(1) 表，这个文法就是 SLR(1) 文法。使用 SLR(1) 表的分析器叫做一个 SLR(1) 分析器

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221119/7ef5812497524581984a16b31f3d8dbd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: /images/20221119/8c3129d43670439ab72a6eb48433e66c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210124002023418.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210126125109737.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2021012614314095.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210124003202317.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210124003259350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70
[20210124003446123.png]: https://img-blog.csdnimg.cn/20210124003446123.png
[20210124003640413.png]: https://img-blog.csdnimg.cn/20210124003640413.png
[20210124003713716.png]: https://img-blog.csdnimg.cn/20210124003713716.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20210124003836340.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20210124003957542.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70