2003年真题部分答案1．该正规式描述的语言是，所有不含子串001的0和1的串。
2．(a) S → Call | AssignCall → id (id_list)Assign → id (id_list) := id (id_list)id_list → id_list, id | id(b) 由于过程参数和下标表达式的中间代码是不一样的，在id 和id_list, id 向id_list 归约时，不知按哪种方式处理。
3．(a) E → E 1 *E 2{if E 1.sign = E 2.sign then E .sign := POS else E .sign := NEG } E → +E 1 { E .sign := E 1.sign }E → -E 1 {if E 1.sign = POS then E .sign := NEG else E .sign := POS}E → unsigned _integer {E .sign := POS}(b) 指令的解释如下：PUSH 值： 将值压栈NEG ： 将栈顶值取出，计算其相反数，把结果压入栈MUL ： 将栈顶和次栈顶的值取出，将它们相乘，把结果压栈 产生代码的翻译方案如下：E → E 1 *E 2 { emit(MUL)}E → +E 1 { }E → -E 1 {emit(…NEG ‟)}E → unsigned _integer {emit(…PUSH ‟ unsigned _integer .lexval )}4．对一个t 类型的数组a[ i 1 ][ i 2 ]…[ i n ]来说，表达式a 的类型是： pointer(array(0.. i 2 –1, … array(0.. i n –1, t)…))而表达式&a 的类型是：pointer(array(0.. i 1 –1, … array(0.. i n –1, t)…))2004年真题部分答案1．对活前缀ac 和bc 有效的项目集分别为{[A → c ·, d ], [B → c ·, e ]}和{[A → c ·, e ], [B → c ·, d ]}，它们是同心的。
合并后变成{[A →c ·, d /e ], [B →c ·, d /e ]}，产生归约-归约冲突。
因此该文法不是LALR(1)文法。
2． S → L . R S. val := L. val + R. val３ start ０ ０ １ . １ ０ １ ２S → L S. val := L. valL → L1 B L. val := L1. val⨯2 + B. valL → B L. val := B. valR → B R1R. val := (R1. val + B. val)/2R → B R. val := B. val/2B → 0 B. val := 0B → 1 B. val := 13．C语言对除结构类型以外的所有类型使用结构等价，而对结构类型使用名字等价。
第1个函数能通过结构等价的检查，而第2个函数不能通过名字等价的检查。
4．在结构的字节数较少时，则为该结构各域分别产生值传送指令。
在结构的字节数较多时，则根据值传送的源地址（b的地址）、目的地址（a 的地址）和该结构的长字数，产生简洁的重复传送指令，以提高效率。
2005年真题部分答案1． D → T L ;T → int | floatL → L, id | id2．给非终结符E一个综合属性v，其值可取lvalue或rvalue，分别表示E是左值表达式和右值表达式，那么语法制导定义如下（无输出则表示无错）：E'→ EE → E1 + E2 E.v := rvalueE → ( E1 ) E.v := E1.vE → E1 ++ if E1.v = rvalue then printf(“invalid lvalue in increment”);E.v := rvalueE →id E.v := lvalueE →num E.v := rvalue3．历史上，C语言中有参函数定义的一般形式是：类型标识符函数名（形式参数列表）形式参数声明对于这种形式的声明，C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的。
如本题中函数f1的声明是这种形式。
现在，ANSI新标准允许使用另一种方法声明形式参数，即在函数名后的括号中列出形式参数的同时，声明形式参数的类型。
本题中函数f2的声明是这种形式。
C语言编译器对于这种形式的函数声明是要进行实在参数和形式参数的个数和类型是否一致的检查的。
因此，在编译函数调用f2(10.0)时，会把浮点数10.0转换成整数10，并产生将整数10压栈的指令。
因此函数调用f2(10.0)的结果是100。
而在编译函数调用f1(10.0)时，会把浮点数10.0转换成双精度型（参见《编译原理习题精选》第5.8题），并产生将该双精度型数压栈的指令。
双精度数占8个字节。
它低地址的4个字节看成整数时正好是0。
因此函数调用f1(10.0)的结果是0（参见/~yiyun 上2003年编译原理试题第7题）。
4．优化时，通过复写转播和常量合并等会发现，对i 和j 的赋值都是无用赋值，可以删除，从而对i 和j 的存储分配没有必要。
2006年真题部分答案1．对于LL(1)分析方法，两个文法都不合适，左边的文法是左递归的，右边文法有公共左因子。
修改右边文法来适应LL(1)分析的要求，相对来说比较容易一些，因为只要提公共左因子。
对于LR 的各种分析方法，两个文法都适用，但是采用左边的文法更好一些。
用左边的文法时，分析器一边扫描一边归约，占用分析栈的空间较少。
而用右边的文法时，分析器要把所有的标识符都移进栈后才进行归约，因此使用较多的分析栈空间。
（结合语法制导的翻译，采用左边的文法还有好处：便于确定T 的类型属性在栈中的位置。
）2．用SLR(1)文法能定义的语言集合 ⊂ 用LALR(1)文法能定义的语言集合，用LALR(1)文法能定义的语言集合 ⊂ 用LR(1)文法能定义的语言集合。
3． 变量名 偏移 字节数c -1(%ebp) 1p -8(%ebp) 4ch -9(%ebp) 1m -24(%ebp) 124．buf 定义在文件link1.c 中，使用在文件link2.c 中。
由于：∙ 目标文件连接时并不检查名字的类型，因此，虽然两个文件对buf 的类型持不同的观点，但仍然能连接成目标程序；∙ 目标文件连接时，是让不同文件中的同一名字的地址相同。
因此，运行时，由于buf 的内容是100，取*buf 的值就是取地址100的内容。
该地址不在用户数据区内，因此报错。
2007年真题部分答案1、（10分）由正规式b*(abb*)*(a| ε)定义的语言是字母表{a, b}上不含子串aa 的所有串的集合。
最简DFA 如下：2、（10分）先给出接受该文法活前缀的DFA 如下：start 1 a b b 2I 0和I 3都只有移进项目，肯定不会引起冲突；I 2和I 4都无移进项目并仅含一个归约项目，也肯定不会引起冲突；在I 1中，E '的后继符号只有$，同第2个项目的展望符号“+”不一样，因此I 1也肯定不会引起冲突。
由此可以断定该文法是SLR(1)的。
3、（10分）语法制导定义如下。
S → id := E { S.type := if (lookup (id.entry) = bool and E.type = bool) or (lookup (id.entry) = int and E.type = int)then type_ok else type_error }E → E 1 and E 2 { E.type := if E 1.type = bool and E 2.type = bool then bool else type_error }E → E 1 + E 2 { E.type := if E 1.type = int and E 2.type = int then int else type_error }E → E 1 = E 2 { E.type := if E 1.type = int and E 2.type = int then bool else type_error }E → id { E.type := lookup (id.entry) }4、（5分）对于函数f1，局部变量x 声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x 。
由于这是一个合法的C 语言函数，因此编译器给出警告错误。
对于函数f2，由于局部变量x 的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。
5、（5分）使用非优化编译时，变量s, pi, r 在局部数据区都分配4个字节的空间。
使用优化编译时，由于复写传播，pi*r*r 变成3.14159*r*r ，pi=3.14159成为无用赋值而删去，函数中不再有pi 的引用，因此不必为pi 分配空间。
类似地，s=3.14159*r*r 也是一个无用赋值（表达式要计算，但赋值是无用的），也不必为s 分配空间。
这样，和非优化情况相比，局部数据区少了8个字节， 因此r 的地址向高地址方向移动了8个字节。
E ' →·EE →·E + idE →·idI 0E ' → E · E → E ·+ id I 1 E → id ·I 2 E id+ E → E +·id I 3 E → E + id · I 4id2008年真题部分答案1、正规式b *a(bb *a) *b *体现的特点是，每个a 的左边都有若干b ，除非a 是第一个字母。
该正规式定义的语言是：至少含一个a ，但不含子串aa 的所有a 和b 的串集。
最简DFA 如下：2、 消除左递归后的文法如下：B → 1 B 'B ' → 0 B ' | 1 B ' | ε相应的翻译方案如下：B → 1 {B '.i := 1 }B '{B.val := B '.val }B ' → 0 {B '1.i := B '.i ⨯ 2 } B '1 {B '.val := B '1.val }| 1 {B '1.i := B '.i ⨯ 2 +1} B '1 {B '.val := B '1.val }| ε {B '.val := B '.i }3、表达式&i 的类型表达式是pointer(long)，表达式&i -&j 的类型表达式是long 。
