一、概述
1、汇编、编译、解释系统的基础知识和基本工作原理。
2、程序设计语言的基本成分:数据、运算、控制和传输,程序调用的实现机制。
3、各类程序设计语言的主要特点和适用情况:过程式程序语言、面向对象程序设计语言、函数式程序设计语言、逻辑程序设计语言的基本特点、脚本语言的特点。
二、汇编、编译、解释系统基础
1. 解释与编译
在计算机中,使用高级语言开发的程序都是不能直接运行的。需要经过一系列的处理,才能运行。这个过程,根据其处理方式的不同,可分为:解释型和编译型。
解释型:接受所输入的用程序语言编写的源程序,然后直接解释执行;这类语言中的最典型代表是BASIC.
编译型:它是将用某种程序语言编写的源程序直接翻译成为另一种语言(目标语言程序),而且两者在逻辑上等价。如:C语言。
2. 编译过程
所谓编译过程,就是使用编译程序将高级语言源程序翻译为等价的机器语言程序的过程。一般来说,编译程序分为以下几个部分:词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成以及贯穿始终的表格管理与出错处理。各部分之间的关系如图3-2所示。
词法分析:从左到右逐字符读入源程序,识别出一个个单词符号;它是根据语言的词法规则(单词结构规则)进行的。本节第4部分对词法分析进行了详细介绍。
语法分析:在词法分析的基础上将单词符号序列分解成各类,诸如"程序"、"语句"、"表达式"等
语法单位。
语义分析:审查源程序有无语义错误,为代码生成阶段收集类型信息。
中间代码生成:在语法分析过程中,随着分析的进展,一条产生式获得匹配或用于归约时,根据这条产生式所对应的语义子程序进行翻译的方法称为语法制导翻译。通过翻译后,将生成中间代码。不同的高级程序语言可能生成同样的中间代码。编译程序使用的中间代码通常有逆波兰、三元式、四元式和树形四种表示法。
代码优化:代码优化是对程序进行等价变换,使其生成更有效(运行时间更短、占用空间更小)的目标代码。根据优化所涉及的程序范围,可以分为局部优化、循环优化和全局优化三个不同的级别。
目标代码生成:目标代码生成是把经过语法分析或优化后的中间代码作为输入,将其转换成特定机器的机器语言或汇编语言代码作为输出,这样的转换程序称为代码生成器。
3. 形式语言基本知识
抽象地说,语言是按照一定规则排列的符号和集合。要形式化地描述一个语言,就需要借助以下一些基本概念。
字母表∑ :非空的有穷集合,例如 ∑ = {a,b}.
字符串:由∑ 的符号组成的有穷序列叫做字母表∑ 上的字符串。其中包含的字符数,称为长度。记做|字符串名|.长度为0的为空串,记做e.要注意的是,e中包括一个元素!而 ∅才是没有元素的空串。
形式语言: 上的字符串的全体记为∑ *, ∑*的任何子集都称做字母表?上的形式语言,简称语言。
前缀、后缀:设v是一个字符串,由v左边若干连续符号组成的字符串称做v的前缀。由v右边若
干连续符号组成的字符串称为v的后缀。
连接:设a=a1a2...an,b=b1b2...bn,则ab表示它们的连接,值为:a1a2...an b1b2...bn.
连续重复(方幂):把n个a的连接记做an.
下面是几个常见的字集运算(设A,B?S*,即A、B是字母表S上的字集):
或操作:AxB={a |axA或a∈B}.
积运算:AB={ab |axA且b∈B}.
幂运算:An=A·An-1=An-1·A,A0={e}.
正则闭包:A+=A1∪A2∪A3∪...∪An∪...(也就是所有幂的组合)。
闭包:A*=A0∪A+(在正则闭包的基础上,加上A0)。
(1)什么是形式文法
文法就是用来描述语言的语法结构的形式规则。我们可以从一个简单的例子来理解文法,如下所示:
张三和李四是工程师。
由五个词组成:张三 和 李四 是 工程师 组成一个句子:由主语、谓语构成。我们知道中文的文法:
<句子>→<主语><谓语>
<主语>→<名词词组>
<名词词组>→<名词><连词><名词词组>
<谓语>→<动宾词组>
<动宾词组>→<动词><宾语>
<宾语>→<名词>
<名词>→张三|李四|工程师
<连词>→和
<动词>→是
而在上面的例子中:所有用<>包括起来的都是"非终结符",而所有直接写出来的就是"终结符",以上规则就是产生式。从上面的例子中,我们通过感性认识理解。
非终结符:它不是语言的组成部分,而是在推导过程中的占位符,最终要替换成终结符。 终结符:语言是组成部分,是最后的内容。
产生式:用终结符替代非终结符的规则。 起始符:能够用于语言开头的符号,在本例中的<主语>就是起始符。 总结而言,整个推导的过程为:
<句子> <主语><谓语>
<名词词组><谓语> <主语>→<名词词组>
<名词><连词><名词词组><谓语>
<名词词组>→<名词><连词><名词词组>
<名词><连词><名词词组><动宾词组> <谓语>→<动宾词组> <名词><连词><名词词组><动词><名词>
<动宾词组>→<动词><宾语>
张三和李四是工程师 我们可以从中发现,它也可以推导出:"张三和工程师是李四",很显然,它属于文法正确,但语义是错误的。
(2)文法的分类
根据乔姆斯基的分类法,文法可以分成四种类型,如表3-3所示
要根据这样的定义来对文法进行判断,总是让许多考生无从下手,其实只要掌握一些规律,就能够更好地完成这一任务。
0型文法:就是一般形式的方法,只要符合我们前面的定义,就属于0型文法。因此也称为无限制文法、短语文法。由0型文法生成的语言称为0型语言。
1型文法:它的每一个产生式应该满足以下条件:jAf→jaf;其中:A?V (也就是说,A属于非终结符),f,j,a (VxT)* (也就是说,f,j,a是非终结符或终结符的组合)。由于这些产生式在替换非终结符时,需要考虑它的前一个、后一个元素(也就是产生式替换的非终结符的前、后均有一个不变的符号),因此又称为上下文有关文法,其产生的就是上下文有关语言,即1型文法。
2型文法:如果它的所有产生式都形如:A→a;其中:A?V(也就是说,A属于非终结符),a ?(V?T)* (也就是说,a是非终结符和/或终结符的组合)。那么,它就是一个2型方法,由于转换与前后元素没有关系(也就是产生式的前后都是空的),因此,也称之为上下文无关文法。
3型文法:它也是一个2型方法。
右线性文法:如果它的所有产生式都形如:A→aB或A→a(也就是除了A→a这种特殊形式外,每个产生式的右边都有一个非终结符);其中:A,BxV(也就是说,A,B属于非终结符),a(VxT)* (也就是说,a是非终结符和/或终结符的组合)。
左线性文法:如果它的所有产生式都形如:A→Ba或A→a(也就是除了A→a这种特殊形式外,每个产生式的左边都有一个非终结符);其他与上面一样。
右线性、左线性都称做3型文法或正则文法。
4. 词法分析
词法分析是整个分析过程的一个子任务,它把构成源程序的字符串转换成语义上关联的单词符号(包括关键字、标识符、常数、运算符和分界符等)的序列。词法分析可以借助于有限自动机的理论与方法进行有效的处理。
(1)有限自动机
有限自动机是一种自动识别装置,能够准确地识别正规集。它与3型文法对应,可以分为确定的有限自动机和不确定的有限自动机两种。
确定的有限自动机(DFA)
M=(S,S, δ,S0,Z)
1)S是一个有限集,每个元素为一个状态 2)S是一个有穷字母表,每个元素为一个输入字符
3)δ是转换函数:是一个单值对照
4)S0,属于S,是其唯一的初态
5)Z是一个终态集(可空)
有限状态自动机可以形象地用状态转换图表示,设有限状态自动机:
DFA = ({S, A, B, C, f}, {1, 0},δ,S, {f}),
其中:
δ(S, 0) = B, δ(S, 1) = A, δ(A, 0) = f, δ(A, 1) = C, δ(B, 0) = C, δ(B, 1) =f,δ(C, 0) = f, δ(C, 1) = f
其对应的状态转换图如图3-3所示。
不确定的有限自动机(NFA)
M=(S,S, δ,S0,Z)
1)S是一个有限集,每个元素为一个状态 2)S是一个有穷字母表,每个元素为一个输入字符
3)δ是转换函数,是多值对照
4)S0,属于S,是非空初态集
5)Z是一个终态集(可空)
与确定的有限自动机一样,不确定有限自动机同样可以用状态转换图表示,所不同的是,在图
中一个状态结点可能有一条以上的边到达其它状态结点。
从定义的角度来区分NFA与DFA,我们发现:DFA是单值对照,NFA是多值对照(其实也就对应
着上面所述的"NFA图中一个状态结点可能有一条以上的边到达其它状态结点")。
NFA可以转换为等价的DFA.
(2)正规式
对于字母表而言,正规则式和它所表示的正规集的递归定义是:
空集是正规表达式。
任何属于的a,都是其正规式。
假定U和V都是上的正规式,那它们的或、连接、闭包都是正规式。
通常在正规表达式中,一元运算符"*"具有最高的优先级,连接运算具有次优先级,运算符"|"具有最低优先级,这三个运算都是左结合的。每一个正规表达式R都对应一个有限自动机M,使M所接受的语言就是正规表达式的值。经过以下步骤可以从一个正规表达式R构造出相应的有限自动机M.
首先定义初始状态S和终止状态f,并且组成有向图:
然后反复应用以下规则:
直到所有的边都以Σ中的字母或ε标记为止。由此产生了一个带ε–转移的非确定有限自动机,然后可以通过上面介绍的方法,把该自动机转换成确定有限状态自动机。
下面举一个例子说明自动机理论在词法分析程序中的应用。C语言中对标识符的规定为由"_"或以字母开头的由"_"、字母和数字组成的字符串,该标识符的定义可以表示为下面的正则表达式:
式中的α代表字母字符{A,...,Z,a,...,z},d代表数字字符{0,1,...,9}.利用前面的方法构造出如图3-4所示的有限自动机。
该自动机所接受的语言就是C语言中的标识符。
在有限自动机的状态转换过程中,需要执行相关的语义动作。例如当识别到一个标识符时,需要在符号表中添加该标识符,并且向语法分析程序输送表示该标识符的单词。
5. 语法分析
语法分析的任务是识别由词法分析给出的单词符号序列是否为给定文法的正确句子(程序),语法分析可以分为自底向上分析和自顶向下分析两大类。
(1)自底向上分析
自底向上分析也称为移进--归约分析法。它的基本思想是:对输入符号串自左向右进行扫描,并将输入符号逐一移进一个后进先出的栈中,边移进边分析;一旦栈顶符号串形成某个句型的可归约串时,就用某产生式的左部非终结符来替代(这称之为归约)。一直重复这个过程,直到栈中只剩下文法的开始符号。
由于"可归约串"的不同,也就形成了几种不同的自底向上分析法。
规范归约分析法:用"句柄"来刻画"可归约串".
规范归约是规范推导的逆过程。LR分析法是一种规范归约分析法,它根据当前分析栈中的符号串和向右顺序查看输入串的k个符号,就可以确定分析器的移进还是归约。
常用的LR分析器有LR(0),SLR(1),LALR(1)和LR(1)四种。一个LR分析器由总控程序、分析表、分析栈三个部分组成。
算符优先分析法:用"最左素短语"来刻画"可归约串".
算符优先分析法是定义文法中终结符之间的优先关系,利用这种关系定义和操作可归约串,从而达到语法分析的目的。
如果文法G中不存在形如P→...QR...的产生式(P,Q,R均为非终结符),也就是产生式中没有非终结符连续出现的情况,则称G为算符文法。
对于一个不含e产生式的算符文法G,任何一对终结符a和b之间具有如下的优先关系,如表3-4所示
(2)自顶向下分析
自顶向下分析法也称为面向目标的分析方法,也就是从文法的开始符号出发尝试推导出与输入
的单词串相匹配的句子。它可以分为确定和不确定两种,如表3-5所示。
有一类称为LL(1)的文法可用递归子程序方法或预测分析方法来实现确定的自顶向下的语法分
析。要采用自顶向下的分析,必须消除左递归、提取公共左因子,然后采用下列方法之一进行分
析,如表3-6所示。
