是 石河子大学2003至2004学年第二学期 二 三、试写出下述语言的上下文无关文法(52分) L1={abcn≥0，m>0J L2=(a0'1'bd"I n>0.m >0} 编译原理 课程试卷J 2. 四、请消去文法G[S: S::=Sa TbclTd T::Segh的左递归。(10 四 六 七 总分 分) 分 五、给出正规式R=(ab)*(ab*)ba等价的FA。 (8分) 系 一、名词解解：(2*5分，所有答案均写在答题纸上) 六、对于下列的文法和相应的句子，试给出这个句子的最 密 1、编译程序2、最右推导3、语言二义性4、语言5、算符优先文法 左推导，并且给出句型aAbcde的全部短语、直按短语、 句柄和最左囊短语(12分) 封 二、填空（每空1分，共18分） 文法G[S]为： 1、编译过程划分为 S-aAcBe A-bA→Ab B→d 线 六个阶段，同时还伴有 两个过程。 2、按Chomsky分类法，文法被分成(0型)短语结构文法、(1型)上下文有关文法、 七、判断下面文法是否为L(1)文法。(12分) 箬 (2 型) 文法、和(3 S-aH H-aMd d M-Ab e A-aM I e 型) 等四类文法。 3 诃 法 分 析 程 序 的基 本工作 八、对于下面的文法(20分) G[E]:1.E-E+F 2.E-T 3.T-TF 4.T-F 它的输入是 输出 5.F-F* 6.F-a7.F+b ①构造其LR(O)项目集族及识别全部活前鞭的DFA。 衫 文 法 G1[s] ②证明该文法是SLR(1)文法，并构造其SR(1)分析表。 B::=cC B::=cCe C::=dS S::=aE ⑧试用SLR(1)分析表写出句子b+b种的分析过程。 则 Vet 】,该文法 为 型文法。 5、 分析句型时，应用算符优先分析技术时，每步被直接归钓的 ,而应用R分析技术时，每步被直接归钓的 命题组组长签字： (」)组 第1页 (本试卷共1页)命题组组长签字： （ J ） 组 第 1 页 （本试卷共 1 页 ） 石河子大学 2003 至 2004 学年第二学期 编译原理 课程试卷 J 题 号 一 二 三 四 五 六 七 八 总分 得 分 一、名词解释：（2*5 分，所有答案均写在答题纸上） 1． 1、编译程序 2、最右推导 3、语言二义性 4、语言 5、算符优先文法 二、填空（每空 1 分，共 18 分） 1、编译过程划分为 ， ， ， ， ， 六个阶段，同时还伴有 ， 两个过程。 2、按 Chomsky 分类法，文法被分成（0 型）短语结构文法、（1 型）上下文有关文法、 （ 2 型 ） 文法、和（ 3 型） 等四类文法。 3 、 词 法 分 析 程 序 的 基 本 工 作 是 ， 它的输入是 ，输出 是 。 4 、 设有文法 G1[S] ： S::=bB B::=cC B::=cCe C::=dS S::=aE 则 VN={ } VT={ }，该文法 为 型文法。 5 、 分 析 句 型 时 ， 应 用 算 符 优 先 分 析 技 术 时 ， 每 步 被 直 接 归 约 的 是 ，而应用 LR 分析技术时，每步被直接归约的 是 。 二． 三、试写出下述语言的上下文无关文法（5*2 分） L1={ an b m c| n≥0,m>0 } 1． L2={ a0n 1 n bdm | n>0，m >0} 2. 四、请消去文法 G[S]： S::=Sa|Tbc|Td T::=Se|gh 的左递归。（10 分） 五、给出正规式 R＝（ab）*（a|b*）ba 等价的 NFA。 （8 分） 六、对于下列的文法和相应的句子，试给出这个句子的最 左推导，并且给出句型 aAbcde 的全部短语、直接短语、 句柄和最左素短语（12 分） 文法 G[S]为： S→aAcBe A→b A→Ab B→d 七、判断下面文法是否为 LL(1)文法。（12 分） S→aH H→aMd | d M→Ab | ε A→aM | e 八、对于下面的文法（20 分） G[E]： 1. E→E+F 2. E→T 3. T→TF 4. T→F 5. F→F* 6. F→a 7. F→b ① 构造其 LR（0）项目集族及识别全部活前缀的 DFA。 ② 证明该文法是 SLR（1）文法，并构造其 SLR（1）分析表。 ③ 试用 SLR（1）分析表写出句子 b+b*#的分析过程。 密 封 线 院 系 班 级 姓 名 学 号