下载掌阅APP，畅读海量书库
立即打开
3.2.1 考点精讲
在计算机中，程序语言分为低级语言和高级语言，如汇编语言便是一种低级语言，而平时我们所使用的Java、C#、Delphi等，都属于高级语言。使用高级语言开发的程序是不能直接运行的，需要经过一系列的处理，才能运行。这个过程，根据其处理方式的不同，可分为解释型和编译型。
解释型：接受所输入的用程序语言编写的源程序，然后直接解释执行。这类语言中的最典型代表是BASIC。
编译型：它是将用某种程序语言编写的源程序直接翻译成为另一种语言（目标语言程序），而且两者在逻辑上等价，如C语言。
所谓的编译过程，就是使用编译程序将高级语言源程序翻译为等价的机器语言程序的过程。一般来说，编译程序分为以下几个部分：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成以及贯穿始终的表格管理与出错处理。各部分之间的关系如图3-1 所示。
图 3-1 编译的主要过程
语言是按照一定规则排列的符号和集合。要形式化地描述一门语言，就需要借助文法的概念。文法就是用来描述语言的语法结构的形式规则。
根据乔姆斯基分类法，文法可以分成 4 种类型，如表 3-1 所示。
表 3-1 乔姆斯基分类法
要根据这样的定义来对文法进行判断，总是让许多考生无从下手，其实只要掌握一些规律，就能够更好地完成这一任务（当然，这个知识点考查概率在不断降低，若完成本节学习后仍有疑问，可考虑先将主要精力投入其他章节学习）。
● 0型文法：就是一般形式的方法，只要符合前面的定义，就属于0型文法，因此也称为无限制文法、短语文法。由0型文法生成的语言称为0型语言。
● 1型文法：它的每一个产生式应该满足以下条件：
；其中：A∈V（也就是说，A属于非终结符），
（也就是说，φ、
、α是非终结符或终结符的组合）。由于这些产生式在替换非终结符时，需要考虑它的前一个、后一个元素（也就是产生式替换的非终结符的前后均有一个不变的符号），因此又称为上下文有关文法，其产生的就是上下文有关语言，即 1 型文法。
● 2型文法：如果它的所有产生式都形如：A→α；其中A∈V（也就是说，A属于非终结符），α∈(V∪T)*（也就是说，α是非终结符和/或终结符的组合）。那么，它就是一个2型文法，由于转换与前后元素没有关系（也就是产生式的前后都是空的），因此，也称之为上下文无关文法。
● 3型文法：它也是一个2型方法。
▶ 右线性文法：如果它的所有产生式都形如A→αB或A→α（也就是除了A→α这种特殊形式外，每个产生式的右边都有一个非终结符）；其中A,B∈V（也就是说，A、B属于非终结符），α∈(V∪T)*（也就是说，α是非终结符和/或终结符的组合）。
▶ 左线性文法：如果它的所有产生式都形如A→Bα或A→α（也就是除了A→α这种特殊形式外，每个产生式的左边都有一个非终结符），其他与上面一样。
▶ 右线性、左线性都称作 3 型文法或正则文法。
词法分析是整个分析过程的一个子任务，它把构成源程序的字符串转换成语义上关联的单词符号（包括关键字、标识符、常数、运算符和分界符等）的序列。词法分析可以借助于有限自动机的理论与方法进行有效的处理。
（1）有限自动机
有限自动机是一种自动识别装置，能够准确地识别正规集。它与 3 型文法对应，可以分为确定的有限自动机和不确定的有限自动机两种。
● 确定的有限自动机（DFA）
M=(S,Σ, δ,S0,Z)
1）S是一个有限集，每个元素为一个状态；
2）Σ是一个有穷字母表，每个元素为一个输入字符；
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-2 所示。
图 3-2 状态转换图
● 不确定的有限自动机（NFA）
M=(S,Σ, δ,S0,Z)
1）S是一个有限集，每个元素为一个状态；
2）Σ是一个有穷字母表，每个元素为一个输入字符；
3）δ是转换函数，是多值对照；
4）S0 属于S，是非空初态集；
5）Z是一个终态集（可空）。
与确定的有限自动机一样，不确定有限自动机同样可以用状态转换图表示，所不同的是，在图中一个状态节点可能有一条以上的边到达其他状态节点。
从定义的角度来区分NFA与DFA，我们发现：DFA是单值对照，NFA是多值对照（其实也就对应着上面所述的“NFA图中一个状态节点可能有一条以上的边到达其他状态节点”）。
NFA可以转换为等价的DFA。
（2）正规式
对于字母表∑而言，正规式和它所表示的正规集的递归定义是：
● 空集是正规表达式。
● 任何属于∑的α，都是其正规式。
● 假定U和V都是∑上的正规式，那它们的或、连接、闭包都是正规式。
通常在正规表达式中，一元运算符“*”具有最高的优先级，连接运算具有次优先级，运算符“|”具有最低优先级，这 3 个运算都是左结合的。每一个正规表达式R都对应一个有限自动机M，使M所接受的语言就是正规表达式的值。经过以下步骤可以从一个正规表达式R构造出相应的有限自动机M。
首先定义初始状态S和终止状态f，并且组成有向图：
然后反复应用以下规则：
直到所有的边都以Σ中的字母或ε标记为止。由此产生了一个带ε–转移的不确定有限自动机，然后可以通过上面介绍的方法，把该自动机转换成确定有限状态自动机。
下面举一个例子说明自动机理论在词法分析程序中的应用。C语言中对标识符的规定为由“_”或以字母开头的由“_”、字母和数字组成的字符串，该标识符的定义可以表示为下面的正则表达式：
式中的α代表字母字符{A,…,Z,a,…,z}，d代表数字字符{0,1,…,9}。利用前面的方法构造出如图 3-3 所示的有限自动机。
图 3-3 有限自动机图例
该自动机所接受的语言就是C语言中的标识符。
在有限自动机的状态转换过程中，需要执行相关的语义动作。例如，当识别到一个标识符时，需要在符号表中添加该标识符，并且向语法分析程序输送表示该标识符的单词。
语法分析的任务是识别由词法分析给出的单词符号序列是否为给定文法的正确句子（程序），语法分析可以分为自底向上分析和自顶向下分析两大类。
（1）自底向上分析
自底向上分析也称为移进—归约分析法。它的基本思想是：对输入符号串自左向右进行扫描，并将输入符号逐一移进一个后进先出的栈中，边移进边分析；一旦栈顶符号串形成某个句型的可归约串时，就用某产生式的左部非终结符来替代（这称为归约）。一直重复这个过程，直到栈中只剩下文法的开始符号。
（2）自顶向下分析
自顶向下分析法也称为面向目标的分析方法，也就是从文法的开始符号出发尝试推导出与输入的单词串相匹配的句子。