第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
编译原理习题答案.pdf
第二章 词法分析
第三章 语法分析
第四章 语法制导的翻译
第五章 类型检查
第六章 运行时存储空间的组织和管理
2008～2009 第一学期·编译原理作业参考
第二章 词法分析
2.3 叙述由下列正规式描述的语言
(a) 0(0|1)*0
［解答］
该正规式所描述的语言为：在字母表{0, 1}上，首字符为 0，尾字符为 0，中间由零
个或多个 0 或 1 所组成的字符串。
(b) ((ε|0)1*))*
［解答］
该正规式所描述的语言为：在字母表{0, 1}上，由 0 和 1 组成的所有字符串，包括
空串。
2.4 为下列语言写正规定义
C 语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀
（本身除外）不以 */ 结尾。
other 指除了*以外 C 语言中的其它字符
other1 指除了*和/以外 C 语言中的其它字符
other → a | b | …
other1 → a | b | …
comment → /* other* (* ** other1 other*)* ** */
［解答］
(f) 由偶数个 0 和偶数个 1 构成的所有 0 和 1 的串。
［解答］
由题目分析可知，一个符号串由 0 和 1 组成，则 0 和 1 的个数只能有四种情况：
偶数个 0 和偶数个 1（用状态 0 表示）；
偶数个 0 和奇数个 1（用状态 1 表示）；
奇数个 0 和偶数个 1（用状态 2 表示）；
奇数个 0 和奇数个 1（用状态 3 表示）；
所以，
状态 0（偶数个 0 和偶数个 1）读入 1，则 0 和 1 的数目变为：偶数个 0
和奇数个 1（状态 1）
状态 0（偶数个 0 和偶数个 1）读入 0，则 0 和 1 的数目变为：奇数个 0
和偶数个 1（状态 2）
状态 1（偶数个 0 和奇数个 1）读入 1，则 0 和 1 的数目变为：偶数个 0
和偶数个 1（状态 0）
状态 1（偶数个 0 和奇数个 1）读入 0，则 0 和 1 的数目变为：奇数个 0
和奇数个 1（状态 3）
状态 2（奇数个 0 和偶数个 1）读入 1，则 0 和 1 的数目变为：奇数个 0
和奇数个 1（状态 3）
lipeng 1
2008～2009 第一学期·编译原理作业参考
状态 2（奇数个 0 和偶数个 1）读入 0，则 0 和 1 的数目变为：偶数个 0
和偶数个 1（状态 0）
状态 3（奇数个 0 和奇数个 1）读入 1，则 0 和 1 的数目变为：奇数个 0
和偶数个 1（状态 2）
状态 3（奇数个 0 和奇数个 1）读入 0，则 0 和 1 的数目变为：偶数个 0
和奇数个 1（状态 1）
因为，所求为由偶数个 0 和偶数个 1 构成的所有 0 和 1 的串，故状态 0 既为
初始状态又为终结状态，其状态转换图如下所示：
0
0
0
2
1
1
1
1
1
0
0
3
由此可以写出其正规文法为：
S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1
S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1
在不考虑 S0 → ε 产生式的情况下，可以将文法变形为：
S0 = 1S1 + 0S2
S2 = 1S3 + 0S0 + 0
S1 = 1S0 + 0S3 + 1
S3 = 1S2 + 0S1
S3 = (00|11)* ((01|10) S0 + (01|10))
S0 = (00|11) S0 + (01|10) S3 + 11 + 00 (1)
S3 = (00|11) S3 + (01|10) S0 + 01 + 10 (2)
所以：
解(2)式得：
代入(1)式得：
=> S0 = ((00|11) + (01|10) (00|11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11)
=> S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|11) + (01|10) (00|11)* (01|10))
=> S0 = ((00|11)|(01|10) (00|11)* (01|10))+
因为 S0→ε 所以由偶数个 0 和偶数个 1 构成的所有 0 和 1 的串的正规定义为：
S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11)
S0 → ((00|11)|(01|10) (00|11)* (01|10))*
(g) 由偶数个 0 和奇数个 1 构成的所有 0 和 1 的串。
［解答］
此题目我们可以借鉴上题的结论来进行处理。
对于由偶数个 0 和奇数个 1 构成的所有 0 和 1 的串，我们分情况讨论：
(1) 若符号串首字符为 0，则剩余字符串必然是奇数个 0 和奇数个 1，因此我们必
须在上题偶数个 0 和偶数个 1 的符号串基础上再读入 10（红色轨迹）或 01（蓝
色轨迹），又因为在 0→1 和 1→3 的过程中可以进行多次循环（红色虚线轨迹），
同理 0→2 和 2→3（蓝色虚线轨迹），所以还必须增加符号串(00|11)*，我们用
S0 表示偶数个 0 和偶数个 1，用 S 表示偶数个 0 和奇数个 1 则其正规定义为：
lipeng 2
2008～2009 第一学期·编译原理作业参考
S → 0(00|11)*(01|10) S0
S0 → ((00|11)|(01|10) (00|11)* (01|10))*
(2) 若符号串首字符为 1，则剩余字符串必然是偶数个 0 和偶数个 1，其正规定义
为：
S
→ 1S0
S0 → ((00|11)|(01|10) (00|11)* (01|10))*
综合(1)和(2)可得，偶数个 0 和奇数个 1 构成的所有 0 和 1 串其正规定义为：
S
→ 0(00|11)*(01|10) S0|1S0
S0 → ((00|11)|(01|10) (00|11)* (01|10))*
2.7 用算法 2.4 为下列正规式构造非确定的有限自动机，给出它们处理输入串
ababbab 的状态转换序列。
(c) ( (ε | a) b* )*
［解答］
0
1
2
4
3
5
6
7
8
9
10
根据算法 2.4 构造该正规式所对应的 NFA，如图所示。
则输入串 ababbab 的状态转换序列为：
a
b
0 → 1 → 4 → 5 → 6 → 7 → 8 → 9 → 1 → 4 → 5 → 6 → 7 → 8
a
b
→ 7 → 8 → 9 → 1 → 4 → 5 → 6 → 7 → 8 → 9 → 10
a
b
2.10 C 语言的注释是以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀
（本身除外）不以 */ 结尾。画出接受这种注释的 DFA 的状态转换图。
b
［解答］
lipeng 3
2008～2009 第一学期·编译原理作业参考
/
1
2
others
*
3
*
*
4
/
others
5
2.12 为下列正规式构造最简的 DFA
(b) (a|b)* a (a|b) (a|b)
［解答］
(1) 根据算法 2.4 构造该正规式所对应的 NFA，如图所示。
(2) 根据算法 2.2（子集法）将 NFA 转换成与之等价的 DFA（确定化过程）
初始状态
S0 = ε-closure(0) = {0, 1, 2, 4, 7}
标记状态 S0
S1 = ε-closure(move(S0, a)) = ε-closure({5, 8}) = {1, 2, 4, 5, 6, 7, 8, 9, 11}
S2 = ε-closure(move(S0, b)) = ε-closure({3}) = {1, 2, 3, 4, 6, 7}
标记状态 S1
S3 = ε-closure(move(S1, a)) = ε-closure({5, 8, 12}) = {1, 2, 4, 5, 6, 7, 8, 9, 11,
12, 13, 14, 16}
S4 = ε-closure(move(S1, b)) = ε-closure({3, 10}) = {1, 2, 4, 5, 6, 7, 10, 13, 14,
16}
标记状态 S2
S1 = ε-closure(move(S2, a)) = ε-closure({5, 8}) = {1, 2, 4, 5, 6, 7, 8, 9, 11}
S2 = ε-closure(move(S2, b)) = ε-closure({3}) = {1, 2, 3, 4, 6, 7}
标记状态 S3
S5 = ε-closure(move(S3, a)) = ε-closure({5, 8, 12, 17}) = {1, 2, 4, 5, 6, 7, 8, 9,
11, 12, 13, 14, 16, 17, 18}
S6 = ε-closure(move(S3, b)) = ε-closure({3, 10, 15}) = {1, 2, 4, 5, 6, 7, 10, 13,
14, 15, 16, 18}
标记状态 S4
S7 = ε-closure(move(S4, a)) = ε-closure({5, 8, 17}) = {1, 2, 4, 5, 6, 7, 8, 9, 11,
17, 18}
S8 = ε-closure(move(S4, b)) = ε-closure({3, 15}) = {1, 2, 3, 4, 6, 7, 15, 18}
标记状态 S5
S5 = ε-closure(move(S5, a)) = ε-closure({5, 8, 12, 17}) = {1, 2, 4, 5, 6, 7, 8, 9,
11, 12, 13, 14, 16, 17, 18}
lipeng 4
2008～2009 第一学期·编译原理作业参考
S6 = ε-closure(move(S5, b)) = ε-closure({3, 10, 15}) = {1, 2, 4, 5, 6, 7, 10, 13,
14, 15, 16, 18}
标记状态 S6
S7 = ε-closure(move(S6, a)) = ε-closure({5, 8, 17}) = {1, 2, 4, 5, 6, 7, 8, 9, 11,
17, 18}
S8 = ε-closure(move(S6, b)) = ε-closure({3, 15}) = {1, 2, 3, 4, 6, 7, 15, 18}
标记状态 S7
S3 = ε-closure(move(S7, a)) = ε-closure({5, 8, 12}) = {1, 2, 4, 5, 6, 7, 8, 9, 11,
12, 13, 14, 16}
S4 = ε-closure(move(S7, b)) = ε-closure({3, 10}) = {1, 2, 4, 5, 6, 7, 10, 13, 14,
16}
标记状态 S8
S1 = ε-closure(move(S8, a)) = ε-closure({5, 8}) = {1, 2, 4, 5, 6, 7, 8, 9, 11}
S2 = ε-closure(move(S8, b)) = ε-closure({3}) = {1, 2, 3, 4, 6, 7}
由以上可知，确定化后的 DFA 的状态集合 S = {S0, S1, S2, S3, S4, S5, S6, S7, S8}，
输入符号集合 Σ = {a, b}，状态转换函数 move 如上，S0 为开始状态，接收状态集合 F =
{S5, S6, S7, S8}，其状态转换图如下所示：
0
1
2
3
4
5
6
7
8
{S5, S6, S7, S8}
{S3, S4}
(3) 根据算法 2.3 过将 DFA 最小化
第一次划分：{
第二次划分：{
第三次划分：{
第四次划分：{
第五次划分：{
第六次划分：{
S0, S1, S2, S3, S4}
{S5, S6, S7, S8}
{S0, S1, S2, S3, S4}a = {S1, S3, S1, S5, S7}
S0, S1, S2}
{S0, S1, S2}a = {S1, S3, S1}
{S3, S4} {S5, S6, S7, S8}
S0, S2} {S1}
{S0, S2}a = {S1}
{S0, S2}b = {S2}
{S5, S6, S7, S8}a = {S5, S7, S3, S1}
S0, S2} {S1}
{S3, S4}a = {S5, S7}
S0, S2} {S1}
{S5, S6}a = {S5, S7}
S0, S2} {S1}
{S7, S8}a = {S3, S1}
{S3} {S4}
{S3} {S4}
{S3, S4} {S5, S6} {S7, S8}
S0, S2 不可区分，即等价。
{S5, S6} {S7, S8}
{S5} {S6} {S7, S8}
lipeng 5
2008～2009 第一学期·编译原理作业参考
S0, S2} {S1}
{S3} {S4}
第七次划分：{
集合不可再划分，所以 S0, S2 等价，选取 S0 表示{S0, S2}，其状态转换图，即题目
所要求的最简 DFA 如下所示：
{S5} {S6} {S7} {S8}
2.14 构造一个 DFA，它接受 Σ = {0，1}上能被 5 整除的二进制数。
［解答］
分析题目可知，一个二进制数除以 5，其余数（十进制）只能是 0，1，2，3，4 五种，
因此我们以 0，1，2，3，4 分别表示这五种状态。因为要求得能被 5 整除的二进制数，故
状态 0 既为初始状态，又为终结状态。
二进制序列中只能有 0 或 1 组成，下面举例说明序列中增加 0 或 1 后余数的变化。
(000)2 增加 0 (0000)2 mod 5 = (0)10 增加 1 (0001)2 mod 5 = (1)10
(001)2 增加 0 (0010)2 mod 5 = (2)10 增加 1 (0011)2 mod 5 = (3)10
(010)2 增加 0 (0100)2 mod 5 = (4)10 增加 1 (0101)2 mod 5 = (0)10
(011)2 增加 0 (0110)2 mod 5 = (1)10 增加 1 (0111)2 mod 5 = (2)10
(100)2 增加 0 (1000)2 mod 5 = (3)10 增加 1 (1001)2 mod 5 = (4)10
所以其 DFA 为下图所示：
1
1
1
0
0
0
1
2
0
0
3
1
0
4
1
lipeng 6
2008～2009 第一学期·编译原理作业参考
第三章 语法分析
3.2 考虑文法
S → aSbS | bSaS | ε
(a) 为句子 abab 构造两个不同的最左推导，以此说明该文法是二义的。
［解答］
S =>lm aSbS =>lm aεbS =>lm aεbaSbS
=>lm aεbaεbS =>lm aεbaεbε =>lm abab
S =>lm aSbS =>lm abSaSbS =>lm abεaSbS
=>lm abεaεbS =>lm abεaεbε =>lm abab
(b) 为 abab 构造对应的最右推导。
［解答］
S =>rm aSbS =>rm aSbaSbS =>rm aSbaSbε
=>rm aSbaεbε =>rm aεbaεbε =>rm abab
S =>rm aSbS =>rm aSbε => abSaSbε
=> abSaεbε => abεaεbε =>rm abab
(c) 为 abab 构造对应的分析树。
［解答］
3.10 构造下列文法的 LL(1)分析表
D → T L T → int | real L → id R R → , id R | ε
［解答］
= { int, real }
FIRST( TL )
D → T L
T → int
= { int }
FIRST( int )
T → real
FIRST( real ) = { real }
L → id R
FIRST(id R )
R → , id R FIRST( ,idR )
R → ε
= { id }
= { , }
= { ε }
FIRST( ε )
FOLLOW( R ) = FOLLOW( L ) = FOLLOW( D ) = { $ }
lipeng 7
2008～2009 第一学期·编译原理作业参考
D
T
L
R
int
real
D → TL D → TL
T → int
T → real
id
,
$
L → id R
R → ,idR R → ε
3.11 下面的文法是否为 LL(1)文法？说明理由。
S → A B | P Q x A → x y B → b c
→ d P | ε Q → a Q | ε
P
［解答］
S → A B | P Q x
FIRST( AB ) = FIRST( A ) = FIRSTt( xy ) = { x }
FIRST( PQx ) = { FIRST( P ) - { ε } } ∪ { FIRST( Q ) - { ε } }
∪ { x }
= FIRST( dP ) ∪ FIRST( aQ ) ∪ { x }
= { d, a, x }
因为FIRST( AB ) ∩ FIRST( PQx ) = { x } ≠ Φ，不满足LL(1)文法的定义。所以此文法不
是LL(1)文法。
3.16 给出接受文法
S → (L) | a
的活前缀的一个 DFA
L → L, S | S
［解答］
拓广文法
构造项目集过程：
‘ → S
S
S → (L) | a
L → L, S | S
I0 = closure( { [ S ‘→S · ] } ) = { S ‘→S ·, S → · (L), S → · a }
I1 = goto( I0, S) = closure( { [ S ‘→S · ] } ) = { S ‘→S · }
I2 = goto( I0, ( ) = closure( { [ S → ( · L) ] } )
= { S → ( · L, L → · L, S, L → · S, S → · (L), S → · a }
I3 = goto( I0, a ) = closure( { [ S → a · ] } ) = { S → a · }
I4 = goto( I2, L ) = closure( { [ S → ( L · ) ], [ L → L · , S ] } )
= { S → ( L · ), L → L · , S }
I2 = goto( I2, ( ) = closure( { [ S → ( · L) ] } )
= { S → ( · L, L → · L, S, L → · S, S → · (L), S → · a }
I5 = goto( I2, S ) = closure( { [ L → S · ] } ) = { L → S · }
I6 = goto( I4, ) ) = closure( { [ S → ( L ) · ] } ) = { S → ( L ) · }
I7 = goto( I4, , ) = closure( { [ L → L , · S ] } ) = { L → L , · S, S → · (L), S → · a }
I8 = goto( I4, S ) = closure( { [ L → L , S · ] } ) = { L → L , S · }
I2 = goto( I7, ( ) = closure( { [ S → ( · L) ] } )
lipeng 8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
