编译原理(六) wu-kan

考虑以下文法

\[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 集

 FIRSTFOLLOW
$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)

STATEACTION$a$ACTION$b$ACTION$+$ACTION$\mathop{\star}$ACTION$\text{\textdollar}$GOTO EGOTO TGOTO F
0s4s5   123
1  s6 accept   
2s4s5r2 r2  7
3r4r4r4s8r4   
4r6r6r6r6r6   
5r7r7r7r7r7   
6s4s5   93 
7r3r3r3s8r3   
8r5r5r5r5r5   
9s4s5r1 r1  7

给出 SLR 分析器识别输入串 $a+ab\mathop{\star}$ 的过程(参照课本 4.6.4 节图 4.38)

STACKSYMBOLSINPUTACTION
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