post on
03 Jun 2020
about
2201words
require
8min
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 |
Loading comments...