2015编译原理复习详解

复习2015.7.1第一章要点编译器的概念。其输入和输出。机器语言->汇编语言->高级语言。乔姆斯基分层结构。0型-无限制文法1型-上下文相关文法2型-上下文无关文法3型-正则文法第一章要点相关程序和概念说明器编辑器交互式开发环境（IDE）调试程序分析和综合前端和后端遍※编译器的翻译过程T型图第一章编译器各处理阶段的正确依次是（）A．词法分析、语法分析、语义分析、代码生成；B．语法分析、词法分析、语义分析、代码生成；C．语义分析，语法分析、词法分析，代码生成；D．以上都不对。编译器中语法分析的输入和输出分别是（） A．字符串、记号串 B．记号串、注释树 C．记号串、语法树 D．语法树、注释树什么是编译器？请简述编译器的功能及其输入输出。第一章以下对编译器(compiler)描述错误的是（）。A编译器的输入是由源语言编写的源程序，输出是由目标语言编写的目标程序。B编译器是一个执行程序而不是一个转换程序。C编译器和编辑器以及其它程序常常被捆绑成一个与用户交互的开发环境(IDE)中。D依据编译器扫描的遍数，可把编译器分为一遍扫描和多遍扫描的编译器。把汇编语言程序翻译成机器可执行的目标程序的工作是由______完成的。A、编译器B、说明器C、汇编器D、预处理器第一章编译器的工作可分为多个阶段，词法分析、语法分析、语义分析阶段的结果分别是（）。A分析树、语法树、语义树；B分析树、语法树、注释树；C记号序列、语法树、语义树；D记号序列、分析树、注释树。文法依据限定条件分为四种文法：0型文法、1型文法、2型文法、3型文法。其中2型文法又叫做（）文法，3型文法又叫做（）文法。高级程序设计语言源程序有两种执行方式，即____和____。什么是编译器？什么是遍。什么是扫描器？扫描器的功能是什么？第一章以下对编译器(compiler)描述错误的是（）。A.编译器是将一种语言翻译成另一种语言的计算机部件，包括软件部分和硬件部分；B.输入编译器的源语言通常是高级语言，如C语言；输出编译器的目标语言通常是低级语言，如01代码；C.词法分析是编译器的一个处理阶段；D.编译器和编辑器以及其它程序常常被捆绑成一个与用户交互的开发环境(IDE)中。第一章汇编语言与机器语言相比，其主要优点在于（）。A．汇编语言机器依靠性强；B．汇编程序的可执行程序的长度可以大幅下降；C．汇编语言的符号形式更易理解，也提高了编写程序的精确性；D．以上都不对。第一章一般的编译器中，语法分析的结果是生成源程序的（）。A．记号序列； B．分析树；C．语法树； D．注释树。编译程序和说明程序有哪些区分？第一章下列程序中没有翻译功能的是（）。 A汇编器 B说明器 C编译器 D编辑器推断：假如编译器的源语言发生了变更，那么其前端操作无需修改。（）什么是语义分析程序？请说明其功能及其输入和输出。其次章要点扫描程序的功能及其输入输出。正则表达式什么是由r生成的语言，字母表，元符号三种基本操作有限自动机定义DFANFA其次章要点※正则表达式=>NFA=>DFA=>程序RE=>NFAThompson’sconstructionNFA=>DFA子集构造法DFA的化简DFA=>程序三种方式+Lex其次章以下对扫描器（scanner）描述正确的是（）。 A扫描器是编译器的一个功能模块，其功能是进行语义分析； B扫描器的输入是语法树，输出是注释树； C扫描器须要分析哪些字符组成了“词”； D扫描器无需提示任何错误，而是由其它编译器模块来完成。其次章下面不属于正则表达式（regularexpression）的基本操作的是（

）。 A递归 B并置

C选择 D闭包其次章下面的NFA中，对状态或状态集合的ε-闭包描述正确的是（

