昆 明 理 工 大 学 试 卷（A ）
考试科目：编译原理 考试日期： 命题教师：集体
学院： 专业班级： 学生姓名： 学号：
任课教师： 上课班级： 考试座位号：
题 号 评 分 阅卷人 一 二 三 四 五 六 七 总分
一、 填空（每空1分，共20分）
1、计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。 2、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 二义性的 。 3、扫描器的任务是从 源程序中 中识别出一个个 单词符号 。
4、语法分析器的输入是 单词符号 ，其输出是 语法单位 。
5、规范规约中的可归约串是句柄 ，算符优先分析中的可归约串是 最左素短语 6、 对于文法G1和G2，若有L(G1)=L(G2) （或 G1和G2的语言相同），则称文法G1
和G2是等价的。
7、最右推导的逆过程称为规范归约 ，也称为 最左归约。
8、自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。
9、语法分析的方法大致可分为两类，一类是自上而下 分析法，另一类是自下而上 分析法。 10、2型文法又称为上下文无关文法；3型文法又称为正则文法。
11、表达式式_a/(b-c)所代表的逆波兰表达式是___ abc-/_。 12、对于文法G，仅含终结符号的句型称为 句子 。 二、单项选择题（每题2分，共20分）
1、词法分析器的输出结果是（ ）。
A． 单词的种别编码 B．单词在符号表中的位置 C． 单词的种别编码和自身值 D． 单词自身值
2、3．一个句型中称为句柄的是该句型的最左（ ）。
A．非终结符号 B．短语 C．句子 D．直接短语
3、下推自动机识别的语言是（ ）。
A．0型语言 B．1型语言 C．2型语言 D．3型语言
4、（ ）型文法也称为正规文法。
A 0 B 1 C 2 D 3
5、采用自上而下分析，必须（ ）。
A．消除左递归 B．消除右递归 C．消除回溯 D．提取公共左因子
6、设有文法G[I]: I→I1|I0|Ia|Ic|a|bc下列符号串中是该文法的句子有（ ）。
（1） ab0 (2) a0c01 (3) aaa (4) bc10
A. (1) B. (2)(3)(4) C. (3)(4) D. (1)(2)(3)(4)
7、正则集合L={a|n≥0}相应的正则表达式是（ ）
n
A．a* B．a+ C．aa* D．aa+
8、在自上而下的语法分析中可能引起回溯的产生式是（ ）。
A S→aAc|(T) B T→ab|cD|fG C A→aB|af D B→cB|dG 9、若文法 G 定义的语言是无限集，则文法必然是______： A ．递归的 B 前后文无关的 C 二义性的 D 无二义性的 10、文法 G 产生的（ ）的全体是该文法描述的语言。 A ．句型 B. 终结符集 C. 非终结符集 D. 句子 三、（10分）对于文法G[E]: E?E+T|E-T|T T?T*F|T/F|F F?(E)|i
(1)写出句型(F+i)-T*(E-T)的最右推导并画出语法树。 (2)写出上述句型的短语，直接短语和句柄。 四、（11分）将下图所示的NFA确定化 。 a
a
0 1 a, b
五、(15分) 对文法 G[S]： S→S,T|(T)|a T→a(b)|a
(1) 消除该文法的左递归和提取左公因子；
(2) 求出文法改写后的各非终结符的FIRST和FOLLOW集合；
(3) 判断该文法是否是LL(1)文法。如果不是，说明理由；如果是，构造该文法的LL(1)分析表。
六、（p177 4-35 （4）） (20分)构造文法G[S]: S->A|Ab| a
(1) 构造该文法识别全部活前缀的DFA或LR(0)项目集规范族；
(2) 判断该文法是否是SLR(1)文法。如果不是，说明理由；如果是，构造该文法的SLR(1)分析表。
七、（p254 5-8（1））(4分)将将赋值语句x:= A*(B+C)+D翻译成四元式。
编译原理模拟试题 - 图文
