《编译原理试卷.doc》由会员分享，可在线阅读，更多相关《编译原理试卷.doc（12页珍藏版）》请在金锄头文库上搜索。
1、一、判断对错：（对 ；错 ； 每小问2分共24分）算符优先分析法是一种规范归约分析法。（ ）若文法Gs中不含形如TBD的产生式，T、B、DVN，则称Gs为算符文法。（ ）若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ ）若两个正规式所表示的正规集相同，则认为二者是等价的。 （ ）LR分析法是一种规范归约分析法。（ ）一个LR(0)项目集I=B .b, P aA.,则说I中含有“移进归约”冲突。（）SLR(1)文法是无二义性文法。（ ）消除左递归后的文法一定是LL(1)文法。（ ）对任何编译程序而言，代码优化是必不可少的。（ ）编译程序与具体的机器无关。（ ）在自动机的概念中，终态与非
2、终态是可区别的。（ ）逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（ ）1. 一个语言有文法是不惟一的。（ ）2. 若一个语言是无穷集合，则定义该语言的文法一定是递归的。（ ）3. 紧跟在条件转移语句后面的语句是基本块的入口语句。（ ）4. 算符优先分析法是一种规范归约分析法。（ ）5. 自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。（）6. LR(0)文法、SLR(1)文法都是无二义性文法。（ ）7K、分别表示有限状态集和有穷字母表, DFA M的转换函数f是一个从K 到K的单值映射。（ ）8. 对任何编译程序而言，代码优化是必不可少的。（
3、）9. 直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。（ ）10. 两个有穷自动机等价是指它们的状态数和有向弧数相等。（ ）11. 一个LR(0)项目集为：I=Aa.b, D.,则说I中含有“移进-归约”冲突。（ ）12. 若两个正规式所表示的正规集相同，则认为二者是等价的。 （ ）13. 无左递归的文法是LL(1)文法。（ ）14. 逆波兰式abcde/+*+所代表的中缀表达式是：a+b*(c+d/e)（ ）15. 编译程序结构中，中间代码优化及目标代码生成两个阶段与具体的机器有关。（ ）16. LALR分析法中，同心集的合并不会产生 “ 移进-归约 ” 冲突。（ ）
4、算符优先分析法是一种规范归约分析法。（ 错 ）若文法Gs中不含形如TBD的产生式，T、B、DVN，则称Gs为算符文法。（对 ）若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ 错 ）若两个正规式所表示的正规集相同，则认为二者是等价的。 （ 对 ）LR分析法是一种规范归约分析法。（ 对 ）一个LR(0)项目集I=B .b, P aA.,则说I中含有“移进归约”冲突。（ 对 ）SLR(1)文法是无二义性文法。（ 对 ）消除左递归后的文法一定是LL(1)文法。（错 ）对任何编译程序而言，代码优化是必不可少的。（ 错 ）编译程序与具体的机器无关。（ 错 ）二、将下图所示的NFA确定化。(状态转
5、换矩阵4分；状态转换图2分)解： 状态转换矩阵4分 状态转换图2分给出语言L= d an b | n1相应的文法。GA：A dBb GA：A dB B aB |a B aB | ab三、编译程序的工作过程一般划分为五个基本阶段： B；D 、语义分析和中间代码生成、代码优化和目标代码生成。A.出错处理 B.词法分析 C.表格管理 D.语法分析已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法终结符集合VT= A；C ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. +,(,),*,E C. +,*,(,),b D. E,T,F已知文法GE：EE+T
6、| T TT*F | F F(E) | b 那么，该文法的非终结符集VN= B ，GE称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.文法的某一个句子有两棵以上不同的语法树。程序设计语言的单词符
7、号一般可分为五种，它们是保留字、 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(
8、0)项目集簇的DFA中，若项目集k中含有项目“A.”，且仅当输入符号aFOLLOW(A)时，才用规则“A ”归约的语法分析方法是 D 。ALALR分析法 BLR(0)分析法 CLR(1)分析法 DSLR(1)分析法3程序设计语言的单词符号一般可分为五种，它们是常数、 C D 及运算符和定界符。A.注解 B.表达式 C.标识符 D.保留字4文法用于描述语言的语法结构，它由如下四个部分组成： A C D 和文法开始符号。A.文法终结符集 B.字母数字串 C. 文法非终结符集 D.文法产生式集5一个文法被称为是二义性的，如果 A C 。A.文法的某一个句子有两个以上的最右或最左推导。B.文法的预测分
9、析表中有多重入口。C.文法的某一个句子有两棵以上不同的语法树。 D.文法的某个LR(0)项目集中有冲突项目。6已知文法GB：BB+T | T TT*F | F F(B) | b 那么，该文法终结符集合VT= A B ， GE称2型文法或上下文无关文法。 A. VT=+,*,(,),b B. VT= b,(, +,* ,) C. VT=B,T,F D. VT=B,T,F,+,*,(,b,)7在动态存储分配时，可以采用的分配方法有 B C 。A.分时动态存储分配 B.栈式动态存储分配 C. 堆式动态存储分配 D.最佳动态存储分配8设有一个LR(0)项目集I=A.d；Ab.B； Bd. ；DdB.
10、，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.语法分析已知文法GE：EE
11、+T | T TT*F | F F(E) | b 那么，该文法终结符集合VT= AC ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. +,(,),*,E C. +,*,(,),b D. E,T,F已知文法GE：EE+T | T TT*F | F F(E) | b 那么，该文法的非终结符集VN= B ，GE称2型文法或上下文无关文法。A. +,(,),*,b B. E,T,F C. +,*,(,),b D. E,T,F,*,+文法用于描述语言的语法结构，它由如下四个部分组成： ACD 和文法开始符号。A.文法终结符集 B.字母数字串 C. 文法非终结符集 D.文法产生式集一个文
12、法被称为是二义性的，如果 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分）对于如下文法GB： B B + D | DD D * F | F 给出句型D + D *d+d 的最左素短语、句柄、F ( B ) | d 所有直接短语、短语。解：已知NFA如下图所示。(8分=6分+2分)确定化。(状态转换矩阵4分；状态转换图2分) 写出与其等价的右线性文法。
