编译原理教程_6 LR分析法

灰太狼 2023-01-21 11:17 276阅读 0赞

> 文章原稿  
> https://gitee.com/fakerlove/fundamentals-of-compiling

### 文章目录 ###

*  6. LR分析法
 *   *  6.1 简介
     *   *  （1）LR分析法的优缺点
         *  （2）分析表的种类
         *  （3）LR分析器
         *  （4）构造LR分析表
         *  （5）关于LR文法
     *  6.2 LR(0)文法:star:
     *  6.3 规范LR(1)分析法:star:
     *   *   *  LALR(1)分析:star:
     *  6.4 SLR:star:
     *   *  SLR分析法的基本思想
         *  SLR(1)分析表的构造
         *  例题
     *  6.4 LR分析法总结

# 6. LR分析法 #

LR分析：从左到右扫描(L)自底向上进行规约®(是**规范规约**，也即最右推导）是自底向上分析方法的高度概括和集中。（历史 + 展望 + 现状 => 句柄）

## 6.1 简介 ##

### （1）LR分析法的优缺点 ###

① 适合文法类足够大，适用于所有上下文无关文法  
② 分析效率高  
③ 报错及时  
④ 可以自动生成  
⑤ 但手工实现工作量大

### （2）分析表的种类 ###

① SLR分析表（简单LR分析表）  
构造简单，最易实现，**大多数上下文无关文法** 都可以构造出SLR分析表，所以具有较高的实用价值。使用SLR分析表进行语法分析的分析器叫SLR分析器。  
② LR分析表（规范LR分析表）  
适用文法类最大，**所有上下文无关文法** 都能构造出LR分析表，但其分析表体积太大，实用价值不大。  
③ LALR分析表（超前LR分析表）  
这种表**适用的文法类** 及其**实现上难易** 在上面两种之间，在实用上很吸引人。使用LALR分析表进行语法分析的分析器叫LALR分析器。

### （3）LR分析器 ###

**LR分析器的构成**  
LR分析器有三部分: 状态栈、分析表、控制程序。  
![在这里插入图片描述][8710a6c1a529a3eb96e4fb709c790890.png]

![在这里插入图片描述][e042c4d018f8f939acdb127637ddb7f8.png]  
**状态栈**：  
可进一步划分：  
![在这里插入图片描述][e1e4a7fcb7e315e54a5f8b37977f8cb7.png]  
*状态栈*：  
划分后的上部，放置分析器状态和文法符号。  
S0, S1, …, Sm 状态  
S0—初始状态  
Sm —栈顶状态  
栈顶状态概括了从分析开始到该状态的全部分析历史和展望信息。  
*符号串*：  
x1 x2… xm 其中：xi∈Vn∪Vt  
划分后的下部，为从开始状态(S0)到当前状态(Sm)所识别出的 **规范句型的活前缀**。  
**规范句型前缀**：将输入串的剩余部分与其连结起来就构成了规范句型。如： x1 x2 … xm ai… an为规范句型。  
**活前缀**：若分析过程能够保证栈中符号均是规范句型的前缀，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀。  
**规范句型的活前缀**：  
对于句型αβｔ，β表示句柄，如果αβ= u1 u2 … ur ，那么符号串u1 u2 …ui (1≤i≤r)即是句型αβｔ的活前缀。  
*个人理解*：**语法分析没有出错状态下**的规范句型前缀就称为规范句型的活前缀。  
**分析表**：  
由两个矩阵组成，其功能是指示分析器的动作，是移进还是规约，根据不同的文法类要采用不同的构造方法。  
**a. 状态转移表 (GOTO表)**  
一个矩阵：  
行—分析器的状态  
列—文法符号（包括Vn和Vt）  
![在这里插入图片描述][9ab23f6270ab7444b0163d700a4f611d.png]  
GOTO\[Si-1, xi\] = Si  
Si-1—当前状态（栈顶状态）  
xi —新的栈顶符号  
Si —新的栈顶状态（转移状态）  
Si需要满足条件是：  
若x1 x2 …. xi-1 是由 S0 到 Si-1 所识别的规范句型的活前缀，则 x1 x2 …. xi 是由 S0 到 Si 所识别的规范句型的活前缀。  
**实际上**：状态转移函数GOTO是定义了一个以文法符号集为字母表的**有穷自动机**，该自动机识别文法所有规范句型的活前缀。  
![在这里插入图片描述][65d5bba1a98568d69f62f32163f5f698.png]  
**b. 分析动作表（ACTION表）**  
![在这里插入图片描述][a0f6001c5157751b7d489e07f16c945e.png]  
ACTION\[ Si , a \] =分析动作 a∈Vt  
**分析动作**：  
① 移进 (shift)  
ACTION\[ Si , a \] = s  
动作：将 a 推进栈，并设置新的栈顶状态为 Sj 。Sj =GOTO\[ Si, a \]，并将指针指向下一个输入符号。  
② 规约 (reduce)  
ACTION\[ Si, a \] = rd  
d：文法规则编号(d) A→β  
动作：将符号串β(假定长度为n ) 连同状态从栈内弹  
出，再把 A 推进栈，并设置新的栈顶状态为Sj。  
Sj = GOTO\[ Si-n , A \]  
③ 接受(accept)  
ACTION\[ Si , \# \] = accept  
④ 出错 (error)  
ACTION\[ Si , a \] = error a∈Vt  
**控制程序**：执行分析表所规定的动作，对栈进行操作。  
1、 根据栈顶状态和现行输入符号，查分析动作表(ACTION表)，执行由分析表所规定的操作；  
2、并根据GOTO表设置新的栈顶状态（即实现状态转移）。  
由分析过程可以看到：  
(1) 每次规约总是规约当前句型的句柄，是规范规约！  
(2) 分析的每一步栈内符号串均是规范句型的活前缀，且与输入串的剩余部分构成规范句型。

### （4）构造LR分析表 ###

方法：  
（1）根据文法构造识别 **规范句型活前缀** 的有穷自动机DFA：  
①构造DFA：  
DFA 是一个五元式 M = ( S, V, GOTO, S0, Z )  
S：有穷状态集  
在此具体情况下，S = LR(0)项目集规范族。  
**项目集规范族**：其元素是由**项目**所构成的集合。  
V：文法字汇表  
S0：初始状态  
Z：终态集合 Z = S - \{ S0 \}  
GOTO：状态转移函数  
GOTO\[Si , x\]=Sj（Si, Sj∈S Si, Sj为项目集，x∈Vn∪Vt）  
表示当前状态 Si 面临文法符号 x 时，应将状态转移到Sj 。  
**构造方法**：  
一、 确定 S 集合，即LR(0)项目集规范族，同时确定S0  
二、确定状态转移函数GOTO  
②构造LR(0)  
LR(0)是DFA的状态集，其中每个状态又都是项目的集合。  
**项目**：文法 G 的每个产生式（规则）的右部添加一个圆点就构成一个项目。  
例1：  
产生式：A→ X Y Z  
项 目：  
A→ . X Y Z  
A→ X .Y Z  
A→ X Y. Z  
A→ X Y Z .  
例2：  
产生式：A→ε  
项 目： A→.  
**项目的直观意义**：指明在分析过程中的某一时刻的已经规约部分和等待规约部分。  
**构造方法**：

1.  将文法扩充  
    目的：使构造出来的分析表只有一个接受状态，  
    这是为了实现上的方便。  
    方法：修改文法，使识别符号（开始符号）的  
    规则只有一条。  
    ![在这里插入图片描述][831563e03878e7b90c68e085beb02404.png]
2.  根据文法列出所有的项目
3.  将有关项目组合成集合，即DFA中的状态；所有状态构成了LR(0) 项目集规范族。  
    ③ 将有关项目组成项目集，所有项目集构成的集合即为LR(0)。  
    为实现这一步，需先定义：  
    • 项目集闭包 closure  
    ![在这里插入图片描述][9de5a44e92822065c41f4743f4faae18.png]  
    • 状态转移函数GOTO  
    GOTO ( I, X ) = closure (J)  
    I：项目集合  
    X：文法符号，X∈V  
    J：项目集合  
    J = \{ 任何形如A→αX.β的项目| A→α.Xβ∈I \}  
    closure (J)：项目集 J 的闭包仍是项目集合。  
    **直观意义**：  
    规定了识别文法规范句型活前缀的DFA从状态I (项目集)出发，经过X弧所应该到达的状态(项目集) 。  
    **LR (0) 项目集规范族的构造算法**:  
    ![在这里插入图片描述][0294d7bac44c662ca8f3302e63072160.png]  
    ④构造DFA  
    M = ( S , V , GOTO , S0, Z)  
    其中：S = LR(0)  
    V = \{ Vn∪Vt\}  
    GOTO( Im , X) = In  
    S0 = I0  
    Z = S - \{ I0 \}  
    **关于该自动机的说明**  
    ①从 I0 到每一状态（除 I0 以外）的每条路径都识别和接受一个规范句型的活前缀。  
    ②要求状态中每个项目对该状态能识别的活前缀都有效。有效项目定义：若项目A→α.β，对活前缀φα有效，则其条件是存在规范推导：  
    E’=|>φA w =|> φαβw  
    注意：项目中圆点前的符号串称为**活前缀的后缀**。  
    有效项目能预测分析的下一步动作  
    ③有效项目能预测分析的下一步动作  
    例：  
    ![在这里插入图片描述][1ab091ccb6c6b33f5b8d10087baeda31.png]  
    ④DFA中的状态既代表了分析历史又提供了展望信息  
    每条规范句型的活前缀都代表了一个确定的规范规约过程，故有效状态可以代表分析历史。由于状态中的项目都是有效项目，所以提供了下一步可能采取的动作。  
    **确定当前句柄！**：  
    ![在这里插入图片描述][6c5422f8df81a8982bb0a52191d7e693.png]  
    \------------------------------分界线--------------------------------------
4.  **正式构造出LR分析表：**  
    1.GOTO表可由DFA直接求出  
    例：  
    ![在这里插入图片描述][631586c31f986e5e94f2edf13cbeb3a0.png]  
    2.ACTION表由项目集规范族求出  
    根据圆点所在的位置和圆点后是终结符还是非终结符，把项目集规范族中的项目分为以下四种：  
    ![在这里插入图片描述][fe5a646d85f3e6be57d35f07d1387e5a.png]  
    求SLR文法ACTION表的一般方法：  
    假定一个LR(0)规范族中含有如下的一个项目集（状态）  
    I＝\{ X→α·bβ，A→α·，B→β·\}（**规约-规约冲突**）  
    FOLLOW(A)和FOLLOW(B)的交集为空，且不包含b，那  
    么，当状态I面临任何输入符号a 时:
5.  若a = b，则移进；
6.  若a∈FOLLOW(A)，用产生式A→α进行归约；
7.  若a∈FOLLOW(B)，用产生式B→β进行归约；
8.  此外，报错。

### （5）关于LR文法 ###

①对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则我们将把这个文法称为LR文法。  
②并非所有的上下文无关文法都是LR文法。但对于多数程  
序语言来说，一般都可用LR文法描述。

## 6.2 LR(0)文法⭐️ ##

**定义**：假若一个文法G的拓广文法G’的活前缀识别自动机中的每个状态(项目集)不存在下述情况：

1.  既含移进项目又含归约项目
2.  含有多个归约项目  
    则称G是一个LR(0)文法。  
    若：  
    a) 移进和归约项目同时存在。**移进-归约冲突**  
    b) 归约和归约项目同时存在。**归约-归约冲突**  
    **特点**：LR(0)分析器的特点是不需要向前查看任何输入符号就能归约。即当栈顶形成句柄，不管下一个输入符号是什么，都可以立即进行归约而不会发生错误。  
    **LR(0)文法过于简单。即使是定义算术表达式这样的简单文法也不是LR(0)文法，所以没有实用价值！**  
    **移进-规约冲突**  
    移进和归约项目同时存在  
    如：  
    ![在这里插入图片描述][9c6d4fb5600ad4de26050cc5f2ad5c8e.png]  
    **解决方法 — 看FOLLOW集**  
    一般地，假定LR(0)规范族的一个项目集：  
    ![在这里插入图片描述][9c6d4fb5600ad4de26050cc5f2ad5c8e.png]  
    如果集合\{a1, …, am\}, FOLLOW(B1) , … , FOLLOW(Bn)两两不相交（包括不得有两个FOLLOW集合有 \# ），则：  
    ![在这里插入图片描述][4a086850b89c0f33e6a6fb6a8d4f1145.png]  
    说明：  
    • 按上述方法构造出的ACTION与GOTO表如果不含多重入口，则称该文法为SLR(1)文法（向前看了一步）。  
    • 使用SLR表的分析器叫做一个SLR分析器。  
    • 每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的。

