【编译原理】第三章部分课后题答案(编译原理第三版)

推荐整理分享【编译原理】第三章部分课后题答案(编译原理第三版)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:编译原理第二版课后答案,编译原理第三版课后答案王生原,编译原理第三版课后答案,编译原理第三版,编译原理第三版课后答案王生原,编译原理第三版课后答案王生原,编译原理第三版课后答案陈意云,编译原理第三版课后答案,内容如对您有帮助，希望把文章链接给更多的朋友！

第 三 章 课 后 习 题

考虑文法 S→(L) ∣ aL→L,S ∣ SS \rightarrow (L)\space | \space a\\ L\rightarrow L, S \space | \space SS→(L) ∣ aL→L,S ∣ S (a) 建立句子 (a,(a,a))(a,(a,a))(a,(a,a)) 和 (a,(a,a),(a,a))(a,(a,a),(a,a))(a,(a,a),(a,a)) 的分析树。

见下面两题。

(b) 为 (a) 的两个句子构造最左推导。

(a,(a,a))(a,(a,a))(a,(a,a)) 最左推导的分析树（包括推导过程中的分析树）：

(a,(a,a),(a,a))(a,(a,a),(a,a))(a,(a,a),(a,a)) 最左推导的分析树： S⇒lm(L)⇒lm(L,S)⇒lm(S,S)⇒lm(a,S)⇒lm(a,(L))⇒lm(a,(L,S))⇒lm(a,(S,S))⇒lm(a,((L),S))⇒lm(a,((L,S),S))⇒lm(a,((S,S),S))⇒lm(a,((a,S),S))⇒lm(a,((a,a),S))⇒lm(a,((a,a),(L)))⇒lm(a,((a,a),(L)))⇒lm(a,((a,a),(L,S)))⇒lm(a,((a,a),(S,S)))⇒lm(a,((a,a),(a,S)))⇒lm(a,((a,a),(a,a)))S\Rightarrow_{lm} (L)\Rightarrow_{lm} (L,S) \Rightarrow_{lm} (S,S) \Rightarrow_{lm} (a,S) \Rightarrow_{lm}(a,(L)) \Rightarrow_{lm} (a,(L,S)) \Rightarrow_{lm} (a,(S,S)) \Rightarrow_{lm} (a,((L),S))\\ \Rightarrow_{lm} (a,((L,S),S)) \Rightarrow_{lm} (a,((S,S),S))\Rightarrow_{lm} (a,((a,S),S)) \Rightarrow_{lm} (a,((a,a),S)) \Rightarrow_{lm} (a,((a,a),(L)))\\ \Rightarrow_{lm} (a,((a,a),(L))) \Rightarrow_{lm} (a,((a,a),(L,S)))\Rightarrow_{lm} (a,((a,a),(S,S))) \Rightarrow_{lm} (a,((a,a),(a,S))) \Rightarrow_{lm} (a,((a,a),(a,a)))S⇒lm​(L)⇒lm​(L,S)⇒lm​(S,S)⇒lm​(a,S)⇒lm​(a,(L))⇒lm​(a,(L,S))⇒lm​(a,(S,S))⇒lm​(a,((L),S))⇒lm​(a,((L,S),S))⇒lm​(a,((S,S),S))⇒lm​(a,((a,S),S))⇒lm​(a,((a,a),S))⇒lm​(a,((a,a),(L)))⇒lm​(a,((a,a),(L)))⇒lm​(a,((a,a),(L,S)))⇒lm​(a,((a,a),(S,S)))⇒lm​(a,((a,a),(a,S)))⇒lm​(a,((a,a),(a,a))) (c) 为 (a) 的两个句子构造最右推导。

(a,(a,a))(a,(a,a))(a,(a,a)) 最右推导的分析树（包括推导过程中的分析树）：

(a,(a,a),(a,a))(a,(a,a),(a,a))(a,(a,a),(a,a)) 最右推导：

