四、消去下面文法中的无用产生式和单产生式。(10分) S-aB S-BC A-aA A-c A-DBb B-DB B-C D→BC→b 石河子大学2003至2004学年第二学期 院 编译原理 课程试卷A 五、给出下列文法所对应的正规式(6分) S-aA A-bAlBb B→aAbBa 三 四 五 六 八 总分 六、令文法GE为：E→T引E+T引E-TT+F|T*F引T/F 分 F+(E)|工证明E+T*F是它的一个句型，指出这个句型 的所有短语、直接短语和句柄。(12分) 密 一、名词解释：(25*4分，所有答案均写在答题纸上) 1、句子2、编译程序3、翻译程序4、简单优先文法 七、为R=1O)101构造NFAN使L(N)=L(R)(10分) 鬟 封 二、试写出下述语言的上下文无关文法(5*2分) 八、求出下面文法产生式的select集，并且正明是否 线 1、L1={ab'abn≥1) 为LL(1)文法。(12分) 2,试给出不以0打头和结尾的正偶数集合的上下文无关文法 1、A→BCe2、A→eDB3、B-&4、B-bCDE5、C-DaB 6、C-+ca 7、D-e8、D→dD9、E→eAf10、E-c 三、填空(1*12分) 1、编译程序的开发常常采用 九、对于下面的文法(S为开始符号)(18分) 技术。 1、构造其LR(O)项目巢族及识别全部活前缴DFA.(10分) 2、编译过程划分为 2、证明该文法是LR(O)的，并构造其LR(O)分折表。(8分) 六个阶段。 1、S→vI:T2、I-I.13、1-i4.T+r 3、多数程序设计语言的词法都能用」 文法来描述，而语法则用」 文法来描迷。 命题组组长签字： (A)组 第1页 (本试卷共1页)
命题组组长签字： （ A ） 组 第 1 页 （本试卷共 1 页 ） 石河子大学 2003 至 2004 学年第二学期 编译原理 课程试卷 A 题 号 一 二 三 四 五 六 七 八 总分 得 分 一、名词解释：（2.5*4 分，所有答案均写在答题纸上） 1、句子 2、编译程序 3、翻译程序 4、简单优先文法 二、试写出下述语言的上下文无关文法（5*2 分） 1、 L1={abn abn-1 |n≥1} 2、试给出不以 0 打头和结尾的正偶数集合的上下文无关文法. 三、填空（1*12 分） 1、编译程序的开发常常采用 ， ， ， 技术。 2、编译过程划分为 ， ， ， ， ， 六个阶段。 3、多数程序设计语言的词法都能用 文法来描述，而语法则用 文法来描述。 四、消去下面文法中的无用产生式和单产生式。（10 分） S→aB S→BC A→aA A→c A→ DBb B→DB B→C D→B C→b 五、给出下列文法所对应的正规式（6 分） S→aA A→bA|aB|b B→aA|bB|a 六、令文法 G[E]为：E→T|E+T|E-T T→F|T*F|T/F F→ (E)|I 证明 E+T*F 是它的一个句型，指出这个句型 的所有短语、直接短语和句柄。（12 分） 七、为 R=1(0|1)*101 构造 NFA N 使 L（N）=L（R）（10 分） 八、求出下面文法各产生式的 select 集，并且证明是否 为 LL（1）文法。（12 分） 1、A→BCc 2、A→eDB 3、B→ε 4、 B→bCDE 5、C→DaB 6、C→ca 7、D→ε 8、D→dD 9、 E→eAf 10、E→c 九、对于下面的文法（S 为开始符号）（18 分） 1、构造其 LR(0)项目集族及识别全部活前缀 DFA.（10 分） 2、证明该文法是 LR(0)的，并构造其 LR(0)分析表。（8 分） 1、S→vI:T 2、I→I,I 3、I→i 4、T→r 密 封 线 院 系 班 级 姓 名 学 号
