陇东学院。
1.(15分)
a) 字母表上的语言是不是正规语言?为什么?
b) 正规式 (0 | 1)* 和( (0) 1* )是否等价,说明理由。
2.(15分)接受文法。
s a a | b a c | d c | b d a
a d活前缀的dfa见下图。请根据这个dfa来构造该文法的slr(1)分析表,并说明该文法为什么不是slr(1)文法。
3.(10分)现有字母表=,写一个和正规式a*等价的上下文无关文法,要求所写的文法既不是lr文法,也不是二义文法。
4.(20分)
(a) 下面的文法定义语言l = 写一个语法制导定义,其语义规则的作用是:对不属于语言l的子集l1= 的句子,打印出错信息。
s d c d a d b | a b c c c | c
(b) 语句的文法如下:
s id :=e | if e then s | while e do s | begin s ; s end | break
写一个翻译方案,其语义动作的作用是:若发现break不是出现在循环语句中,及时报告错误。
5.(5分)c程序设计的教材上说,可以用两种形式表示字符串:其一是用字符数组存放一个字符串,另一种是用字符指针指向一个字符串。教材上同时介绍了这两种形式的很多共同点和不同点,但是有一种可能的区别没有介绍。
下面是一个包含这两种形式的c程序:
char c1=good!”;
char *c2=“good!”;
main()
c1[0]= g’;
printf(“c1=%s”, c1);
c2[0]= g’;
printf(“c2=%s”, c2);
该程序在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 = d”, f1(10.0), f2(10.0) )
其中函数f1和f2仅形式参数的描述方式不一样。该程序在x86/linux机器上的运行结果如下:
f1 = 0, f2 = 100
请解释为什么用同样的实在参数调用这两个函数的结果不一样。
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将当前栈顶指针作为基地址指针。
subl $8,%esp为局部变量分配空间。
cmpl $0,-8(%ebp)
je .l2
incl -4(%ebp)
jmp .l3
l2:l4:
cmpl $0,-4(%ebp)
jne .l6
jmp .l5
l6:incl -8(%ebp)
jmp .l4
l5:l3:
l1:le**e和下一条指令一起完成恢复老的基地址指针,将栈顶。
ret指针恢复到调用前参数压栈后的位置,并返**用者。
8.(10分)cc是unix系统上c语言编译命令,l是连接库函数的选择项。两个程序员分别编写了函数库和当用命令。
cc 编译时,报告有重复定义的符号。(备注:库名中的lib在命令中省略。该命令和命令cc 的效果是一致的)。而改用命令。
cc 时,能得到可执行程序。试分析原因。
编译原理和技术试题参***。
1. (a) 语言是正规语言,因为该语言只包括有限个句子,它可以用正规式定义如下:
b) 我们分析正规式( (0) 1* )表示的语言。可以看出正规式( |0) 1*描述的语言是集合,它含长度为1的两个串0和1。那么,(0 | 1)* 所描述的语言是( (0) 1* )所描述的语言的子集,因为(0 | 1)* 表示字母表上所有串的集合,因此( (0) 1* )所描述的语言不可能再有更多的句子,因而也是表示字母表上所有串的集合。
2.分析表如下。因为有两处有移进-归约冲突,所以该文法不是slr(1)文法。
注:fallow(a) =
3.满足条件的一个文法如下:
s a s a | a |
4. (a) 语法制导的定义如下:
s d cif then print (“error”)
d a :=1
d a d1 :=1
c :=1c c1 :=1
b) 翻译方案如下:
s ss id :=e
s if e then s1
s begin
5.c1是字符数组,c1=good!”看成是对这个数组的元素逐个地赋值。c2是字符指针,它所指向的“good!
”看成是一个字符串常量,常量的值不允许修改,因此编译器把这个字符串常量分配在只读数据区。
当执行赋值c2[0]= g’时,试图对只读数据区赋值,因此报告错误。
6.历史上,c语言中有参函数定义的一般形式是:
类型标识符函数名(形式参数列表)
形式参数声明。
对于这种形式的声明,c语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的。如本题中函数f1的声明是这种形式。
现在,ansi新标准允许使用另一种方法声明形式参数,即在函数名后的括号中列出形式参数的同时,声明形式参数的类型。本题中函数f2的声明是这种形式。c语言编译器对于这种形式的函数声明是要进行实在参数和形式参数的个数和类型是否一致的检查的。
因此,在编译函数调用f2(10.0)时,会把浮点数10.0转换成整数10,并产生将整数10压栈的指令。因此函数调用f2(10.0)的结果是100。
而在编译函数调用f1(10.0)时,会把浮点数10.0转换成双精度型 ,并产生将该双精度型数压栈的指令。
双精度型数占8个字节。它低地址的4个字节看成整数时正好是0。因此函数调用f1(10.
0)的结果是0
7.(a) 条件语句和循环语句的中间**结构如下:
if (e) then s1 else s2while (e) do s
e的**l4: e的**。
假转 l2真转 l6
s1的**转 l5
转 l3l6: s的**。
l2: s2的**转 l4
l3l5:用这种**结构,当while语句作为条件语句的s2时,就会出现题目所给的这种情况。
(b) .l1标号定义的入口是返**用者时该执行的指令,在函数内部有return语句时就会跳转到。l1。
8.这是基于下面几点原因。
1.两个函数库和都定义了某个函数或某个置初值的外部变量,把它简称为a。
2.引用a。
3.还引用的其它某个函数或外部变量,把它简称为b。在中,a和b在同一个目标文件中。
4.在中,含a的那个目标文件不含b。
进一步的解释如下。
由于引用a和b,用第二种次序连接时,a和b的定义在都能找到,所以不会再把中含a定义的目标文件连接进来。而用第一种次序连接时,先把中含a定义的目标文件连接进来,然后还需要把中含b定义的目标文件连接进来,引起把a的定义也要带进来,因为在中a和b的定义在同一个目标文件中。由此造成要连接a的两个定义。
9.c++语言中类的对象声明不加翻译就成了c语言中相应结构类型的变量声明,不管对象声明出现在程序中的什么地方。
备注: 由于c++语言中一个类的所有非静态属性构成一个c语言的结构类型,并且类的名字就作为结构类型的名字,因此上面的语句不做任何修改,_center自然就成了point结构类型的变量。所要注意的是,还应该根据point类中构造函数的参数置初值的情况,来给_center适当地静态置初值。
编译原理试题
语法分析 自顶向下的分析。重点与难点。重点 自顶向下分析的基本思想,分析器总体结构,分析表的构造,递归下降分析法基本思想,简单算术表达式的递归下降分析器。难点 first和follow集的求法,对它们的理解以及在构造ll 1 分析表时的使用。递归子程序法中如何体现分析的结果。基本要求。掌握语法分析 ...
编译原理试题
编译原理模拟试题。班级姓名学号。1 20分 写出字母表 上语言l 的正规式,并画出接受该语言的最简dfa。2.10分 计算文法g m 的每个非终结符的first和follow集合,并判断该文法是否是ll 1 的,请说明理由。g mm tb t ba b db et d d 3.10分 写一个文法使其...
编译原理试题
东南大学。一 文法g1 e et t t tf f f fp p p e i1 试证明符号串tet i 是g1的一个句型 要求画出语法树 2 写出该句型的所有短语,简单短句和句柄。三 1 试写出一个上下文无关文法g3,它能产生配对的圆括号串 例如等,甚至包含0对括号 2 使用文法g3给出输入串 的自...