S⇒rm(L)⇒rm(L,S)⇒rm(L,(L))⇒rm(L,(L,S))⇒rm(L,(L,(L)))⇒rm(L,(L,(L,S)))⇒rm(L,(L,(L,a)))⇒rm(L,(L,(S,a)))⇒rm(L,(L,(a,a)))⇒rm(L,(S,(a,a)))⇒rm(L,((L),(a,a)))⇒rm(L,((L,S),(a,a)))⇒rm(L,((L,a),(a,a)))⇒rm(L,((S,a),(a,a)))⇒rm(L,((a,a),(a,a)))⇒rm(S,((a,a),(a,a)))⇒rm(a,((a,a),(a,a)))S\Rightarrow_{rm} (L) \Rightarrow_{rm} (L,S) \Rightarrow_{rm} (L,(L)) \Rightarrow_{rm} (L,(L,S)) \Rightarrow_{rm} (L,(L,(L)))\Rightarrow_{rm} (L,(L,(L,S)))\Rightarrow_{rm} (L,(L,(L,a))) \\ \Rightarrow_{rm} (L,(L,(S,a))) \Rightarrow_{rm} (L,(L,(a,a))) \Rightarrow_{rm} (L,(S,(a,a))) \Rightarrow_{rm} (L,((L),(a,a)))\Rightarrow_{rm} (L,((L,S),(a,a))) \\ \Rightarrow_{rm} (L,((L,a),(a,a))) \Rightarrow_{rm} (L,((S,a),(a,a)))\Rightarrow_{rm} (L,((a,a),(a,a))) \Rightarrow_{rm} (S,((a,a),(a,a)))\Rightarrow_{rm} (a,((a,a),(a,a)))S⇒rm​(L)⇒rm​(L,S)⇒rm​(L,(L))⇒rm​(L,(L,S))⇒rm​(L,(L,(L)))⇒rm​(L,(L,(L,S)))⇒rm​(L,(L,(L,a)))⇒rm​(L,(L,(S,a)))⇒rm​(L,(L,(a,a)))⇒rm​(L,(S,(a,a)))⇒rm​(L,((L),(a,a)))⇒rm​(L,((L,S),(a,a)))⇒rm​(L,((L,a),(a,a)))⇒rm​(L,((S,a),(a,a)))⇒rm​(L,((a,a),(a,a)))⇒rm​(S,((a,a),(a,a)))⇒rm​(a,((a,a),(a,a))) (d) 这个文法产生的语言是什么？

该文法产生的语言是括号匹配的串，串中的各项用“，”隔开，项可以是括号匹配的子串或 a。

考虑文法 S→aSbS ∣ bSaS ∣ εS\rightarrow aSbS\space|\space bSaS \space | \space \varepsilonS→aSbS ∣ bSaS ∣ ε (a) 为句子 abababababab 构造两个不同的最左推导，以此说明该文法是二义的。

第一种最左推导的分析树（包括推导过程中的分析树）：

​

第二种最左推导的分析树（包括推导过程中的分析树）：

一个文法，如果存在某个句子有不止一棵分析树与之对应，那么称这个文法是二义的；故，该文法是是二义的。

(b) 为 abababababab 构造对应的最右推导。

两种最右推导的分析树（包括推导过程中的分析树）如下：

(c) 为 abababababab 构造对应的分析树。

见上面四幅图。

(d) 这个文法产生的语言是什么？

通过最左推导的方式和产生式 S→aSbS\rightarrow aSbS→aSb 可以得到前缀为若干个 aaa 的任意长度的串；

通过最左推导的方式和产生式 S→bSaS\rightarrow bSaS→bSa 可以得到前缀为若干个 bbb 的任意长度的串；

题目给的产生式为 S→aSbSS\rightarrow aSbSS→aSbS 、 S→bSaSS\rightarrow bSaSS→bSaS 和 S→εS\rightarrow \varepsilonS→ε，由 SSS 可以推导出空串，可以说明可以产生 S→aSbS\rightarrow aSbS→aSb 和 S→bSaS\rightarrow bSaS→bSa，因此由任意长度的前缀 aaa 和前缀 bbb 的子串可以构成 aaa 和 bbb 任意交错的串；

