《试题编译原理.doc》由会员分享，可在线阅读，更多相关《试题编译原理.doc（5页珍藏版）》请在金锄头文库上搜索。
1、陇东学院1（15分）(a) 字母表S = ( , ) 上的语言 ( ), ( )( ), ( ), ( )( )( )( )( )是不是正规语言？为什么？(b) 正规式 (0 | 1)* 和( (e | 0) 1* )*是否等价，说明理由。2（15分）接受文法S A a | b A c | d c | b d aA dS .SS .A aS .b A cS .d cS .b d aA .dI0S b .A cS b .d aA .dI3daS d .cA d .I4AS S .I1SS A .aI2AS A a .I5bS b A .cI6dS d c .I8S b d .aA d .I7cS
2、 b A c .I9S b d a .I10ca活前缀的DFA见下图。请根据这个DFA来构造该文法的SLR(1)分析表，并说明该文法为什么不是SLR(1)文法。3（10分）现有字母表S= a ，写一个和正规式a*等价的上下文无关文法，要求所写的文法既不是LR文法，也不是二义文法。4（20分）(a) 下面的文法定义语言L = anbncm | m, n 1。写一个语法制导定义，其语义规则的作用是：对不属于语言L的子集L1= anbncn | n 1的句子，打印出错信息。S D CD a D b | a bC C c | c(b) 语句的文法如下：S id := E | if E then S |
3、 while E do S | begin S ; S end | break写一个翻译方案，其语义动作的作用是：若发现break不是出现在循环语句中，及时报告错误。5（5分）C程序设计的教材上说，可以用两种形式表示字符串：其一是用字符数组存放一个字符串，另一种是用字符指针指向一个字符串。教材上同时介绍了这两种形式的很多共同点和不同点，但是有一种可能的区别没有介绍。下面是一个包含这两种形式的C程序：char c1=“good!”;char *c2=“good!”;main()c10= G;printf(“c1=%sn”, c1);c20= G;printf(“c2=%sn”, c2);该程序在
4、X86/Linux机器上运行时的信息如下：c1=Good!Segmentation fault (core dumped)请问，出现Segmentation fault的原因是什么？6（15分）下面是一个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请解释为什么用同样的实在参
5、数调用这两个函数的结果不一样。7（10分）下面是一个C语言程序和在X86/Linux机器上编译（未使用优化）该程序得到的汇编代码（为便于理解，略去了和讨论本问题无关的部分，并改动了一个地方）。(a) 为什么会出现一条指令前有多个标号的情况，如.L2和.L4，还有.L5、.L3和.L1？从控制流语句的中间代码结构加以解释。(b) 每个函数都有这样的标号.L1，它的作用是什么，为什么本函数没有引用该标号的地方？main() long i,j; if ( j ) i+; else while ( i ) j+;main:pushl %ebp将老的基地址指针压栈movl %esp,%ebp将当前栈顶指
6、针作为基地址指针subl $8,%esp为局部变量分配空间cmpl $0,-8(%ebp)je .L2incl -4(%ebp)jmp .L3.L2:.L4:cmpl $0,-4(%ebp)jne .L6jmp .L5.L6:incl -8(%ebp)jmp .L4.L5:.L3:.L1:leave和下一条指令一起完成恢复老的基地址指针，将栈顶ret指针恢复到调用前参数压栈后的位置，并返回调用者8（10分）cc是UNIX系统上C语言编译命令，-l是连接库函数的选择项。两个程序员分别编写了函数库libuser1.a和libuser2.a。当用命令cc test.c -luser1.a -luse
7、r2.a编译时，报告有重复定义的符号。（备注：库名中的lib在命令中省略。该命令和命令cc test.c libuser1.a libuser2.a的效果是一致的）。而改用命令cc test.c -luser2.a -luser1.a时，能得到可执行程序。试分析原因。 编译原理和技术试题参考答案1(a) 语言 ( ), ( ) ( ), ( ), ( ) ( ) ( ) ( ) ( )是正规语言，因为该语言只包括有限个句子，它可以用正规式定义如下：( ) | ( )( ) | ( ) | ( ) ( ) ( ) ( ) ( )(b) 我们分析正规式( (e | 0) 1* )*表示的语言。可以
8、看出正规式(e | 0) 1*描述的语言是集合e, 1, 11, 111, , 0, 01, 011, 0111, ，它含长度为1的两个串0和1。那么，(0 | 1)* 所描述的语言是( (e | 0) 1* )* 所描述的语言的子集，因为(0 | 1)* 表示字母表0, 1上所有串的集合，因此( (e | 0) 1* )* 所描述的语言不可能再有更多的句子，因而也是表示字母表0, 1上所有串的集合。2分析表如下。因为有两处有移进归约冲突，所以该文法不是SLR(1)文法。注：Fallow(A) = a, c状态 动作转移 a b c d $ S A 0 s3 s4 1 2 1 acc 2 s5
9、 3 s7 6 4 r5 s8, r5 5 r1 6 s9 7 s10, r5 8 r3 9 r2 10 r43满足条件的一个文法如下：S a S a | a | e4(a) 语法制导的定义如下：S D Cif D.length C.length then print (“error”)D a bD.length := 1D a D1 bD.length := D1.length + 1C cC.length := 1C C1 cC.length := C1.length + 1(b) 翻译方案如下：S S.loop := falseSS id := E S if E then S1.loop
10、 := S.loopS1S while E do S1.loop := trueS1S begin S1.loop := S.loopS1 ; S2.loop := S.loopS2 endS breakif not S.loop then print(“error”) 5c1是字符数组，c1=“good!”看成是对这个数组的元素逐个地赋值。c2是字符指针，它所指向的“good!”看成是一个字符串常量，常量的值不允许修改，因此编译器把这个字符串常量分配在只读数据区。当执行赋值c20= G时，试图对只读数据区赋值，因此报告错误。6历史上，C语言中有参函数定义的一般形式是：类型标识符 函数名（形式
11、参数列表）形式参数声明对于这种形式的声明，C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的。如本题中函数f1的声明是这种形式。现在，ANSI新标准允许使用另一种方法声明形式参数，即在函数名后的括号中列出形式参数的同时，声明形式参数的类型。本题中函数f2的声明是这种形式。C语言编译器对于这种形式的函数声明是要进行实在参数和形式参数的个数和类型是否一致的检查的。因此，在编译函数调用f2(10.0)时，会把浮点数10.0转换成整数10，并产生将整数10压栈的指令。因此函数调用f2(10.0)的结果是100。而在编译函数调用f1(10.0)时，会把浮点数10.0转换成双精度型 ，并产生
12、将该双精度型数压栈的指令。双精度型数占8个字节。它低地址的4个字节看成整数时正好是0。因此函数调用f1(10.0)的结果是0 7(a) 条件语句和循环语句的中间代码结构如下：if (E) then S1 else S2while (E) do SE的代码L4: E的代码假转 L2真转 L6 S1的代码转 L5转 L3L6:S的代码L2:S2的代码转 L4L3:L5:用这种代码结构，当while语句作为条件语句的S2时，就会出现题目所给的这种情况。(b) .L1标号定义的入口是返回调用者时该执行的指令，在函数内部有return语句时就会跳转到.L1。8这是基于下面几点原因。1两个函数库libuser1.a和libuser2.a都定义了某个函数或某个置初值的外部变量，把它简称为a。2test.c引用a。3test.c还引用libuser2.a的其它某个函数或外部变量，把它简称为b。在libuser2.a中，a和b在同一个目标文件中。4在libuser1.a中，含a的那个目标文件不含b。进一步的解
