03 Jun 2020 2131字 8分 次 编译原理
如果这篇博客帮助到你，可以请我喝一杯咖啡~
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