编译原理考试————————————————————————————————作者：————————————————————————————————日期：一、判断对错：（对√；错 ；每小问2分共24分）<1>算符优先分析法是一种规范归约分析法。
（ ）<2>若文法Gs中不含形如T→…BD…的产生式，T、B、D∈V N，则称Gs为算符文法。
（√）<3>若一个语言是有穷集合，则定义该语言的文法一定是递归的。
（ ）<4>若两个正规式所表示的正规集相同，则认为二者是等价的。
（√）<5>LR分析法是一种规范归约分析法。
（√）<6>一个LR(0)项目集I={B →α.bβ, P →aA.},则说I中含有“移进—归约”冲突。
（√）<7>SLR(1)文法是无二义性文法。
（√）<8>消除左递归后的文法一定是LL(1)文法。
（ ）<9>对任何编译程序而言，代码优化是必不可少的。
（ ）<10>编译程序与具体的机器无关。
（ ）<11>在自动机的概念中，终态与非终态是可区别的。
（√）<12>逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（√）1. 一个语言有文法是不惟一的。
（√）2. 若一个语言是无穷集合，则定义该语言的文法一定是递归的。
（√）3. 紧跟在条件转移语句后面的语句是基本块的入口语句。
（√）4. 算符优先分析法是一种规范归约分析法。
（ ）5. 自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。
（√）6. LR(0)文法、SLR(1)文法都是无二义性文法。
（√）7．K、∑分别表示有限状态集和有穷字母表, DFA M的转换函数f是一个从K ⨯∑到K的单值映射。
（√）8. 对任何编译程序而言，代码优化是必不可少的。
（ ）9. 直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。
（√）10. 两个有穷自动机等价是指它们的状态数和有向弧数相等。
（ ）11. 一个LR(0)项目集为：I={A→α.bβ, D→β.},则说I中含有“移进--归约”冲突。
（√）12. 若两个正规式所表示的正规集相同，则认为二者是等价的。
（√）13. 无左递归的文法是LL(1)文法。
（ ）14. 逆波兰式abcde/+*+所代表的中缀表达式是：a+b*(c+d/e)（√）15. 编译程序结构中，中间代码优化及目标代码生成两个阶段与具体的机器有关。
（ ）16. LALR分析法中，同心集的合并不会产生“移进--归约”冲突。
（√）<1>算符优先分析法是一种规范归约分析法。
（错）<2>若文法Gs中不含形如T→…BD…的产生式，T、B、D∈V N，则称Gs为算符文法。
（对）<3>若一个语言是有穷集合，则定义该语言的文法一定是递归的。
（错）<4>若两个正规式所表示的正规集相同，则认为二者是等价的。
（对）<5>LR分析法是一种规范归约分析法。
（对）<6>一个LR(0)项目集I={B →α.bβ, P →aA.},则说I中含有“移进—归约”冲突。
（对）<7>SLR(1)文法是无二义性文法。
（对）<8>消除左递归后的文法一定是LL(1)文法。
（错）<9>对任何编译程序而言，代码优化是必不可少的。
（错）<10>编译程序与具体的机器无关。
（错）二、<1>将下图所示的NFA确定化。
(状态转换矩阵4分；状态转换图2分)解：<1> 状态转换矩阵4分状态转换图2分<2>给出语言L={ d a n b | n≥1}相应的文法。
G A：A → dBb G A：A → dBB→ aB |a B → aB | ab三、①编译程序的工作过程一般划分为五个基本阶段： B；D 、语义分析和中间代码生成、代码优化和目标代码生成。
A.出错处理B.词法分析C.表格管理D.语法分析②已知文法G E：E→E+T | T T→T*F | F F→(E) | b 那么，该文法终结符集合V T= A；C ，G E称2型文法或上下文无关文法。
A. {+,(,),*,b}B. {+,(,),*,E}C. {+,*,(,),b}D. {E,T,F}③已知文法G E：E→E+T | T T→T*F | F F→(E) | b 那么，该文法的非终结符集V N= B ，G E称2型文法或上下文无关文法。
A. {+,(,),*,b}B. {E,T,F}C. {+,*,(,),b}D. {E,T,F,*,+}④文法用于描述语言的语法结构，它由如下四个部分组成： A；C；D 和文法开始符号。
A.文法终结符集B.字母数字串C. 文法非终结符集D.文法产生式集⑤一个文法被称为是二义性的，如果 A , D 。
A.文法的某一个句子有两个以上的最右或最左推导。
B.文法的预测分析表中有多重入口。
C.文法的某个LR(0)项目集中有冲突项目。
D.文法的某一个句子有两棵以上不同的语法树。
⑥程序设计语言的单词符号一般可分为五种，它们是保留字、 A；D 及运算符和定界符。
A.常数B.表达式C.注解D.标识符⑦设有一个LR(0)项目集I={A→β.bδ， B→β. ，D→δ.}，I中存在冲突项目，它们是 A；D 。
A.“移进-归约”冲突B. “移进-接受”冲突C. “移进-待约”冲突D. “归约-归约”冲突⑧一个文法的SLR(1)方法和与其相应的LR(0)方法的状态数 A 。
A.相同B.不相同的C.前者大于后者D.后者大于前者1．编译程序的工作过程一般划分为五个基本阶段：词法分析、 B D 、中间代码优化、目标代码生成。
A.出错处理B.语法分析C.表格管理D.语义分析与中间代码生成2．识别某文法所有LR(0)项目集簇的DFA中，若项目集k中含有项目“A→δ.”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A →δ”归约的语法分析方法是 D 。
A．LALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法3．程序设计语言的单词符号一般可分为五种，它们是常数、 C D 及运算符和定界符。
A.注解B.表达式C.标识符D.保留字4．文法用于描述语言的语法结构，它由如下四个部分组成： A C D 和文法开始符号。
A.文法终结符集B.字母数字串C. 文法非终结符集D.文法产生式集5．一个文法被称为是二义性的，如果 A C 。
A.文法的某一个句子有两个以上的最右或最左推导。
B.文法的预测分析表中有多重入口。
C.文法的某一个句子有两棵以上不同的语法树。
D.文法的某个LR(0)项目集中有冲突项目。
6．已知文法G B：B→B+T | T T→T*F | F F→(B) | b 那么，该文法终结符集合V T= A B ， G E称2型文法或上下文无关文法。
A. V T={+,*,(,),b}B. V T={ b,(, +,* ,)}C. V T={B,T,F}D. V T={B,T,F,+,*,(,b,)}7．在动态存储分配时，可以采用的分配方法有 B C 。
A.分时动态存储分配B.栈式动态存储分配C. 堆式动态存储分配D.最佳动态存储分配8．设有一个LR(0)项目集I={A→β.dδ；A→b.Bδ； B→βd. ；D→dB. }，I中存在冲突项目，它们是 A B 。
A.“移进-归约”冲突B.“归约-归约”冲突C. “移进-待约”冲突D. “移进-接受”冲突9．在编译程序采用的优化方法中， B C D 是在循环语句范围内进行的。
A. 删除多余运算B.代码外提C. 删除归纳变量D.强度消弱10．编译程序生成的目标代码通常有3种形式，它们是 A C D 。
A.能够立即执行的机器语言代码B.中间语言代码C.汇编语言程序D.待装配的机器语言代码①编译程序的工作过程一般划分为五个基本阶段： BD 、语义分析和中间代码生成、代码优化和目标代码生成。
A.出错处理B.词法分析C.表格管理D.语法分析②已知文法G E：E→E+T | T T→T*F | F F→(E) | b 那么，该文法终结符集合V T= AC ，G E称2型文法或上下文无关文法。
A. {+,(,),*,b}B. {+,(,),*,E}C. {+,*,(,),b}D. {E,T,F}③已知文法G E：E→E+T | T T→T*F | F F→(E) | b 那么，该文法的非终结符集V N=B ，G E称2型文法或上下文无关文法。
A. {+,(,),*,b}B. {E,T,F}C. {+,*,(,),b}D. {E,T,F,*,+}④文法用于描述语言的语法结构，它由如下四个部分组成： ACD 和文法开始符号。
A.文法终结符集B.字母数字串C. 文法非终结符集D.文法产生式集⑤一个文法被称为是二义性的，如果 D 。
A.文法的某一个句子有两个以上的最右或最左推导。
B.文法的预测分析表中有多重入口。
C.文法的某个LR(0)项目集中有冲突项目。
D.文法的某一个句子有两棵以上不同的语法树。
⑥程序设计语言的单词符号一般可分为五种，它们是保留字、 AD 及运算符和定界符。
A.常数B.表达式C.注解D.标识符⑦设有一个LR(0)项目集I={A→β.bδ， B→β. ，D→δ.}，I中存在冲突项目，它们是 AD 。
A.“移进-归约”冲突B. “移进-接受”冲突C. “移进-待约”冲突D. “归约-归约”冲突⑧一个文法的SLR(1)方法和与其相应的LR(0)方法的状态数 A 。
A.相同B.不相同的C.前者大于后者D.后者大于前者四、计算题（共10分；画出语法树4分；其余按要求分别得：1分+1分+2分+2分）对于如下文法G B：B → B + D| DD→ D * F| F 给出句型D + D *d+d 的最左素短语、句柄、F→ ( B ) | d 所有直接短语、短语。
解：已知NFA如下图所示。
(8分=6分+2分)<1>确定化。
(状态转换矩阵4分；状态转换图2分) <2>写出与其等价的右线性文法。
解：<1> 计算出DFA的状态转换矩阵4分；画出相应的状态转换图2分<2>与其等价的右线性文法为：G A：A → dA | bB | b A → dA | bA | bB | B A代表结点1B → bB | dA | b B → bC | b B代表结点2按确定化后的DFA构造的结果；按NFA构造的结果对于文法G E：（共8分：语法树2分；其余按要求分别得1分、1分、2 分、2分）E → E + B| BB→ B * F| F 给出句型B + B * b + b 的最左素短语、句柄、F→ ( E ) | b 直接短语和所有短语。
