2001年编译原理试题
1．（10分）处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA 的状态转换图。 2．（10分）为语言
L ＝ {a m b n  | 0 ≤ m ≤ 2n}（即a 的个数不超过b 的个数的两倍 写一个LR （1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR （1）文法，最多给5分。） 3．（10分）构造下面文法的LL （1）分析表。    D → TL  T → int | real  L → id R  R → , id R | ε 4．（15分）就下面文法  S → ( L) | a  L → L , S | S  ∙ 给出一个语法制导定义，它输出配对括号的个数。  ∙ 给出一个翻译方案，它输出每个a 的嵌套深度。  如句子(a, (a, a) )，第一小题的输出是2，第二小题的输出是1 2 2。 9．（10分）如果在A 机器上我们有C 语言编译器CC A ，也有它的源码S A （用C 语言写成）。如何利用它通过尽量少的工作来得到B 机器的C 语言编译器CC B 。 10．（5分）表达式(λx .(λyz .(x  + y ) + z ) 3) 4 5和(λx .(λyz .(x  + y ) + z ) 3 5) 4有同样的结果。在抽象机FAM 上，哪一个表达式对应的目标代码的执行效率高？为什么？
2001年编译原理试题参考答案
1
2．LR （1）文法  LR （1）文法    二义文法  S → AB | aABb  S → AB      S → AASb | ε  A  → aaAb | ε  A  → aaAb | ab | ε    A  → a | ε    B → Bb | ε      B → Bb | ε 3．  int    real  id  ,  $    D  D →TL  D →TL  T  T →int  T →real  L        L →id R  R          R →, id R R → ε 4． S ' → S    print(S.num)  S → (L)  S.num := L.num +1  S → a    S.num := 0  L → L 1,S  L.num := L 1.num + S.num  L → S    L.num := S.num
*
S ' → {S.depth := 0} S  S → {L.depth := S.depth +1} (L)  S → a {print(S.depth)}  L → {L 1.depth := L.depth} L 1, {S.depth := L.depth} S  L → { S.depth := L.depth} S
9． ∙ 修改源码S A  的代码生成部分，让它产生B 机器的代码，称结果程序为S B 。  ∙ 将S B 提交给CC
A 进行编译，得到一个可执行程序。  ∙ 将S B 提交给上述可执行程序进行编译，得到所需的编译器CC B 。
10．第一个表达式在执行λyz .(x  + y ) + z ) 3时出现参数个数不足的情况，因此有FUNV AL 的值进入栈顶，然后发现参数个数不足，又把它做成FANV AL 的情况。而第二个表达式执行的是(λyz .(x  + y ) + z ) 3 5，不会出现参数个数不足的情况。因此第二个表达式的执行效率比第一个表达式的高。
2003年编译原理试题
1．（20分）写出字母表∑ = {a, b}上语言L = {w  | w 中a 的个数是偶数}的正规式，并画出接受该语言的最简DFA 。 2．（15分）考虑下面的表达式文法，它包括数组访问、加和赋值：      E → E[E] | E + E | E = E | (E) | id
该文法是二义的。请写一个接受同样语言的LR(1)文法，其优先级从高到低依次是数组访问、加和赋值，并且加运算是左结合，赋值是右结合。 3．（10分）下面是产生字母表∑ = { 0, 1, 2}上数字串的一个文法：  S → D S D | 2      D → 0 | 1
写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和从右向左读都一样时，称它为回文数）。
2003年编译原理试题参考答案
1．语言L 的正规式是：  (a b *a | b )* 或 b *(a b *a  b *)*  接受该语言的最简DFA 是：
2．    E → T = E | T  T → T + F | F      F → F[E] | (E) | id
3．
S ' → S
print(S.val)
b
S → D1 S1 D2S.val = (D1.val = D2.val) and S1.val
S → 2 S.val = true
D → 0    D.val = 0
D → 1    D.val = 1
画出while语句的流程图
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 }，写一个和正规式a*等价的上下文无关文法，要求所写的文法既不是LR文法，也不是二义文法。
4．（20分）
(a) 下面的文法定义语言L = { a n b n c m | m, n ≥ 1}。写一个语法制导定义，其语义规则的作用是：对不属于语言L的子集L1= { a n b n c n | n ≥ 1}的句子，打印出错信息。
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不是出现在循环语句中，及时报告错误。
2005年编译原理和技术试题参考答案
1．(a) 语言{ ( ), (( ) ( )), ((( ))), ( ) ( ) ( ) ( ) ( )}是正规语言，因为该语言只包括有限个句子，它可以用正规式定义如下：
( ) | (( )( )) | ((( ))) | ( ) ( ) ( ) ( ) ( )
(b) 我们分析正规式( (ε | 0) 1* )*表示的语言。可以看出正规式(ε | 0) 1*描述的语言是集合{ε, 1, 11, 111, …, 0, 01, 011, 0111, …}，它含长度为1的两个串0和1。那么，(0 | 1)*所描述的语言是( (ε | 0) 1* )*所描述的语言的子集，因为(0 | 1)*表示字母表{0, 1}上所有串的集合，因此( (ε | 0) 1* )*所描述的语言不可能再有更多的句子，因而也是表示字母表{0, 1}上所有串的集合。
2．分析表如下。因为有两处有移进－归约冲突，所以该文法不是SLR(1)文法。
注：
3
S → a S a | a | ε
4．(a) 语法制导的定义如下：
S → D C  if D.length ≠C.length then print (“error”)
D → a b    D.length := 1
D → a D1 b    D.length := D1.length + 1
C → c    C.length := 1
C → C1 c    C.length := C1.length + 1
(b) 翻译方案如下：
S'→ {S.loop := false}S
S →id := E
S →if E then {S1.loop := S.loop}S1
S →while E do {S1.loop := true}S1
S →begin {S1.loop := S.loop}S1 ; {S2.loop := S.loop}S2end
S →break{if not S.loop then print(“error”) }
1、（15分）
(a) 用正规式表示字母表{a, b}上，a不会相邻的所有串。b*(abb*)*(a| ε)
(b) 画出一个最简的确定有限自动机，它接受所有大于101的二进制整数。
2、（10分）构造下面文法的LL(1)分析表。
S → a B S | b A S | ε
A→ b A A | a
B → a B B | b
3、（10分）下面的文法是二义文法
S → E
E →while E do E | id := E | E + E | id | (E)
请你为该语言重写一个规范的LR(1)文法，它为该语言中的各种运算体现通常的优先级和结合规则。不需要证明你的文法是规范LR(1)的。
4、（10分）为下面文法写一个语法制导的定义，它完成一个句子的while-do最大嵌套层次的计算并输出这个计算结果。
S → E
E →while E do E | id := E | E + E | id | (E)
8、（5分）把下面左边的文件file1.c提交给编译器，编译器没有报告任何错误。而把文件file2.c提交给编译器，错误报告如下：
file2.c: 2: error: conflicting types for …func‟
file2.c: 1: error: previous declaration of …func‟
试分析原因。（在这两个文件中，第1行都是函数func的原型，第2行都是函数func的定义，函数体为空。）
file1.c file2.c
int func(double); int func(double);
int func(f) float f; {} int func(float f) {}
9、（5分）教材上第342页倒数第7行说“将C++语言中一个类的所有非静态属性构成一个C语言的结构类型，取类的名字作为结构类型的名字”。在这一章都学过后，你认为这句话需要修改吗？
参考答案
1、(a) b*(abb*)*(a| ε)
(b) 见下图。若不允许前缀的无效0，则去掉状态0上的0转换。
号集合LL(1)分析表

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。