编译原理作业7

由于格式的问题，dollar用$\psi$代替。

Exercise 7.1

Consider the grammar

$$S → ( S R | a\\ R → , S R | )$$

Try to construct an SLR(1) parsing table for the grammar, and see if there are conflicts in the parsing table.

对文法做扩展如下：

$(0)S' → S\\ (1)S → ( S R\\ (2)S → a \\ (3)R → , S R\\ (4)R → )$

 

做出DFA如下：

 

计算FIRST和FOLLOW如下：

$$FIRST(R) = \{, \ , )\}\\ FIRST(S) = \{(,a\}\\ FIRST(S') = \{(,a\}\\ <p>FOLLOW(S’) = {\psi }\<br>FOLLOW(S) = {\psi , \ , \ ,) } \<br>FOLLOW(R) = {\psi , \ , \ ,) }$$

填充parsing table如下：

state	(	$a$	,	)	$\psi$	S	R
0	s2	s3				1
1					acc
2	s2	s3				4
3			r2	r2	r2
4			s6	s7			5
5			r1	r1	r1
6	s2	s3				8
7			r4	r4	r4
8			s6	s7			9
9			r3	r3	r3

不会出现冲突。

Exercise 7.2

Consider the grammar

$$S → S a b | a R\<br>R → S | a$$

Is the grammar an SLR(1) grammar? and why?

对文法做扩展如下：

$(0)S'→S\ (1)S → S a b\ (2)S → a R\<br>(3)R → S \ (4)R→ a$

​

 

计算FIRST和FOLLOW如下：

$FIRST(R) = \{a\}\\FIRST(S) = \{a\}\\FIRST(S') = \{a\}\\FOLLOW(S') = \{\psi \}\\FOLLOW(S) = \{\psi ,a\}\\FOLLOW(R) =\{\psi ,a\}$

在$I_5$处，遇到$a$可以shift，同时由于$a \in FOLLOW(R)$,所以在SLR(1)中，可以使用r4来做reduce，这时候就出现了冲突。

所以该文法不是SLR(1)的。

Exercise 7.3

Consider the grammar

$$S → A\\ A → B A | \epsilon \\ B → a B | b$$

Prove that the grammar is an LR(1) grammar.

Construct an LR(1) parsing table for the grammar.

Show the detailed parsing procedure for the sentence $abab$, following the style in slides of this lecture.

扩展文法如下：

$(0)S'→ S\\ (1)S → A\\ (2)A → B A \\ (3)A → \epsilon \\ (4)B → a B \\ (5)B → b$

求FIRST和FOLLOW:

$FIRST(B) = \{a,b\}\\FIRST(A) = \{a,b.\epsilon\}\\FIRST(S) = \{a,b.\epsilon\}\\FIRST(S') = \{a,b.\epsilon\}$

 

$FOLLOW(S') = \{\psi \}\\FOLLOW(S) = \{\psi \}\\FOLLOW(A) = \{\psi \}\\FOLLOW(B) = \{a,b,\psi \}$

做出DFA如下：

构建parse table：

state	$a$	$b$	$\psi$	$S$	$A$	$B$
0	s5	s6	r3	1	2	3
1			acc
2			r1
3	s5	s6	r3		4	3
4			r2
5	s5	s6				7
6	r5	r5	r5
7	r4	r4	r4

没有冲突，所以该文法是LR(1)的。

parsing过程如下：

step	symbol	state	input	reference	action	output
1	$\psi$	0	$abab\psi$	$a[0,a] = s5$	shift
2	$\psi a$	05	$bab\psi$	$a[5,b] = s6$	shift
3	$\psi ab$	056	$ab\psi$	$a[6,a] = r5, g[5,B] = 7$	reduce	$B → b$
4	$\psi aB$	057	$ab\psi$	$a[7,a] = r4, g[0,B] = 3$	reduce	$B → aB$
5	$\psi B$	03	$ab\psi$	$a[3,a] = s5$	shift
6	$\psi Ba$	035	$b\psi$	$a[5,b] = s6$	shift
7	$\psi Bab$	0356	$\psi$	$a[6,\psi ] = r5,g[5,B] = 7$	reduce	$B → b$
8	$\psi Bab$	0357	$\psi$	$a[7,\psi ] = r4,g[3,B] = 3$	reduce	$B → aB$
9	$\psi BB$	033	$\psi$	$a[3,\psi ] = r3,g[3,A] = 4$	reduce	$A → \epsilon$
10	$\psi BBA$	0334	$\psi$	$a[4,\psi ] = r2,g[3,A] = 4$	reduce	$A → B A$
11	$\psi BA$	034	$\psi$	$a[4,\psi ] = r2,g[0,A] = 2$	reduce	$A → B A$
12	$\psi A$	02	$\psi$	$a[2,\psi ] = r1,g[0,S] = 1$	reduce	$S → A$
13	$\psi S$	01	$\psi$	$a[1,\psi ] = acc$	accept

 

Exercise 7.4

Show that the grammar

$$S → A a \ |\ b A c\ |\ d c\ |\ b d a\\ A → d$$

is LALR(1) but not SLR(1).

扩展文法如下：

$(0)S'→ S\\(1)S → A a \\(2) S → b A c\\ (3)S → d c\\ (4)S → b d a\\ (5)A → d$

 

 

FIRST和FOLLOW如下：

$FIRST(A) = \{d\}\\FIRST(S) = \{b,d\}$

$FOLLOW(S) = \{\psi \}\\ FOLLOW(A) = \{a,c\}$

state	$a$	$b$	$c$	$d$	$\psi$	$S$	$A$
0		s4		s9		1	2
1					acc
2	s3
3					r1
4				s7			5
5			s6
6					r2
7	s8		r5
8					r4
9	r5		s10
10					r3

不会出现冲突，所以该文法是LALR(1)的。

它不是SLR(1)的，

在这里，如果input的下一个字符是c，因为$c \in FOLLOW(A)$，所以可以使用$A → d·$进行reduce，也可以用$S→d·c$来shift，出现了shift-reduce冲突。所以该文法不是SLR(1)的。