编译原理复习题_给学生(2014)

.. .. ..

(2) 写出文法G’(S)的预测分析表。 解：

（1）消除左递归，文法变为： S→aPS’| *aPS’ S’→ *aPS’ | ε

P→+aP| +a

提取公共左因子，文法变为G’(S)： S→aPS’| *aPS’

S’→ *aPS’ |ε

P→+aP’ P’→P| ε

（2）计算每个非终结符的FIRST集和FOLLOW集： FIRST(S) = {a, *} FIRST(S’) = {*, ε} FIRST(P) = {+}

FOLLOW(S) = {#}

FOLLOW(S’) = {#} FOLLOW(P) = {*, #} FOLLOW(P’) = {*, #}

FIRST(P’) = {+, ε}

构造该文法的预测分析表如下：

S S’ P P’ * S→*aPS’ S’→ *aP P’→ε + P→+aP’ P’→P a S→aPS’ # S’→ ε P’→ε 参考材料

.. .. ..

19．已知文法G(S)：

S→aS | bS | a

(1) 构造识别该文法所产生的活前缀的DFA；

(2) 判断该文法是LR(0)还是SLR(1)，并构造所属文法的LR分析表。 解：

（1）将文法G(S)拓广为G’(S’)：

(0) S’→S (1) S→aS (2) S→bS (3) S→a

识别该文法所产生的活前缀的DFA：

I4: S’→ aS? S I2: S→ a?S S→ ?aS S→ ?bS S→ ?a S→ a? a a I0: S’→ ?S S→ ?aS S→ ?bS S→ ?a b S I1: S’→ S? b a I5: S’→ bS? I3: S→ b?S S→ ?aS S→ ?bS S→ ?a S b （2）在状态I2存在“移近-归约”冲突，因此该文法不是LR(0)文法。

计算S的FOLLOW集合： FOLLOW(S)= {#}

参考材料

.. .. ..

I2中的冲突用FOLLOW集合可以解决，所以该文法是SLR(1)文法。 构造SLR(1)分析表如下：

ACTION 状态 a 0 1 2 3 4 5

20．构造文法S→AaAb|BbBa A→ε B→ε，的预测分析表。

答：first（S）={a，b},First（AaAb）={a}，First（BbBa ）={b} Follow（A）={a，b} Follow（B）={a，b}

S A B

21．设有如下文法：

参考材料

GOTO # acc r3 r1 r2 S 1 4 5 b s3 s3 s3 s2 s2 s2 a S→AaAb A→ε b S→BbBa A→ε $ B→ε B→ε .. .. ..

G[E]：E→EWT|T T→T/F|F F→（E）|a|b|c W→+|-

证明符号串a/(b-c)是句子。

解答：有推导E?T?T/F?F/F?a/F?a/(E)?a/(EWT)? a/(TWT)? a/(FWT)? a/(bWT)? a/(b-T)? a/(b-c)，即从文法开始符号E能够推导出a/(b-c)，所以a/(b-c)是文法G[E]的句子。 55．对于下列文法 G[S]： S→Sb|bA A→aA|a

（1）构造一个与G等价的LL（1）文法G′。 （2）对于文法G′,构造相应的LL（1）分析表。 解：

（1） G′：S→bAS′ S′→b S′|ε

A→aA′ A′→A|ε

（2）FIRST（S）={ b } FIRST（S′）={ b，ε} FIRST（A）={a} FIRST（A′）={a，ε} FOLLOW（S）={#}

参考材料