《编译原理》总复习-习题与试题-2010.ppt

1、编译原理综述，刘建，西安电子科技大学软件工程学院，2。课程内容要求(希望)牢牢掌握基本概念，灵活运用基本方法总结所学知识；1.导言词汇分析。语法分析。语义分析。语法指导的翻译产生中间代码，所以你在学习中不能走捷径，如果你努力，你会得到更多的收获。3.第一章引言：语言翻译，不同的翻译形式：汇编，编译，转换(预编译)，逆向翻译。翻译方法：4，编译器的基本组成，5，编译器的综合分析模式，编译器的扫描次数和编译，6。第二章词汇分析、构词规则和词汇分析：首先，确定构词规则，称之为构词规则。然后根据构词规则识别输入序列，这就是词法分析。主要内容：词标记(范式和范式集)的标记、模式和形式描述标记识别有限自动

2、机从范式到词法分析器，词法分析器的作用：过滤掉源程序中无用的成分；处理与特定操作系统或机器相关的输入；识别标记并将其交给解析器；调用符号表管理器和错误处理程序进行相关处理。标记、模式和单词、模式：指定单词识别的规则标记：根据特定模式识别的一种单词(标记类型);词位：识别字符串本身的输出：标记=标记类型标记属性、标记描述模式的形式描述、范式和范式集的定义(基本范式，三种运算)范式的等价性(描述同一个集合)利用范式的等价性(范式的代数性质)简化范式形式描述模式如何使用范式来描述编程语言中的常见标记，例如标识符、数字、运算符和分隔符等范式的简化形式，以及辅助定义和规则；8.用于令牌识别的有限自动机N

3、FA和有限自动机的表示：定义表示、状态转移图和状态转移矩阵；NFA和DFA的主要区别：NFA的不确定性：存在国家转型；同一字符在当前状态下有多个下一个状态转换；使用NFA识别输入序列的弱点：尝试所有路径来确定由于输入未被接收和回溯导致的问题；模拟离散傅立叶变换的算法(算法2.1):用离散傅立叶变换识别标记。从范式到词法分析器，构造了NFA的汤普森算法(算法2.2):与范式的对应关系；模拟NFA的“并行”算法(算法2.3)；从NFA构造离散傅立叶变换子集(算法2.5):SMOVE(s，a)和-闭包(t)的计算；最小化可区分性的概念：所有不可区分的状态被视为一个状态(算法2.6)；灵活运用各种方法

4、构建DFA(规范化简化、状态转移图等)。)，尤其是人工构造和算法构造之间的区别(考虑到NFA的(a|b)*abb)。第三章语法分析是编译过程中的一个重要阶段，也是语法引导翻译模式编译的核心。语法分析也有双重含义：根据一定的规则，形成各种语言结构，即语法规则；根据语法规则，即语法分析，识别输入序列(标记流)中的语言结构。语法分析的分析对象是构成语言的句子。句子具有层次结构的特点。表征结构的最好方法是树，这使得语法分析有两种方法：从根到叶和从叶到根。主要内容从上到下分析了从程序设计语言和语法中得出的基本概念。11.程序设计语言和语法，范式和范式语法：范式和范式语法用于描述线性结构，如构成句子的标记

