## 5.10. LR语法分析

LR语法分析本质上为从左到右自底向上算法，从左到右一个一个读入字符，然后按照产生式进行规约，直到规约出文法开始的符号。

## 5.10.1. LR算法

LR语法分析最重要的就是移入和规约。下面举一个例子来理解移入和规约。

graph LR
number("number(1)")

graph TD
pro("PRODUCTION") --> number("number(1)")

graph TD
pro("PRODUCTION") --> number("number(1)")
+

graph TD
pro("PRODUCTION") --> number("number(1)")
+
number2("number(2)")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
number3("number(3)")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")
left("(")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")
left("(")
n4("number(4)")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")
left("(")
pro4(PRODUCTION) --> n4("number(4)")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")
left("(")
pro4(PRODUCTION) --> n4("number(4)")
add2(+)

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")
left("(")
pro4(PRODUCTION) --> n4("number(4)")
n5("number(5)")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")
left("(")
pro4(PRODUCTION) --> n4("number(4)")
pro5(PRODUCTION) -->n5("number(5)")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")
left("(")
pro4(PRODUCTION) --> n4("number(4)")
pro5(PRODUCTION) -->n5("number(5)")
proSum2(PRODUCTION) --> pro4 & add2 & pro5

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")
left("(")
pro4(PRODUCTION) --> n4("number(4)")
pro5(PRODUCTION) -->n5("number(5)")
proSum2(PRODUCTION) --> pro4 & add2 & pro5
right(")")

graph TD
pro1("PRODUCTION") --> number("number(1)")
+
pro2("PRODUCTION") --> number2("number(2)")
*
pro3("PRODUCTION") --> number3("number(3)")
proMum(PRODUCTION) --> pro2 & pro3 & *
mul2("*")
left("(")
pro4(PRODUCTION) --> n4("number(4)")
pro5(PRODUCTION) -->n5("number(5)")
proSum2(PRODUCTION) --> pro4 & add2 & pro5
right(")")
proLeftRight(PRODUCTION) --> left & proSum2 & right
pro2LeftRight --> proLeftRight & proMum & mul2

1 s2
2
3
4 s6
5 s8
6 s7
7
8 s10
9 s6
10

[栈底,1,5,8,9] [栈底,PRODUCTION,+,MUL]
11 从状态栈顶读取状态

## 5.10.6 SLR算法伪代码

1. 构造文法的规范LR(0) 项集簇 C = $${I_0, I_1, ... I_n}$$.
2. 对于状态i，   ① 如果[A->α·aβ]在状态中，a为终结符且GOTO(i,a)=j， 则ACTION[i,a]为: "移入j"   ② 如果[A->α·]在状态中且A不为开始符号，则对于所有的FOLLOW(A)的字符a，将ACTION[i,a]设为: "规约A->α"   ③ 如果[A->α·]在状态中且A为开始符号，则将ACTION[i,$]设为: "接受" 3. 对于状态i，如果A为非终结符且 GOTO(i,A)=j 则GOTO[i,A]=j 4. 剩下的地方就是报错 5. 起点是[S'->·S] ## 5.10.7 冲突与规约 由于SLR文法很简单，他能识别的文法其实很少很少，大部分文法在他这里都会冲突，也就是一张SLR表中，一个状态遇到了同一个符号时，表要求进行多种操作。 但是SLR文法也容易实现，所以在笔者的compiler项目中，很多地方都直接执行了SLR算法 所以我们还需要对文法进行进一步增广，后面提出LR1算法。 ## 5.10.8 LR1 增广文法 LR1在SLR的基础上继续进行增广，继续引入了end集合，下面继续回忆一下文法和项集 graph TD I1("状态1<br/>PRODUCTION -> · SUM<br/>PRODUCTION -> · MUL<br/>SUM -> · PRODUCTION + MUL<br/>MUL -> · MUL * number<br/>MUL -> · number") I2("状态2<br/>MUL -> number ·") I3("状态3<br/>PRODUCTION -> SUM · ") I4("状态4<br/>PRODUCTION -> MUL · <br/>MUL -> MUL · * number") I5("状态5<br/>SUM -> PRODUCTION · + MUL") I6("状态6<br/>MUL -> MUL * · number") I7("状态7<br/>MUL -> MUL * number · ") I8("状态8<br/>SUM -> PRODUCTION + · MUL<br/>MUL -> · MUL * number<br/>MUL -> · number") I9("状态9<br/>SUM -> PRODUCTION + MUL ·<br/>MUL -> MUL · * number") I10("状态10<br/>MUL -> number ·") I1 -->|number| I2 I1 -->|SUM| I3 I1 -->|MUL| I4 I1 -->|PODUCTION| I5 I4 -->|*| I6 I6 -->|number| I7 I5 -->|+| I8 I8 -->|MUL| I9 I8 -->|number| I10 I9 -->|*| I6 关注状态1· 对于其中的PRODUCTION -> · SUM，我们发现，其后紧跟着的因该是$

SUM -> · PRODUCTION + MUL得出，PRODUCTION -> · SUM后可为+

graph TD
I1("状态1<br/>PRODUCTION -> · SUM, $/+<br/>PRODUCTION -> · MUL,$/+<br/>SUM -> · PRODUCTION + MUL, $/+<br/>MUL -> · MUL * number,$/+<br/>MUL -> · number, *")
I2("状态2<br/>MUL -> number · , *")
I3("状态3<br/>PRODUCTION -> SUM · , $/+") I4("状态4<br/>PRODUCTION -> MUL · ,$/+<br/>MUL -> MUL · * number, $/+") I5("状态5<br/>SUM -> PRODUCTION · + MUL,$/+")
I6("状态6<br/>MUL -> MUL * · number, $/+") I7("状态7<br/>MUL -> MUL * number ·,$/+")
I8("状态8<br/>SUM -> PRODUCTION + · MUL, $/+<br/>MUL -> · MUL * number,$/+<br/>MUL -> · number, *")
I9("状态9<br/>SUM -> PRODUCTION + MUL ·, $/+<br/>MUL -> MUL · * number,$/+")
I10("状态10<br/>MUL -> number ·, *")
I1 -->|number| I2
I1 -->|SUM| I3
I1 -->|MUL| I4
I1 -->|PODUCTION| I5
I4 -->|*| I6
I6 -->|number| I7
I5 -->|+| I8
I8 -->|MUL| I9
I8 -->|number| I10
I9 -->|*| I6

## 5.10.9 LR1表生成算法伪代码

1. 构造文法的规范LR(0) 项集簇 C = $${I_0, I_1, ... I_n}$$.
2. 对于状态i，   ① 如果[A->α·aβ]在状态中，a为终结符且GOTO(i,a)=j， 则ACTION[i,a]为: "移入j"   ② 如果[A->α·]在状态中且A不为开始符号，则对于此时的增广文法中的end集的字符a，将ACTION[i,a]设为: "规约A->α"   ③ 如果[A->α·]在状态中且A为开始符号，则将ACTION[i,\$]设为: "接受"
3. 对于状态i，如果A为非终结符且 GOTO(i,A)=j 则GOTO[i,A]=j
4. 剩下的地方就是报错 5. 起点是[S'->·S]

## 5.10.12 总结

-----------------------本文结束感谢您的阅读-----------------------