五、构造下列正规式相应的FA。(8分) 石河子大学2003至2004学年第二学期 1(0|1)101 编译原理 课程试卷G 六、对于下列的文法和相应的句子，试给出这个句子的最 院 右推导，并且给出句子的全部短语、直接短语、句柄和最 四 五 六 七 总分 左素短语(12分) G[s]:1、E-ET+2、E-T3、T-TE*4、T-F5、F-FP1 分 6、F→P7、P→E8、P一i句子iii*i+1 系 七、证明下述文法是否是L(1)文法(12分) 一、名词解舞：(2*5分，所有答案均写在答题纸上) 1、S-aAcB2、A→BaB3、S-BdS4、A→a5、BcAB 6、AaBc7、B+aScA8、B-b 密 1、编译程序2、文法3、句柄4、文法二义性5、算符优先文法 八、对于下面的文法(20分) 封 二、填空（每空1分，共18分） G[S]:1、S…A2、S-B3、A+aAb4、Ac 5、B+ah6、B-d 1、编译过程划分为 ①构造其LR(O)项目集族及识别全部话前鳜的DFA。 线 六个阶段，同时还伴有 两个过程。 ②证明该文法是LR(O)文法，并构造其LR(O)分析表。 2、简单优先文法与算符优先文法的区别在于」 ⑧试用LR(0)分析表写出句子acb#的分析过程。 箬 3.文法G[S]:1、S一Ac|aB2、A→ab3、B-bc是型文法，其语言是 4、编译程序的开发常常采用 技术。 5、在编译原理中，词法器的作用是 6、多数程序设计语言的词法都能用文法来描述，而语法则用 文法 来描述。 三、试写出下述语言的上下文无关文法(*2分) L1={aba'b"m,n≥1) L2={wcE(0la)*,w是W的反置}，例如W=a000,w=000a 四、已知文法为（共10分） G[E]:E--EE E-EE…aE-bE·c 试问--a-bc是不是L(G)的句子？若是，请给出该句子所有可能的语法树，若 不是，请说明理由。 命题组组长签字： (G)组 第1页 (本试在共1页)
命题组组长签字： （ G ） 组 第 1 页 （本试卷共 1 页 ） 石河子大学 2003 至 2004 学年第二学期 编译原理 课程试卷 G 题 号 一 二 三 四 五 六 七 八 总分 得 分 一、名词解释：（2*5 分，所有答案均写在答题纸上） 1． 1、编译程序 2、文法 3、句柄 4、文法二义性 5、算符优先文法 二、填空（每空 1 分，共 18 分） 1、编译过程划分为 ， ， ， ， ， 六个阶段，同时还伴有 ， 两个过程。 2、简单优先文法与算符优先文法的区别在于 。 3、文法 G[S]：1、S→Ac│aB 2、A→ab 3、B→bc 是 型文法，其语言是 。 4、编译程序的开发常常采用 、 、 、 技术。 5、在编译原理中，词法器的作用是 。 6、多数程序设计语言的词法都能用 文法来描述，而语法则用 文法 来描述。 二． 三、试写出下述语言的上下文无关文法（5*2 分） 1． L1={a m b n a n b m |m,n≥1} 2. L2={wcwR |w(0|a)*, wR是 W 的反置}，例如 W=a000, wR =000a 四、已知文法为（共 10 分） G[E]： E→-EE E→-E E→a E→b E→c 试问- -a-bc 是不是 L（G）的句子？若是，请给出该句子所有可能的语法树，若 不是，请说明理由。 五、构造下列正规式相应的 NFA。（8 分） 1（0│1）* 101 六、对于下列的文法和相应的句子，试给出这个句子的最 右推导，并且给出句子的全部短语、直接短语、句柄和最 左素短语（12 分） G[S]：1、E→ET+ 2、E→T 3、T→TE* 4、T→F 5、F→FP↑ 6、 F→P 7、P→E 8、P→i 句子 iii*i+↑ 七、证明下述文法是否是 LL（1）文法（12 分） 1、S→aAcB 2、A→BaB 3、S→BdS 4、A→a 5、B→cAB 6、A→aBc 7、B→aScA 8、B→b 八、对于下面的文法（20 分） G[S]：1、S→A 2、S→B 3、A→aAb 4、A→c 5、B→aBb 6、B→d ① 构造其 LR（0）项目集族及识别全部活前缀的 DFA。 ② 证明该文法是 LR（0）文法，并构造其 LR（0）分析表。 ③ 试用 LR（0）分析表写出句子 acb#的分析过程。 密 封 线 院 系 班 级 姓 名 学 号