）。A状态1的ε-闭包是{2、4}；B状态{2、3}的ε-闭包是{2、3、4}；C状态3的ε-闭包是{2、4}；D状态4的ε-闭包是空集。其次章7.正则表达式(a|b)+生成的语言，以下描述正确的是（）。 AL((a|b)+)={由a和b组成的随意字符串} BL((a|b)+)={由a组成的字符串或由b组成的字符串} CL((a|b)+)={由a组成的字符串和由b组成的字符串} D以上都不对其次章请说明下面各正则表达式的含义，并分别列出其生成语言的实例。 a．[a-zA-Z]([0-9]|[a-zA-Z])* b．AA*\n|*AA\n c．(+|-)?[0-9]+(“”[0-9]+)? d．(b*ab*ab*)+其次章（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．以上都不对。其次章其次章请写出下面各个字符串的正规表达式(regularexpression)a．十六进制的数字串；b．含有偶数个2的数字串；c．不以AA开头的大写字母串。其次章（15分）已知正则表达式(a|b)*a(b|ε)1.利用Thompson构造法(Thompson’sconstruction)将该正规表达式(regularexpression)转化为NFA；2.将1中得到的NFA转化为DFA；3.将2中得到的DFA进行化简，以得到状态数最少的DFA。其次章表示“由a或b组成的含有偶数个b的字符串”的正则表达式是（） A．a*ba*ba* B.(a*ba*ba*)* C．(abab)* D.以上都不对请写出下面各个字符串的正则表达式全部整数的数字串（包括负数）字符串中至多含有一个A的大写字母串请简述有限自动机的组成元素并说明DFA和NFA的区分。其次章以下不是有限自动机的组成元素的是（） A．起先状态 B．结束状态 C．正则表达式 D．状态转换函数已知正则表达式(ab)*(a|b)1．构造该正则表达式所对应的NFA；2．由NFA构造DFA；3．对DFA进行最小化。其次章以下对有穷自动机的图形表示描述错误的是（）。用带箭头的线表示一个状态到另一个状态的转换；用圆圈表示状态；用双线边界的圆圈表示接受状态。一个有穷自动机里只能有唯一的一个接受状态；对于给定的一个非确定性有限自动机（NFA），以下正确的是（）。不存在与之等价的DFA。存在一个唯一等价的DFA。存在一个唯一的具有最少状态数的等价DFA。存在等价DFA，但具有最少状态数的DFA不唯一。其次章请写出下面各个字符串的正则表达式：以a开头或者以b结尾的小写字母串；以字母开头，后面是数字或字母的符号串；（即标识符）已知正则表达式a(ba)*（1）构造该正则表达式所对应的NFA；（2）由NFA构造DFA；（3）对DFA进行最小化。第三章要点分析程序的功能及其输入输出。常见的高级语言的文法（上下文无关文法）、表示方式（BNF）以及其特点（包含递归）。推导分析给定文法的：终结符、非终结符、生成的语言、对某个串的推导。二义性文法概念及消退二义性的方法（1、2）常见产生缘由及消退的方法第三章在一般的编译器中，语法分析基于（

）文法进行，即识别的单词串是该类文法的句子。分析器（parser）的主要功能是进行（

）。第三章以下对于文法二义性的描述正确的是（）。A LL(1)文法是无二义性文法；B 二义性文法会对全部的符号串产生多个语法树；C 通过相应算法可以推断文法的二义性；D 在语法分析中，二义性文法是不被允许的，必需通过修改文法来消退。第三章推断：一个文法所描述的语言是唯一的；描述一个语言的文法是不唯一的。（）考虑下列文法G[D]： DTV Tint|float Vid，V|id请给出intid，id，id进行的最右推导过程，并画出其分析树或语法树第三章分析器(parser)的主要功能是进行__________，分析器的输入是________，输出是________。第三章请写出下面文法对于表达式（（））（）进行的最左推导过程，并画出其分析树或语法树。 A→（A）A|ε试描述由下列文法所产生的语言。 S→aSS|a第三章在文法中可能引起二义性的缘由有：（） A．运算的优先级 B.运算的结合性 C．else的悬挂问题 D.以上都有可能第三章以下对于语法二义性的描述正确的是（）。A假如文法G的某个句子存在两棵或者两棵以上的语法树（或分析树），则称该文法是存在二义性的；B假如文法G的某个文法存在两个或者两个以上的句子符合该文法规则，则称该文法是存在二义性的；C消退文法二义性只能对文法进行修改，别无他法；D能够通过算法判别文法是否存在二义性。编译过程中，语法分析器的任务是_______。①分析单词是怎样构成的②分析单词串是如何构成语句和说明的③分析语句和说明是如何构成程序的④分析程序的结构A、②和③ B、④C、②③④D、①②③④第三章已知文法G[S]：S::=a|(T) T::=T，S|S