5、(终止符)；识别正常语言的自动机是有限自动机，其特点是没有记忆能力；上下文无关语法(CFG=(n，t，s，p): CFG用于描述层次结构，如构成程序的句子；CFL识别的自动机是下推自动机，它在有限自动机的基础上增加了一个下推栈，具有简单的记忆能力；语法分类：0型，1型，2型和3型语法词汇分析器和语法分析器：法和PDA，12。关于派生的基本概念，导出了生成CFG语言的基本方法：从语法的起始符号开始，句型中的非终结符被生成的正确部分反复替换。演绎的基本概念：句子、直接演绎、最左演绎和左句型(最右演绎和右句型)；(定义3.2、3.3、3.4)分析树和语法树：分析树和语法树都反映语言结构；分析树还记录

6、了分析过程(包括非终结符)；(定义3.5，3.6)语法歧义：歧义的本质是对语法中语法符号的优先顺序和组合没有限制，因此一个句子可以衍生出多个分析树。(定义3.7)消除歧义：将二进制语法改写为非二进制语法；(两个关键步骤)限制语法符号的优先级和组合，使每个分析步骤都有唯一的选择。13、自上而下分析，分析方法：演绎，自上而下构建分析树，是一种预测性和尝试性的方法；语法要求：无公共左因子和左递归左递归和直接左递归(定义3.9)消除直接左递归和左递归(算法3.1和3.2)提取公共左因子(类似于提取公共因子)递归下降子例程方法：匹配终止符，展开非终止符(子例程调用)，自上而下分析(续)，预测分析表方法：

7、的工作模式和过程：PDA(DPDA)模式：(堆栈内容，当前剩余输入，模式改变动作)模式改变动作：匹配终止符，展开非终止符， 接受，错误报告驱动程序(算法3.4)预测分析表和分析表的构造：分析表的组成和含义：ma，A FIRST集和FOUND集(定义3.10，3.11)FIRST和FOUND的计算(算法3.5，3.6)分析表的构造(算法3.7) LL(1)语法及其区分：预测分析表中没有多个定义条目(定义3.12，推论3.2)。 15、自下而上分析，分析方法：归约(推导的逆过程)，从叶到根构建分析树；基本概念：短语、直接短语、句柄(定义3.13)、最左边的约简(定义3.14)、约简和规范约简。切断

8、把手。实现方法：移动缩减(模式中的两个关键动作)。关键问题：如何确定手柄已经形成在堆叠的顶部，以及当手柄形成时，如何确定哪种产品用于规格；移入缩减分析器的工作模式(与预测分析表方法相反)，移入(匹配终止符)缩减(扩展非终止符)驱动程序(算法3.8)，并从下至上进行分析(续1)。移动-归约分析表：动作表和goto lr (k)语法(定义3.15)核心：DFA识别活动前缀：活动前缀和LR(0)项(NFA状态)(定义3.16，3.17)，一个产品是NFA识别活动前缀和一个LR(0扩展语法和子集方法构造DFA闭包(I)，goto(I，x)(定义3.18，3.19)核心项和非核心项(定义3.20)构造算

9、法(算法3.9)核心是：闭包(goto(I，I)移减分析表的构造：(算法3.10)；LR语法和LR分析：LR(0)，SLR(1)，LALR(1)，LR(1)。在第四章中，语法引导翻译生成中间代码，讨论了编程语言的静态语义分析，并基于语法分析生成中间代码。采用的基本方法是语法指导翻译。与前两章的词法分析和语法分析不同，词法分析和语法分析的讨论侧重于理论，而这一章则结合编程语言的实例着重于语言结构的具体翻译方法和一些实用技巧。语法指导翻译：概念和基本方法；中间代码符号表的组织；声明的翻译；可执行语句的翻译；语法指导翻译的基本概念；语法和语义语法；语言结构；语义：附加于结构的实际意义，属性和属性的计

10、算属性：附加于语法符号的意义，如val，place和其他语义规则：计算属性的语义规则的两种表达，语法指导定义：计算表示的抽象属性和语义规则，翻译方案：特定属性和计算表示的语义规则，基本设计方法，与语法分析的关系：自下而上的语法分析(LR分析的两种扩展)，自上而下的语法分析(递归下降子例程方法)，语义规则设计：设计属性，基本操作(函数或过程)，语义规则；声明性陈述：需要保存什么信息，这些信息有什么特征，以及设计什么样的数据结构来存储这些信息以便于处理；可执行语句：语句的结构应该生成什么样的中间代码序列，语法指导定义应该根据中间代码序列来设计，翻译方案应该根据序列的特点来设计。中间代码，为什么生成

11、中间代码：中间代码是编译器分析综合模式的前端和后端之间的分水岭；中间代码的特点：形式接近目标机器码，但与具体机器码无关，便于编译器开发和移植以及代码优化；常见的中间代码形式：后缀、树(图)和三个地址码；三种地址码的实现：三进制和四进制中间码的关系；树与后缀、三元与四元的关系；符号表的组织；符号表的功能；连接声明和引用的桥符号表的条目和信息的存储；范围信息的直接和间接存储；静态范围最近嵌套原则线性表：堆栈结构；表上的操作哈希表；每个子表都是堆栈结构。提高表操作的效率，声明语句的翻译、定义和声明：类型定义和变量声明，过程定义和过程声明变量声明：填充符号表信息(简单变量和数组变量)；过程声明：左值和

12、右值；参数传递：不同形式的参数传递以及各种形式参数传递的处理方法；名称范围：符合静态范围和最近嵌套原则；声明中范围信息的保存。可执行语句的翻译，简单算术表达式和赋值语句的翻译：语法引导翻译的设计，类型转换；数组元素的引用：从多维数组到一维存储空间的映射；数组元素地址计算的递归公式；数组元素地址计算的语法指导翻译：布尔表达式短路计算的翻译：为什么需要短路计算和短路计算的控制流程；真出口和假出口；拉链/回填技术：真实价值链和虚假价值链控制声明的翻译：控制声明的分类、转移和有条件转移。结论(2010年5月25日)，试题及练习，认真复习，注重掌握基本概念。当基本概念被掌握后，相当数量的试题的答案将会出

13、现。练习和试题的目的区别：练习的目的是理解和掌握通过反复练习所学到的知识，会有许多复杂、困难和众多的步骤；试题的目的是调查理解总之，学习方法的掌握是个人努力的结果，不能单靠别人来学习。27，关于考试，题目类型：填空题(30分)，简答题(20分)，算术题(50分)考试范围：第14章中提到的内容侧重于调查：掌握基本概念和方法，容易犯的错误，不仔细检查问题(对问题要求的错误理解：对意思理解错误，对疑难问题容易思考，对疑难问题容易思考。关键问题是基本概念不清楚。不相关的答案(例如，在不需要L1分析的情况下将语法更改为L1)会使问题变得简单(例如，只询问是否有任何冲突，但首先构建分析表)，并且会偷工减料

14、(例如，有一些问题，只有一半得到了回答)，警告不要作弊！命运掌握在你自己手中！实际试题示例1。简短回答问题1。(2)什么方法可以消除语法歧义？2(2分)写出-(a b) * c) d的后缀公式。3(4分)测试证明正规公式(ab)*a和(ba)*是等价的。1 (1)重写语法(2)规定语法符号的优先级和关联性。2 ab c*d(或ab c*-d) 3证明考虑任何字符串ababab.在L(ab)*a)中，我们可以从字符串连接的关联性中得到：A (BA) (BA) (B.a)也可以用归纳法证明(提示：以ab重复0次和1次为归纳法依据，假设ab重复n次有效，证明ab重复n次也有效)。填空(30分)，1(

15、6分)编译器的基本组件是：词法分析、中间代码生成、和。2(1点)正规公式r和s的等价描述是相同的。3(2点)没有子串baa的所有A和B符号串的正常表达式是。4(4点)已知语法g定义如下：SeT|RT TDR| RdR| Da|bd然后FIRST(S)=，FIRST(D)=，FIRST(T)=，FIRST(R)=。1语法分析、语义分析、代码优化、目标代码生成、符号表管理和错误处理2 r和S代表正常集3 a*(b|ba)* 4 FIRST(S)=e、D、a、b、FIRST(D)=a、b、FIRST(T)=a、b、FIRST(III)。计算问题(1)，1(13分)认识一个如图所示的NFA。(a)(4

16、点)简要描述自动机在自然语言中识别的语言特征，并列出它能识别的两个字符串。(b)(3分)写出等价于自动机的正规公式。(3)(6点)用子集法构造识别R的最小DFA。解决方案：包含至少两个连续B的A和B字符串，如bb、bbb等。r=(a|b)*bb(a|b)* .直接用状态转移矩阵构造：初始状态：0子集法得到：(2是最终状态)，让：0=A，0，1=B，0，1，2=C，0，2=D得到：最小化DFA得到：(C和D无法区分)，3。计算问题(2)，2发射(*，E1.place，T.place，E . place；| T e . place=T . place；TT1 F T.place=newtemp发射(T1，T2，T3；| F t . place=F . place；f(E)f . place=E . place；| id f . pl