CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
考虑以下文法
\[E\to E+T\\ E\to T\\ T\to TF\\ T\to F\\ F\to F\mathop{\star}\\ F\to a\\ F\to b\\\]写出每个非终端符号的 FIRST 集和 FOLLOW 集
| FIRST | FOLLOW | |
|---|---|---|
| $E$ | $a,b$ | $\text{\textdollar},+$ |
| $T$ | $a,b$ | $\text{\textdollar},+,a,b$ |
| $F$ | $a,b$ | $\text{\textdollar},+,a,b,\mathop{\star}$ |
构造识别这一文法所有活前缀（viable prefixes）的 LR(0) 自动机（参照课本 4.6.2 节图 4.31）
使用增广文法增加新的开始符号 $E’$ 和产生式 $E’\to E$。
flowchart TB
I0--E-->I1
I0--T-->I2
I0--F-->I3
I0--a-->I4
I0--b-->I5
I1--$-->AC
I1--+-->I6
I2--a-->I4
I2--b-->I5
I2--F-->I7
I3--*-->I8
I6--F-->I3
I6--a-->I4
I6--b-->I5
I6--T-->I9
I7--*-->I8
I9--a-->I4
I9--b-->I5
I9--F-->I7
AC["accept"]
I0["
I0
E'#rarr;#middot;E
E#rarr;#middot;E+T
E#rarr;#middot;T
T#rarr;#middot;TF
T#rarr;#middot;F
F#rarr;#middot;F*
F#rarr;#middot;a
F#rarr;#middot;b
"]
I1["
I1
E'#rarr;#middot;E
E#rarr;E#middot;+T
"]
I2["
I2
E#rarr;T#middot;
T#rarr;T#middot;F
F#rarr;#middot;F*
F#rarr;#middot;a
F#rarr;#middot;b
"]
I3["
I3
T#rarr;F#middot;
F#rarr;F#middot;*
"]
I4["
I4
F#rarr;a#middot;
"]
I5["
I5
F#rarr;b#middot;
"]
I6["
I6
E#rarr;E+#middot;T
T#rarr;T#middot;F
F#rarr;#middot;F*
F#rarr;#middot;a
F#rarr;#middot;b
"]
I7["
I7
T#rarr;TF#middot;
"]
I8["
I8
F#rarr;F*#middot;
"]
I9["
I9
E#rarr;E+T#middot;
T#rarr;T#middot;F
F#rarr;#middot;F*
F#rarr;#middot;a
F#rarr;#middot;b
"]
构造这一文法的 SLR 分析表（参照课本 4.6.3 节图 4.37）
| STATE | ACTION$a$ | ACTION$b$ | ACTION$+$ | ACTION$\mathop{\star}$ | ACTION$\text{\textdollar}$ | GOTO E | GOTO T | GOTO F |
|---|---|---|---|---|---|---|---|---|
| 0 | s4 | s5 | 1 | 2 | 3 | |||
| 1 | s6 | accept | ||||||
| 2 | s4 | s5 | r2 | r2 | 7 | |||
| 3 | r4 | r4 | r4 | s8 | r4 | |||
| 4 | r6 | r6 | r6 | r6 | r6 | |||
| 5 | r7 | r7 | r7 | r7 | r7 | |||
| 6 | s4 | s5 | 9 | 3 | ||||
| 7 | r3 | r3 | r3 | s8 | r3 | |||
| 8 | r5 | r5 | r5 | r5 | r5 | |||
| 9 | s4 | s5 | r1 | r1 | 7 |
给出 SLR 分析器识别输入串 $a+ab\mathop{\star}$ 的过程（参照课本 4.6.4 节图 4.38）
| STACK | SYMBOLS | INPUT | ACTION |
|---|---|---|---|
| 0 | $a+ab\mathop{\star}\text{\textdollar}$ | shift | |
| 04 | $a$ | $+ab\mathop{\star}\text{\textdollar}$ | reduce |
| 03 | $F$ | $+ab\mathop{\star}\text{\textdollar}$ | reduce |
| 02 | $T$ | $+ab\mathop{\star}\text{\textdollar}$ | reduce |
| 01 | $E$ | $+ab\mathop{\star}\text{\textdollar}$ | shift |
| 016 | $E+$ | $ab\mathop{\star}\text{\textdollar}$ | shift |
| 0164 | $E+a$ | $b\mathop{\star}\text{\textdollar}$ | reduce |
| 0163 | $E+F$ | $b\mathop{\star}\text{\textdollar}$ | reduce |
| 0169 | $E+T$ | $b\mathop{\star}\text{\textdollar}$ | shift |
| 01695 | $E+Tb$ | $\mathop{\star}\text{\textdollar}$ | reduce |
| 01697 | $E+TF$ | $\mathop{\star}\text{\textdollar}$ | shift |
| 016978 | $E+TF\mathop{\star}$ | $\text{\textdollar}$ | reduce |
| 01697 | $E+TF$ | $\text{\textdollar}$ | reduce |
| 0169 | $E+T$ | $\text{\textdollar}$ | reduce |
| 01 | $E$ | $\text{\textdollar}$ | accept |