编译原理2012复习

复习2011.4.26第一章要点编译器的概念。其输入和输出。机器语言-汇编语言-高级语言。乔姆斯基分层结构。0型-无限制文法1型-上下文相关文法2型-上下文无关文法3型-正则文法第一章要点相关程序和概念解释器编辑器交互式开发环境（IDE）调试程序分析和综合前端和后端遍※编译器的翻译过程第一章2009编译器各处理阶段的正确顺序是（）A．词法分析、语法分析、语义分析、代码生成；B．语法分析、词法分析、语义分析、代码生成；C．语义分析，语法分析、词法分析，代码生成；D．以上都不对。编译器中语法分析的输入和输出分别是（）A．字符串、记号串B．记号串、注释树C．记号串、语法树D．语法树、注释树什么是编译器？请简述编译器的功能及其输入输出。第一章2008以下对编译器(compiler)描述错误的是（）。A编译器的输入是由源语言编写的源程序，输出是由目标语言编写的目标程序。B编译器是一个执行程序而不是一个转换程序。C编译器和编辑器以及其它程序经常被捆绑成一个与用户交互的开发环境(IDE)中。D按照编译器扫描的遍数，可把编译器分为一遍扫描和多遍扫描的编译器。把汇编语言程序翻译成机器可执行的目标程序的工作是由______完成的。A、编译器B、解释器C、汇编器D、预处理器第一章2008编译器的工作可分为多个阶段，词法分析、语法分析、语义分析阶段的结果分别是（）。A分析树、语法树、语义树；B分析树、语法树、注释树；C记号序列、语法树、语义树；D记号序列、分析树、注释树。文法根据限定条件分为四种文法：0型文法、1型文法、2型文法、3型文法。其中2型文法又叫做（）文法，3型文法又叫做（）文法。高级程序设计语言源程序有两种执行方式，即____和____。什么是编译器？什么是遍。什么是扫描器？扫描器的功能是什么？第一章2010以下对编译器(compiler)描述错误的是（）。A.编译器是将一种语言翻译成另一种语言的计算机部件，包括软件部分和硬件部分；B.输入编译器的源语言通常是高级语言，如C语言；输出编译器的目标语言通常是低级语言，如01代码；C.词法分析是编译器的一个处理阶段；D.编译器和编辑器以及其它程序经常被捆绑成一个与用户交互的开发环境(IDE)中。第一章2010汇编语言与机器语言相比，其主要优点在于（）。A．汇编语言机器依赖性强；B．汇编程序的可执行程序的长度可以大幅下降；C．汇编语言的符号形式更易理解，也提高了编写程序的准确性；D．以上都不对。第一章2010一般的编译器中，语法分析的结果是生成源程序的（）。A．记号序列；B．分析树；C．语法树；D．注释树。编译程序和解释程序有哪些区别？第一章2011下列程序中没有翻译功能的是（）。A汇编器B解释器C编译器D编辑器判断：如果编译器的源语言发生了改变，那么其前端操作无需修改。（）什么是语义分析程序？请解释其功能及其输入和输出。第二章要点扫描程序的功能及其输入输出。正则表达式什么是由r生成的语言，字母表，元符号三种基本操作有限自动机定义DFANFA第二章要点※正则表达式=NFA=DFA=程序RE=NFAThompson’sconstructionNFA=DFA子集构造法DFA的化简DFA=程序三种方式+Lex第二章2011以下对扫描器（scanner）描述正确的是（）。A扫描器是编译器的一个功能模块，其功能是进行语义分析；B扫描器的输入是语法树，输出是注释树；C扫描器需要分析哪些字符组成了“词”；D扫描器无需提示任何错误，而是由其它编译器模块来完成。第二章2011下面不属于正则表达式（regularexpression）的基本操作的是（）。A递归B并置C选择D闭包第二章2011下面的NFA中，对状态或状态集合的ε-闭包描述正确的是（）。A状态1的ε-闭包是{2、4}；B状态{2、3}的ε-闭包是{2、3、4}；C状态3的ε-闭包是{2、4}；D状态4的ε-闭包是空集。第二章20117.正则表达式(a|b)+生成的语言，以下描述正确的是（）。AL((a|b)+)={由a和b组成的任意字符串}BL((a|b)+)={由a组成的字符串或由b组成的字符串}CL((a|b)+)={由a组成的字符串和由b组成的字符串}D以上都不对第二章2011请解释下面各正则表达式的含义，并分别列出其生成语言的实例。a．[a-zA-Z]([0-9]|[a-zA-Z])*b．AA*\n|*AA\nc．(+|-)?[0-9]+(“”[0-9]+)?d．(b*ab*ab*)+第二章2011（15分）已知正则表达式(aa|b)*a(a|b|ε)1.利用Thompson构造法(Thompson’sconstruction)将该正规表达式(regularexpression)转化为NFA；2.将1中得到的NFA转化为DFA；3.将2中得到的DFA进行化简，以得到状态数最少的DFA。下面的DFA中，（）可以合并。A．状态1和状态2；B．状态2和状态3；C．状态1和状态3；D．以上都不对。第二章2010123abbb第二章2010请写出下面各个字符串的正规表达式(regularexpression)a．十六进制的数字串；b．含有偶数个2的数字串；c．不以AA开头的大写字母串。第二章2010（15分）已知正则表达式(a|b)*a(b|ε)1.利用Thompson构造法(Thompson’sconstruction)将该正规表达式(regularexpression)转化为NFA；2.将1中得到的NFA转化为DFA；3.将2中得到的DFA进行化简，以得到状态数最少的DFA。第二章2009表示“由a或b组成的含有偶数个b的字符串”的正则表达式是（）A．a*ba*ba*B.(a*ba*ba*)*C．(abab)*D.以上都不对请写出下面各个字符串的正则表达式所有整数的数字串（包括负数）字符串中至多含有一个A的大写字母串请简述有限自动机的组成元素并解释DFA和NFA的区别。第二章2009以下不是有限自动机的组成元素的是（）A．开始状态B．结束状态C．正则表达式D．状态转换函数已知正则表达式(ab)*(a|b)1．构造该正则表达式所对应的NFA；2．由NFA构造DFA；3．对DFA进行最小化。第二章2008以下对有穷自动机的图形表示描述错误的是（）。用带箭头的线表示一个状态到另一个状态的转换；用圆圈表示状态；用双线边界的圆圈表示接受状态。一个有穷自动机里只能有唯一的一个接受状态；对于给定的一个非确定性有限自动机（NFA），以下正确的是（）。不存在与之等价的DFA。存在一个唯一等价的DFA。存在一个唯一的具有最少状态数的等价DFA。存在等价DFA，但具有最少状态数的DFA不唯一。第二章2008请写出下面各个字符串的正则表达式：以a开头或者以b结尾的小写字母串；以字母开头，后面是数字或字母的符号串；（即标识符）已知正则表达式a(ba)*（1）构造该正则表达式所对应的NFA；（2）由NFA构造DFA；（3）对DFA进行最小化。第三章要点分析程序的功能及其输入输出。常见的高级语言的文法（上下文无关文法）、表示方式（BNF）以及其特点（包含递归）。推导分析给定文法的：终结符、非终结符、生成的语言、对某个串的推导。二义性文法概念及消除二义性的方法（1、2）常见产生原因及消除的方法第三章2011在一般的编译器中，语法分析基于（）文法进行，即识别的单词串是该类文法的句子。分析器（parser）的主要功能是进行（）。第三章2011以下对于文法二义性的描述正确的是（）。ALL(1)文法是无二义性文法；B二义性文法会对所有的符号串产生多个语法树；C通过相应算法可以判断文法的二义性；D在语法分析中，二义性文法是不被允许的，必须通过修改文法来消除。第三章2011判断：一个文法所描述的语言是唯一的；描述一个语言的文法是不唯一的。（）考虑下列文法G[D]：DTVTint|floatVid，V|id请给出intid，id，id进行的最右推导过程，并画出其分析树或语法树第三章2010判断：一个文法所描述的语言是不唯一的；描述一个语言的文法是唯一的。（）分析器(parser)的主要功能是进行__________，分析器的输入是________，输出是________。第三章2010请写出下面文法对于表达式（（））（）进行的最左推导过程，并画出其分析树或语法树。A→（A）A|ε试描述由下列文法所产生的语言。S→aSS|a第三章2009在文法中可能引起二义性的原因有：（）A．运算的优先级B.运算的结合性C．else的悬挂问题D.以上都有可能第三章2008以下对于语法二义性的描述正确的是（）。A如果文法G的某个句子存在两棵或者两棵以上的语法树（或分析树），则称该文法是存在二义性的；B如果文法G的某个文法存在两个或者两个以上的句子符合该文法规则，则称该文法是存在二义性的；C消除文法二义性只能对文法进行修改，别无他法；D能够通过算法判别文法是否存在二义性。编译过程中，语法分析器的任务是_______。①分析单词是怎样构成的②分析单词串是如何构成语句和说明的③分析语句和说明是如何构成程序的④分析程序的结构A、②和③B、④C、②③④D、①②③④第三章2008已知文法G[S]：S::=a|(T)T::=T，S|S给出句子（a，（a，a））的最左推导并画出语法树。第四章要点语法分析的分类：自顶向下，自底向上自顶向下分析方法：递归下降，LL(1)分析LL(1)基本方法，三种动作（生成、匹配、接受）判断文法是否是LL(1)文法First集和Follow集左递归和左因子的消除构造分析表第四章2011对下面文法中非终结符First集合描述正确的是（）。E(L)|a|εLEL+|EAFirst(E)={(a+}BFirst(L)={(a+}CFirst(E)={(a+ε}DFirst(L)={(a+ε}第四章2011考虑下列文法G[S]：SPSk|PPa|*S*|εS为开始符号，请计算S和P的First集合和Follow集合，判断文法G[S]是否是LL(1)文法并说明理由。第四章2011（20分）已知文法G[S]为SSAT|TA+|-T(S)|k1．通过消除左递归和提取左因子（回溯），给出与G[S]等价的文法G’[S]；2．计算文法G’[S]非终结符的First集合和Follow集合；3．判断文法G’[S]是否为LL(1)文法；4．如果文法G’[S]是LL(1)文法，构造G’[A]的分析表；5．给出输入串k-(k+k)的分析过程。第四章2010对于文法G[S]：S→Q*S|Q|SQ→a|(S)|εS为开始符号，请计算S和Q的FIRST集合和FOLLOW集合。第四章2010已知文法G[A]为A→a|BPB→b|εP→P*A|Ak通过消除左递归和提取左因子（回溯），给出与G[A]等价的文法G’[A]；计算文法G’[A]非终结符的FIRST集合和FOLLOW集合；判断文法G’[A]是否为LL(1)文法；如果文法G’[A]是LL(1)文法，构造G’[A]的分析表；给出输入串bak*a的分析过程。第四章2009设有文法G[S]：S→XS|εX→aSb|{S}|c计算文法G[S]非终结符的FIRST集合和FOLLOW集合；若采用自顶向下分析方法，对此文法来说，在分析过程中能否避免二义性？为什么？分析符号串aababb是否为此文法的句子。第四章2009已知文法G[A]为A→(L)A|(x)L→L,s|k通过消除左递归和提取左因子（回溯），给出与G[A]等价的文法G’[A]；计算文法G’[A]非终结符的FIRST