石河子大学：《编译原理》课程教学资源（试卷习题）第三套

5、任何LR(K)文法都是无二义性的.() 6、文法的二义性和语言的二义性是两个不同的概念。() 7、简单优先分析法每次都是对最左素短语进行归钓。() 8、文法中不含左公共因子是L(1)文法的充分必要条件。() 石河子大学2003至2004学年第二学期 9、所有的优先矩阵都能线性化。( 10、对于每个NFA,都存在一个与之等价的DFA。 编译原理 课程试卷0 四、试写出下述语言的上下文无关文法(52分) 1.L={≥1 2、l={a'b'c|ni≥1，i≥0j 题号 四 五六 总分 五、对于下列的文法和相应的句子，试给出这个句子的最 得分 右推导，并且给出句子的全部短语，直接短语和句柄， 最左素短语。(12分) E一ET+ E一T T-F F→FP↑F→P 一、名词解释：(2*5分，所有答案均写在答题纸上) P-E P-i 句子iiii计↑ 1、编译程序2、文法3、句柄4、语言二义性 六、给出下述文法所对应的正规式：(5分) 封 5、算符优先文法 S→0A1B A-1S11 B--0510 线 二、填空(120分) 七、求下列文法各产生式SBCT集，判断是否为山()文 1、编译过程划分为 法。(10分) 六个阶段。 1.S-AB 2.S-PQx 3.A-xy 4.A-m 5.B--bC 2、编译程序各阶段的工作都涉及到 6.C-bC 7.C-E 8.P-+pP 9.P-e 10.Q-qQ 11.Q-8 3、高级语言的语言处理程序分为编译程序和解释程序两种。编译程序有 六个阶段，而解释程序通常缺少 和 上·与编译系统相比， 八、对下列文法：(23分) 解释系统执行速度 ,占用内存 4、山(1)分析法中，第一个L的含义是 ,第二个L的含义是 1、构造其LR(O)项目集族及识别全部活前簸D队（⑧分） “1”的含义是 2、构造该文法的SLR(1)分析表。(8分) 5、已知文法G(S):S一A0B1,A一S11,B一S00,则由此文法产生的只含有四个符 3、给出句子bebf的分析过程。(7分) 号的句子是， ,该文法是Cho阳sky的型文法。 1、s-S2、s-bRsT 3、S-bR 4、R-dsa,5、R-e6、T-fRa7、T→f 三、判断对错（错的打“×”，对的打“√”）(10*1分) 1、编译程序是一种常用的系统软件。( 2、编译程序生成的目标程序一定是可执行的程序。() 3、描述一个语言的文法是不唯一的。(：) 4、若一个文法是递归的，则它所产生的语言必定是无穷的。() 命腿组组长蜜字 C）组 第1页 (本试卷共1奥)

命题组组长签字： （ C ） 组 第 1 页 （本试卷共 1 页 ） 石河子大学 2003 至 2004 学年第二学期 编译原理 课程试卷 C 题 号 一 二 三 四 五 六 七 八 总分 得 分 一、名词解释：（2*5 分，所有答案均写在答题纸上） 1、编译程序 2、文法 3、句柄 4、语言二义性 5、算符优先文法 二、填空（1*20 分） 1、编译过程划分为 ， ， ， ， ， 六个阶段。 2、编译程序各阶段的工作都涉及到 ， 。 3、高级语言的语言处理程序分为编译程序和解释程序两种。编译程序有 六个阶段，而解释程序通常缺少 和 。与编译系统相比， 解释系统执行速度 ，占用内存 。 4、LL（1）分析法中，第一个 L 的含义是 ，第二个 L 的含义是 ， “1”的含义是 。 5、已知文法 G（S）：S→A0|B1，A→S1|1，B→S0|0，则由此文法产生的只含有四个符 号的句子是 ， ， ， ，该文法是 Chomsky 的 型文法。 三、 判断对错（错的打“”，对的打“”）（10*1 分） 1、编译程序是一种常用的系统软件。（ ） 2、编译程序生成的目标程序一定是可执行的程序。（ ） 3、描述一个语言的文法是不唯一的。（ ） 4、若一个文法是递归的，则它所产生的语言必定是无穷的。（ ） 5、任何 LR（K）文法都是无二义性的。（ ） 6、文法的二义性和语言的二义性是两个不同的概念。（ ） 7、简单优先分析法每次都是对最左素短语进行归约。（ ） 8、文法中不含左公共因子是 LL（1）文法的充分必要条件。（ ） 9、所有的优先矩阵都能线性化。（ ） 10、对于每个 NFA，都存在一个与之等价的 DFA。 四、试写出下述语言的上下文无关文法（5*2 分） 1、L={a n bbn |n≥1} 2、L={a n b n c i | n≥1，i ≥0} 五、对于下列的文法和相应的句子，试给出这个句子的最 右推导，并且给出句子的全部短语，直接短语和句柄， 最左素短语。（12 分） E→ET+ E→T T→TE* T→F F→FP↑ F→P P→E P→i 句子 iii*i+↑ 六、给出下述文法所对应的正规式：（5 分） S→0A|1B A→1S|1 B→0S|0 七、求下列文法各产生式 SELECT 集，判断是否为 LL(1)文 法。（10 分） 1.S→AB 2.S→PQx 3.A→xy 4.A→m 5.B→bC 6.C→bC 7.C→ε 8.P→pP 9.P→ε 10.Q→qQ 11.Q→ε 八、对下列文法：（23 分） 1、构造其 LR(0)项目集族及识别全部活前缀 DFA.(8 分) 2、构造该文法的 SLR（1）分析表。（8 分） 3、给出句子 bebef 的分析过程。（7 分） 1、S＇→S 2、S→bRST 3、S→bR 4、R→dSa, 5、R→e 6、T→fRa 7、T→f 密 封 线 院 系 班 级 姓 名 学 号

五、给出下列文法所对应的正规式(6分) S-bSlaA A-aAlbB B-aAlbClb C-bSlaA 大、令文法G[E]为：B→TE+TT→P|T+PP→)川i 正明P+T+(+1)是它的一个句型，指出这个句型的所 有短语、直接短语和句柄。(12分) 七、为R=(ab)bb构造NFAN使的L(ND=L(R)(10分) 八、求出下面文法各产生式的slct集，并且正明是香为 LL(1)文法。(12分) 1.S-aABC 2.S-e3.A-a 4.A-bbD 5.B-a 6B8 7.c-b 8.C-e 9 D-c 10.D-e 九、对于下面的文法(S为开始符号)(18分) (1)构造其LR(O)项目集族及识别全部话前缀DFA.(8分) (2)证明该文法是LR(O)的，并构造其LR(O)分析表。(10分) 1.S→BB 2.B→aB|b 命腿组组长签字 (C)组 第1页 (本试卷共1)

命题组组长签字： （ C ） 组 第 1 页 （本试卷共 1 页 ） 五、给出下列文法所对应的正规式（6 分） S→bS|aA A→aA|bB B→aA|bC|b C→bS|aA 六、令文法 G[E]为：E→T|E+T T→P|T+P P→(E)|i 证明 P+T+（E+i）是它的一个句型，指出这个句型的所 有短语、直接短语和句柄。（12 分） 七、为 R=(a|b)* abb 构造 NFAN 使的 L（N）=L（R）（10 分） 八、求出下面文法各产生式的 select 集，并且证明是否为 LL（1）文法。（12 分） 1．S→aABC 2.S→ε 3.A→a 4. A→bbD 5.B→a 6.B→ε 7.C→b 8.C→ε 9 D→c 10.D→ε 九、对于下面的文法（S 为开始符号）（18 分） （1）构造其 LR(0)项目集族及识别全部活前缀 DFA.（8 分） （2）证明该文法是 LR(0)的，并构造其 LR(0)分析表。（10 分） 1．S→BB 2.B→aB│b