又因为每个产生式中 aaa 和 bbb 的个数都相同，故产生 aaa 和 bbb 数目相等且任意长度的串。

下面的二义文法描述命题演算公式，为它写一个等价的非二义性文法。 S→S and S ∣ S or S ∣ not S ∣ true ∣ false ∣ (S)S→S \space\textbf{and}\space S\space|\space S\space \textbf{or}\space S\space|\space \textbf{not}\space S\space|\space \textbf{true}\space|\space \textbf{false} \space|\space(S)S→S and S ∣ S or S ∣ not S ∣ true ∣ false ∣ (S) 通过引入非终结符消除二义性： E→Eor T ∣ TT→Tand F ∣ FF→not F ∣ (E) ∣ true ∣ falseE\rightarrow E \textbf{or}\space T\space |\space T \\ T\rightarrow T \textbf{and}\space F\space |\space F \\ F\rightarrow \textbf{not} \space F\space |\space (E)\space |\space \textbf{true}\space |\space \textbf{false} \\E→Eor T ∣ TT→Tand F ∣ FF→not F ∣ (E) ∣ true ∣ false

文法 R→R ′∣′ R ∣ R R ∣ R∗ ∣ (R) ∣ a ∣ bR\rightarrow R\space '|' \space R \space |\space R \space R \space|\space R^*\space|\space(R)\space|\space a \space | \space bR→R ′∣′ R ∣ R R ∣ R∗ ∣ (R) ∣ a ∣ b 产生字母表 {a,b}\{a,b\}{a,b} 上所有不含 ε\varepsilonε 的正规式。注意，第一条竖线加了引号，它是正规式的或运算符号，而不是文法产生式右部各选择之间的分隔符，另外∗^*∗在这里是一个普通的终结符。该文法是二义的。

(a) 证明该文法产生字母表 {a,b}\{a,b\}{a,b} 上的所有正规式。

证明：

(1) 该文法产生的串是字母表 {a,b}\{a,b\}{a,b} 上的正规式：

R→aR\rightarrow aR→a和R→bR\rightarrow bR→b产生aaa和bbb，而aaa和bbb是 {a,b}\{a,b\}{a,b}上的符号，因此是正规式。若R1R_1R1​，R2R_2R2​产生正规式α\alphaα和β\betaβ 则： R→R1R2R\rightarrow R_1R_2R→R1​R2​ 产生正规式 αβ\alpha\betaαβ

R→R1∣R2R\rightarrow R_1|R_2R→R1​∣R2​ 产生正规式 α ∣ β\alpha\space|\space\betaα ∣ β

R→R1∗R\rightarrow R_1^*R→R1∗​ 产生正规式 α∗\alpha^*α∗

R→(R1)R\rightarrow (R_1)R→(R1​) 产生正规式 (α)(\alpha)(α)

(2) 字母表 {a,b}\{a,b\}{a,b} 上的所有正规式都可由此文法产生：

字母表 {a,b}\{a,b\}{a,b} 上的任一正规式（其中 α\alphaα，β\betaβ 为正规式）必为以下形式之一：

αβ\alpha\betaαβ，可由 R→RRR\rightarrow RRR→RR 产生

α ∣ β\alpha\space | \space\betaα ∣ β，可由 R→R ∣ RR\rightarrow R\space | \space RR→R ∣ R 产生

α∗\alpha^*α∗，可由 R→R∗R\rightarrow R^*R→R∗ 产生

(α)(\alpha)(α)，可由 R→(R)R\rightarrow (R)R→(R) 产生

aaa，可由 R→aR\rightarrow aR→a 产生

bbb，可由 R→bR\rightarrow bR→b 产生

因而，该文法产生字母表 {a,b}\{a,b\}{a,b} 上的所有正规式

(b) 为该文法写一个等价的非二义文法。它给予算符 ∗^*∗ 、连接和 ∣|∣ 的优先级和结合性同 2.2 节中定义的一致。

