陈意云编译原理全套陈意云编译原理全套99_02

1999年 1．（10分）构造一个DFA，它接受(((0, 1(上0和1的个数都是偶数的字符串。 2．（5分） 现有句型( b( l( 和产生式A( b(，分别指出LL（1）方法和LR（1）方法在扫描到此句型的什么位置决定用此产生式？ 3．（15分）在PASCAL语言中，简单类型的变量的声明例举如下： m, n : integer p, q, r : real 为这样的声明写一个LR（1）文法（为简单起见，变量标识符都用id表示），并根据你的文法写一个语法制导定义（或叫做为你的文法加上语义动作），它将变量的类型填入符号表。 4．（5分） 下面的PASCAL程序在VAX机器上运行时，报告存储访问错，为什么？ program strange(output); var p: ( integer; begin p (= nil; if (p <> nil) and (p( = 10) then writeln(10) else writeln(‘nothing’) end. 5．（10分）PASCAL语言和C语言都是栈式分配的语言。它们在语言构造上的哪些区别，使得C语言允许一函数的返回值类型是函数类型（实际是函数指针类型），而PASCAL语言不允许。 6．（5分）代码优化中的强度削弱是什么意思，举一例加以说明 2000年 1．（8分）Pascal语言无符号数的正 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 义如下： num ( digit+ (.digit+)? (E(+|-)? digit+)? 其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。 2．（10分）一个非LR（1）的文法如下： L ( MLb | a M ( ( 请给出所有有移进－归约冲突的LR（1）项目集，以说明该文法确实不是LR（1）的。 3．（14分）程序的文法如下： P ( D D ( D ; D | id : T | proc id ; D ; S （1）写一个语法制导定义，打印该程序一共声明了多少个id。 （2）写一个 翻译 阿房宫赋翻译下载德汉翻译pdf阿房宫赋翻译下载阿房宫赋翻译下载翻译理论.doc 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，打印该程序每个变量id的嵌套深度。 4．（5分）C语言程序引用sizeof函数时，该函数的计算是在编译该程序时完成，还是在运行该程序时完成？说明理由。 5．（5分）一个C语言程序如下： func(i1,i2,i3) long i1,i2,i3; { long j1,j2,j3; printf("Addresses of i1,i2,i3 = %o,%o,%o\n",&i1,&i2,&i3); printf("Addresses of j1,j2,j3 = %o,%o,%o\n",&j1,&j2,&j3); } main() { long i1,i2,i3; func(i1,i2,i3); } 该程序在SUN工作站上的运行结果如下： Addresses of i1,i2,i3 = 35777773634,35777773640,35777773644 Addresses of j1,j2,j3 = 35777773524,35777773520,35777773514 从上面的结果可以看出，func 函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。 6．（8分）一个C语言程序如下： main() { func(); printf("Return from func\n"); } func() { char s[4]; strcpy(s,"12345678"); printf("%s\n",s); } 该程序在PC机linux操作系统上的运行结果如下： 12345678 Segmentation fault (core dumped) 试 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 为什么会出现这样的运行错误。 2001年 1.（7分）用状态转换图表示接收(a|b)(aa的确定的有限自动机。 2．（10分）为语言 L ＝ {ambn | 0 ( m ( 2n}（即a的个数不超过b的个数的两倍） 写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。） 3．（8分）为下面文法添加语义规则（或叫动作子程序），输出S(产生的二进制数的值，如输入是101时，输出5。 S( ( S S ( S B | B B ( 0 | 1 4．（5分）C语言程序引用sizeof（求字节数运算符）时，该运算是在编译该程序时完成，还是在运行该程序时完成？说明理由。 5．（15分）一个C语言函数如下： func(i) long i; { long j; j=i-1; func(j); } 该函数在PC机linux操作系统上编译生成的汇编代码如下： .file "stack.c" gcc2_compiled.: __gnu_compiled_c: .text .align 2 .globl _func .type _func,@function _func: pushl %ebp movl %esp,%ebp subl $4,%esp movl 8(%ebp),%edx decl %edx movl %edx, -4(%ebp) movl -4(%ebp),%eax pushl %eax call _func addl $4,%esp L1: leave ret Lfe1: .size _func,Lfe1-_func 试画出该函数的一个活动 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 的内容，包括活动记录的每个单元存放什么东西、执行movl 8(%ebp),%edx指令时栈顶指针所指的的位置、与活动记录有关的另一个指针所指的位置和地址增长方向。 6．（5分）一个C语言函数如下： main() { int i,j,k; i=5; j=1; while(j<100){ k=i+1; j=j+k; } } 经优化编译后，生成的代码如下： .file “optimize.c” gcc2_compiled.: ___gnu_compiled_c: .text .align 2 .globl _func .type _func,@function _func: pushl %ebp movl %esp,%ebp movl $1,%eax movl $6,%edx .align 2,0x90 L4: addl %edx,%eax cmpl $99,%eax jle L4 leave ret Lfe1: .size _func,Lfe1-_func 试说明编译器对这个程序作了哪些种类的优化（只需要说复写传播、删除公共子表达式等，不需要说怎样完成这些优化）。 2002年 1. （10分）一个C语言的文件如下。 long gcd(p,q) long p,q; { if (p%q == 0) return q else return gcd(q, p%q); } 基于LALR（1）方法的一个编译器的报错情况如下。 如果缺少第二行的逗号，编译器报告parse error before ‘q’ ( line 2)。如果缺少第四行的右括号，编译器报告parse error before ‘return’ ( line 5)。这两个示例表明LALR（1）方法能及时发现错误，且不会把出错点后面的符号移进分析栈（活前缀性质）。 (a) 如果第四行的if误写成fi，编译器仍报告parse error before ‘return’ ( line 5)。此时是否违反了活前缀性质？请给出你的解释。 (b) 若在上面程序文件中加入下面的main函数 main() { printf("\n%ld\n",gcdx(4,12)); } 编译得到的出错如下。 In function ‘main’ : undefined reference to ‘gcdx’ ld returned 1 exit status. 请问，这个gcdx没有定义，是在编译时发现的，还是在联接装配时发现的？试说明理由。 2．（10分）一个文法如下： S ( ( S ) S ( a 请给出该文法中对活前缀(((有效的LR (1)项目。 3．（10分）算符(作用于表达式e1, e2, …, ek的前缀形式是( p1 p2 … pk，其中pi是ei的前缀形式。 (a) 写出a( ( (b + c)的前缀形式。 (b) 给出把中缀表达式翻译成前缀形式的翻译方案，中缀表达式的文法如下。 E ( E + T | T T ( T ( F | F F ( id | (E) 4．（10分）在下面假想的程序中，第（11）行语句f := a调用函数a，a传递函数addm作为返回值。 (a) 画出该程序执行的活动树。 (b) 假定非局部名字使用静态作用域，为什么该程序在栈式分配情况下不能正确工作？ (c) 在堆分配策略下，该程序的输出是什么？ (1) program ret (input, output); (2) var f: function (integer): integer; (3) function a: function (integer): integer; (4) var m: integer; (5) function addm (n: integer): integer; (6) begin return m+n end; (7) begin m:= 0; return addm end; (8) procedure b (g: function (integer): integer); (9) begin writeln ( g(2)) end; (10) begin (11) f := a; b(f) (12) end. 5．（10分）一个C语言的函数如下： func(c,l) char c;long l; { func(c,l); } 在X86/Linux机器上编译生成的汇编代码如下： .file "parameter.c" .version "01.01" gcc2_compiled.: .text .align 4 .globl func .type func,@function func: pushl %ebp —— 将老的基地址指针压栈 movl %esp,%ebp —— 将当前栈顶指针作为基地址指针 subl $4,%esp —— 分配空间 movl 8(%ebp),%eax movb %al,-1(%ebp) movl 12(%ebp),%eax pushl %eax movsbl -1(%ebp),%eax pushl %eax call func addl $8,%esp .L1: leave —— 和下一条指令一起完成恢复老的基地址指针，将栈顶 ret —— 指针恢复到调用前参数压栈后的位置，并返回调用者 .Lfe1: .size func,.Lfe1-func .ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)" (a) 请指出对应源程序第5行的函数调用func(c,l)的汇编指令是哪几条。 (b) 请说明字符型参数和长整型参数在参数传递和存储分配方面有什么区别。（小于长整型size的整型参数的处理方式和字符型参数的处理方式是一样的。）