紫龙书部分答案

4.6.5

LR(0) items in initial:

S’ -> S

S -> AaAb|BbBa

A -> e

B ->e

So , I :

S’ ->·S

S -> ·AaAb

S -> ·BbBa

A ->·

B ->·

FOLLOW(A) = FOLLOW(B) = {a,b}

Therefore, when input ‘a’ we may get a conflict since FOLLOW(A) = FOLLOW(B).

This grammar is not SLR(1)

FIRST(S) = {a,b}

FIRST(A) = F IRST(B) = {e}

FOLLOW(S) = {$}

FOLLOW(A) = FOLLOW(B)={a,b}

The parse table is

	a	b	$
S	S -> AaAb	S ->BbBa
A	A -> e	A -> e
B	B -> e	B -> e

There are no conflicts , so the grammar is LL(1).

4.6.6

FIRST(S) = {a}

FIRST(A) = {a}

FOLLOW(S) = {$,a}

FOLLOW(A) = {$,a}

The parse table is :

a

$

S

S – SA

S -> A

A

A -> a

There is a conflict , so it is not LL(1). Then

I :

S’ -> ·S

S -> ·SA

S -> ·A

A -> ·a

I :

S’ -> ·S

S -> S·A

A -> ·a

I :

S -> A·

I :

A -> a·

I :

S -> SA·

So the parse table is

state	action	goto
	a	$	S	A
0	S3		1	2
1	S3	acc		4
2	Y2	R2
3	Y3	R3
4	R1	R1

There are no conflicts , so the grammar is SLR(1).

4.7.1

(a)LR

I :

S’ -> ·S , $

S -> ·SS+ , $/a

S -> ·SS* , $/a

S -> ·a , $/a

I :

S’ -> S· , $

S -> S·S+ , $/a

S -> S·S* , $/a

S -> ·SS+ , +/*/a

S -> ·SS* , +/*/a

S -> ·a , +/*/a

I :

S -> a· , $/+/*/a

I :

S ->S S·, $/a

S -> SS·+ , $/a

S -> SS·* , $/a

S -> S·S+ , +/*/a

S -> S·S* , +/*/a

S -> ·SS+ , +/*/a

S -> ·SS* , +/*/a

S -> ·a , +/*/a

I :

S -> a· , +/*/a

I :

S -> SS·+ , +/*/a

S -> SS·* , +/*/a

S -> S·S+ , +/*/a

S -> S·S* , +/*/a

S -> ·SS+ , +/*/a

S -> ·SS* , +/*/a

S -> ·a , +/*/a

I :

S -> SS+· , $/a

I :

S -> SS*· , $/a

I :

S -> SS+· , +/*/a

I :

S -> SS*· , +/*/a

(b)LALR

I :

S’ -> ·S , $

S -> ·SS+ , $/a

S -> ·SS* , $/a

S -> ·a , $/a

I :

S’ -> S· , $

S -> S·S+ , $/a

S -> S·S* , $/a

S -> ·SS+ , +/*/a

S -> ·SS* , +/*/a

S -> ·a , +/*/a

I :

S -> a· , $/+/*/a

I :

S -> SS·+ , $/+/*/a

S -> SS·* , $/+/*/a

S -> S·S+ , +/*/a

S -> S·S* , +/*/a

S -> ·SS+ , +/*/a

S -> ·SS* , +/*/a

S -> ·a , +/*/a

I :

S -> SS+· , $/+/*/a

I :

S -> SS*· , $/+/*/a