编译原理5、6

5.1

---

(1)
S−>(L)|a
L−>SL′
L′−>,SL′|ℇ
First( S ) = {(,a}
First( L ) = {(,a}
First( L′ ) = {,}
Follow( S ) = {,,)}
Follow( L ) = {)}
Follow( L′ ) = {)}

(2)The parsing table:

-	a	,	(	)	$
S	S−>a		S−>(L)
L	L−>SL′		L−>SL′
L′		L′−>,SL′		L′−>ϵ

(3)

Step	Stack	Input	Reference	Action	Output
0	$S	(a,(a,a))$	[S,(]=S−>(L)	derive	S−>(L)
1	$)L(	(a,(a,a))$		match
2	$)L	a,(a,a))$	[L,a]=L−>SL′	derive	L−>SL′
3	$)L′S	a,(a,a))$	[S,a]=S−>a	derive	S−>a
4	$)L′a	a,(a,a))$		match
5	$)L′	,(a,a))$	[L′,,]=L′−>,SL′	derive	L′−>,SL′
6	$)L′S,	,(a,a))$		match
7	$)L′S	(a,a))$	[S,(]=S−>(L)	derive	S−>(L)
8	$)L′)L(	(a,a))$		match
9	$)L′)L	a,a))$	[L,a]=L−>SL′	derive	L−>SL′
10	$)L′)L′S	a,a))$	[S,a]=S−>a	derive	S−>a
11	$)L′)L′a	a,a))$		match
12	$)L′)L′	,a))$	[L′,,]=L′−>,SL′	derive	L′−>,SL′
13	$)L′)L′S,	,a))$		match
14	$)L′)L′S	a))$	[S,a]=S−>a	derive	S−>a
15	$)L′)L′a	a))$		match
16	$)L′)L′	))$	[L′,)]=L−>ϵ	derive	L′−>ϵ
17	$)L′)	))$		match
18	$)L′	)$	[L′,)]=L−>ϵ	derive	L′−>ϵ
19	$)	)$		match
20	$	$		accept

5.2

---

(1)
A−>BA′
A′−>C|ϵ
B−>aB|ϵ
C−>ab
First( A ) = First( B ) = First( A′ )= {a,ϵ}
First( C ) = {a}
Follow( A )= {$}
Follow( A′ )= {$}
Follow( B )= {a,$}
Follow( C )= {$}

(2)The parsing table:

-	a	$
A	A−>BA′	A−>ϵ
A′	A′−>C	A′−>ϵ
B	B−>aB | B−>ϵ	B−>ϵ
C	C−>ab

Exist more than one element in [A′,a] , so this is not a LL(1) grammar.

(3)When lookahead == 2:
First( A ) = {aa,ab,ϵ}
First( B ) = {aa,ϵ}
First( A′ )= {ab,ϵ}
First( C ) = {ab}
Follow( A )= {$}
Follow( A′ )= {$}
Follow( B )= {ab,$}
Follow( C )= {$}
The parsing table:

-	aa	ab	$
A	A−>BA′	A−>BA′	A−>ϵ
A′		A′−>C	A′−>ϵ
B	B−>aB	B−>ϵ	B−>ϵ
C		C−>ab

6.1

---

Step	Stack	Input	Reference	Action	Output
0	$	(a,(a,a))$	$<(	shift
1	$(	a,(a,a))$	(<a	shift
2	$(a	,(a,a))$	a>,	reduce	S−>a
3	$(S	,(a,a))$	(<,	shift
4	$(S,	(a,a))$	,<(	shift
5	$(S,(	a,a))$	(<a	shift
6	$(S,(a	,a))$	a>,	reduce	S−>a
7	$(S,(S	,a))$	(<,	shift
8	$(S,(S,	a))$	,<a	shift
9	$(S,(S,a	))$	a>)	reduce	S−>a
10	$(S,(S,S	))$	,>)	reduce	L−>S
11	$(S,(S,L	))$	,>)	reduce	L−>L,S
12	$(S,(L	))$	(=)	shift
13	$(S,(L)	)$	)>)	reduce	S−>(L)
14	$(S,S	)$	,>)	reduce	L−>S
15	$(S,L	)$	,>)	reduce	L−>L,S
16	$(L	)$	(=)	shift
17	$(L)	$	)>$	reduce	S−>(L)
18	$)S	$		accept