## 6.3 规范LR(1)分析法⭐️ ##

若项目集\[ A→α•Bβ \]属于 I 时，则\[ B→• γ \] 也属于I。  
把FIRST(β)作为用产生式归约的搜索符（称为向前搜索符），即用产生式B→γ归约时查看的符号集合（用以代替SLR(1)分析中的FOLLOW集），并把此搜索符号的集合也放在相应项目的后面，这种处理方法即为LR(1)分析方法。  
**LR(1)项目集族的构造**：  
针对初始项目S’→•S, \# 求闭包后再  
用转换函数逐步求出整个文法的LR(1)项目集族。  
1）构造LR(1) 项目集的闭包函数  
a) I 的项目都在closure(I)中；  
b) 若A→α•Bβ, a属于closure(I)，B→γ是文法的产生式，  
β∈V\*，b∈first(βa)，则B→• γ, b也属于closure(I)；  
c) 重复b)直到closure(I)不再扩大为止。  
2) 转换函数的构造  
GOTO(I, X) = closure（J）  
其中：I为LR(1)的项目集，X为一文法符号  
J = \{任何形如A→αX•β, a的项目 | A→α•X β, a属于I \}  
**LR(1)分析表的构造算法**：  
![在这里插入图片描述][90c8efbd23eb91833a115ea2f2270da3.png]  
**LR(1)分析法的特点**：  
• 可适用的文法范围最大。  
• 每个SLR(1)文法都是LR(1)文法，但反之不成立！  
• LR(1)项目集的构造对某些项目集的分裂可能使状态数目剧烈地增长。

