发布时间 : 星期三 文章(整理完)编译原理网上作业题参考答案20121101更新完毕开始阅读
I 1 2 3
Ia 2 2 2 Ib 3 3 4.请写出在∑=(a,b)上,不是a开头的,但以aa结尾的字符串集合的正规表达式,并构造与之等价状态最少的DFA。(﹡﹡﹡)
解答:根据题意,不以a开头就意味着以b开头,且以aa结尾的正规式为:b(a|b)* aa
根将图1所示的NFA确定化,如图2所示。
NFA将图1所示的NFA确定化,如图
从图2可知已为最简状态,由于开始状态0只能输入字符b而不能与状态1合并,而状态2和状态3面对输入符号的下一状态相同,但两者一为非终态、一为终态,故也不有合并,故图2所示的状态转换矩阵已是最简的DFA,如图3所示据正规式画出NFA,如图1所示。
图2 状态转换矩阵
图3 最简DFA
5. 人运狼、羊、菜过河,一次运一件,不让羊吃掉菜,也不让狼吃掉羊,画出渡河的状态转换图。可否
将其抽象为一个有限自动机。(﹡﹡﹡)
解答:先写出渡河的方法,串中对象顺序为人来回渡河时所运的货物的顺序: ①羊空菜羊狼空羊 ②羊空狼羊菜空羊
现给出一个NFA: M=(Σ,Q,0,{9},δ) 其中Σ={羊,空,菜,狼} Q={0,1,2,3,4,5,6,7,8,9} 转形函数
δ(0,羊)=1, δ(1,空)=2, δ(2,菜)=3, δ(2,狼)=5 δ(3,羊)=4, δ(5,羊)=6, δ(4,狼)=7, δ(6,菜)=7 δ(7,空)=8, δ(8,羊)=9
6.对于正规表达式 (a|b)a(a|b) 构造最小状态的DFA。(﹡﹡) 解答:①NFA M:
*
②DFA M:
③化简: ②中的DFA M中没有等价状态,因此为最小化的DFA M。
第四章 语法分析
多项选择题:
1. AD 2. CE 3. ACDE 4. CE 5. ABCE 6. ACDE
填空题:
1.对于一个文法,如果能够构造 (LR(0)文法) 。使得它的 (每个入口) 均是唯一确定的,则称该文法为LR文法。(﹡)
2.字的前缀是指该字的 (任意首部) 。(﹡)
3.活前缀是指 (规范句型) 的一个前缀,这种前缀不含 (句柄) 之后的任何符号。(﹡)
4.在LR分析过程中,只要 (输入串) 的已扫描部分保持可归约成一个 (活前缀) ,则扫描过的部分正确。(﹡)
5.将识别 (活前缀) 的NFA确定化,使其成为以 (项目集合) 为状态的DFA,这个DFA就是建立 (LR分析算法) 的基础。(﹡﹡)
6.A→α·称为 (归约) 项目;对文法开始符S′→α·为 (接受) 项目;若a为终结符,则称A→α·aβ为 (移进) 项目;若B为非终结符,则称A→α·aβ为 (待约) 项目。(﹡﹡)
7.LR(0)分析法的名字中“L”表示 (自左至右分析) ,“R”表示 (采用最右推导的逆过程即最左归约) ,“0”表示 (向右查看0个字符) 。(﹡﹡)
判断题:
1.正确
简答题: 综合题:
1.构造下面文法的LL(1)分析表。(﹡﹡﹡) D→TL T→int | real L→id R R→, id R | ε
解答:LL(1)分析表见下表。
分析 虽然这个文法很简单,我们还是从求开始符号集合和后继符号集合开始。 FIRST(D)=FIRST(T)={int, real} FOLLOW(D)=FOLLOW(L) ={#} FIRST(L)={id} FOLLOW(T)={id} FIRST(R)={,, ε} FOLLOW(R)={#}
有了上面每个非终结符的FIRST集合,填分析表时要计算一个产生式右部α的FIRST(α)就不是件难事了。
填表时唯一要小心的时,ε是产生式R→ε右部的一个开始符号,而#在FOLLOW(R)中,所以R→ε填在输入符号#的栏目中。
表 LL(1)分析表
2.下面文法G[S]是否为LL(1)文法?说明理由。(﹡﹡) S→AB|PQx A→xy B→bc P→dP|ε Q→aQ|ε
解答:该文法不是LL(1)文法,见下面分析中的说明。 分析 只有三个非终结符有两个选择。
(1)P的两个右部dP和ε的开始符号肯定不相交。 (2)Q的两个右部aQ和ε的开始符号肯定不相交。
(3)对S来说,由于x∈FIRST(AB),同时也有x∈FIRST(PQx)(因为P和Q都可能为空)。所以该文法不是LL(1)文法。
3.设有以下文法:(﹡﹡﹡) G[S]:S→aAbDe|d A→BSD|e B→SAc|cD|ε D→Se|ε
(1)求出该文法的每一个非终结符U的FOLLOW集。 (2)该文法是LL(1)文法吗? (3)构造C[S]的LL(1)分析表。
解答:(1)求文法的每一个非终结符U的FOLLOW集的过程如下: 因为:
①S是识别符号,且有A→BSD、B→SAc、D→Se,所以FOLLOW(S)应包含 FIRST(D)∪FIRST(Ac) ∪FIRST(e) ∪{#} ={a,d}∪{a,d,c,e}∪{e}∪{#} ={a,c,d,e#}
②又因为A→BSD和D→ε,所以FOLLOW中还包含FOLLOW(A)。 因为S→aAbDe和B→SAc,所以
FOLLOW(A)=FIRST(bDe)∪FIRST(c)={b,c} 综合①、②得FOLLOW(S)={a,d,c,e,#}∪{a,b,c,d,e,#}