五、对于下列的文法和相应的句子，试给出这个句子的最 右推导，并且给出句子的全部短语及句柄(10分) 石河子大学2003至2004学年第二学期 G[S]:1、S-AB2、S+c3、A-bA4、A+a5、B-aSb 6、B-c句子bbaacb 院 编译原理 课程试卷F 六、证明下列文法有二义性，此文法所描述的语言是什么 (10分) 四 六 七 总分 G[N]:1、N→SEIE 2.S→SDlD 3、E-012|4|68 4、D-01213|45l6171819 分 系 七、证明下述文法是山(1)文法(12分) 1、S-aAB2、s-ξ3、A+a4、A-bbC5、B-a 一、名词解释：(2*5分，所有答案均写在答题纸上) 6、B-ξ7、C-b8、C-ξ 密 1、编译程序2、规范规钓3、句子4、句柄5、算符文法 八、对于下面的文法(22分) 级 G[S]:1、S+A,2、S+B,3、A+aAb,4A+c 封 二、填空（每空1分，共20分） 5、B+aBb,6、B+d 1、编译过程划分为 ①构造其LR(0)项目集族及识别全部活前缀的DFA。 线 六个阶段，同时还伴有 ②证明该文法是LR(O)文法，并构造其LR(0)分析表。 两个过程。 ③试用LR(0)分析表写出句子acb#的分析过程。 2、简单优先文法与算符优先文法的区别在于」 箬 3、乔姆斯基定义的四种形式语言文法分别为： 型文法 型文法（又称 文法)， 型文法（又称 文法)， 型文法（又称文法）。 4、编译程序的开发常常采用 技术。 三、生成下述语言的上下文无关文法（共10分） 1、L1=0W1∈(0|a),是W的反置)，例如=a000.W=000a。 2、L2={abab1n≥1] 四、写出下面文法的语言。(6分) G[S]:S-Az S-xB A-xy B-bc 命题组组长签字： (F)组 第1页 (本试卷共1页)
命题组组长签字： （ F ） 组 第 1 页 （本试卷共 1 页 ） 石河子大学 2003 至 2004 学年第二学期 编译原理 课程试卷 F 题 号 一 二 三 四 五 六 七 八 总分 得 分 一、名词解释：（2*5 分，所有答案均写在答题纸上） 1、编译程序 2、规范规约 3、句子 4、句柄 5、算符文法 二、填空（每空 1 分，共 20 分） 1、编译过程划分为 ， ， ， ， ， 六个阶段，同时还伴有 ， 两个过程。 2、简单优先文法与算符优先文法的区别在于 。 3、乔姆斯基定义的四种形式语言文法分别为： 型文法， 型文法（又称 文法）， 型文法（又称 文法）， 型文法 （又称 文法）。 4、编译程序的开发常常采用 、 、 、 技术。 三、生成下述语言的上下文无关文法（共 10 分） 1、 L1={WCWR│W∈（0│a）*，W R是 W 的反置}， 例如 W=a000 ,WR =000a。 2、L2={abn abn-1│n≥1} 四、写出下面文法的语言。（6 分） G[S]： S→Az S→xB A→xy B→bc 五、对于下列的文法和相应的句子，试给出这个句子的最 右推导，并且给出句子的全部短语及句柄（10 分） G[S]：1、S→AB 2、S→c 3、A→bA 4、A→a 5、B→aSb 6、 B→c 句子 bbaacb 六、证明下列文法有二义性，此文法所描述的语言是什么 （10 分） G[N]：1、N→SE|E 2、S→SD|D 3、E→0|2|4|6|8 4、D→0|1|2|3|4|5|6|7|8|9 七、证明下述文法是 LL（1）文法（12 分） 1、S→aAB 2、S→ξ 3、A→a 4、A→bbC 5、B→a 6、B→ξ 7、C→b 8、C→ξ 八、对于下面的文法（22 分） 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#的分析过程。 密 封 线 院 系 班 级 姓 名 学 号