#### LALR(1)分析⭐️ ####

• 对LR(1)项目集规范族合并同心集，若合并同心集后不产生新的冲突，则为LALR(1)项目集。  
• 相应的分析方法即为LALR(1)分析法。  
**合并同心集的几点说明**  
• 同心集合并后心仍相同，只是超前搜索符集合为各同心集超前搜索符的和集；  
• 合并同心集后转换函数自动合并；  
• LR(1)文法合并同心集后只可能出现归约-归约冲突，而没有移进-归约冲突；  
• 合并同心集后可能会推迟发现错误的时间，但错误出现的位置仍是准确的。

## 6.4 SLR⭐️ ##

LR(0)文法要求文法的每一个LR(0)项目都不含有冲突的项目，这个条件比较苛刻。对于大多数程序设计语言来说，一般都不能满足LR(0)文法的条件。

例如：

![在这里插入图片描述][58a638b9fdd15476301f2bec9e7765c0.png]

不难看出在状态 I 2 I\_2 I2中既存在规约项目，又存在移进项目，因而这个文法不是LR(0)文法。

为了对语言句子进行确定性的分析，需要解决冲突。可以采用对**含有冲突的项目集**向前查看一个输入符号的办法来解决冲突，这种分析法称为简单的LR分析法，即SLR(1)分析法。

