2007 一、简答题(共 15 分。) 1. 通过合并 LR(1)文法中的同心状态得到的 LALR(1)文法可能会产生哪些冲突?一定不会产生哪些冲突?为什么?(5 分) 答:可能会产生归约-归约冲突,一定不会产生移进-归约冲突。 因为在对 LR(1)合并同心集合时,有可能将原本没有冲突的同心集的项目集合并后造成一些归约项目向前搜索符集合的交集不是空,产生归约-归约冲突。但是由于文法本身已经是 LR(1)文法,因此可知,在项目集中一定不存在移进-归约冲突,也就是移进项目要求输入的终结符和任意归约项目的向前搜索符集合的交集都是空集。这样,在将同心集合并之后,移进项目要求输入的终结符和归约项目的向前搜索符集合的交集也还是空集。 2. 如果在 A 机器上我们有 C 语言编译器 CCA,也有它的源码 SA(用 C 语言写成)。如何利用它通过尽量少的工作来得到 B 机器的 C 语言编译器 CCB。(5 分) 答:A 机器上 C 语言编译器 CCA 的结构如下: CAA 其源码 SA 结构如下: CAC 首先,用 C 语言编写一个从 C 语言到 B 机器语言的编译器,成为 SB,其结构如下: CBC 第二步,将这个编译器放到 CCA 中进行编译,得到用 A 机器语言编写的,将 C 语言编译成B 机器代码的编译器,其过程和结构如下: CAACBCCBA 第三步,再将 SB 放入新得到的这个编译器中去编译,就得到了要求的编译器 CCB,其过程和结构如下: CBACBCCBB 3. Pascal 语言允许过程嵌套声明,C 语言的过程声明不能嵌套。在Pascal 程序中,数据分为局部数据、非局部数据,而C 程序中,数据分为局部数据和全局数据。因此,C 程序执行时只用到了控制链(动态链),不需要使用访问链(静态链)。试根据前面的已知说明,为什么Pascal 程序执行时需要使用访问链,而c 程序不需要。(5 分) 答:由于C 语言不允许嵌套的过程声明,因此所有的非局部名字都可以静态地绑定到所分配的存储单元,因此,可以不使用访问链。而Pascal 语言允许过程的嵌套,并使用静态作用域,确定用于名字的声明需要根据过程的嵌套层次来决定。和C 语言不同的是,Pascal 语言的非局部名字不一定就是全局的。运行时访问非局部名字的时候,我们首先要确定该非局部名字被绑定到的活动记录,因此就必须要用到访问链。 二、简单计算题(共25 分) 1. 令文法G[E]为 E→T | E+T | E-T T→F | T*F | T/F F→(E) | i (1) 证明E+T*F 是它的一个句型,指...