写出句子(a,a),a)的规范归钓过程及每一步的句柄， 石河子大学2003至2004学年第二学期 五、设有正则文法G[S】]: S::=Sc Bc B::Bb I Ab A::Aa|a 请为其构造相应的有穷状态自动机。（⑨分） 编译原理 课程试卷H 六、对于下列的文法和相应的句子，试给出这个句子的最 愿号 四 五大七八 总分 右推导，并且给出句子的全部短语、直接短语、句柄和最 得分 左素短语(12分) G(E)E--TIE+T T一FlT*FF(E)li 然 一、名词解瘠：(25分，所有答案均写在客题纸上) 七、设文法G(⑨：(12分) S+ωlasla 1、编译程序2、语言3、句柄4、文法5、算符优先文法 L-L,SIS (1)消除左递归和回测： 二、填空（每空1分，共17分） (2)计算每个非终结符的FRST和POLLOW: 1、编译过程划分为」 线 六个阶段，同时还件有■ 八、对于下面的文法(20分) 两个过程。 G[S]:1、S-E2、E-AalbB3、A→cAld4、B-cBld 2、编译程序与解释程序的区别在于」 ①构造其LR(O)项目集族及识别全部活前鱖的DFA。 3、设有文法G[S]: ②证明该文法是IR(0)文法，并构造其LR(0)分析表， S::=S:T S::=T T::=if E then S T::=V:=E T::=A ©试用LR(0)分析表写出句子acccd#的分析过程。 则=( }.ve{ 4、语法分析最常用的两类方法是 和 分析法。 5、词法扫描器的任务是从 _中识别出一个 6、多数程序设计语言的词法都能用文法来描述，而语法则用 文法 来描述。 三、试写出下述语言的上下文无关文法(5*2分) L1=ababn≥1 L2=c1Ealb),是W的反置,例如=abbb.bbba 四、已知文法为（共10分） G[s]: s→alA|(T) T→T,Sls 命腿组组长签字： H) 组 (本试在共1
命题组组长签字： （ H ） 组 第 1 页 （本试卷共 1 页 ） 石河子大学 2003 至 2004 学年第二学期 编译原理 课程试卷 H 题 号 一 二 三 四 五 六 七 八 总分 得 分 一、名词解释：（2*5 分，所有答案均写在答题纸上） 1． 1、编译程序 2、语言 3、句柄 4、文法 5、算符优先文法 二、填空（每空 1 分，共 17 分） 1、编译过程划分为 ， ， ， ， ， 六个阶段，同时还伴有 ， 两个过程。 2、编译程序与解释程序的区别在于 。 3、设有文法 G[S]: S::=S;T S::=T T::=if E then S T::=V:=E T::=A 则 VN ={ },VT={ }。 4、语法分析最常用的两类方法是 和 分析法。 5、词法扫描器的任务是从 中识别出一个个 。 6、多数程序设计语言的词法都能用 文法来描述，而语法则用 文法 来描述。 二． 三、试写出下述语言的上下文无关文法（5*2 分） 1． L1={abn abn-1 | n≥1} 2. L2={wcwR |w(a|b)*, wR是 W 的反置}，例如 W=abbb, w R =bbba 四、已知文法为（共 10 分） G[S]: S→a|∧|(T) T→T，S|S 写出句子((a，a)，a)的规范归约过程及每一步的句柄。 五、设有正则文法 G[S]: S::= Sc | Bc B::= Bb | Ab A::= Aa | a 请为其构造相应的有穷状态自动机。(9 分) 六、对于下列的文法和相应的句子，试给出这个句子的最 右推导，并且给出句子的全部短语、直接短语、句柄和最 左素短语（12 分） G(E) E→T|E＋T T→F|T * F F→(E)|i 七、设文法 G(S)：（12 分） S→(L)|aS|a L→L，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的 FIRST 和 FOLLOW； 八、对于下面的文法（20 分） G[S]：1、S→E 2、E→Aa|bB 3、A→cA|d 4、B→cB|d ① 构造其 LR（0）项目集族及识别全部活前缀的 DFA。 ② 证明该文法是 LR（0）文法，并构造其 LR（0）分析表。 ③ 试用 LR（0）分析表写出句子 acccd#的分析过程。 密 封 线 院 系 班 级 姓 名 学 号