Menu
    1. 写出每个非终端符号的 FIRST 集和 FOLLOW 集
    2. 构造识别这一文法所有活前缀（viable prefixes）的 LR(0) 自动机（参照课本 4.6.2 节图 4.31）
    3. 构造这一文法的 SLR 分析表（参照课本 4.6.3 节图 4.37）
    4. 给出 SLR 分析器识别输入串 $a+ab\mathop{\star}$ 的过程（参照课本 4.6.4 节图 4.38）

    编译原理（六）

    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...