第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
东北大学 软件学院 编译方法 习题答案.doc
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
N -> 1 | 3 | 5 | 7 | 9 | BN
B -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B0
G1：
S->AB
A->aA| (
B->bc|bBc
G2：
S->aA|a
A->aS
B ( bc
B ( bBc( bbcc
B ( bBc( bbBcc ( bbbccc
A ( ε
A ( aA ( a
A ( aA ( aaA ( aa
S ( a
S ( aA ( aaS ( aaa
S ( aA ( aaS ( aaaA (aaaaS ( aaaaa
A->(SaA)|(a)
S
S
3.1 构造下列正规式相应的DFA。
NFA化为DFA：
±① b
±① ③
S->aS|bA|b
A->aS
A->aS
B->ε
NFA：令 ①-S, ②-A, ③-B
NFA化为DFA：
B ( bC
C ( aA | bD | ε
D ( aB | bD| ε
补充题1：构造与正规式(a|b)*c+|ab等价的DFA
(1) 与之等价的NFA为
(2) 消除ε边后的NFA为
(3)确定化过程如下：
A
b
c
+ A {1,2}
B {2,4}
C {2}
D {3}
B {2,4}
C {2}
E {2,5}
D {3}
C {2}
C {2}
C {2}
D {3}
- D {3}
D {3}
- E {2,5}
C {2}
C {2}
D {3}
得到的DFA为：
4.3 设有文法G[S]:
S->A
A->B | AiB
B->C | B+C
C-> )A* | (
(1) 原文法有左递归，利用A->A(|(可以化为
A->(A`
A`->(A`|(
S->A
A->BA`
A`->iBA`|(
B->CB`
B`->+CB`|(
C->)A*|(
(2) 扩展文法，增设一个产生式S`->S，作为主程序，得到的递归下降子程序的流程如下：
(3) 每个非终结符的FIRST集和FOLLOW集如下：
(4) 为产生式编号：
A->BA` ②
A`->iBA` ③ |( ④
B->CB` ⑤
B`->+CB` ⑥ |( ⑦
C->)A* ⑧ |( ⑨
S->rD
D->D,i | i
S`->S (0)
S->r D (1)
D->D , i (2)| i (3)
S->aA | bB
A->0A |1
B->0B |1
(1) 扩展文法：
S`->S (0)
S->a A (1)| b B (2)
A->0 A (3) |1 (4)
B->0 B (5) |1 (6)
(2) 从以上句柄识别器中可以看出，没有任何状态存在移进和规约冲突，因此，是LR(0)文法。根据句柄
E-> E + T | T
T-> T * F | F
F-> P↑F | P
P-> (E) | i
E -> T { + T}
T -> F { * F}
F-> P↑F | P
P -> ( E ) | i
E -> T { + T{GEQ(+)}}
T -> F { * F{GEQ(*)}}
F-> P↑F{GEQ(↑)} | P
P -> ( E ) | i {PUSH(i)}
E -> T E´
E´-> + T E´| (
T -> F T´
T´-> * F T´| (
F-> P↑F | P
P -> ( E ) | i
E -> T E´
E´-> + T {GEQ(+)} E´| (
T -> F T´
T´-> * F {GEQ(*)} T´| (
F-> P↑F{GEQ(↑)} | P
P -> ( E ) | i {PUSH(i)}
E -> T E´ ①
E´-> + T {GEQ(+)} E´②| - T {GEQ(-)} E´③| ( ④
T -> F T´⑤
T´-> * F {GEQ(*)} T´⑥| / F {GEQ(/)} T´⑦| ( ⑧
F -> i {PUSH(i)} ⑨ | ( E ) ⑩
LL(1)分析表如下：
A = 0;
B = 1;
L1 : A = A + B;
If B >= C goto L2;
B = B + 1;
L2: print A;
A=2*3+B/C;
B=2*3+B/C;
C=2*3+B/C;
T1=B-C
T2=A*T1
T3=D+1
T4=E-F
T5=T3*T4
W=T2/T5
2.2 设有文法 G[N]:
第 2 章 形式语言基础
N -> D | ND
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
(1) G[N]定义的语言是什么?
(2) 给出句子 0123 和 268 的最左推导和最右推导。
解答：
(1) L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或 L(G[N])={| 为可带前导 0 的正整数}
(2)
0123 的最左推导：N ND NDD NDDD DDDD 0DDD 01DD 012D 0123
0123 的最右推导：N ND N3 ND3 N23 ND23 N123 D123 0123
268 的最左推导：N ND NDD DDD 2DDD 26D 268
268 的最右推导：N ND N8 ND8 N68 D68 268
2.4 写一个文法，使其语言是奇数的集合，且每个奇数不以 0 开头。
解答：
N -> 1 | 3 | 5 | 7 | 9 | BN
B -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B0
2.7 下面文法生成的语言是什么？
G1：
S->AB
A->aA|
B->bc|bBc
解答：
B bc
B bBc bbcc
B bBc bbBcc bbbccc
……
A ε
A aA a
A aA aaA aa
……
∴S AB ambncn , 其中 m≥0,n≥1
G2：
S->aA|a
A->aS
| m≥0,n≥1}
即 L(G1)={ ambncn
S a
S aA aaS aaa
S aA aaS aaaA aaaaS aaaaa
……
∴S a2n+1 , 其中 n≥0
即 L(G2)={ a2n+1
| n≥0}
2.11 已知文法 G[S]:
S->(AS)|(b)
A->(SaA)|(a)
请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。
解答：
S
)(
S
(
(
A
a
S
)
b )
因为 S 不能 (a),
所以 (a)不是文法的句型。
没有短语、直接短语和句柄。
(
A
S
)
(
A
S
)
(
S a A
) (
b
)
因为 S (AS) (A(AS)) (A((SaA)S))
(A((SaA)(b))),
所以(A((SaA)(b)))是文法的句型。
短语：(A((SaA)(b)))，((SaA)(b))，(SaA)，
(b)
直接短语：(SaA)，(b)
句柄：(SaA)
第 3 章 自动机基础
3.1 构造下列正规式相应的 DFA。
(2) (a|b)*(aa|bb)(a|b)*
解答：
NFA：
aa
a
a
+①
b
a
+①
b
②-
b
bb
a
b
③
④
NFA 化为 DFA：
{1}
{1,3}
{1,4}
{1,2,3}
{1,2,4}
a
{1,3}
{1,2,3}
{1,3}
{1,2,3}
{1,2,3}
a
b
a
②-
b
b
{1,4}
{1,4}
{1,2,4}
{1,2,4}
{1,2,4}
+
-
-
{1}
{2}
{3}
{4}
{5}
a
b
+①
a
② a ④-
b
a
b
a
③ b
⑤-
b
最小化 DFA：初始划分：{1,2,3},{4,5} 最终划分：{1},{2},{3},{4,5}
这样，状态 4 与状态 5 等价，将 4 和 5 合并：
②
a
b
+①
b
a
③
a
b
a
④-
b
3.2 将下图中的(a)和(b)分别确定化和最小化。
a
0
+
-
a
a,b
(a)
1
解答：
(a) NFA 化为 DFA：
{0}
{0,1}
{1}
a
{0,1}
{0,1}
{0}
a
±①
+-{1}
- {2}
{3}
b
{1}
{1}
a
②-
b
b
a ③
b
b
a
0+
-
a
-
1
a
2
a
4
(b)
b
b
b
b
a
a
3
5
(b) 本身为 DFA，最小化 DFA：
a
{0,1},{2,3,4,5} {0,1},{2,4},{3,5}
a
±①
a
b
②
b
b
a
③
最小化 DFA：{1,2},{3}
a
±①
b
③
3.4 给出文法 G[S]，构造相应最小的 DFA。
S->aS|bA|b
A->aS
解： 原文法等价于：S->aS|bA|bB
A->aS
B->ε
NFA：令 ①-S, ②-A, ③-B
a
a
+① b
NFA 化为 DFA：
a
{1}
{1}
{1}
{2,3}
a
③-
②
b
b
{2,3}
+{1}
- {2}
a
+① b
②-
3.6 给出与下图中的 NFA 等价的正规文法 G。
a
+
Ａ
b
b
b
Ｃ
-
a
a
Ｂ
Ｄ -
b
解：G(A)：A aB | bD
B bC
C aA | bD | ε
D aB | bD| ε
补充题 1：构造与正规式(a|b)*c+|ab 等价的 DFA
(1) 与之等价的 NFA 为
(2) 消除ε边后的 NFA 为
(3)确定化过程如下：
+ A {1,2}
B {2,4}
C {2}
- D {3}
A
B {2,4}
C {2}
C {2}
b
C {2}
E {2,5}
C {2}
c
D {3}
D {3}
D {3}
D {3}
- E {2,5}
C {2}
得到的 DFA 为：
C {2}
D {3}
4.3 设有文法 G[S]:
第 5 章 语法分析
S->A
A->B | AiB
B->C | B+C
C-> )A* | (
(1) 将文法 G[S]改写为 LL(1)文法。
(2) 构造改写后的文法的递归子程序(给出流程图即可) 。
(3) 求经改写后的文法的每个非终结符的 FIRST 集和 FOLLOW 集。
(4) 构造相应的 LL(1)分析表，并给出输入串 (+)(*# 的分析过程。
解答：
(1) 原文法有左递归，利用 A->A|可以化为
A->A`
A`->A`|
可以得到，原文法可以化为 G`(S)：
S->A
A->BA`
A`->iBA`|
B->CB`
B`->+CB`|
C->)A*|(
(2) 扩展文法，增设一个产生式 S`->S，作为主程序，得到的递归下降子程序的流程如下：
主程序
子程序 S：
子程序 A：
子程序 A`：
子程序 B：
子程序 B`：
子程序 C：
(3) 每个非终结符的 FIRST 集和 FOLLOW 集如下：
S
A
A`
B
B`
C
First
{ ), ( }
{ ), ( }
{ i }
{ ), ( }
{ + }
{ ), ( }
Follow
{ # }
{ #, * }
{ # , * }
{ i, # ,*}
{ i,#,* }
{ +, i ,# ,*}
其中，follow(B)=first(A`)∪follow(A)= first(A`)∪{*}∪follow(S)={i}∪{*}∪{#}
(4) 为产生式编号：
S->A ①
A->BA` ②
A`->iBA` ③ | ④
B->CB` ⑤
B`->+CB` ⑥ | ⑦
C->)A* ⑧ |( ⑨
根据每个非终结符的 FIRST 集和 FOLLOW 集，可以得到各产生式的 select 集如下：
select(①)=first(A) ={), (}
select(②)= first(B) ={), (}
select(③)=first(iBA`)={i}
select(④)=first()∪follow(A`)={#,*}
select(⑤)=first(C)= {), (}
select(⑥)=first(+CB`)={+}
select(⑦)= first()∪follow(B`)={i,#,*}
select(⑧)=first()A*)={)}
select(⑨)=first(()={(}
根据以上 select 集，可以得到 LL(1)分析表：
相关推荐
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
