编译原理考研真题USTC.doc

2003年编译原理考研真题1（10分）叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。( 1 | 01 )* 0*2（10分）某语言有两种语句：S 过程调用语句 | 下标变量赋值语句过程调用语句的形式是：id(id, id, , id)，即过程名加置于圆括号中的变量表。下标变量赋值语句的形式是：id(id, id, , id) := id(id, id, , id)，赋值号两边都是数组名加置于圆括号中的变量表。(a) 请你完成过程调用语句和下标变量赋值语句的文法设计，得到一个以语句S为开始符号的LR(1)文法。不得超过6个产生式，不需要给出你的文法是LR(1)文法的证明。(b) 如果想在LR分析的同时完成语义分析和中间代码生成，基于你的文法有什么困难？3（10分）(a) 为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。E E *E | +E | -E | unsigned_integer(b) 为上面的表达式产生栈机器代码。代码执行后，表达式的值留在栈上。你自己设计所需的栈机器指令，并写清楚指令的含义。4（10分）在C语言的教材上，称&为地址运算符，&a为变量a的地址。但是教材上没有说明表达式&a的类型是什么。另外，教材上说，数组名代表数组的首地址，但是也没有说明这个值的类型。它们所带来的一个问题是，如果a是一个数组名，那么表达式a和&a的值都是数组a的首地址，但是它们的使用是有区别的，初学时很难掌握。下面我们给出4个C文件，请你根据编译报错信息和程序运行结果，写出表达式a和&a的类型表达式。若你能掌握它们的类型，那么它们的区别就清楚了，你也就会正确使用它们了。（1）文件1：typedef int A1020;A a;A *fun()return(a);该函数在Linux上用gcc编译时，报告的类型错误如下：第6行：warning: return from incompatible pointer type（2）文件2：typedef int A1020;A a;A *fun()return(&a);该函数在Linux上用gcc编译时，没有类型方面的错误。（3）文件3：typedef int A1020;typedef int B20;A a;B *fun()return(a);该函数在Linux上用gcc编译时，没有类型方面的错误。（4）文件4：typedef int A1020;A a;fun()printf(“%d,%d,%dn”, a, a+1, &a+1);main()fun();该程序的运行结果是：134518112, 134518192, 1345189122004编译原理部分考研真题1（10分）下面的文法是LR(1)文法。请合并该文法LR(1)项目集规范族中的同心集，以说明该文法不是LALR(1)文法。S a A d | b B d | a B e | b A eA cB c2（10分）为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S. val := 5.625。（不得修改文法。）S L . R | LL L B | BR B R | BB 0 | 13（5分）在X86/Linux机器上，编译器报告第15行有错误：incompatible types in return在C语言中，数组和结构都是构造类型，为什么下面第2个函数有类型错误，而第1个函数没有？typedef int A110;typedef int A210;A1 a;typedef struct int i;S1;typedef struct int i;S2;S1 s;A2 *fun1() return(&a);S2 fun2() return(s);4（5分）在C语言中，若a和b是相同的结构类型，那么赋值a=b是可以的。但是编译器对这种赋值的实现方式可能和它们的字节数（size）有关。下面是两个C语言程序及在X86/Linux机器上生成的目标代码（略去了和本题目无关的部分）。扼要叙述这些目标代码中体现出的实现方式上的区别。（在下面汇编程序中给出的注释仅供参考。）struct long i,j; double m;a,b;main() a=b;main:pushl %ebpmovl %esp,%ebpmovl $b,%eaxmovl $a,%edxmovl (%eax),%ecxmovl %ecx,(%edx)movl 4(%eax),%ecxmovl %ecx,4(%edx)movl 8(%eax),%ecxmovl %ecx,8(%edx)movl 12(%eax),%eaxmovl %eax,12(%edx).L1:leaveretstruct long i,j; double m,n;a,b;main() a=b;main:pushl %ebpmovl %esp,%ebppushl %edipushl %esimovl $a,%edimovl $b,%esicld 设定方向标志，使地址指针自动增量movl $6,%ecx 设定重复次数rep 表示重复下面的指令movsl 传送指令.L1:leal -8(%ebp),%esppopl %esipopl %edileaveret2005编译原理考研真题1（5分）下面是用正规式表示的变量声明：( int | float ) id (, id )* ;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。2（10分）在C语言中，3+和( id + id )+这样的表达式被编译时，编译器都会报告如下的错误：invalid lvalue in increment现有如下简化的C语言表达式文法：E E + E | ( E ) | E + | id | num请你写一个语法制导定义或翻译方案，它检查+的运算对象是否合法。3（10分）下面是一个C语言程序： long f1(i)long i;return(i*10);long f2(long i)return(i*10);main()printf(“f1 = %d, f2 = %dn”, f1(10.0), f2(10.0) );其中函数f1和f2仅形式参数的描述方式不一样。该程序在X86/Linux机器上的运行结果如下：f1 = 0, f2 = 100请解释为什么用同样的实在参数调用这两个函数的结果不一样。4（5分）优化编译器对下面程序的局部变量i和j不分配空间，为什么？main()long i, j;i = 5;j = i * 2;printf(“%dn”, i+j);2006编译原理考研真题1、（10分）下面是int i, j, k这样的类型声明的两种不同语法：D T LD T LT int | real T int | realL L , id | id L id , L | id如果用LL(1)分析方法，应该选择哪个文法？如果用某种LR分析方法，选择哪个文法更好？简要说明理由。2、（6分）用SLR(1)文法能定义的语言集合、用LR(1)文法能定义的语言集合和用LALR(1)文法能定义的语言集合之间有什么关系？（不需要给出理由。）3、（8分）下面是一个C语言的函数：void f(char c, long j) char *p; char ch; long m3; p=&c; m0=j; 在x86/Linux机器上经某版本的编译器编译生成的汇编代码如下：.fileframe.c.version01.01gcc2_compiled.:.text.align 4.globl f.type f,functionf:参数j参数c返回地址老ebp（控制链）esp ebp栈增长方向高地址低地址pushl %ebpmovl %esp,%ebpsubl $24,%espmovl 8(%ebp),%eaxmovb %al,-1(%ebp)leal -1(%ebp),%edxmovl %edx,-8(%ebp)movl 12(%ebp),%eaxmovl %eax,-24(%ebp).L1:leaveret.Lfe1:.size f,.Lfe1-f.identGCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)请将执行subl $24,%esp后，esp和ebp指向地址之间的区域（见上图）用于存放哪些变量的值，按照这些变量的名字、相对于ebp指向地址的偏移、字节数（size）列出来。4、（6分）两个C语言文件link1.c和link2.c的内容分别如下：int buf1 =100;和extern int *buf;main()printf(“%dn”, *buf);在X86/Linux经命令cc link1.c link2.c编译后，运行时产生如下的出错信息：Segmentation fault (core dumped)请说明原因。2007年编译原理部分1、（10分）描述由正规式b*(abb*)*(a| e)定义的语言，并画出接受该语言的最简DFA。2、（10分）证明文法E E + id | id是SLR(1)文法。3、（10分）下面是表达式和赋值语句的文法，其中and的类型是bool bool bool，+的类型是int int int，=的类型是int int bool，:= 要求id 和E的类型都是int或者都是bool。为该文法写一个语法制导定义或翻译方案，它完成类型检查。S id := EE E and E | E + E | E = E |id4、（5分）对于下面C语言文件s.c f1(int x)long x;x = 1;f2(int x)long x;x = 1;某编译器编译时报错如下：s.c: In function f1:s.c:3: warning: declaration of x shadows a parameter请回答，对函数f2为什么没有类似的警告错误。5、（5分）下面C语言程序经非优化编译后，若运行时输入2，则结果是area=12.566360, addr= - 1073743076经优化编译后，若运行时输入2，则结果是area=12.566360, addr= - 1073743068请解释为什么输出结果有区别。main() float s, pi, r; pi=3.14159; scanf(%f, &r); printf(area=%f, addr=%dn, s=pi*r*r, &r);2008年编译原理考研真题1、（10分）描述由正规式b*a(bb*a) *b*定义的语言，并画出接受该语言的最简DFA。2、（10分）下面的文法产生代表正二进制数的0和1的串集：B B 0 | B 1 | 1下面的翻译方案计算这种正二进制数的十进制值：B B1 0B.val := B1.val 2 | B1 1B.val := B1.val 2 +1| 1 B.val := 1 请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值。3、（10分）在C语言中，如果变量i和j都是long类型，请写出表达式&i和表达式&i-&j的类型表达式。为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。main() long i, j;printf(“%dn”, &i-&j);4、（10分）一个C语言的函数如下：func(i) long i; long j;j = i 1;func(j);下面左右两边的汇编代码是两个不同版本GCC编译器为该函数产生的代码。左边的代码在调用func之前将参数压栈，调用结束后将参数退栈。右边代码对参数传递的处理方式没有实质区别。请叙述右边代码对参数传递的处理方式并推测它带来的优点。func:|func:pushl%eb