给出句子（a，（a，a））的最左推导并画出语法树。第四章要点语法分析的分类：自顶向下，自底向上自顶向下分析方法：递归下降，LL(1)分析LL(1)基本方法，三种动作（生成、匹配、接受）推断文法是否是LL(1)文法First集和Follow集左递归和左因子的消退构造分析表第四章对下面文法中非终结符First集合描述正确的是（

）。 E(L)|a|ε LEL+|E AFirst(E)={(a+} BFirst(L)={(a+} CFirst(E)={(a+ε} DFirst(L)={(a+ε}第四章考虑下列文法G[S]： SPSk|P Pa|*S*|εS为起先符号，请计算S和P的First集合和Follow集合，推断文法G[S]是否是LL(1)文法并说明理由。第四章（20分）已知文法G[S]为 SSAT|T A+|- 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)的分析过程。第四章对于文法G[S]：S→Q*S|Q|SQ→a|(S)|εS为起先符号，请计算S和Q的FIRST集合和FOLLOW集合。第四章已知文法G[A]为 A→a|<BP> B→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>的分析过程。第四章设有文法G[S]： S→XS|ε X→aSb|{S}|c计算文法G[S]非终结符的FIRST集合和FOLLOW集合；若接受自顶向下分析方法，对此文法来说，在分析过程中能否避开二义性？为什么？分析符号串aababb是否为此文法的句子。第四章已知文法G[A]为 A→(L)A|(x) L→L,s|k通过消退左递归和提取左因子（回溯），给出与G[A]等价的文法G’[A]；计算文法G’[A]非终结符的FIRST集合和FOLLOW集合；推断文法G’[A]是否为LL(1)文法；假如文法G’[A]是LL(1)文法，构造G’[A]的分析表；给出输入串(k,s,s)(x)的分析过程。第四章高级语言编译程序常用的语法分析方法中，递归下降分析法属于______分析方法。 A、自左至右B．自顶向下 C、自底向上D．自右向左LL(1)分析方法是这样得名的：第一个“L”指的是___，其次个“L”指的是___，括号中的数字1指的是___。第四章（10分）设有文法G[Z]： Z::=(A) A::=a│bB B::=Aab(1)若接受自顶向下分析方法，对此文法来说，在分析过程中能否避开二义性？为什么？(2)分析符号串（bbaabab）是否为此文法的句子。（20分）已知文法G[A]为A::=aABe|aB::=Bb|d(1)通过消退左递归和提取左因子（回溯），给出与G[A]等价的文法G’[A]；(2)计算文法G’[A]非终结符的FIRST集合和FOLLOW集合；(3)推断文法G’[A]是否为LL(1)文法；(4)假如文法G’[A]是LL(1)文法，构造G’[A]的分析表；(5)给出输入串aade的分析过程。第五章要点什么是自底向上的分析方法基本操作：移入、归约方法及实力、符号的意义：LR(0)<SLR(1)<SLR(k)LR(0)<SLR(1)<LR(1)<LR(K)LR(0)项构造DFA核心项、闭包项第五章要点分析过程 LR(0) SLR(1)移入归约冲突、归约归约冲突（留意两种方法的冲突有不同之处）LR(0)文法的推断SLR(1)文法的推断第五章LR(0)分析中的分析动作包括__________和__________。第五章对于文法：E->(L)|qL->EL|Ea．为这个文法构造LR(0)项目的DFAb．构造SLR(1)分析表c．对输入串(q

q)进行分析（15分）第五章课后习题5.1、5.3第六章要点属性文法概念：联编联编时间静态语义和动态语义常见的静态语义符号表的作用、内容符号表存储的属性第六章属性文法例题2、例题3第六章下面不属于语义属性的是（ ）A.变量的数据类型 B.表达式的值C.变量对应的内存地址 D.源程序文件名推断：为了提高查找及存取速度，符号表都接受有序表的形式。（）第七章要点概念运行时环境过程活动记录调用序列和返回序列几种运行时环境及其特点，举例。完全静态的运行时环境FORTRAN77不允许递归调用、不支持指针基于栈的