编译原理2012复习.ppt

复习,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=NFAThompsonsconstructionNFA=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,请解释下面各正则表达式的含义，并分别列出其生成语言的实例。aa-zA-Z(0-9|a-zA-Z)*bAA*n|*AAnc(+|-)?0-9+(“”0-9+)?d(b*ab*ab*)+,第二章2011,（15分）已知正则表达式(aa|b)*a(a|b|)1.利用Thompson构造法(Thompsonsconstruction)将该正规表达式(regularexpression)转化为NFA；2.将1中得到的NFA转化为DFA；3.将2中得到的DFA进行化简，以得到状态数最少的DFA。,下面的DFA中，（）可以合并。A状态1和状态2；B状态2和状态3；C状态1和状态3；D以上都不对。,第二章2010,第二章2010,请写出下面各个字符串的正规表达式(regularexpression)a十六进制的数字串；b含有偶数个2的数字串；c不以AA开头的大写字母串。,第二章2010,（15分）已知正则表达式(a|b)*a(b|)1.利用Thompson构造法(Thompsonsconstruction)将该正规表达式(regularexpression)转化为NFA；2.将1中得到的NFA转化为DFA；3.将2中得到的DFA进行化简，以得到状态数最少的DFA。,第二章2009,表示“由a或b组成的含有偶数个b的字符串”的正则表达式是（）Aa*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,判断：一个文法所描述的语言是唯一的；描述一个语言的文法是不唯一的。（）考虑下列文法GD：DTVTint|floatVid，V|id请给出intid，id，id进行的最右推导过程，并画出其分析树或语法树,第三章2010,判断：一个文法所描述的语言是不唯一的；描述一个语言的文法是唯一的。（）分析器(parser)的主要功能是进行_，分析器的输入是_，输出是_。,第三章2010,请写出下面文法对于表达式（）（）进行的最左推导过程，并画出其分析树或语法树。A（A）A|试描述由下列文法所产生的语言。SaSS|a,第三章2009,在文法中可能引起二义性的原因有：（）A运算的优先级B.运算的结合性Celse的悬挂问题D.以上都有可能,第三章2008,以下对于语法二义性的描述正确的是（）。A如果文法G的某个句子存在两棵或者两棵以上的语法树（或分析树），则称该文法是存在二义性的；B如果文法G的某个文法存在两个或者两个以上的句子符合该文法规则，则称该文法是存在二义性的；C消除文法二义性只能对文法进行修改，别无他法；D能够通过算法判别文法是否存在二义性。编译过程中，语法分析器的任务是_。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构A、和B、C、D、,第三章2008,已知文法GS：S:=a|(T)T:=T，S|S给出句子（a，（a，a）的最左推导并画出语法树。,第四章要点,语法分析的分类：自顶向下，自底向上自顶向下分析方法：递归下降，LL(1)分析LL(1)基本方法，三种动作（生成、匹配、接受）判断文法是否是LL(1)文法First集和Follow集左递归和左因子的消除构造分析表,第四章2011,对下面文法中非终结符First集合描述正确的是（）。E(L)|a|LEL+|EAFirst(E)=(a+BFirst(L)=(a+CFirst(E)=(a+DFirst(L)=(a+,第四章2011,考虑下列文法GS：SPSk|PPa|*S*|S为开始符号，请计算S和P的First集合和Follow集合，判断文法GS是否是LL(1)文法并说明理由。,第四章2011,（20分）已知文法GS为SSAT|TA+|-T(S)|k1通过消除左递归和提取左因子（回溯），给出与GS等价的文法GS；2计算文法GS非终结符的First集合和Follow集合；3判断文法GS是否为LL(1)文法；4如果文法GS是LL(1)文法，构造GA的分析表；5给出输入串k-(k+k)的分析过程。,第四章2010,对于文法GS：SQ*S|Q|SQa|(S)|S为开始符号，请计算S和Q的First集合和Follow集合。,第四章2010,已知文法GA为Aa|Bb|PP*A|Ak通过消除左递归和提取左因子（回溯），给出与GA等价的文法GA；计算文法GA非终结符的First集合和Follow集合；判断文法GA是否为LL(1)文法；如果文法GA是LL(1)文法，构造GA的分析表；给出输入串的分析过程。,第四章2009,设有文法GS：SXS|XaSb|S|c计算文法GS非终结符的First集合和Follow集合；若采用自顶向下分析方法，对此文法来说，在分析过程中能否避免二义性？为什么？分析符号串aababb是否为此文法的句子。,第四章2009,已知文法GA为A(L)A|(x)LL,s|k通过消除左递归和提取左因子（回溯），给出与GA等价的文法GA；计算文法GA非终结符的First集合和Follow集合；判断文法GA是否为LL(1)文法；如果文法GA是LL(1)文法，构造GA的分析表；给出输入串(k,s,s)(x)的分析过程。,第四章2008,高级语言编译程序常用的语法分析方法中，递归下降分析法属于_分析方法。A、自左至右B自顶向下C、自底向上D自右向左LL(1)分析方法是这样得名的：第一个“L”指的是_，第二个“L”指的是_，括号中的数字1指的是_。,第四章2008,（10分）设有文法GZ：Z:=(A)A:=abBB:=Aab(1)若采用自顶向下分析方法，对此文法来说，在分析过程中能否避免二义性？为什么？(2)分析符号串（bbaabab）是否为此文法的句子。（20分）已知文法GA为A:=aABe|aB:=Bb|d(1)通过消除左递归和提取左因子（回溯），给出与GA等价的文法GA；(2)计算文法GA非终结符的FIRST集合和FOLLOW集合；(3)判断文法GA是否为LL(1)文法；(4)如果文法GA是LL(1)文法，构造GA的分析表；(5)给出输入串aade的分析过程。,第五章要点,什么是自底向上的分析方法基本操作：移入、归约方法及能力：LR(0)SLR(1)SLR(k)LR(0)SLR(1)EL|Ea为这个文法构造LR(0)项目的DFAb构造SLR(1)分析表c对输入串(qq)进行分析（15分）,第六章要点,属性文法概念：联编联编时间静态语义和动态语义常见的静态语义符号表的作用、内容符号表存储的属性,第六章2008-2011,下面不属于语义属性的是（）A.变量的数据类型B.表达式的值C.变量对应的内存地址D.源程序文件名判断：为了提高查找及存取速度，符号表都采用有序表的形式。（）,第七章要点,概念运行时环境过程活动记录调用序列和返回序列几种运行时环境及其特点，举例。完全静态的运行时环境基于栈的运行时环境,第七章2008-2011,在编译方法中，动态存储分配的含义是_。A、在运行阶段对源程序中的量进行分配B、在编译阶段对源程序中的量进行分配C、在编译阶段对源程序中的量进行分配，在运行时这些量的地址可以根据需要改变D、以上都不正确对于数据空间的存贮分配，FORTRAN采用_策略