03答案。
第一题：判断题（15分）
1、共有15道小题，每小题1分， 15×1＝15分。
2、答案：第二题：简述**优化的概念和常用的几种优化技术 （5分)
1、**优化的概念（2分）
参***：所谓**优化，实质上是对**进行等价变换，使得变换后的**运行结果与变换前的**运行结果相同（1分），但运行速度或占用的存储空间加大（1分）。
2、常用的优化技术（3分）
参***：删除多余运算、**外提、强度削弱、变换循环控制条件、合并已知变量与复写传播、删除无用赋值等（各项顺序任意，每对2项加1分）。
第三题：（12分）
1、证明（3分）：因为存在推导序列e=>ee+=>ee*e+=>fe*e+=>ie*e+=>if*e+=>ii*e+=>ii*f+=>ii*i+，即有eii*i+成立（2分），且ii*i+所含符号全部为终结符（1分），所以，ii*i+是文法的一个句子。
2、语法树（3分）
3、句型分析（6分）
句型ii*i+相对于e的短语有： i1i2*i3+, i1i2*, i1,i2,i3 （3分）
句型ii*i+相对于f的短语有： i1,i2,i3 （1分）
句型ii*i+相对于f→i的直接短语有：i或i1,i2,i3 （1分）
句型ii*i+的句柄为： i1 （1分）
说明：（1）短语、直接短语的说明可不具体指明所相对的非终结符或规则。
2）没用下标区分i1,i2,i3 的扣1分。
3）短语每错两个扣1分。
第四题：（12分）
1、nfa m （3分）
2、确定化（3分）
步骤如下表所示（可省）：
将集合t0至t7各用一个状态表示，确定化后所得dfa m如下：
3、最小化 （3分）
步骤如下表所示（可省）：
最后有六个不可再分割的子集，每个子集对应一个状态，得最小化dfa如下：
说明：此大题答案只供参考，可以是其他答案，只要功能等价即可。
第五题： (18分)
1、给出(+,b,+)的最左推导：(2分)
s=>(t)=>t,s)=>s,s)=>s)=>t))=t,s)) s,s))=b,s)) b,+)
2、证明：(3分)
计算各条规则的select集及左部相同规则的select集的交集如下：
显然，g[s]不是 ll(1) 文法。
3、（1）将g[s]改写如下：(4分)
g[s]：s→b|+|t)
t’→,s t’|ε
t→s t’
显然，改写后的g[s]是 ll(1) 文法。
2）**分析表：(4分)
4、输入串(b,+)#的分析过程：(5分)
第六题： (18分)
1、g[e’]中各非终结符的firstvt、lastvt 集：（6分）
由firstvt、lastvt 集构造≮和≯如下：
2、（1）优先矩阵为：（5分）
2）该文法是算符优先文法（2分）。
3、输入串i+i# 的算符优先分析过程：（5分）
第七题 (20分)
对任意给定的一个上下文无关文法g[s]：
1、判断是否为lr(0)文法的步骤：(4分)
1）构造g[s]的lr(0)项目集规范族。
2）检查各项目集中是否存在移进—归约冲突或归约—归约冲突。如果有某一个项目集中同时存在移进项目和归约项目，或者同时存在两个或两个以上的归约项目，则该项目集存在移进—归约冲突或归约—归约冲突。
3）如果所有状态中都不存在移进—归约冲突或归约—归约冲突，说明g[s]是lr(0)文法。否则，说明g[s]不是lr(0)文法。
2、 判断是否为slr(1)文法的步骤：(4分)
1）构造g[s]的lr(0)项目集规范族。
2）检查各项目集中是否存在移进—归约冲突或归约—归约冲突。如果有某一个项目集中同时存在移进项目和归约项目，或者同时存在两个或两个以上的归约项目，则该项目集存在移进—归约冲突或归约—归约冲突。
3）如果对各个项目集i中存在的移进—归约冲突或归约—归约冲突都可通过如下引入follow集的方法解决，即对i=，若所有含有a和b的句型中，满足：follow(a)∩follow(b)=φ且follow (a)∩=follow(b)∩ 则在状态i中面临输入符a的动作可由下面规定决策：若a=b，则移进；若a∈follow(a)，则用a → 归约，若a∈follow(b)，则用b→δ.
归约；此外报错。也即在根据lr(0)项目集规范族构造lr分析表时，遇到归约项目时，只在该项目左边非终结符的follow集元素列置归约标记rj。如果这样构造出来的lr分析表不存在冲突，则 g[s]为slr（1）文法。
否则，g[s]不是slr(1)文法。
3、判断是否为lr(1)文法的步骤：(4分)
1）构造g[s]的lr(1)项目集规范族（注意各个项目都带有向前搜索符号集）。
2）检查各项目集中是否存在移进—归约冲突或归约—归约冲突。如果有某一个项目集中同时存在移进项目和归约项目，或者同时存在两个或两个以上的归约项目，则该项目集存在移进—归约冲突或归约—归约冲突。
3）如果对各个项目集i中存在的移进—归约冲突或归约—归约冲突都可通过考虑项目所带的向前搜索符号集来解决，即根据lr(1)项目集规范族构造lr分析表时，遇到归约项目时，只在该项目所带的向前搜索符号集元素列置归约标记rj。如果这样构造出来的lr分析表不存在冲突，则 g[s]为lr（1）文法。否则，g[s]不是lr(1)文法。
4、判断是否为lalr(1)文法的步骤：(4分)
1）构造g[s]的lr(1)项目集规范族，并进一步合并lr(1)项目集规范簇中的所有同心集。
2）检查合并同心集后各项目集中是否存在移进—归约冲突或归约—归约冲突。如果有某一个项目集中同时存在移进项目和归约项目，或者同时存在两个或两个以上的归约项目，则该项目集存在移进—归约冲突或归约—归约冲突。
3）如果对各个项目集i中存在的移进—归约冲突或归约—归约冲突都可通过考虑项目所带的向前搜索符号集来解决，即根据合并同心集后的lr(1)项目集规范族构造lr分析表时，遇到归约项目时，只在该项目所带的向前搜索符号集元素列置归约标记rj。如果这样构造出来的lr分析表不存在冲突，则 g[s]为lalr（1）文法。否则，g[s]不是lalr(1)文法。
5、四类文法的相互关系： (4分)
一个lr(0)文法肯定是slr(1)文法；一个slr(1)文法肯定是lalr(1)文法；而一个lalr(1)文法肯定是lr(1)文法。反之，不成立。
编译原理作业1答案
计算机科学系 2012春季学期。编译原理 第一次作业参 一 下列正则表达式定义了什么语言 用尽可能简短的自然语言描述 1.b ab ab 所有含有偶数个a的由a和b组成的字符串。2.c a a c b a b c c b b c a a b c 答案一 所有至少含有1个a和1个b的由a，b和c组成的...
编译原理作业7答案
软件学院 2012秋季学期。编译原理 第七次作业参 一 证明下列文法。s aa bac dc bdaa d是lalr 1 文法但不是slr 1 文法。构造lr 1 自动机 没有需要合并的状态 没有状态存在冲突，因而是lalr 1 文法。构造lr 0 自动机 在状态i6，由于 a follow a 因...
编译原理作业20150515 答案
1.写一文法，使其语言是偶正整数的集合。要求 1 允许0打头 2 不允许0打头。解 1 允许0打头且含0的偶正整数集合的文法为 n 0 d e n e 0 d 1 3 5 7 9 e 2 4 6 8 2 不允许0打头的偶正整数集合的文法为 r d e n e n 0 d e n e 0 d 1 3 ...