24-25-2-编译原理与技术-期中

一（15分）

设字母表 $\Sigma=\{0, 1\}$ ， $\Sigma$ 上的正规表达式 $R=1(0|1)^*0^+$ 。

请构造与之等价的 DFA，要求给出 DFA 的状态转换图。

答案 / 解析

根据上述 DFA，构造与之等价的右线性文法，要求给出产生式集合。

答案 / 解析

S->1A
A->1A|0B
B->1A|0B|ε

或者

S->1A
A->1A|B
B->1A|0B|0

二（40分）

有如下文法

$S \rightarrow ABc$

$A \rightarrow aAd \mid ab \mid \varepsilon$

$B \rightarrow Bb \mid \varepsilon$

判断该文法是否为 LL(1) 文法，说明原因。若不是，做（2），若是，做（3）。

答案 / 解析

$A\rightarrow aAc\mid a\mid\varepsilon$ 含左公因子 $a$ ； $B\rightarrow Bb\mid\varepsilon$ 含左递归，所以不是 LL(1) 文法。

是否将该文法变换为等价的 LL(1) 文法？如果可以，给出改造后的文法，并根据产生式说明改造后的文法为 LL(1) 文法，之后继续做 (3)；如果不可以，说明理由，并尝试完成 (3) 和 (4)。

答案 / 解析

改写后的文法为

\begin{align*} &S\rightarrow ABc\\ &A\rightarrow aA'\mid\varepsilon\\ &A'\rightarrow Ad\mid b\\ &B\rightarrow B'\\ &B'\rightarrow bB\mid\varepsilon \end{align*}

计算 LL(1) 文法中每个非终结符号的 FIRST 集合和 FOLLOW 集合。

答案 / 解析

	First 集	Follow 集
S	{a,b,c}	{$}
A	{a,ε}	{b,c,d}
A’	{a,b,d}	{b,c,d}
B	{b,ε}	{c}
B’	{b,ε}	{c}

构造文法的 LL(1) 分析表。

答案 / 解析

	a	b	c	d	$
S	S->ABc	S->ABc	S->ABc
A	A->aA	A->ε	A->ε	A->ε
A’	A’->Ad	A’->b		A’->Ad
B		B->B’	B->B’
B’		B’->bB	B’->ε

三（45分）

有如下文法

$E \rightarrow AaBa \mid BbAb$

$A \rightarrow c$

$B \rightarrow c$

构造该文法的 LR(1) 项目集规范族及识别其所有活前缀的 DFA；

答案 / 解析

拓广文法为

0. E'->E
1. E->AaBa
2. E->BbAb
3. A->c
4. B->c

I₀={[E’->⋅E, $], [E->⋅AaBa,$ ], [E->⋅BbAb,$], [A->⋅c,a], [B->⋅c,b]}

I₁=goto(I₀,E)={[E’->E⋅,$]}

I₂=goto(I₀,A)={[E->A⋅aBa,$]}

I₃=goto(I₀,B)={[E->B⋅bAb,$]}

I₄=goto(I₀,c)={[A->c⋅,a], [B->c⋅,b]}

I₅=goto(I₂,a)={[E->Aa⋅Ba,$], [B->⋅c,a]}

I₆=goto(I₃,b)={[E->Bb⋅Ab,$], [A->⋅c,b]}

I₇=goto(I₅,B)={[E->AaB⋅a,$]}

I₈=goto(I₅,c)={[B->c⋅,a]}

I₉=goto(I₆,A)={[E->BbA⋅b,$]}

I₁₀=goto(I₆,c)={[A->c⋅,b]}

I₁₁=goto(I₇,a)={[E->AaBa⋅,$]}

I₁₂=goto(I₉,b)={[E->BbAb⋅,$]}

判断该文法是否为 LR(1) 文法，如果是，构造该文法的 LR(1) 分析表，如果不是，请阐述理由；

答案 / 解析

所有项目集均无冲突，所以是 LR(1) 文法。LR(1) 分析表如下：

	action				goto
状态	a	b	c	$	E	A	B
0			S4		1	2	3
1				ACC
2	S5
3		S6
4	R3	R4
5			S8				7
6			S10				9
7	S11
8	R4
9		S12
10		R3
11			R1
12			R2

判断该文法是否为 SLR(1) 文法，如果是，构造该文法的 SLR(1) 分析表，如果不是，请阐述理由；

答案 / 解析

项目集 I₄ 存在归约-归约冲突，follow(A)=follow(B)={a,b}，所以该冲突不能通过简单向前看一个符号来解决，所以该文法不是 SLR(1) 文法。

判断该文法是否为 LALR(1) 文法，如果是，构造该文法的 LALR(1) 分析表，如果不是，请阐述理由；

答案 / 解析

因为该 LR(1) 项目集规范族中没有同心集，所以文法是 LALR(1) 文法，分析表同 LR(1) 分析表。