发布时间 : 星期日 文章(整理完)编译原理网上作业题参考答案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,#}