该文法没有体现运算符∗^*∗ 、()()()、 ∣|∣ 和连接的优先级，因而是二义的。例如： R⇒R ∣ R⇒a ∣ R ⇒a ∣ R∗⇒a ∣ b∗R⇒R∗⇒R ∣ R∗ ⇒a ∣ R∗⇒a ∣ b∗R\Rightarrow R\space | \space R \Rightarrow a\space | \space R\space\Rightarrow a\space|\space R^*\Rightarrow a\space|\space b^* \\ R\Rightarrow R^* \Rightarrow R\space | \space R^*\space\Rightarrow a\space|\space R^*\Rightarrow a\space|\space b^*R⇒R ∣ R⇒a ∣ R ⇒a ∣ R∗⇒a ∣ b∗R⇒R∗⇒R ∣ R∗ ⇒a ∣ R∗⇒a ∣ b∗ 通过引入非终结符消除二义性： E→E ′∣′ T ∣ TT→TF ∣ FF→F∗ ∣ (E) ∣ a ∣ bE\rightarrow E\space'|' \space T \space|\space T \\ T\rightarrow TF\space |\space F \\ F\rightarrow F^*\space | \space (E)\space |\space a \space |\space bE→E ′∣′ T ∣ TT→TF ∣ FF→F∗ ∣ (E) ∣ a ∣ b 消除二义性后： E⇒E ∣ T⇒E ∣ F⇒E ∣ F∗ ⇒E ∣ b∗⇒T ∣ b∗⇒F ∣ b∗⇒a ∣ b∗E\Rightarrow E\space|\space T\Rightarrow E\space|\space F\Rightarrow E\space|\space F^*\space\Rightarrow E\space |\space b^* \Rightarrow T\space | \space b^* \Rightarrow F \space | \space b^*\Rightarrow a \space | \space b^*E⇒E ∣ T⇒E ∣ F⇒E ∣ F∗ ⇒E ∣ b∗⇒T ∣ b∗⇒F ∣ b∗⇒a ∣ b∗ (c) 按上面两个文法构造句子 ab ∣ b∗aab\space|\space b^*aab ∣ b∗a 的分析树。

存在二义性：

不存在二义性：

条件语句文法 stmt→if expr then stmt ∣ matched_stmtmatched_stmt→if expr then matched_stmt else stmst ∣ otherstmt \rightarrow \textbf{if}\space expr \space \textbf{then} \space stmt \space | \space matched\_stmt \\ matched\_stmt \rightarrow \textbf{if} \space expr \space \textbf{then} \space matched\_stmt\space \textbf{else} \space stmst \space | \space \textbf{other}stmt→if expr then stmt ∣ matched_stmtmatched_stmt→if expr then matched_stmt else stmst ∣ other

试图消除悬空 elseelseelse 的二义性，请证明该文法仍然是二义的。

由于matched_stmtmatched\_stmtmatched_stmt不能保证thenthenthen和elseelseelse的配对，因而存在二义性。

句型 if expr then if expr then matched_stmt else if expr then matched_stmt else stmtif\space expr\space then \space if \space expr\space then \space matched\_stmt \space else \space if \space expr\space then \space matched\_stmt \space else \space stmtif expr then if expr then matched_stmt else if expr then matched_stmt else stmt 存在两个不同的最左推导。

期望的是：

一种和期望不一样的推导：

另一种推导：

(a) 消除习题 3.1 文法的左递归。 S→(L) ∣ aL→SL′L′→ ,SL′ ∣ εS\rightarrow (L)\space | \space a \\ L\rightarrow SL' \\ L'\rightarrow\space ,SL'\space | \space \varepsilonS→(L) ∣ aL→SL′L′→ ,SL′ ∣ ε (b) 为 (a) 的文法构造预测分析器。

