2 二时中女站吉有年个有不0所 石河子大学2003至2004学年第二学期 四、什么是二义性文法？请用例说明文法G®： (10分) 编译原理 课程试卷I E::=i (E)EAB A:=+1-1*|/ 是二义性文法。 三四 五大七八 总分 五、设有正则文法G[]: G[Z]: Z:=2 alAaIB助 A::=Bala 得分 B::=Ablb 请为其构造相应的有穷状态自动机。（⑨分） 一、名词解解：(2*5分，所有答案均写在客题纸上) 六、对于下列的文法和相应的句子，试给出这个句子的最 密 1、编译程序2、规范规钓3、句子4、语言5、算符优先文法 左推导，并且给出句型(SdG)<a的全部短语、直接短语、 句柄和最左素短语(12分) 封 二、填空（每空1分，共17分） 文法G[S]为： 1、编译过程划分为 S-SdT I T T--TG I G G-(S)I a 线 六个阶段，同时还伴有■ 两个过程。 2、如果两个文法 ,则称这两个文法是等价的文法，为了适合于 七、判断下面文法是否为山()文法。(12分) 某种分析技术，很可能需要进行文法的等价变换。 S-aD D--STel 3、语法分析器的输入是 ,其输出是 4 设 有 法 G1[S] T-bM M-bH B:cC B::=cCe C::=dS S::=aE H→Me 则 Vi=( 八、对于下面的文法(20分) 1 G[M]:1)S--VdB 2)V÷e 5、词法扫描器的任务是从， 中识别出一个个 3)V-e 4)B-a 6、分析句型时，应用算符优先分析技术时，每步被直接归约的 是 5)B -Bda 6)B+ 而应用LR分析技术时，每步被直接归钓的 是 ①构造其LR(O)项目集族及识别全部活前鳜的DFA: ②证明该文法是LR(0)文法，并构造其LR(0)分析表。 ⑧试用LR(0)分析表写出句子dada*的分析过程。 三、试写出下述语言的上下文无关文法(5*2分) 命腿组组长字 (1)组 第1页 (本试卷共1页
命题组组长签字： （ I ） 组 第 1 页 （本试卷共 1 页 ） 石河子大学 2003 至 2004 学年第二学期 编译原理 课程试卷 I 题 号 一 二 三 四 五 六 七 八 总分 得 分 一、名词解释：（2*5 分，所有答案均写在答题纸上） 1． 1、编译程序 2、规范规约 3、句子 4、语言 5、算符优先文法 二、填空（每空 1 分，共 17 分） 1、编译过程划分为 ， ， ， ， ， 六个阶段，同时还伴有 ， 两个过程。 2、如果两个文法 ，则称这两个文法是等价的文法，为了适合于 某种分析技术，很可能需要进行文法的等价变换。 3、语法分析器的输入是 ，其输出是 。 4 、 设有文法 G1[S] ： S::=bB B::=cC B::=cCe C::=dS S::=aE 则 VN={ } VT={ }。 5、词法扫描器的任务是从 中识别出一个个 。 6 、 分 析 句 型 时 ， 应 用 算 符 优 先 分 析 技 术 时 ， 每 步 被 直 接 归 约 的 是 ，而应用 LR 分析技术时，每步被直接归约的 是 。 二． 三、试写出下述语言的上下文无关文法（5*2 分） 1． L1={abn abn-1 | n≥1} 2. L2=写一个文法使其语言为奇数集，且每个奇数不以 0 开头。 四、什么是二义性文法？请用例说明文法 G[E]: （10 分） E::=i | (E) | EAE A::= + | - | * | / 是二义性文法。 五、设有正则文法 G[S]: G[Z]: Z::=Za|Aa|Bb A::=Ba|a B::=Ab|b 请为其构造相应的有穷状态自动机。(9 分) 六、对于下列的文法和相应的句子，试给出这个句子的最 左推导，并且给出句型(SdG)<a 的全部短语、直接短语、 句柄和最左素短语（12 分） 文法 G[S]为： S→SdT | T T→T<G | G G→(S) | a 七、判断下面文法是否为 LL(1)文法。（12 分） S→aD D→STe|ε T→bM M→bH H→M|ε 八、对于下面的文法（20 分） G[M]: 1) S →VdB 2) V →e 3) V →ε 4) B →a 5) B →Bda 6) B →ε ① 构造其 LR（0）项目集族及识别全部活前缀的 DFA。 ② 证明该文法是 LR（0）文法，并构造其 LR（0）分析表。 ③ 试用 LR（0）分析表写出句子 dada#的分析过程。 密 封 线 院 系 班 级 姓 名 学 号