分析构造LR(0)分析表的方法，易看出是分析表出现多重定义的原因在于其中的**规则2**。即对于每一个项目集 I k I\_k Ik中的规约项目 A → α ⋅ A\\rightarrow\{\\alpha·\} A→α⋅，不管当前输入符号是什么，都将`ACTION`表中第k行的各个元素均置为 r j r\_j rj。

因此当一个LR(0)项目集闺范族中存在一个含有冲突的项目集，例如：

$I\_k = \{ X \\to δ ⋅ b B ， A → α ⋅ ， B → r ⋅ \} $  
当遇到符号`b`时，必然会出现多重定义元素。

如要解决则需要向前查看一个输入符号以考察当前所处环境。对规约项目 A → α ⋅ 和 B → r ⋅ , A \\rightarrow\{\\alpha·\}和B\\rightarrow\{r·\}, A→α⋅和B→r⋅,只需要考察当讲句柄 α \\alpha α或`r`规约为`A`或`B`时，直接跟在`A`或`B`后面的终结符集合即`FOLLOW(A)`和`FOLLOW(B)`互不相交且不包含**移进符号b**，即满足：  
 F O L L O W ( A ) ∩ F O L L O W ( B ) = ∅ FOLLOW(A) \\cap FOLLOW(B) = \\varnothing FOLLOW(A)∩FOLLOW(B)=∅

