编译原理复习.pptx

第一章要点编译器的概念。其输入和输出。机器语言-汇编语言-高级语言。乔姆斯基分层结构。0型-无限制文法1型-上下文相关文法2型-上下文无关文法3型-正则文法第1页/共58页第一章要点相关程序和概念解释器编辑器交互式开发环境（IDE）调试程序分析和综合前端和后端遍编译器的翻译过程T型图第2页/共58页第一章 编译器各处理阶段的正确顺序是（）A词法分析、语法分析、语义分析、代码生成；B语法分析、词法分析、语义分析、代码生成；C语义分析，语法分析、词法分析，代码生成；D以上都不对。编译器中语法分析的输入和输出分别是（）A字符串、记号串B记号串、注释树C记号串、语法树D语法树、注释树 什么是编译器？请简述编译器的功能及其输入输出。第3页/共58页第一章 以下对编译器(compiler)描述错误的是（）。A 编译器的输入是由源语言编写的源程序，输出是由目标语言编写的目标程序。B 编译器是一个执行程序而不是一个转换程序。C 编译器和编辑器以及其它程序经常被捆绑成一个与用户交互的开发环境(IDE)中。D 按照编译器扫描的遍数，可把编译器分为一遍扫描和多遍扫描的编译器。把汇编语言程序翻译成机器可执行的目标程序的工作是由_完成的。A、编译器 B、解释器C、汇编器 D、预处理器第4页/共58页第一章 编译器的工作可分为多个阶段，词法分析、语法分析、语义分析阶段的结果分别是（）。A 分析树、语法树、语义树；B 分析树、语法树、注释树；C 记号序列、语法树、语义树；D 记号序列、分析树、注释树。文法根据限定条件分为四种文法：0型文法、1型文法、2型文法、3型文法。其中2型文法又叫做（）文法，3型文法又叫做（）文法。高级程序设计语言源程序有两种执行方式，即_和_。什么是编译器？什么是遍。什么是扫描器？扫描器的功能是什么？第5页/共58页第一章 以下对编译器(compiler)描述错误的是（）。A.编译器是将一种语言翻译成另一种语言的计算机部件，包括软件部分和硬件部分；B.输入编译器的源语言通常是高级语言，如C语言；输出编译器的目标语言通常是低级语言，如01代码；C.词法分析是编译器的一个处理阶段；D.编译器和编辑器以及其它程序经常被捆绑成一个与用户交互的开发环境(IDE)中。第6页/共58页第一章 汇编语言与机器语言相比，其主要优点在于（）。A汇编语言机器依赖性强；B汇编程序的可执行程序的长度可以大幅下降；C汇编语言的符号形式更易理解，也提高了编写程序的准确性；D以上都不对。第7页/共58页第一章 一般的编译器中，语法分析的结果是生成源程序的（）。A记号序列；B分析树；C语法树；D注释树。编译程序和解释程序有哪些区别？第8页/共58页第一章 下列程序中没有翻译功能的是（）。A汇编器B 解释器C 编译器D 编辑器判断：如果编译器的源语言发生了改变，那么其前端操作无需修改。（）什么是语义分析程序？请解释其功能及其输入和输出。第9页/共58页第二章要点扫描程序的功能及其输入输出。正则表达式什么是由r生成的语言，字母表，元符号三种基本操作有限自动机定义DFA NFA第10页/共58页第二章要点正则表达式=NFA=DFA=程序RE=NFA Thompsons constructionNFA=DFA 子集构造法DFA的化简DFA=程序 三种方式+Lex第11页/共58页第二章 以下对扫描器（scanner）描述正确的是（）。A 扫描器是编译器的一个功能模块，其功能是进行语义分析；B 扫描器的输入是语法树，输出是注释树；C 扫描器需要分析哪些字符组成了“词”；D 扫描器无需提示任何错误，而是由其它编译器模块来完成。第12页/共58页第二章 下面不属于正则表达式（regular expression）的基本操作的是（）。A 递归B 并置C 选择D 闭包第13页/共58页第二章 下面的NFA中，对状态或状态集合的-闭包描述正确的是（）。A 状态1的-闭包是2、4；B 状态2、3的-闭包是2、3、4；C 状态3的-闭包是2、4；D 状态4的-闭包是空集。第14页/共58页第二章 7.正则表达式(a|b)+生成的语言，以下描述正确的是（）。A L(a|b)+)=由a和b组成的任意字符串B L(a|b)+)=由a组成的字符串或由b组成的字符串C L(a|b)+)=由a组成的字符串和由b组成的字符串D 以上都不对第15页/共58页第二章 请解释下面各正则表达式的含义，并分别列出其生成语言的实例。aa-zA-Z(0-9|a-zA-Z)*bAA*n|*AAnc(+|-)?0-9+(“”0-9+)?d(b*ab*ab*)+第16页/共58页第二章（15分）已知正则表达式(aa|b)*a(a|b|)1.利用Thompson构造法(Thompsons construction)将该正规表达式(regular expression)转化为NFA；2.将1中得到的NFA转化为DFA；3.将2中得到的DFA进行化简，以得到状态数最少的DFA。第17页/共58页下面的DFA中，（）可以合并。A状态1和状态2；B状态2和状态3；C状态1和状态3；D以上都不对。第二章 第18页/共58页第二章 请写出下面各个字符串的正规表达式(regular expression)a十六进制的数字串；b含有偶数个2的数字串；c不以AA开头的大写字母串。第19页/共58页第二章（15分）已知正则表达式(a|b)*a(b|)1.利用Thompson构造法(Thompsons construction)将该正规表达式(regular expression)转化为NFA；2.将1中得到的NFA转化为DFA；3.将2中得到的DFA进行化简，以得到状态数最少的DFA。第20页/共58页第二章 表示“由a或b组成的含有偶数个b的字符串”的正则表达式是（）Aa*ba*ba*B.(a*ba*ba*)*C(abab)*D.以上都不对请写出下面各个字符串的正则表达式所有整数的数字串（包括负数）字符串中至多含有一个A的大写字母串请简述有限自动机的组成元素并解释DFA和NFA的区别。第21页/共58页第二章 以下不是有限自动机的组成元素的是（）A开始状态B结束状态C正则表达式D状态转换函数已知正则表达式(ab)*(a|b)1构造该正则表达式所对应的NFA；2由NFA构造DFA；3对DFA进行最小化。第22页/共58页第二章 以下对有穷自动机的图形表示描述错误的是（）。用带箭头的线表示一个状态到另一个状态的转换；用圆圈表示状态；用双线边界的圆圈表示接受状态。一个有穷自动机里只能有唯一的一个接受状态；对于给定的一个非确定性有限自动机（NFA），以下正确的是（）。不存在与之等价的DFA。存在一个唯一等价的DFA。存在一个唯一的具有最少状态数的等价DFA。存在等价DFA，但具有最少状态数的DFA不唯一。第23页/共58页第二章 请写出下面各个字符串的正则表达式：以a开头或者以b结尾的小写字母串；以字母开头，后面是数字或字母的符号串；（即标识符）已知正则表达式a(ba)*（1）构造该正则表达式所对应的NFA；（2）由NFA构造DFA；（3）对DFA进行最小化。第24页/共58页第三章 要点分析程序的功能及其输入输出。常见的高级语言的文法（上下文无关文法）、表示方式（BNF）以及其特点（包含递归）。推导分析给定文法的：终结符、非终结符、生成的语言、对某个串的推导。二义性文法概念及消除二义性的方法（1、2）常见产生原因及消除的方法第25页/共58页第三章在一般的编译器中，语法分析基于（）文法进行，即识别的单词串是该类文法的句子。分析器（parser）的主要功能是进行（）。第26页/共58页第三章 以下对于文法二义性的描述正确的是（）。A LL(1)文法是无二义性文法；B 二义性文法会对所有的符号串产生多个语法树；C 通过相应算法可以判断文法的二义性；D 在语法分析中，二义性文法是不被允许的，必须通过修改文法来消除。第27页/共58页第三章 判断：一个文法所描述的语言是唯一的；描述一个语言的文法是不唯一的。（）考虑下列文法GD：DT VTint|floatVid，V|id 请给出int id，id，id进行的最右推导过程，并画出其分析树或语法树第28页/共58页第三章 分析器(parser)的主要功能是进行_，分析器的输入是_，输出是_。第29页/共58页第三章 请写出下面文法对于表达式（）（）进行的最左推导过程，并画出其分析树或语法树。A（A）A|试描述由下列文法所产生的语言。S aSS|a第30页/共58页第三章 在文法中可能引起二义性的原因有：（）A运算的优先级B.运算的结合性Celse的悬挂问题 D.以上都有可能第31页/共58页第三章 以下对于语法二义性的描述正确的是（）。A如果文法G的某个句子存在两棵或者两棵以上的语法树（或分析树），则称该文法是存在二义性的；B如果文法G的某个文法存在两个或者两个以上的句子符合该文法规则，则称该文法是存在二义性的；C消除文法二义性只能对文法进行修改，别无他法；D能够通过算法判别文法是否存在二义性。编译过程中，语法分析器的任务是_。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构A、和B、C、D、第32页/共58页第三章已知文法GS：S:=a|(T)T:=T，S|S给出句子（a，（a，a）的最左推导并画出语法树。第33页/共58页第四章 要点语法分析的分类：自顶向下，自底向上自顶向下分析方法：递归下降，LL(1)分析LL(1)基本方法，三种动作（生成、匹配、接受）判断文法是否是LL(1)文法First集和Follow集左递归和左因子的消除构造分析表第34页/共58页第四章 对下面文法中非终结符First集合描述正确的是（）。E(L)|a|LEL+|EA First(E)=(a +B First(L)=(a +C First(E)=(a +D First(L)=(a +第35页/共58页第四章 考虑下列文法GS：SPSk|PPa|*S*|S为开始符号，请计算S和P的First集合和Follow集合，判断文法GS是否是LL(1)文法并说明理由。第36页/共58页第四章（20分）已知文法GS为S S A T|T A +|-T(S)|k1通过消除左递归和提取左因子（回溯），给出与GS等价的文法GS；2计算文法GS非终结符的First集合和Follow集合；3判断文法GS是否为LL(1)文法；4如果文法GS是LL(1)文法，构造GA的分析表；5给出输入串k-(k+k)的分析过程。第37页/共58页第四章 对于文法GS：S Q*S|Q|S Q a|(S)|S为开始符号，请计算S和Q的FIRST集合和FOLLOW集合。第38页/共58页第四章 已知文法GA为 A a|B b|P P*A|Ak通过消除左递归和提取左因子（回溯），给出与GA等价的文法GA；计算文法GA非终结符的FIRST集合和FOLLOW集合；判断文法GA是否为LL(1)文法；如果文法GA是LL(1)文法，构造GA的分析表；给出输入串的分析过程。第39页/共58页第四章 设有文法GS：S X S|X a S b|S|c计算文法GS非终结符的FIRST集合和FOLLOW集合；若采用自顶向下分析方法，对此文法来说，在分析过程中能否避免二义性？为什么？分析符号串aababb是否为此文法的句子。第40页/共58页第四章 已知文法GA为A(L)A|(x)L L,s|k 通过消除左递归和提取左因子（回溯），给出与GA等价的文法GA；计算文法GA非终结符的FIRST集合和FOLLOW集合；判断文法GA是否为LL(1)文法；如果文法GA是LL(1)文法，构造GA的分析表；给出输入串(k,s,s)(x)的分析过程。第41页/共58页第四章 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_分析方法。A、自左至右 B自顶向下 C、自底向上 D自右向左LL(1)分析方法是这样得名的：第一个“L”指的是_，第二个“L”指的是_，括号中的数字1指的是_。第42页/共58页第四章（10分）设有文法GZ：Z:=(A)A:=abBB:=Aab(1)若采用自顶向下分析方法，对此文法来说，在分析过程中能否避免二义性？为什么？(2)分析符号串（bbaabab）是否为此文法的句子。（20分）已知文法GA为 A:=aABe|a B:=Bb|d(1)通过消除左递归和提取左因子（回溯），给出与GA等价的文法GA；(2)计算文法GA非终结符的FIRST集合和FOLLOW集合；(3)判断文法GA是否为LL(1)文法；(4)如果文法GA是LL(1)文法，构造GA的分析表；(5)给出输入串aade的分析过程。第43页/共58页第五章 要点什么是自底向上的分析方法基本操作：移入、归约方法及能力、符号的意义：LR(0)SLR(1)SLR(k)LR(0)SLR(1)LR(1)(L)|qL-E L|Ea为这个文法构造LR(0)项目的DFAb构造SLR(1)分析表c对输入串(q q)进行分析（15分）第47页/共58页第五章 课后习题5.1、5.3第48页/共58页第六章 要点属性文法概念：联编联编时间静态语义和动态语义常见的静态语义符号表的作用、内容符号表存储的属性第49页/共58页第六章属性文法例题2、例题3第50页/共58页第六章下面不属于语义属性的是（）A.变量的数据类型 B.表达式的值 C.变量对应的内存地址 D.源程序文件名判断：为了提高查找及存取速度，符号表都采用有序表的形式。（）第51页/共58页第七章 要点概念运行时环境过程活动记录调用序列和返回序列几种运行时环境及其特点，举例。完全静态的运行时环境 FORTRAN77不允许递归调用、不支持指针基于栈的运行时环境 C C+Pascal三种指针完全动态的运行时环境 LISP第52页/共58页第七章在编译方法中，动态存储分配的含义是_。A、在运行阶段对源程序中的量进行分配B、在编译阶段对源程序中的量进行分配C、在编译阶段对源程序中的量进行分配，在运行时这些量的地址可以根据需要改变D、以上都不正确对于数据空间的存储分配，FORTRAN采用_策略。下列对完全静态存储分配的含义描述错误的是()。A每个过程只有一个活动记录；B每个变量都有一个固定的存储地址；C没有指针和动态分配；D允许递归调用。第53页/共58页第七章关于基于栈的运行时环境(runtime environment)，以下描述正确的是（）A.不支持递归函数调用；B.支持递归函数调用；C.局部变量可用静态地址访问；D.一个函数对应唯一一个过程活动记录。判断：基于栈的运行时环境中，允许程序的递归调用，一个程序可能同时存在多个活动记录。（）第54页/共58页第8-10章 要点中间代码的种类后缀表示及其特点三元码和四元码代码生成的概念（要考虑机器的物理特性）代码优化的分类源代码优化的具体实例第55页/共58页第8-10章 后缀表示的特点是：（）A操作数的顺序与原来相同；B操作符的顺序就是计算发生的顺序；C后缀表示中无需括号；D以上都是。第56页/共58页第8-10章 请写出A:=3+(5-A/B)的后缀表示和三元组表示。请写出a/b-c*(d+e)的后缀表示和四元组表示。请举出中间代码(Intermediate code)的两种主要形式：_、_。请写出k:=i+k-3*4的后缀表示和四元组表示。请写出i:=2+(4+3*5)的后缀表示和三元组表示。第57页/共58页感谢您的欣赏第58页/共58页