First(S)={ ( , a }First(L)={ ( , a }First(L′)={ ′,′ , ε }Follow(S)={ ) , ′,′ , $ }Follow(L)={ ) , $ }Follow(L′)={ ) , $ }First(S) = \{\space(\space,\space a\space\} \\ First(L) = \{\space(\space,\space a\space\} \\ First(L') = \{\space','\space,\space\varepsilon\space\} \\\\ Follow(S) = \{\space)\space,\space','\space,\space\$\space\} \\ Follow(L) = \{\space)\space, \space\$\space\} \\ Follow(L')= \{\space)\space, \space\$\space\} \\First(S)={ ( , a }First(L)={ ( , a }First(L′)={ ′,′ , ε }Follow(S)={ ) , ′,′ , $ }Follow(L)={ ) , $ }Follow(L′)={ ) , $ }

构造下面文法的 LL(1) 分析表。 D→TLT→int ∣ realL→id RR→ ,id R ∣ εD\rightarrow TL \\ T\rightarrow \textbf{int} \space | \space \textbf{real} \\ L\rightarrow \textbf{id} \space R \\ R\rightarrow\space ,\textbf{id}\space R \space | \space \varepsilonD→TLT→int ∣ realL→id RR→ ,id R ∣ ε 先确定非终结符的 FirstFirstFirst 和 FollowFollowFollow 集： First(D)=First(T)={int,real}First(L)={id}First(R)={′,′,ε}Follow(D)=Follow(L)={$}Follow(T)={id}Follow(R)={$}First(D)=First(T) = \{\textbf{int}, \textbf{real}\}\\ First(L)=\{\textbf{id}\} \\ First(R)=\{',', \varepsilon\} \\ \\ Follow(D)=Follow(L)=\{\$\} \\ Follow(T)=\{\textbf{id}\} \\ Follow(R)=\{\$\}First(D)=First(T)={int,real}First(L)={id}First(R)={′,′,ε}Follow(D)=Follow(L)={$}Follow(T)={id}Follow(R)={$}

构造下面文法的 LL(1) 分析表。 S→aBS ∣ bAS ∣ εA→bAA ∣ aB→aBB ∣ bS\rightarrow aBS\space |\space bAS \space | \space \varepsilon \\ A\rightarrow bAA\space | \space a \\ B\rightarrow aBB \space | \space bS→aBS ∣ bAS ∣ εA→bAA ∣ aB→aBB ∣ b

First(S)={a,b,ε}First(A)=First(B)={a,b}Follow(S)=Follow(A)=Follow(B)={$}First(S) = \{a, b, \varepsilon\}\\ First(A) = First(B) =\{a, b\} \\ \\ Follow(S)=Follow(A)=Follow(B)=\{\$\}First(S)={a,b,ε}First(A)=First(B)={a,b}Follow(S)=Follow(A)=Follow(B)={$}

下面的文法是否为 LL(1) 文法，说明理由。 S→AB ∣ PQxA→xyB→bcP→dP ∣ εQ→aQ ∣ εS\rightarrow AB\space|\space PQx \\ A\rightarrow xy \\ B\rightarrow bc \\ P\rightarrow dP\space|\space \varepsilon\\ Q\rightarrow aQ\space | \space \varepsilonS→AB ∣ PQxA→xyB→bcP→dP ∣ εQ→aQ ∣ ε 上面文法不是 LL(1) 文法。

LL(1) 文法：对于产生式 A→α ∣ βA\rightarrow \alpha \space | \space \betaA→α ∣ β 满足：

① FIRST(α) ∩ FIRST(β)=ϕFIRST(\alpha)\space∩ \space FIRST(\beta) = \phiFIRST(α) ∩ FIRST(β)=ϕ

② 若 β⇒∗ε\beta\Rightarrow ^* \varepsilonβ⇒∗ε ，那么 FIRST(α) ∩ Follow(A)=ϕFIRST(\alpha)\space∩ \space Follow(A) = \phiFIRST(α) ∩ Follow(A)=ϕ

而本题中，FIRST(AB)={x}FIRST(AB) = \{x\}FIRST(AB)={x}，FIRST(PQx)={d,a,x}FIRST(PQx) = \{d,a,x\}FIRST(PQx)={d,a,x}，不满足条件 ①，故，上面文法不是 LL(1) 文法。

为习题3.3的文法构造SLR分析表

扩展文法：

