五、给出下列文法所对应的正规式(6分) S→bSlaA A+aA[bB B-aAlbClb C-bSlaA 石河子大学2003至2004学年第二学期 六、令文法G[]为：B+TB+TT→P|T+PP+)1i 院 证明P+T+(+1)是它的一个句型，指出这个句型的所 编译原理 课程试卷B 有短语、直接短语和句柄。(12分) 四 五 六 八 总分 七、为R=(ab)"abb构造NFAN使的L(N)L(R)(10分) 分 八、求出下面文法各产生式的8e1ect集，并且证明是否为 LL(1)文法。(12分) 一、名词解释：(25*4分，所有答案均写在答题纸上) 1.S-aABC 2.S-3.A+a 4.A-+bbD 密 5.B-a 6.B-e 7.C-b 8.C-e 1、编译程序2、句子3、算符优先文法4、文法 9 D-c 10.D-e 鬟 封 九、对于下面的文法(S为开始符号)(18分) 二、试写出下述语言的上下文无关文法(5*2分) 线 (1)构造其LR(O)项目集族及识别全部活前缀DFA(8分) 1、L1={wewRwe0阳片，w是W的反置}，例如w=a000,wR=000a 2、试给出以0打头和结尾的正偶数集合的上下文无关文法. (2)证明该文法是LR(O)的，并构造其LR(O)分析表。(10分) 箬 1.S→BB 2.B-aB Ib 三、填空(112分) 1、编译程序的开发常常采用 技术。 2、编译过程划分为 六个阶段。 3、多数程序设计语言的词法都能用 文法来描述，而语法则用 文法来描述。 四、文法G=(B,S},{a,b,cl,P,S)其中P:S+Ac aB A→ab B+bc写出L(G[s])的全部元素。(10分) 命避组组长蜜字 (B组 第1页 (本试卷共1页)
命题组组长签字： （ B ） 组 第 1 页 （本试卷共 1 页 ） 石河子大学 2003 至 2004 学年第二学期 编译原理 课程试卷 B 题 号 一 二 三 四 五 六 七 八 总分 得 分 一、名词解释：（2.5*4 分，所有答案均写在答题纸上） 1、编译程序 2、句子 3、算符优先文法 4、文法 二、试写出下述语言的上下文无关文法（5*2 分） 1． 1、L1={wcwR|wє(0|a)*, wR是 W 的反置}，例如 W=a000, wR=000a 2、试给出以 0 打头和结尾的正偶数集合的上下文无关文法。 三、填空（1*12 分） 1、编译程序的开发常常采用 ， ， ， 技术。 2、编译过程划分为 ， ， ， ， ， 六个阶段。 3、多数程序设计语言的词法都能用 文法来描述，而语法则用 文法来描述。 四、文法 G=({A,B,S},{a,b,c},P,S) 其中 P: S→Ac|aB A→ab B→bc 写出 L(G[s])的全部元素。（10 分） 五、给出下列文法所对应的正规式（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 密 封 线 院 系 班 级 姓 名 学 号
