厦门大学《编译原理》课程试卷 计算机学院计算机系 2009 年级计算机科学与技术专业 主考教师：＿史晓东＿试卷类型：（期中） 注意： 考试时间为 90 分钟，试卷满分为 100 分； 答案写在答卷纸上 1. (20 分) 基础知识。 （1）（10 分）一个编译程序可以分成几个阶段（phases）？请给出每个阶段的输入输出。 （2）（5 分）给出上下文无关文法的定义。 （3）（5 分）lex（flex）在编译中起什么作用？简述 lex 的工作原理。 2. （10 分）对以下 C 程序： int if0; int m(int x) { int if0; if (if0<’0’); if0 = x*x; return m(iffy); 一个编译器可能会给出哪些下面的陈述？ 词法错误：if0 不是有效的标志符； 语法错误：if 语句不完整； 语义错误：变量 if0 和’0’不能比较； 逻辑错误：死循环； 没有错误：该程序是合法的 C 程序。 } 简要说明理由。你认为编译器还应该给出那些警告？ 3． (15 分) 写出字母表 = {a, b}上语言 L = {w | w 中 a 的个数是偶数}的正规式，并画出接 受该语言的最小状态 DFA。 4. (15 分)Unix shell 的简单命令可以是执行文件名，输入输出用重定向来表示。若干可执 行文件可以用管道运算连接起来。假设第一个可执行才能有输入重定向，最后一个可执 行才有输出重定向。命令的例子如： simple > outfile < infile lexer < goodfile.c | parser | translator > bug.txt (a) 请用 CFG 写出该命令语言的文法，假设文件名、’<’、’>’、’|’为终结符； (b) 对上面两个例子，画出分析树。 5. （20 分）已知文法 G （S 为开始符）为： S→ id := E E→ id | num | E + E （1）求出 First(E)和 Followt(E)， （2）并给出与 G 等价的 LL（1）文法 G'。 (3) 对你给出的文法 G', 构造句子 id :=num+id 的规范推导，并指出每个右句型的句柄 6. (20分) 文法G （S为开始符）为： S→ i E t S e S | i E t S E→b （1）（5分）证明该文法是二义的 （2）（10分）画出LR（0）自动机的项集，指出是否存在冲突。 （3）（5分）说明如用YACC，如何消除二义性。