F O L L O W ( A ) ∩ \{ b \} = ∅ FOLLOW(A) \\cap \\\{b\\\} = \\varnothing FOLLOW(A)∩\{ b\}=∅

F O L L O W ( B ) ∩ \{ b \} = ∅ FOLLOW(B) \\cap \\\{b\\\} = \\varnothing FOLLOW(B)∩\{ b\}=∅

那么，当状态`k`面临输入符号`a`是，可按下列规则解决冲突：

1.  若`a=b`则移进
2.  若 a ∈ F O L L O W ( A ) a\\in FOLLOW(A) a∈FOLLOW(A)，则用规则 A → α A \\rightarrow\{\\alpha\} A→α进行规约
3.  若 a ∈ F O L L O W ( B ) a\\in FOLLOW(B) a∈FOLLOW(B)，则用规则 B → r B \\rightarrow\{r\} B→r进行规约
4.  此外都报错

### SLR分析法的基本思想 ###

![在这里插入图片描述][41540acef5d16dd535707fcd713a3af9.png]

**这种用来解决分析动作冲突的方法称为SLR(1)方法。如果对于一个文法的某些LR(0)项目集或LR(0)分析表中所含有的动作冲突都能用SLR(1)方法解决，则称这个文法是SLR(1)文法**。

### SLR(1)分析表的构造 ###

**SLR(1)分析表的构造与LR(0)分析表的构造基本相同。**（LR(0)分析表的构造方法在[这里][Link 1]）

仅对LR(0)分析表构造方法的第二步进行如下修改：

若规约项目 A → α ⋅ A\\rightarrow\{\\alpha·\} A→α⋅属于 I k I\_k Ik，则对任何终结符 α ∈ F O L L O W ( A ) \\alpha \\in FOLLOW(A) α∈FOLLOW(A)置 A C T I O N \[ k , a \] = r j ACTION\[k,a\] = r\_j ACTION\[k,a\]=rj，其中 A → α A\\rightarrow\{\\alpha\} A→α为文法的第j条的规则。

### 例题 ###

由于LR(0)的能力实在是太弱了。例如：

I = \{ X=>α·bβ，

A=>α·，

B=>α· \}

这时候就存在两个冲突。

1、移进和规约的冲突；

2、规约和规约的冲突。

**SLR（1）就是为了解决冲突而设计的，解决冲突的方法就是向后多看一个字符，这就是SLR（1）。**

**简而言之就是为每个非终结符，计算出它们的follow集。从而可以解决移进与规约、规约与规约的冲突了。**

**SLR（1）所说的多看一个字符在构造分析表的时候就根据follow集已经构造好了，分析程序和LR(0)是一样的，分析表不同。**

具体实现如下：

拓广文法 G’\[S’\]:

(0) S’→S

(1) S→ABC

(2) A→Aa

(3) A→a

(4) B→Bb

(5) B→b

(6) C→Cc

(7) C→c

1、计算初始状态的项目集

Q0=CLOSURE(\{S’→•S \})=\{ S’→•S , S→•ABC, A→•Aa, A→•a \};

2、计算每个状态的项目集

Q1=GO(Q0,a)=CLOSURE(\{A→a •\})=\{ A→a• \};

Q2=GO(Q0,S)=CLOSURE(\{S’→S •\})=\{ S’→S • \};

Q3=GO(Q0,A) = CLOSURE(\{S→A•BC, A→A•a\}) = \{S→A•BC, A→A•a, B→•Bb, B→•b\}; Q4=GO(Q3,a)=CLOSURE(\{A→Aa• \})=\{ A→Aa• \};

Q5=GO(Q3,b)=CLOSURE(\{B→b• \})=\{ B→b•\};

Q6=GO(Q3,B)=CLOSURE(\{S→AB•C, B→B•b \}) =\{ S→AB•C, B→B•b , C→•Cc , C→•c \}; Q7=GO(Q6,b)=CLOSURE(\{B→Bb •\})=\{ B→Bb •\};

Q8=GO(Q6,c)=CLOSURE(\{C→c •\})=\{ C→c •\};

