编译原理2012复习.ppt

复习 2011.4.26 第一章要点 l编译器的概念。其输入和输出。 l机器语言-汇编语言-高级语言。 l乔姆斯基分层结构。 l0型-无限制文法 l1型-上下文相关文法 l2型-上下文无关文法 l3型-正则文法 第一章要点 l相关程序和概念 l解释器 l编辑器 l交互式开发环境（IDE） l调试程序 l分析和综合 l前端和后端 l遍 l编译器的翻译过程 第一章 2009 l编译器各处理阶段的正确顺序是（ ） lA词法分析、语法分析、语义分析、代码生成； lB语法分析、词法分析、语义分析、代码生成； lC语义分析，语法分析、词法分析，代码生成； lD以上都不对。 l编译器中语法分析的输入和输出分别是（ ） lA字符串、记号串B记号串、注释树 lC记号串、语法树D语法树、注释树 l 什么是编译器？请简述编译器的功能及其输入输出。 第一章 2008 l以下对编译器(compiler)描述错误的是（ ）。 lA 编译器的输入是由源语言编写的源程序，输出是由目标语 言编写的目标程序。 lB 编译器是一个执行程序而不是一个转换程序。 lC 编译器和编辑器以及其它程序经常被捆绑成一个与用户交 互的开发环境(IDE)中。 lD 按照编译器扫描的遍数，可把编译器分为一遍扫描和多遍 扫描的编译器。 l把汇编语言程序翻译成机器可执行的目标程序的工作 是由_完成的。 lA、编译器 B、解释器 lC、汇编器 D、预处理器 第一章 2008 l编译器的工作可分为多个阶段，词法分析、语法分析、语义分析 阶段的结果分别是（）。 lA 分析树、语法树、语义树； lB 分析树、语法树、注释树； lC 记号序列、语法树、语义树； lD 记号序列、分析树、注释树。 l文法根据限定条件分为四种文法：0型文法、1型文法、2型文法 、3型文法。其中2型文法又叫做（）文法，3型文法又叫做（ ）文法。 l高级程序设计语言源程序有两种执行方式，即_和_。 l什么是编译器？ l什么是遍。 l什么是扫描器？扫描器的功能是什么？ 第一章 2010 l以下对编译器(compiler)描述错误的是（ ）。 lA. 编译器是将一种语言翻译成另一种语言的计算机 部件，包括软件部分和硬件部分； lB. 输入编译器的源语言通常是高级语言，如C语言 ；输出编译器的目标语言通常是低级语言，如01代 码； lC. 词法分析是编译器的一个处理阶段； lD. 编译器和编辑器以及其它程序经常被捆绑成一 个与用户交互的开发环境(IDE)中。 第一章 2010 l汇编语言与机器语言相比，其主要优点在于（ ）。 lA汇编语言机器依赖性强； lB汇编程序的可执行程序的长度可以大幅下降； lC汇编语言的符号形式更易理解，也提高了编写 程序的准确性； lD以上都不对。 第一章 2010 l一般的编译器中，语法分析的结果是生成源程 序的（ ）。 lA记号序列；B分析树； lC语法树；D注释树。 l编译程序和解释程序有哪些区别？ 第一章 2011 l下列程序中没有翻译功能的是（ ）。 A汇编器B 解释器 C 编译器D 编辑器 l判断：如果编译器的源语言发生了改变，那么 其前端操作无需修改。（ ） l什么是语义分析程序？请解释其功能及其输入 和输出。 第二章要点 l扫描程序的功能及其输入输出。 l正则表达式 l什么是由r生成的语言，字母表，元符号 l三种基本操作 l有限自动机 l定义 lDFA NFA 第二章要点 l正则表达式=NFA=DFA=程序 lRE =NFA Thompsons construction lNFA=DFA 子集构造法 lDFA的化简 lDFA=程序 三种方式+Lex 第二章 2011 l以下对扫描器（scanner）描述正确的是（ ）。 A 扫描器是编译器的一个功能模块，其功能是进行语 义分析； B 扫描器的输入是语法树，输出是注释树； C 扫描器需要分析哪些字符组成了“词”； D 扫描器无需提示任何错误，而是由其它编译器模块 来完成。 第二章 2011 l下面不属于正则表达式（regular expression）的 基本操作的是（ ）。 A 递归B 并置 C 选择D 闭包 第二章 2011 l下面的NFA中，对状态或状态集合的-闭包描述 正确的是（ ）。 A 状态1的-闭包是2、4； B 状态2、3的-闭包是2、3、4； C 状态3的-闭包是2、4； D 状态4的-闭包是空集。 第二章 2011 l7.正则表达式(a|b)+生成的语言，以下描述正 确的是（ ）。 lA L(a|b)+)=由a和b组成的任意字符串 lB L(a|b)+)=由a组成的字符串或由b组成的字符 串 lC L(a|b)+)=由a组成的字符串和由b组成的字符 串 lD 以上都不对 第二章 2011 l请解释下面各正则表达式的含义，并分别列出其 生成语言的实例。 aa-zA-Z(0-9|a-zA-Z)* bAA*n|*AAn c(+|-)?0-9+(“”0-9+)? d(b*ab*ab*)+ 第二章 2011 l（15分）已知正则表达式(aa|b)*a(a|b|) 1. 利用Thompson构造法(Thompsons construction)将该 正规表达式(regular expression)转化为NFA； 2. 将1中得到的NFA转化为DFA； 3. 将2中得到的DFA进行化简，以得到状态数最少的DFA 。 l下面的DFA中，（ ）可以合并。 lA状态1和状态2； lB状态2和状态3； lC状态1和状态3； lD以上都不对。 第二章 2010 第二章 2010 l请写出下面各个字符串的正规表达式(regular expression) la十六进制的数字串； lb含有偶数个2的数字串； lc不以AA开头的大写字母串。 第二章 2010 l（15分）已知正则表达式(a|b)*a(b|) l1. 利用Thompson构造法(Thompsons construction)将该正规表达式(regular expression) 转化为NFA； l2. 将1中得到的NFA转化为DFA； l3. 将2中得到的DFA进行化简，以得到状态数最少 的DFA。 第二章 2009 l 表示“由a或b组成的含有偶数个b的字符串”的 正则表达式是（ ） lAa*ba*ba*B. (a*ba*ba*)* lC(abab)*D. 以上都不对 l请写出下面各个字符串的正则表达式 l所有整数的数字串（包括负数） l字符串中至多含有一个A的大写字母串 l请简述有限自动机的组成元素并解释DFA和 NFA的区别。 第二章 2009 l以下不是有限自动机的组成元素的是（） lA开始状态B结束状态 lC正则表达式D状态转换函数 l已知正则表达式(ab)*(a|b) l1构造该正则表达式所对应的NFA； l2由NFA构造DFA； l3对DFA进行最小化。 第二章 2008 l以下对有穷自动机的图形表示描述错误的是（）。 l用带箭头的线表示一个状态到另一个状态的转换； l用圆圈表示状态； l用双线边界的圆圈表示接受状态。 l一个有穷自动机里只能有唯一的一个接受状态； l对于给定的一个非确定性有限自动机（NFA），以 下正确的是（）。 l不存在与之等价的DFA。 l存在一个唯一等价的DFA。 l存在一个唯一的具有最少状态数的等价DFA。 l存在等价DFA，但具有最少状态数的DFA不唯一。 第二章 2008 l请写出下面各个字符串的正则表达式： l以a开头或者以b结尾的小写字母串； l以字母开头，后面是数字或字母的符号串；（即 标识符） l已知正则表达式a(ba)* l（1）构造该正则表达式所对应的NFA； l（2）由NFA构造DFA； l（3）对DFA进行最小化。 第三章 要点 l分析程序的功能及其输入输出。 l常见的高级语言的文法（上下文无关文法）、 表示方式（BNF）以及其特点（包含递归）。 l推导 l分析给定文法的：终结符、非终结符、生成的 语言、对某个串的推导。 l二义性文法 l概念及消除二义性的方法（1、2） l常见产生原因及消除的方法 第三章 2011 l在一般的编译器中，语法分析基于（ ）文 法进行，即识别的单词串是该类文法的句子。 l分析器（parser）的主要功能是进行（ ） 。 第三章 2011 l 以下对于文法二义性的描述正确的是（ ）。 A LL(1)文法是无二义性文法； B 二义性文法会对所有的符号串产生多个语法 树； C 通过相应算法可以判断文法的二义性； D 在语法分析中，二义性文法是不被允许的， 必须通过修改文法来消除。 第三章 2011 l判断：一个文法所描述的语言是唯一的； 描述一个语言的文法是不唯一的。（ ） l考虑下列文法GD： lDT V lTint|float lVid，V|id 请给出int id，id，id进行的最右推导过程 ，并画出其分析树或语法树 第三章 2010 l 判断： l一个文法所描述的语言是不唯一的；描述一个语言 的文法是唯一的。（ ） l分析器(parser)的主要功能是进行_ ，分析器的输入是_，输出是 _。 第三章 2010 l请写出下面文法对于表达式（）（）进行 的最左推导过程，并画出其分析树或语法树。 A （A）A | l试描述由下列文法所产生的语言。 S aSS | a 第三章 2009 l在文法中可能引起二义性的原因有：（ ） lA运算的优先级B. 运算的结合性 lCelse的悬挂问题D. 以上都有可能 第三章 2008 l以下对于语法二义性的描述正确的是（）。 A如果文法G的某个句子存在两棵或者两棵以上的语法树（或 分析树），则称该文法是存在二义性的； B如果文法G的某个文法存在两个或者两个以上的句子符合该 文法规则，则称该文法是存在二义性的； C消除文法二义性只能对文法进行修改，别无他法； D能够通过算法判别文法是否存在二义性 。 l编译过程中，语法分析器的任务是_。 l分析单词是怎样构成的 l分析单词串是如何构成语句和说明的 l分析语句和说明是如何构成程序的 l分析程序的结构 A、和B、 C、 D、 第三章 2008 l已知文法GS： S:=a | (T) T:=T，S | S 给出句子（a，（a，a）的最左推导并画出 语法树。 第四章 要点 l语法分析的分类：自顶向下，自底向上 l自顶向下分析方法：递归下降，LL(1)分析 lLL(1) l基本方法，三种动作（生成、匹配、接受） l判断文法是否是LL(1)文法 lFirst集和Follow集 l左递归和左因子的消除 l构造分析表 第四章 2011 l 对下面文法中非终结符First集合描述正确的 是（ ）。 E(L)|a| LEL+|E A First(E)= ( a + B First(L)= ( a + C First(E)= ( a + D First(L)= ( a + 第四章 2011 l 考虑下列文法GS： SPSk|P Pa|*S*| S为开始符号，请计算S和P的First集合和Follow 集合，判断文法GS是否是LL(1)文法并说明 理由。 第四章 2011 l（20分）已知文法GS为 S S A T | T A + | - T (S) | k 1通过消除左递归和提取左因子（回溯），给出与GS等 价的文法GS； 2计算文法GS非终结符的First集合和Follow集合； 3判断文法GS是否为LL(1)文法； 4如果文法GS是LL(1)文法，构造GA的分析表； 5给出输入串k-(k+k)的分析过程。 第四章 2010 l对于文法GS： S Q * S | Q | S Q a | (S) | S为开始符号，请计算S和Q的FIRST集合和 FOLLOW集合。 第四章 2010 l已知文法GA为 A a | B b | P P*A | Ak l通过消除左递归和提取左因子（回溯），给出与GA等 价的文法GA； l计算文法GA非终结符的FIRST集合和FOLLOW集合 ； l判断文法GA是否为LL(1)文法； l如果文法GA是LL(1)文法，构造GA的分析表； l给出输入串的分析过程。 第四章 2009 l设有文法GS： S X S | X a S b | S | c l计算文法GS非终结符的FIRST集合和FOLLOW集 合； l若采用自顶向下分析方法，对此文法来说，在分析 过程中能否避免二义性？为什么？ l分析符号串aababb是否为此文法的句子。 第四章 2009 l已知文法GA为 A (L)A | (x) L L,s | k l通过消除左递归和提取左因子（回溯），给出与 GA等价的文法GA； l计算文法GA非终结符的FIRST集合和FOLLOW 集合； l判断文法GA是否为LL(1)文法； l如果文法GA是LL(1)文法，构造GA的分析表； l给出输入串(k,s,s)(x)的分析过程。 第四章 2008 l高级语言编译程序常用的语法分析方法中， 递归下降分析法属于_分析方法。 lA、自左至右 B自顶向下 lC、自底向上 D自右向左 lLL(1)分析方法是这样得名的：第一个“L”指的 是_，第二个“L”指的是_，括号中的数字 1指的是_。 第四章 2008 l（10分）设有文法GZ： Z:=(A) A:=abB B:=Aab l(1) 若采用自顶向下分析方法，对此文法来说，在分析过程中能否避免二义性 ？为什么？ l(2) 分析符号串（bbaabab）是否为此文法的句子。 l（20分）已知文法GA为 A:=aABe | a B:=Bb | d l(1) 通过消除左递归和提取左因子（回溯），给出与GA等价的文法GA； l(2) 计算文法GA非终结符的FIRST集合和FOLLOW集合； l(3) 判断文法GA是否为LL(1)文法； l(4) 如果文法GA是LL(1)文法，构造GA的分析表； l(5) 给出输入串aade的分析过程。 第五章 要点 l什么是自底向上的分析方法 l基本操作：移入、归约 l方法及能力：LR(0) (L) | q lL - E L | E la为这个文法构造LR(0)项目的DFA lb构造SLR(1)分析表 lc对输入串(q q)进行分析（15分） 第六章 要点 l属性文法 l概念： l联编 l联编时间 l静态语义和动态语义 l常见的静态语义 l符号表的作用、内容 l符号表存储的属性 第六章 2008-2011 l下面不属于语义属性的是（） A. 变量的数据类型 B. 表达式的值 C. 变量对应的内存地址 D. 源程序文件名 l判断：为了提高查找及存取速度，符号表都 采用有序表的形式。（ ） 第七章 要点 l概念 l运行时环境 l过程活动记录 l调用序列和返回序列 l几种运行时环境及其特点，举例。 l完全静态的运行时环境 l基于栈的运行时环境 第七章2008-2011 l在编译方法中，动态存储分配的含义是_。 lA、在运行阶段对源程序中的量进行分配 lB、在编译阶段对源程序中的量进行分配 lC、在编译阶段对源程序中的量进行分配，在运行时这些 量的地址可以根据需要改变 lD、以上都不正确 l对于数据空间的存贮分配，FORTRAN采用_策 略。