编译原理（六）

03 Jun 2020 2201字 8分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

考虑以下文法

E→E+TE→TT→TFT→FF→F⋆F→aF→bE\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
EE a,ba,b $,+\text{\textdollar},+
TT a,ba,b $,+,a,b\text{\textdollar},+,a,b
FF a,ba,b $,+,a,b,⋆\text{\textdollar},+,a,b,\mathop{\star}

构造识别这一文法所有活前缀（viable prefixes）的 LR(0) 自动机（参照课本 4.6.2 节图 4.31）

使用增广文法增加新的开始符号 E’E’ 和产生式 E’→EE’\to E。

E
T
F
a
b
$
+
a
b
F
*
F
a
b
T
*
a
b
F
I0
E'→·E
E→·E+T
E→·T
T→·TF
T→·F
F→·F*
F→·a
F→·b
I1
E'→·E
E→E·+T
I2
E→T·
T→T·F
F→·F*
F→·a
F→·b
I3
T→F·
F→F·*
I4
F→a·
I5
F→b·
accept
I6
E→E+·T
T→T·F
F→·F*
F→·a
F→·b
I7
T→TF·
I8
F→F*·
I9
E→E+T·
T→T·F
F→·F*
F→·a
F→·b
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 ACTIONaa ACTIONbb 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⋆a+ab\mathop{\star} 的过程（参照课本 4.6.4 节图 4.38）

STACK SYMBOLS INPUT ACTION
0   a+ab⋆$a+ab\mathop{\star}\text{\textdollar} shift
04 aa +ab⋆$+ab\mathop{\star}\text{\textdollar} reduce
03 FF +ab⋆$+ab\mathop{\star}\text{\textdollar} reduce
02 TT +ab⋆$+ab\mathop{\star}\text{\textdollar} reduce
01 EE +ab⋆$+ab\mathop{\star}\text{\textdollar} shift
016 E+E+ ab⋆$ab\mathop{\star}\text{\textdollar} shift
0164 E+aE+a b⋆$b\mathop{\star}\text{\textdollar} reduce
0163 E+FE+F b⋆$b\mathop{\star}\text{\textdollar} reduce
0169 E+TE+T b⋆$b\mathop{\star}\text{\textdollar} shift
01695 E+TbE+Tb ⋆$\mathop{\star}\text{\textdollar} reduce
01697 E+TFE+TF ⋆$\mathop{\star}\text{\textdollar} shift
016978 E+TF⋆E+TF\mathop{\star} $\text{\textdollar} reduce
01697 E+TFE+TF $\text{\textdollar} reduce
0169 E+TE+T $\text{\textdollar} reduce
01 EE $\text{\textdollar} accept