(a) 为下面文法构造规范LR(1)分析表，画出像图3.20这样的状态转换图就可以。 S→V=E ∣ EV→*E ∣ idE→VS\rightarrow V\textbf{=}E\space|\space E\\ V\rightarrow \textbf{*}E\space|\space\textbf{id}\\ E\rightarrow VS→V=E ∣ EV→*E ∣ idE→V 详述构建II_0I0​的过程：

① 拓展文法： S′→S    ()S→V=E    (1)S→E    (2)V→*E    (3)V→id    (4)E→V    (5)S'\rightarrow S\space\space\space\space (0)\\ S\rightarrow V\textbf{=}E\space\space\space\space (1) \\ S\rightarrow E\space\space\space\space (2) \\ V\rightarrow \textbf{*}E\space\space\space\space (3) \\ V\rightarrow\textbf{id}\space\space\space\space (4)\\ E\rightarrow V \space\space\space\space (5)S′→S    (0)S→V=E    (1)S→E    (2)V→*E    (3)V→id    (4)E→V    (5) ② 由于S′S'S′后面不会存在任何字符，所以其FollowFollowFollow集中只有$元素，因此产生式(0)的搜索符为$

③ 对于项目S′→⋅ S , S'\rightarrow ·\space S\space, \spaceS′→⋅ S ,  $  \space ，可以将产生式(1)代入，因为项目右部SSS后面为空串，所以新项目的搜索符为$，故得到新项目S→⋅ V=E , S\rightarrow·\space V\textbf{=}E\space, \spaceS→⋅ V=E ,  $ \space ；类似地，将产生式(2)代入，得到新项目S→⋅ E , S\rightarrow·\space E\space, \spaceS→⋅ E ,  $

④ 对于项目S→⋅ V=E , S\rightarrow·\space V\textbf{=}E\space, \spaceS→⋅ V=E ,  $，可以将产生式(3)和(4)代入，因为项目右部VVV后面为===，所以新项目的搜索符为===，而不是$，故得到新项目V→⋅ *E , =V\rightarrow·\space\textbf{*}E\space, \space=V→⋅ *E , =和V→⋅ id , =V\rightarrow·\space\textbf{id}\space, \space=V→⋅ id , =

⑤ 对于项目S→⋅ E , S\rightarrow·\space E\space, \spaceS→⋅ E , $，可以将产生式(5)代入，因为项目右部EEE后面为空串，所以新项目的搜索符为$，故得到新项目S→⋅ V , S\rightarrow·\space V\space,\spaceS→⋅ V ,  $

⑥ 项目V→⋅ *EV\rightarrow ·\space\textbf{*}EV→⋅ *E和V→⋅ idV\rightarrow· \space\textbf{id}V→⋅ id 不会产生新的项目

⑦ 对于项目S→⋅ V , S\rightarrow·\space V\space,\spaceS→⋅ V ,  $，可以将产生式(3)和(4)代入，注意此时产生的新项目应该继承项目S→⋅ V , S\rightarrow·\space V\space,\spaceS→⋅ V ,  $的搜索符$，因此两个新项目为V→⋅ *E , V\rightarrow·\space\textbf{*}E\space, \spaceV→⋅ *E , $和V→⋅ id , V\rightarrow·\space\textbf{id}\space, \spaceV→⋅ id , $

⑧ 不妨将第一个分量相同的项目对应的搜索符集合合并一下

生成其他状态的道理类似，只展示结果。

(b) 上述状态转换图有同心项目集吗？若有，合并同心项目集后是否会出现动作冲突？

其中I4I_4I4​和I11I_{11}I11​、I5I_5I5​和I12I_{12}I12​、I7I_7I7​和I13I_{13}I13​、I8I_8I8​和I10I_{10}I10​分别为同心项目集。

同心项目集的合并（又得到LALR自动机的过程）不会引入新的移进-归约冲突，可能会引入新的归约-归约冲突；又因为规范LR(1)自动机已经解决了移进-归约冲突的问题，所以只需要验证是否存在归约-归约冲突即可。显然合并后不存在归约-归约冲突，综上，不存在动作冲突。