考软件设计师专题二编译原理

第1页专题二：程序语言部分1、程序语言知识1.1程序语言：程序语言分为低级语言和高级语言两个大类。低级语言：又称为面向机器语言，它是特定的计算机系统所固有的语言。机器语言：虽然执行效率高，但编写出来的程序可读性很差，程序难以修改和维护。汇编语言：汇编语言是机器语言的一种提升，它使用了一些助记符号来表示机器指令中的操作码和操作数。但它仍然是一种和计算机的机器语言十分接近的语言，使用起来仍然不太方便。高级语言：与人们的自然语言比较接近，使用起来很方便，也极大的提高了程序设计的效率。下面简单介绍了几种高级语言的特点：Fortran：第一个被广泛用于进行科学计算的高级语言。Algol60：早期研制出来的高级语言。有严格的文法规则，用巴科斯范BNF来描述语言的文法，是一个分程序结构的语言。(最近嵌套原则和存储器使用效率高)Cobol：面向事务处理的高级语言。在数据库管理系统设计方面使用广泛。Pascal：具有相当强的表达能力，特别是对于数据结构功能的表达极具优势。是一种结构化程序设计C：当今最通用的程序设计语言。C是一种较低级的语言，提供了指针和地址操作的能力，但正是因为它的这一特点，才使它更具灵活性。C与UNIX操作系统紧密相关。Prolog：逻辑型语言的代表。它是建立在关系理论和一阶谓词逻辑理论基础上的。Prolog程序由一些俗称事实和规则的Horn子句组成，具有很强的推理功能，适用书写自动定理证明、专家系统、自然语言理解等问题的程序。LISP：典型的函数型程序语言。它以λ演算为基础。它广泛的用于问题求解等第2页人工智能领域。面向对象技术具有3个最重要的特征：封装性、继承性和多态性。◆封装性：指隐藏类对象内部实现的复杂细节，将类以变量类型的形式提供给用户，从而有效地保护内部所有数据不受外部破坏。◆继承性：指一个类（父类）再加上某些新的特征生成另外一个新类（子类），子类具有父类的全部特征，从而增强了类的共享机制，实现了软件的可重用性，简化了软件的开发工作。◆多态性：指将同一处理过程或函数应用于不同的变量（参数），实现数据和过程的功能重载，从而简化编码。下面简单介绍一下几种面向对象语言。C++：是在C语言的基础上发展起来与C兼容的语言。是目前最流行的面向对象语言，主要增加了类功能和从其他类中继承类对象的功能。Smalltalk：典型的面向对象的程序设计语言，引入了类和对象。Java：由SUN公司开发的一种面向对象的程序设计语言。其主要特点是可移植性好，可用于各种平台，尤其适合网络上运行。数据类型和控制结构：对于不同的程序语言，其提供的数据类型都不相同。数据是程序操作的对象，使用时都需要分配内存空间，它们都具有以下的属性。数据名称：由用户通过标示符命名；类型：说明数据占用内存的大小和存放方式存储类：说明数据在内存中的位置和生存期作用域：说明数据可以使用的范围生存期：说明数据占用内存的时间数据从不同角度可分成不同的类别：纯量数据类型（基础数据类型）和结构数据类型：其中纯量数据类型包括（实型、整型、布尔型、指针，双精度型和枚举型）；而结构数据类型包括（联合、数组、复型和记录）按作用域分：全局量和局部量按生存期分：自动生存期(auto)、静态生存期(static)和动态生存期按程序运行期数据值是否改变：常量和变量第3页按类型分：void、标量、函数和聚合标量又可分为算术、枚举和指针；聚合可分为数组、结构体和共用体。按构造方式分：基本类型和派生类型（主要参考C语言）基本类型是void、char、int、float、double和枚举类型，以及其变种short、long、signed和unsigned。派生类型包括指针、数组、函数、结构体（struct）和共用体(union)。其中，最后两种为用户类型。程序语言中的控制结构为数据和数据上的运算组合成程序提供了基本框架，主要包括3种控制结构，即顺序：选择：if语句重复：while语句1.2汇编语言：汇编程序是为特定的计算机或者计算机系统设计的面向机器的语言。汇编语言中的语句可以分成两大类：与机器指令相对应的可执行汇编语句；汇编控制语句，即伪指令。伪指令并不翻译成机器指令，它的作用是控制汇编程序工作。每条汇编语句被划分成4个区，依次是标号区、操作码区、操作数区和注解区。例如：[标号][操作码][操作数][注解]用汇编语言编写的源程序，要通过汇编程序将它翻译成机器语言程序，才能被计算机执行。因此，汇编程序的功能就是将汇编语言所编写的源程序翻译成由机器指令和其他信息组成的目标程序。它的基本工作包括：将每一条可执行汇编语句转换成对应的机器指令处理源程序中出现的伪指令整个汇编程序工作通常要对源程序进行两次扫描才能完成。第一次扫描主要工作是定义符号的值。第二次扫描的目的则是产生目标程序。其中，可执行汇编语句被翻译成对应的二进制代码机器指令，而伪指令会根据伪指令记忆码调用伪指令第4页表对应元素所规定的子程序入口。1.3解释程序：解释程序是一种语言处理程序，它直接执行源程序或源程序的内部形式。它并不产生目标程序，这是它和编译程序的主要区别。高级语言实现语言处理有4种方案：源程序被直接解释执行。先将源程序翻译成高级中间代码，然后再扫描和解释执行高级中间代码。先将源程序转化成和机器代码十分接近的低级中间代码，再解释执行这种中间代码。源程序被最终翻译成机器语言表示的目标程序。这类系统的目标程序执行效率最高。翻译系统与解释系统比较：翻译系统在执行速度上都优于建立在解释执行基础上的系统；翻译系统的缺点是其复杂性高，这使得它的开发和维护费用都大；解释系统比较简单，可移植性较好，适合于以交互方式执行程序；解释系统缺点是执行速度慢；纯粹的解释和纯粹的编译都是极端，因此一般是两种技术的结合，先将源程序编译形成中间代码，然后由解释器解释执行。解释系统的结构可分成两个部分。1．包括通常的词法分析程序以及语法和语义分析程序，它的作用仍是把源程序翻译成中间代码，中间代码的设计常采用逆波兰（后缀）表示形式（符号在后面）。2．解释部分，用来对第一部分所产生的中间代码进行解释执行，完成真正的解释。1.4编译程序：编译程序的功能是把某些高级语言书写的源程序翻译成与之等价的低级语言（汇编语言或者机器语言）的目标程序。其过程可以分成6个阶段。过程阶段任务及其特点第5页词法分析阶段该阶段的任务是从左到右逐个字符的读入源程序，识别出一个个的单词符号。词法分析所依据的是语言的词法规则，即描述单词结构的规则。词法规则可用3型文法（正规文法）或正规式来描述，有限自动机能识别正规文法所定义的语言和正规式所表示的集合。语法分析阶段该阶段任务是在词法分析的基础上将单词符号序列分解成各类语法单元。语法分析所依据的是语言的语法规则，即描述程序结构的规则。语法分析有自顶向下分析（递归子程序分析法LL1）和自底向上分析（LR和算符优先分析）两大类。语义分析阶段审查源程序有无语义错误，为代码生成阶段收集类型信息。中间代码生成阶段在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓“中间代码”是一种简单、含义明确的记号系统。代码优化阶段该阶段是对前阶段产生的中间代码进行变换改造，目的是使生成的目标代码更为高级，即省时间和省空间。优化所依据的原则是程序的等价变换规则。目标代码生成阶段此阶段使把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。其中，词法分析和语法分析本质上都是对源程序的结构进行分析。而语义分析和中间代码生成所依据的是语言的语义规则，一般采用语法指导翻译和中间代码生成。自底向上分析法采用一个后进先出栈的数据结构，是移进-规约过程（找出句柄）。自顶向下分析法必须改写文法，采用预测分析法，要消除左递归和提取公共左因子。编译过程6个阶段的任务以及表格管理和出错处理工作可分别由几个模块或第6页程序完成，他们分别称作词法分析程序、语法分析程序、语义分析程序，中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。2．重点与难点2.1文法及语言形式描述：本部分的内容难点是编译原理。与程序员级别的要求一样，这部分的内容比较复杂，不易理解。可以从下面几个知识点来掌握：文法和语言形式描述这一部分主要是需要搞清楚一些基本概念和基本原理，这也是编译原理的最基本的知识。基本定义：包括字母表、字符、字、字长度、空字、字运算等等。文法的定义：描述语言的语法结构的形式规则称为文法。文法G是一个四元组，可表示为G（VT,VN,S,P）。VT是一个非空有限集，每个元素称为终结符。VN是一个非空有限集，每个元素称为非终结符。P是一个非终结符，称为开始符号；它至少要在一条产生式中作为左部出现。S是一个产生式集合（有限）。句子和语言：主要涉及几个概念。I.直接推导与推导（区别是否直接导出）II.直接归约与归约（直接推导和推导的逆过程）III.句型和句子（由开始符号推导出的称为句型，仅含终结符的句型称为句子）IV.语言（句子的全体）文法的分类：文法根据对产生式施加不同的限制，分成4种类型，即0型、1型、2型和3型。下表列出了这几种文法的特点和区别。文法类型文法名称语言名称对应的自动机0型（PSG）短语结构文法递归可枚举语言图灵机（Turing）第7页1型（CSG）上下文有关文法上下文有关语言线性界限自动机2型（CFG）上下文无关文法上下文无关语言非确定下推自动机3型右线性文法（正规文法）有限状态文法有限状态自动机2型文法（上下文无关文法）：如今程序语言基本都可以用它来描述。重点涉及几个概念，对于这几个概念可以根据书上的例子来理解和掌握。在复习资料上有例题，可以找一个分析一下（99页）；规范推导（最右推导）：总是对句型的最右端的非终结符进行置换；短语、直接短语和句柄(句柄：最左直接短语)素短语：至少含有一个终结符，除本身外不含更小的素短语规范归约语法树和文法的二义性对于上面的术语，一定要知道其意义，还要知道其具体的做法。2.2词法分析词法分析的任务是把构成源程序的字符串转换成单词符号串的中间程序。词法规则可用3型文法（正规文法）或正规表达式描述。转换方法有人工的状态转换图方法和有限自动机的自动方法。这部分主要涉及以下两个方面的内容。正规表达式和正规集有限自动机有限自动机作为一种识别装置，它能准确地识别正规集。它分为两类：确定的有限自动机（DFA）和不确定的有限自动机（NFA）。在有限自动机理论中，可以通过子集法的算法来实现NFA到DFA的转换。比如：：所有与b为首后跟任意多个a的字：所有与a为首的字；第8页：含有两个相继的a或两个相继的b的字；（需要拷贝）语言L={ambn|m≥0，n≥1}的正规表达式是__A__。（程序语言）(14)A.a*bb*B.aa*bb*C.aa*b*D.a*b*2.3语法分析语法分析的任务是识别由词法分析给出的单词符号序列是否为给定文法的正确句子（程序）。语法分析常用的方法有两类：◆自底向上分析方法（LR分析法和算符优先分析法）也称为移进-归约分析法。对“可归约串”刻画的不同，形成两种不同的分析方法，即规范归约分析法和算符优先分析法。◆自顶向下分析方法也称为面向目标的分析方法。存在两种分析方法，递归子程序法和预测分析法，都使用LL（1）文法来进行语法分析。例题：假设某程序语言的文法如下：S→a|b|(T)T→TdS|S其中，VT={a,b,d,(,)}，VN={S,T}，S是开始符号。考查该文法，称句型(Sd(T)db)是S的一个A。其中B是句柄；C是素短语；D是该句型的直接短语；E是短语。A：①最左推导②最右推导③规范推导④推导B：①S②b③(T)④Sd(T)C：①S②b③(T)④Sd(T)D：①S②S,(T),b③S,(T),TdS,b④(Sd(T)db)E：①(Sd(T)db)②d(T)③Td④Sd(T)d此句型的语法树如下所示：