Q9=GO(Q6,C)=CLOSURE(\{S→ABC•, C→C•c \})=\{ S→ABC•, C→C•c \}; Q10=GO(Q9,c)=CLOSURE(\{C→Cc• \})=\{ C→Cc•\};

3、构造识别可归约前缀的 DFA

![img][]

4、计算文法的 FIRST 和 FOLLOW 集合

<table> 
 <thead> 
  <tr> 
   <th>非终结符</th> 
   <th>FIRST</th> 
   <th>FOLLOW</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>S</td> 
   <td>a</td> 
   <td>#</td> 
  </tr> 
  <tr> 
   <td>A</td> 
   <td>a</td> 
   <td>a,b</td> 
  </tr> 
  <tr> 
   <td>B</td> 
   <td>b</td> 
   <td>b,c</td> 
  </tr> 
  <tr> 
   <td>C</td> 
   <td>c</td> 
   <td>c,#</td> 
  </tr> 
 </tbody> 
</table>

状态节点 Q9= \{ S→ABC•, C→C•c \}中存在存在移进-规约冲突。

\{b\}∩FOLLOW(S) =\{b\}∩\{\#\}=Φ，因此文法是 SLR(1)文法。

5、构造 SLR(1)分析表

实验程序：

#include<bits/stdc++.h>
    #define ROW 12
    #define COLUMN 9
    using namespace std;
    //产生式
    string products[8][2]={
    {"S'","S"},
    {"S","ABC"},
    {"A","Aa"},
    {"A","a"},
    {"B","Bb"},
    {"B","b"},
    {"C","Cc"},
    {"C","c"}
    };
    //SLR（1）分析表
    string actiontable[ROW][COLUMN]={
    {"","a","b","c","#","S","A","B","C"},
    {"0","s1","","","","2","3","",""},
    {"1","r3","r3","","","","","",""},
    {"2","","","","acc","","","",""},
    {"3","s4","s5","","","","","6",""},
    {"4","r2","r2","","","","","",""},
    {"5","","r5","r5","","","","",""},
    {"6","","s7","s8","","","","","9"},
    {"7","","r4","r4","","","","",""},
    {"8","","","r7","r7","","","",""},
    {"9","","","s10","r1","","","",""},
    {"10","","","r6","r6","","","",""}
    };
    stack<int> sstatus; //状态栈
    stack<char> schar; //符号栈
    struct Node{
        char type;
        int num;
    };
    //打印步骤
    void print_step(int times){
        stack<char> tmp2;
        cout<<times<<setw(4);
        while(!schar.empty()){
            char t=schar.top();
            schar.pop();
            tmp2.push(t);
            cout<<t;
        }
        while(!tmp2.empty()){
            int t=tmp2.top();
            tmp2.pop();
            schar.push(t);
        }
    }
    //查表
    Node Action_Goto_Table(int status,char a){
        int row=status+1;
        string tmp;
        for(int j=1;j<COLUMN;j++){
            if(a==actiontable[0][j][0]){
                tmp=actiontable[row][j];
            }
        }
        Node ans;
        if(tmp[0]>='0'&&tmp[0]<='9'){
            int val=0;
            for(int i=0;i<tmp.length();i++){
                val=val*10+(tmp[i]-'0');
            }
            ans.num=val;
            ans.type=' ';
        }else if(tmp[0]=='s'){
            int val=0;
            for(int i=1;i<tmp.length();i++){
                val=val*10+(tmp[i]-'0');
            }
            ans.type='s';
            ans.num=val;
        }else if(tmp[0]=='r'){
            int val=0;
            for(int i=1;i<tmp.length();i++){
                val=val*10+(tmp[i]-'0');
            }
            ans.type='r';
            ans.num=val;
        }else if(tmp[0]=='a'){
            ans.type='a';
        }else{
            ans.type=' ';
        }
        return ans;
    }
    //SLR(1)分析算法
    bool SLR1(string input){
        while(!sstatus.empty()){
            sstatus.pop();
        }
        while(!schar.empty()){
            schar.pop();
        }
        int times=0;
        bool flag=true;
        int st=0;
        sstatus.push(st);
        schar.push('#');
        int i=0;
        char a=input[i];
        while(true){
            Node action=Action_Goto_Table(st,a);
            if(action.type=='s'){
                st=action.num;
                sstatus.push(st);
                schar.push(a);
                a=input[++i];
                print_step(++times);
                cout<<setw(10)<<'s'<<st<<endl;
    
            }else if(action.type=='r'){
                int n=action.num;
                string ls=products[n][0];
                string rs=products[n][1];
                for(int j=0;j<rs.length();j++){
                    sstatus.pop();
                    schar.pop();
                }
                schar.push(ls[0]);
                st=sstatus.top();
                action =Action_Goto_Table(st,ls[0]);
                st=action.num;
                sstatus.push(st);
                print_step(++times);
                cout<<setw(10)<<'r'<<" "<<ls<<"->"<<rs<<endl;
    
            }else if(action.type=='a'){
                flag=true;
                break;
            }else{
                flag=false;
                break;
            }
        }
        return flag;
    }
    int main(){
        string input;
        while(cin>>input){
            if(SLR1(input)){
                cout<<"syntax correct"<<endl;
            }else{
                cout<<"syntax error"<<endl;
            }
        }
        return 0;
    }

## 6.4 LR分析法总结 ##

![在这里插入图片描述][ab9459eb6eec3241a64e66910ed95d39.png]

关系

![img][img 1]

[8710a6c1a529a3eb96e4fb709c790890.png]: /images/20221020/22f5196e9df4408fb5c2a26a9c500d11.png
[e042c4d018f8f939acdb127637ddb7f8.png]: /images/20221020/c77f02ddcf594798847506d5f63f1ecb.png
[e1e4a7fcb7e315e54a5f8b37977f8cb7.png]: /images/20221020/53ecf145bc814baba3a2e276a039cb95.png
[9ab23f6270ab7444b0163d700a4f611d.png]: /images/20221020/bcff5e55a1324814bec0cc186677e17b.png
[65d5bba1a98568d69f62f32163f5f698.png]: /images/20221020/6c9eaa40caed462798a269f7cbb6fc37.png
[a0f6001c5157751b7d489e07f16c945e.png]: /images/20221020/2936e7b84c3b4685a2eabad1f2b3bceb.png
[831563e03878e7b90c68e085beb02404.png]: /images/20221020/fcc6978a1d3f40a489e8d30b5a79385c.png
[9de5a44e92822065c41f4743f4faae18.png]: /images/20221020/1572e4ab78e84a4cace4983d9af3cff9.png
[0294d7bac44c662ca8f3302e63072160.png]: /images/20221020/9854db7405b046e89ddba6c2aba31e74.png
[1ab091ccb6c6b33f5b8d10087baeda31.png]: /images/20221020/a22f50eaa9f840c0a0e6091e5f341183.png
[6c5422f8df81a8982bb0a52191d7e693.png]: /images/20221020/ec313f30ced8432a88eb04ca6ff8a64c.png
[631586c31f986e5e94f2edf13cbeb3a0.png]: /images/20221020/c44598f2c67d419491c0dfb7d294e8a7.png
[fe5a646d85f3e6be57d35f07d1387e5a.png]: /images/20221020/7ac26b7ea4734277bd5da179f893df6d.png
[9c6d4fb5600ad4de26050cc5f2ad5c8e.png]: /images/20221020/c0696a8fdaa0449496b1221d3c6b80bc.png
[4a086850b89c0f33e6a6fb6a8d4f1145.png]: /images/20221020/69c0e4667f034e6eaa63498405a9ccef.png
[90c8efbd23eb91833a115ea2f2270da3.png]: /images/20221020/24d8fee1dceb4bc0964ce389611a171d.png
[58a638b9fdd15476301f2bec9e7765c0.png]: /images/20221020/8a387bd6cf2a445c8c4251227833bbd8.png
[41540acef5d16dd535707fcd713a3af9.png]: /images/20221020/962f08f38a8e4b01bbd445e3f9ec6596.png
[Link 1]: https://blog.csdn.net/hjc256/article/details/90572695
[img]: /images/20221020/de4d0e92bb224a49bb2b0334f75ea784.png
[ab9459eb6eec3241a64e66910ed95d39.png]: /images/20221020/651df41d3dc6462aa953c87e1f528be1.png
[img 1]: /images/20221020/158a431caa524981a063c5a613a15a0f.png