语⾔处理程序c，第三章程序语⾔和语⾔处理程序基础知识
⼀、概述
1、汇编、编译、解释系统的基础知识和基本⼯作原理。
2、程序设计语⾔的基本成分：数据、运算、控制和传输，程序调⽤的实现机制。
3、各类程序设计语⾔的主要特点和适⽤情况：过程式程序语⾔、⾯向对象程序设计语⾔、函数式程序设计语⾔、逻辑程序设计语⾔的基本特点、脚本语⾔的特点。
⼆、汇编、编译、解释系统基础
1. 解释与编译
在计算机中，使⽤⾼级语⾔开发的程序都是不能直接运⾏的。需要经过⼀系列的处理，才能运⾏。这个过程，根据其处理⽅式的不同，可分为：解释型和编译型。
解释型：接受所输⼊的⽤程序语⾔编写的源程序，然后直接解释执⾏；这类语⾔中的最典型代表是BASIC.
编译型：它是将⽤某种程序语⾔编写的源程序直接翻译成为另⼀种语⾔(⽬标语⾔程序),⽽且两者在逻辑上等价。如:C语⾔。
2. 编译过程
所谓编译过程，就是使⽤编译程序将⾼级语⾔源程序翻译为等价的机器语⾔程序的过程。⼀般来说，编译程序分为以下⼏个部分：词法分析、语法分析、语义分析、中间代码⽣成、代码优化、⽬标代码⽣成以及贯穿始终的表格管理与出错处理。各部分之间的关系如图3-2所⽰。
词法分析：从左到右逐字符读⼊源程序，识别出⼀个个单词符号；它是根据语⾔的词法规则(单词结构规则)进⾏的。本节第4部分对词法分析进⾏了详细介绍。
语法分析：在词法分析的基础上将单词符号序列分解成各类，诸如"程序"、"语句"、"表达式"等
语法单位。
语义分析：审查源程序有⽆语义错误，为代码⽣成阶段收集类型信息。
中间代码⽣成：在语法分析过程中，随着分析的进展,⼀条产⽣式获得匹配或⽤于归约时，根据这条产⽣式所对应的语义⼦程序进⾏翻译的⽅法称为语法制导翻译。通过翻译后，将⽣成中间代码。不同的⾼级程序语⾔可能⽣成同样的中间代码。编译程序使⽤的中间代码通常有逆波兰、三元式、四元式和树形四种表⽰法。
代码优化：代码优化是对程序进⾏等价变换，使其⽣成更有效(运⾏时间更短、占⽤空间更⼩)的⽬标代码。根据优化所涉及的程序范围，可以分为局部优化、循环优化和全局优化三个不同的级别。
⽬标代码⽣成:⽬标代码⽣成是把经过语法分析或优化后的中间代码作为输⼊，将其转换成特定机器的机器语⾔或汇编语⾔代码作为输出，这样的转换程序称为代码⽣成器。
3. 形式语⾔基本知识
抽象地说，语⾔是按照⼀定规则排列的符号和集合。要形式化地描述⼀个语⾔，就需要借助以下⼀些基本概念。
字母表∑ :⾮空的有穷集合，例如 ∑ = {a,b}.
字符串：由∑ 的符号组成的有穷序列叫做字母表∑ 上的字符串。其中包含的字符数，称为长度。记做|字符串名|.长度为0的为空串，记做e.要注意的是,e中包括⼀个元素!⽽ ∅才是没有元素的空串。
形式语⾔: 上的字符串的全体记为∑ *, ∑*的任何⼦集都称做字母表?上的形式语⾔，简称语⾔。
前缀、后缀：设v是⼀个字符串，由v左边若⼲连续符号组成的字符串称做v的前缀。由v右边若
⼲连续符号组成的字符串称为v的后缀。
连接：设an,bn，则ab表⽰它们的连接，值为: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所⽰。
三、程序设计语⾔基础