下面答案僅供參考！

目前修改了第三題的部分問題。

1.考慮下面文法G1:

S→a∣∧∣(T)

T→T，S∣S

(1) 消去 Q 的左遞歸。然后，對(duì)每個(gè)非終結(jié)符，寫岀不帶回溯的遞歸子程序。

(2) 經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測(cè)分析表。

2.對(duì)下面的文法G:

P→(E)lalblΛ

(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST和FOLIOW.

(2)證明這個(gè)文法是LL(1)的。

?

(3)構(gòu)造它的預(yù)測(cè)分析表。

(4)構(gòu)造它的遞歸下降分析程序。

?

?

3.下面文法中,哪些是LL(1)的,說明理由。

（1）S→Abc

? ? ? ? ?A→a∣ε

? ? ? ? ?B→b∣ε

這里是不是寫錯(cuò)了，應(yīng)該是S→ABc？，下圖答案是以S→ABc為準(zhǔn)。

? ? ?看了一下網(wǎng)上流傳的答案，基本上都是first(S)={a,b,c}和下圖結(jié)果一樣，如果是S->Abc的話，那么first(S)={a,b}。

下圖答案是以S→Abc為準(zhǔn)

?

（2）S→Ab

? ? ? ? ?A→a∣B∣ε

? ? ? ? ?B→b∣ε

（3）S→ABBA

? ? ? ? ?A→a∣ε

? ? ? ? ?B→b∣ε

?（4)S→aSe∣B

? ? ? ?B→bBe∣C

? ? ? ?C→cCe∣d

4. 對(duì)下面文法：

????????????? Expr→-Expr

????????????? Expr→(Expr)∣Var

????????????? ExprTail→-Expr∣ε

????????????? Var→id VarTail

????????????? VarTail→(Expr)∣ε

(1) 構(gòu)造 LL(1)分析表。

(2) 給出對(duì)句子 id - -id((id))的分析過程。

構(gòu)造文法的預(yù)測(cè)分析表,通常應(yīng)當(dāng)按下列步驟進(jìn)行： (1) 消除文法的左遞歸(包括所有直接左遞歸和間接左遞歸）； (2) 對(duì)消除左遞歸后的文法，提取左公因子； (3) 對(duì)經(jīng)過上述改造后的文法，計(jì)算它的每個(gè)非終結(jié)符的 FIRST 集合和 FOLLOW 集合?⑷ 根據(jù) FIRST 集合和 FOLLOW 集合構(gòu)造預(yù)測(cè)分析表：

第1步對(duì)文法G的每個(gè)產(chǎn)生式A→α執(zhí)行第1步和第3步；

第2步對(duì)每個(gè)終結(jié)符a∈FIRST(α)，把A→α加至M[A，a]中；

第3步若ε∈FIRST(α)，則對(duì)任何b∈FOLLOW(A)把A→α加至M[A，b]中；

第4步把所有無定義的M[A，a]標(biāo)上“出錯(cuò)標(biāo)志”。

解答：

（1）計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：

????????????? FIRST(Expr)={-，(，id}

????????????? FIRST(ExprTail)={-，ε}

????????????? FIRST(Var)={id}

????????????? FIRST(VarTail)={(，ε}

????????????? FOLLOW(Expr)={)，#}

????????????? FOLLOW(ExprTail)={)，#}

????????????? FOLLOW(Var)={-，)，#}

????????????? FOLLOW(VarTail)={-，∣，#}

構(gòu)造其預(yù)測(cè)分析表如下：? ??

（2）句子id--id((id))的分析過程如下：? ??

5. 把下面文法改寫為 LL(1)的：

?????? Declist→Declist；Decl∣Decl

?????? Decl→IdList：Type

?????? IdList→IdList，id∣id

?????? Type→ScalarType∣array(ScalarTypeList) of Type

?????? ScalarType→id∣Bound..Bound

?????? Bound→Sign IntLiteral∣id

?????? Sign→+∣-∣ε

?????? ScalarTypeList→ScalarTypeList，ScalarType∣ScalarType

? ? ? ?答：本題目主要考査學(xué)生理解和運(yùn)用消除文法的左遞歸、提取左公共因子等算法的能力， 為判斷文法是否是 LL(1)文法，還要計(jì)算文法的 FIRST 集合和 FOLLOW 集合。

? ? ?消除文法的左遞歸的基本思想是，將文法規(guī)則中的左遞歸結(jié)構(gòu)變換成等價(jià)的右遞歸結(jié)構(gòu)。

? ? ?提取左公因子的算法，是對(duì)包含公共左因子的產(chǎn)生式候選，反復(fù)提取左因子，就能夠 把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。

? ? ?消除文法的左遞歸、提取左公共因子后，再計(jì)算文法的各非終結(jié)符00的首符集 FIRST( X)和隨符集 FOLLOW( X)，然后根據(jù) LL(1)文法的充分必要條件（即 LL(1)文法 的定義)來判斷文法是否是 LL(1)文法。

首先消除左遞歸，得到文法G(Declist)：

???????????????????? Declist→Decl Declist’

???????????????????? Declist’→；Decl Declist’∣ε

???????????????????? Decl→IdList：Type

???????????????????? IdList→id IdList’

???????????????????? IdList’→，id List’∣ε

???????????????????? Type→ScalarType∣array(ScalarTypeList) of Type

???????????????????? ScalarType→id∣Bound..Bound

???????????????????? Bound→Sign IntLiteral∣id

???????????????????? Sign→+∣-∣ε

???????????????????? ScalarTypeList→ScalarType ScalarTypeList’

???????????????????? ScalarTypeList’→，ScalarType ScalarTypeList’∣ε

??顯然，改造后的文法沒有左公共因子，計(jì)算每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合如下：

???????????????????? FIRST(Declist)={id}

???????????????????? FIRST(Declist’)={；，ε}

???????????????????? FIRST(Decl)={id}

???????????????????? FIRST(IdList)={id}

???????????????????? FIRST(IdList’)={；，ε}

???????????????????? FIRST(Type)={id，+，-，IntLiteral，array}

???????????????????? FIRST(ScalarType)={id，+，-，IntLiteral}

???????????????????? FIRST(Bound)={id，+，-，InLiteral}

???????????????????? FIRST(Sign)={+，-，ε}

???????????????????? FIRST(ScalarTypeList)={id，+，-，IntLiteral }

???????????????????? FIRST(ScalarTypeList’)={，，ε}

???????????????????? FOLLOW(Declist)={#}

???????????????????? FOLLOW(Declist’)={#}

???????????????????? FOLLOW(Decl)={id，；}

???????????????????? FOLLOW(IdList)={：}

???????????????????? FOLLOW(IdList’)={：}

???????????????????? FOLLOW(Type)={id，；}

???????????????????? FOLLOW(ScalarType)={id，；，），，}

???????????????????? FOLLOW(Bound)={id，；，）’，’..}

???????????????????? FOLLOW(Sign)={IntLiteral}

???????????????????? FOLLOW(ScalarTypeList)={)}

???????????????????? FOLLOW(ScalarTypeList’)={)}

顯然，改造后的文法是 LL(1)的。文章來源地址http://www.zghlxwxcb.cn/news/detail-438535.html

到了這里，關(guān)于編譯原理陳火旺版第四章課后題答案的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！