西南大学育才学院第10届毕业大补考《编译原理》课程考试试题（a）卷。
一、填空题（共10题，20分，每题2分）
1. 高级程序设计语言的翻译主要有两种方式和。
2. 编译程序的工作过程主要分为如下几个阶段：词法分析、语法分析、语义分析目标**生成。
3. 文法g产生的的全体是该文法描述的语言。
4. 算符优先分析法中每次归约的是当前句型的。
5. 自上而下语法分析方法中会遇到的主要问题有左递归和。
6. 假设有文法g[s]：s?sa|b，对该文法消除左递归后得到的文法为。
7. 以01结尾的二进制串的正规式描述为。
8. 属性文法中综合属性用于“自下而上”传递信息，而属性用于“自上而下”传递信息。
9. 表达式(a+b)* c的逆波兰式是。
10. 以下方法中不能够用于表示源程序中间**形式的有。
a. 语法分析树 b. 逆波兰表示法
c. 三地址** d. 抽象语法树。
二、简答题（共4题，每题5分，共20分）
1. 简述文法的形式化定义。
2. 什么是二义性文法？
3. 简述自上而下语法分析过程的含义。
4. 简述follow集合的定义。
三、综合计算题（共5题，共60分）
1． 请画出编译程序的基本结构框图。（10分）
2． 已知：基本字母表∑=，则∑*=u=，v=，u和v都是∑*的子集，请求出如下字符串集合：
uv＝｛ u0=，u2 ＝｛u3=｛ 10分）
3． 令文法为g[e]：
e? t| e+t | e-t
t? f| t*f | t/f
f? (e) |i
1）给出句子i * i + i )的最左推导和最右推导。
2）给出句子i * i + i )的的句柄。（10分）
4． 构造正规式1（0|1）*101相应的dfa。（10分）
5． 已知文法g[s]:
s?ahh?amd |d
m?ab|ε
a?am|e
1） 计算文法中每个非终结符的first集合和follow集合。（5分）
2） 判断该文法是否为ll(1)文法？（5分）
3） 构造该文法的**分析表。（10分）
一、填空题（共10题，20分，每题2分）
1. 编译、解释。
2. 中间**生成、**优化。
3. 句子。
4. 最左素短语。
5. 回溯。
6. s?bs’, s’?as’|ε
8. 继承属性。
9. ab+c*
10. a二、简答题（共4题，每题5分，共20分）
1. 简述文法的形式化定义。
文法g是一个四元组（vn，vt，p，s）。其中vn为非终结符集合，非终结符表示语法实体或语法变量；vt为终结符集合；p为产生式集合，p中每个产生式的形式为α—>其中α∈(vn∪vt )*且至少包含一个非终结符，β∈vn∪vt )*s称为文法的开始符号。
2. 什么是二义性文法？
某文法若存在一个句子对应两棵不同的语法树，则说这个文法是二义性文法。或者说，若一个文法中存在某个句子，有两个不同的最左推导或最右推导，则该文法是二义的。
3. 简述自上而下语法分析过程的含义。
所谓自上而下语法分析，是从文法的开始符号出发，反复使用各产生式，寻找“匹配”于输入符号串的推导。从语法树的角度来看，自上而下方法是从文法符号开始，将它作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。
4. 简述follow集合的定义。
文法中非终结符a的follow集定义为：
follow（a）＝。
若有s ==a，则规定＃∈follow（a）。
三、综合计算题（共6题，每题10分，共60分）
1. 请画出编译程序的基本结构框图。
2. 已知：基本字母表∑=，则∑*=u=，v=，u和v都是∑*的子集，请求出如下字符串集合：
uv＝｛aaba, aabb, abba, abbb｝，u0 =
u2 ＝uu=｛aaaa, aaab, abaa, abab｝
u3 ＝uuu=(uu)u=｛ aaaaaa,aaabaa,abaaaa,ababaa，aaaaab,aaabab,abaaab,ababab｝
3．（1）给出句子i * i + i )的最左推导和最右推导。
句子i * i + i )的最左推导为：
e==>t==>t*f==>f*f==>i*f==>i*(e) =i*(e+t) =i*(t+t)
=> i*(f+t) =i*(i+t) =i*(i+f) =i*(i+i)
句子i * i + i )的最右推导为：
e==>t==>t*f==>t*(e) =t*(e+t) =t*(e+f) =t*(e+i)
=> t*(t+i) =t*(f+i ) t*(i+i) =f*(i+i) =i*(i+i)
2)则该句子的句柄为：i
4.（1）正规式1（0|1）*101对应的nfa：
2）从nfa的初始状态x的转换过程：
重新命名状态，令ab为b，ac为c，aby为d。
得到新dfa的状态转换图如下所示：
5．（1）计算文法中每个非终结符的first集合和follow集。
非终结符 first集 follow集。
s h
m a
2）判断该文法是否为ll(1)文法。
文法不含有左递归；
对与如下产生式，候选式的first集的交集为空。
h?amd |d
m?ab|ε
a?am|e
因为ε∈first( m )，故考察first（m）与follow(m)的交集为空。
综上所述，该文法为ll（1）文法。
3）构造该文法的**分析表：(网页显示有问题)
a d b e ＃
s ?ah
h ?amd ?d
m ?ab ?εab
a ?am ?ε
编译原理试题
语法分析 自顶向下的分析。重点与难点。重点 自顶向下分析的基本思想，分析器总体结构，分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。难点 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给出输入串 的自...