北方工业大学《编译原理》期中试卷2017
- 格式：pdf
- 大小：458.83 KB
- 文档页数：7
北方工业大学
《编译原理》课程期中试卷答案
A 卷
2017年春季学期
开课学院： 计算机
考试方式：闭卷
考试时间：95 分钟
班级 姓名 学号 一、 判断题（每个小题1分，共10分）
1. 汇编程序与编译程序都是翻译程序，主要区别是加工对象的不同。
（ ）
2. 解释程序同时处理源程序和数据。
（ ）
3. 编译各阶段都涉及到构造、查找或更新有关的表格。
（ ）
4. 上下文有关文法所定义的语法范畴是完全独立于这种范畴可能出现的环境
的。
（ ）
5. 乔姆斯基把文法分为0型、1型、2型和3型，0型文法的描述能力弱于1型。
（ ）
6. 词法分析器不断地从输入缓冲区读入字符串，并进行识别。
（ ）
7. 超前搜索是为了得到某一个单词符号的确切性质，需要超前扫描若干个字符。
（ ）
8. 一张转换图只包含有限个状态，其中有一个为初态，一个为终态。
（ ） 9. LR 分析法不是规范归约方法。
（ ） 10. 程序设计语言的单词都能用正规式来定义。
（ ） 解： 1. √ 2. √ 3. √ 4. × 5. × 6. × 7. √ 8. × 9. × 10. √
二、 选择题（每个小题1分，共20分）
1. 自下而上语法分析的工作原理是____。
A. 移进-推导法
B. 最左推导法
C. 移进-规约法
D. 推导-规约法 2. LR 分析法每次都是对当前句型的____进行规约。
A. 素短语
B. 句柄
C.短语
D. 最左素短语
订
线
装
3. 如果文法G是无二义的，则对于它的任何句子____。
A. 最左推导和最右推导对应的语法树必定相同
B. 最左推导和最右推导对应的语法树可能不同
C. 最左推导和最右推导必定相同
D. 可能存在两个不同的最左推导，但它们对应的语法树相同
4. 消除间接左递归时，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。
但不难证明，它们都是____。
A. 等价的
B. 不等价的
C. 形式上不一样
D. 形式上完全一样
5. 语法制导翻译法直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时____这些语义规则。
A. 考虑
B. 不考虑
C. 不执行
D. 执行
6. 若一个文法是递归的，则它产生的句子个数是____。
A. 有限个
B. 无穷个
C. 可能有限个
D. 以上均不对
7. 下面哪种不是自下而上的语法分析方法____。
A. SLR(1)
B. LR(1)
C. LL(1)
D. 算符优先分析法
8. 一个上下文无关文法消除了左递归，提取了公共左因子后是满足LL(1) 文法的____。
A. 没有关系
B. 充分必要条件
C. 必要条件
D. 充分条件
9. 正规式M1和M2等价是指____。
A. M1和M2的有向边条数相等
B. M1和M2的状态数相等
C. M1和M2的状态数和有向边条数相等
D. M1和M2所识别的语言集相等
10. 字母表｛a,b｝上以aa开头任何符号串的集合，可用正规式表示为____。
A. aa(a*|b*)
B. A、B、 C均不正确
C. aa(a|b)*
D. (a|b)*aa
11. 文法G所描述的语言是____的集合。
A. 文法G的字母表Σ的闭包Σ*中的所有符号串
B. 由文法的开始符号推出的所有终结符号串
C. 由文法的开始符号推出的所有符号串
D. 文法G的字母表Σ中所有符号组成的符号串
12. 经过编译所得到的目标程序是____。
A. 四元式序列
B. 间接三元式序列
C. 三元式序列
D. 机器语言程序或汇编语言程序
13. ____和代码优化部分不是每个编译程序都必需的。
A．语法分析B．中间代码生成 C．词法分析D．目标代码生成
14. 不可能是目标代码的是____。
A．中间代码B．可重定位的指令代码 C．绝对指令代码D．汇编指令代码
15. 语言是____。
A．句子的集合B．产生式的集合C．符号串的集合D．句型的集合
16. 一个句型的最左素短语是指处于句型最左边的____。
A．非终结符号B．短语C．素短语D．直接短语
17. 自上而下分析法是从文法开始符号出发，反复使用各种产生式，寻找匹配的____。
A．终结符号B．规约C．推导D．非终结符号
18. 自下而上分析的核心问题是识别____。
A．最左素短语B．可归约串C．句柄D．非终结符号
19. 规范归约是一个____的逆过程。
A．规范句型B．最左归约C．最左推导D．规范推导
20. 在正规式中运算符的优先级从高到低的顺序是____。
A．•，*，| B．|，•，*，C．*，•，| D．*，| ，•解：1. C 2. B 3. A 4. A 5. D 6. B 7. C 8. D 9. D 10. C
11. B 12.D 13.B 14. A 15. A 16. C 17. C 18. B 19. D 20. C
三、填空题（每空1分，共10分）
1. 有些编译程序对优化没有要求，阶段即可省去。
2. 是语言中具有独立意义的最基本结构。
3. 语法分析的描述工具是。
4. 自下而上分析法基本思想是从输入串开始，逐步进行，直到文法的开始符号。
即从树末端开始，构造语法树。
5. 消除左递归前后，文法的不变。
6. 由源程序的语法结构所驱动的处理办法就是。
7. 项目S→b.BB是。
8. 综合属性是传递信息。
9. 仅仅使用综合属性的属性文法称为文法。
10. LR(k)分析法中的R是指对应的最左归约。
解：1. 优化 2. 单词符号 3. 上下文无关文法 4. 归约 5. 开始符号
6. 语法制导翻译法
7. 待约项目
8. 自下而上
9. S-属性10. 最右推导
四、简答题（60分）
1. 请给出一个上下文无关文法，使其语言是能被5整除且不以0开头的无符号整数的集合。
（5分）解：文法G[S]为：
S→MF| 5
F→5 | 0
N→1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
D→N | 0
M→MD | N
2. 请给出一个上下文无关文法G，使得L(G)={a n b m c m d n | n≥0, m≥1} （3分）解：文法G[S]为：
S→aSd| A
A→bAc | bc
3. 语言L是所有由偶数个0和偶数个1组成的句子的集合，请给出定义L的右线性正规文法。
（5分）解：构造状态转换图为：
L的右线性正规文法为：
4. 请证明下面的文法G[E]是二义文法。
E→EiT | T
T →T+F | iF | F
F→E* | ( （3分）
5. 请构造正规式(a|b)*abb相应的最小化的DFA。
（12分）
6. 对于文法G[S]：
S→S*aT∣aT∣*aT
T→+aT∣+a
（1）请给出句型a+a*a+aT的最左推导，并给出语法树；
（2）给出上述句型的所有短语、直接短语、句柄和最左素短语。
（10分）
7. 对于文法G[S]：
S → iEtS | iEtSeS | a
E → b
（1）请给出消除G[S]的左递归和回溯后的文法；
（2）计算消除G[S]左递归和回溯后文法的每个非终结符的FIRST和FOLLOW；
（3）构造它的预测分析表；证明这个文法是否是LL(1)文法；
（4）请改造文法，并为之构造满足LL(1)文法的LL(1)分析表。
（12分）解：（1）G[S]不存在左递归，存在回溯。
提取公共左因子，消除G[S]的左递归和回溯后的文法G'[S] :
S → iEtSS' | a
S'→eS | ε
E → b
（2）计算消除G[S]左递归和回溯后文法G'[S]的每个非终结符的FIRST和FOLLOW；
FIRST(S)={i, a } FOLLOW(S)={e, #}
FIRST(S')={e, ε} FOLLOW(S')={e, #}
FIRST(E)={b} FOLLOW(E) ={t}
（3）构造它的预测分析表为：
由于FIRST(eS)∩FOLLOW(S’)={e}∩{e, #}={e} ，所以证明了G'[S]不是LL(1)文法。
（4）根据最近匹配原则，在嵌套if-then-else 语句中，else和if按照最近匹配原则配对，即相距最近且还没有配对的一对if和else首先配对。
改造后的文法G'[S] :
S → iEtSS' | a
S'→eS
E → b
满足LL(1) 文法的LL(1)分析表为：
8. 对于文法G[S]：
S→a Sb | P
P→bPc | bQc
Q→Qa | a
（1）计算文法G的FIRSTVT和LASTVT；
（2）构造优先关系表；
（3）G是算符优先文法吗?请给出判断理由。
（10分）。
