编译原理小测验(有答案)

《编译原理小测验(有答案)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、选择题1.词法分析器的输入（）A．单词符号B．源程序C．语法单位D．目标程序2.构造编译程序应该掌握()。A.源程序B.目标语言C.目标代码生成D.以上三者都要3.编译程序绝大多数时间花在（）。A.出错处理B.词法分析C.目标代码生成D.表格管理4.编译程序的各阶段都涉及到（）。A.词法分析B.表格管理C.语法分析D.语义分析5.解释程序和编译程序的区别是（）之间的转换。A.是否生成中间代码B.加工的对象不同C.使用的实现技术不同D.是否生成目标代码6.一个上下文无关文法G包含四个组成部分，依次为：一组

2、（　G　　），一组（H　　），一个（　E　　）和一组（　C　　）。　A．字符串　　　　　B.字母数字串C.产生式D.结束符号E.开始符号F.文法G.非终结符H.终结符7.一个语言的文法是（）。A．唯一的B.不唯一的C.数量有限的8.编译程序中的语法分析器接受以（）为单位的输入，并产生有关信息供以后各阶段使用。A.表达式B.产生式C.单词D.语句9.文法的二义性和语法的二义性是两个（）的概念。A.不同B.相同C.无法判断10、如果L(M)=L(M'），则M与M'（）A．等价B．M与M'都是二义的C．M与M'都

3、是无二义的D．他们的状态数相等11、如果文法G是无二义的，则它的任何句子α（）A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同12、给定文法,A->bA

4、cc,下面哪些符号串可由其推导出（）。①cc②b*cc③b*cbcc④bccbcc⑤bbbcc可选项有：a.①b.①③④⑤c.①⑤d.①②⑤e.①②③④⑤13.若一个文法是递归的，则它所产生语言的句子个数（）。a.必定是无穷的b.是有限个

5、的c.根据具体情况而定14.Chmosky的3型语言是这样一种语言，其产生式限制为____。a.A->πb.A->aA->aBc.α->βd.αAβ->απβ15.词法分析器的输出结果是（）。A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值16、文法：G：S→xSx

6、y所识别的语言是（）。A、xyxB、（xyx）*C、x+yx+D、{xnyxn

7、（n≥0）}二、判断题设有文法G[I]:  I->I1/I0/Ia/Ic/a/b/c  判断下面符号串中哪些是该文法的句子.  (

8、1)ab0  (2)a0c01  (3)aaa  (4)bc10  (5)aabc  (6)bbca答：(1)错误  (2)正确  (3)正确  (4)正确  (5)错误  (6)错误  三、问答题1.什么是正规式，正规式的递归定义是什么？答：正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。下面是正规式和它所表示的正规集的递归定义。    设字母表为∑，辅助字母表为∑'={Ф，ε，

9、，·，*，(，)}  (1).ε和Ф都是∑上的正规式，它们所表示的正规集分别为{ε}和Ф  (

10、2).任意a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}  (3).若e1，e2都是∑上的一个正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么e1

11、e2，e1·e2和，(e1)也都是正规式,它们所表示的正规集分别为L(e1)∪L(e2),L(e1)·L(e2)和，L(e1)  (4).仅由有限次使用上述三步骤而定义的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上正规集。2.何谓二义性文法？试举一例说明。答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性

12、的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。3.什么是有穷自动机？什么是确定的有穷自动机？答：有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。    有穷自动机分为两类：确定的有穷自动机(DeterministicFiniteAutomata)和不确定的有穷自动机(NondeterministicFiniteAutomata)，下面我们分别给出确定

13、有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。确定的有穷自动机（DFA）一个确定的有穷自动机（DFA）是一个五元组：M=（K，∑，f，S，Z），其中  (1)K是一个有穷集，它的每个元素称为一个状态；  (2)∑是一个有穷字母表，它的每个元素称为一个输入字符，所以也称∑为输入符号字母表；  (3)f是转换函数，是在K×∑→K上映像，即，如f（，a）=（∈