编译原理

编译程序：将高级语言的源程序翻译成与之等价的低级语言的目标程序的这样一种程序

源程序运行过程：编译阶段+运行阶段或者编译阶段+汇编阶段+运行阶段

解释程序：以源程序作为输入，但不产生目标程序，解释一条执行一条

汇编程序：用于特定计算机上的汇编语言的翻译程序。有时编译器把汇编语言作为目标语言，然后再由汇编程序将它翻译成目标代码。

连接程序：将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中

装入程序：编译器、汇编程序或连接程序生成的代码还不能运行，装入程序处理所有的与指定的基地址有关的可重定位地址，并将修改后的指令和数据放在内存中适当的位置。

预处理程序：预处理程序是在真正的编译开始之前由编译器调用的独立程序。预处理程序可以删除注释、包含其它文件以及执行宏替代。

源程序+初始数据→解释程序→计算结果

源程序→编译程序→初始数据+目标程序+运行系统子程序→计算结果

一般分为5个阶段：词法分析→语法分析→语义分析与中间代码产生→优化→目标代码生成

表格管理程序：登记源程序的各类信息和编译程序各阶段的进展情况，如符号表。

出错处理程序：发现并指出源程序中错误的性质和位置；自动校正错误

遍：对源程序或源程序的中间结果从头至尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序的处理过程称为一遍。可以把一个阶段分为若干遍，也可以把多个阶段合为一遍，通常有一遍和多遍编译程序。

前端（front end）：由与源语言有关但与目标机无关的部分组成。

后端（back end）：包括与目标机有关的部分。而一般不依赖于源语言，只与中间代码有关的编译阶段。

程序语言是符号语言，即一个记号系统，它主要有语法、语义和语用等三方面定义。

语法：是对语言结构的定义（什么样的符号序列是合法的）。任何语言程序都可看成是一定字符集上的一字符串（有限序列），语法定义语言的词法和语法的形式规则。

语义：描述语言的含义；定义语言的单词符号和语法单位的意义。目前编译程序中常用的语义分析方法是一种基于属性文法的语法制导翻译。即在语法分析的同时对其中识别出的语法单位进行语义的分析与翻译工作；在描述文法的同时为定义的语法范畴加上它们的属性计算规则，属性可以是语法范畴的类型、地址、取值、执行动作等信息。

语用：是从使用的角度去描述语言。定义程序设计技术和语言成分的使用方法，它使语言的基本概念与语言的外界（如数学概念或计算机的对象和操作）联系起来

字母表(alphabet)：字母表是元素的非空有穷集合，任何语言的字母表指出了该语言中允许出现的一切符号。

符号(symbol)：字母表中的元素称为符号，或称为字符。

符号串（string）:符号的有穷序列称为字符串。符号串总是建立在某个特定字母表上的且只能由字母表上的有穷多个符号组成。不包含任何符号的符号串，称为空符号串，用(epsilon)表示

符号串的连结 catenation：设 x 和 y 是符号串，则串 xy 称为它们的连结。

特别，对任意一符号串 x 有：

集合的乘积 product：设 A 和 B 是符号串的集合，则 A 和 B 的乘积定义为：AB = {xy | x ∈ A, y ∈ B}

空集 Φ empty set：Φ 表示不含任何元素的空集 { }

符号串的幂运算 power：设 x 是符号串，则 x 的幂运算定义为：

集合的幂运算同理，只不过

集合A的正闭包A+与闭包A：设 A 是符号串的集合，则集合 A 的正闭包 A+ 和闭包 A* 定义为：

形式语言：序列(字符串)的集合称为形式语言。每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合；任何一个字母表上符号串的集合均可定义一个形式语言。

形式语言的描述有两种方法：

显然由 A 生成的符号串属于 ∑+，这就是文法描述语言，它描述了无穷集合的语言。

文法的形式定义：

规则：规则也称产生式，它是一个符号与一个符号串的有序对（A,），通常写做A→（ 或 A::= ）

其中 A 是规则左部，是一个符号；是规则右部，是一个符号串。→ 或 ::= 表示“定义为”或“生成”，意思是左部符号用右部符号串定义或左部符号生成右部符号串。规则的作用是告诉如何用规则中的符号串生成语言中的序列。一组规则规定了一个语言的语法结构。

非终结符：出现在产生式左部能派生出符号或符号串的那些符号，即每个非终结符表示一定符号串的集合。用大写字母表示或用尖括号把非终结符括起来。 终结符：是不属于非终结符的那些符号，它是组成语言的基本符号，是一个语言的不可再分的基本符号，只出现在产生式右部。通常用小写字母表示。

文法：文法是规则的非空集合，是一个四元式G =（，，P，S），其中：

左部相同的产生式，如A→α1， A→α2， …， A→αn，可合并为一个，缩写为A→ α1|α2| … |αn

例1

设字母表∑＝{a,b},试设计文法，描述语言 L={， | n≥1}

分析：设计文法来描述一个语言，关键是设计一组规则生成语言中的符号串。设计语言的文法，必须分析这个语言是由怎样一些符号串组成，即首先分析语言中符号串的结构特征：

很显然，a,b是终结符，非终结符A定义完整L，需要终结符B、D来描述A，按照逻辑，该文法能描述语言L，此外，描述该语言的文法不是唯一的。

G 和 G’ 是两个的文法，如果它们描述的语言相同，那么称 G 和 G’ 为等价文法。

例2

设计一个表示所有标识符的文法

分析：标识符的定义是字母或以字母开头的字母数字串（此处先不考虑大写字母）

显然，终结符是字母数字集合{a-z}∪{0-9}中的元素，标识符语言={字母*字母,字母*数字}，因此设计文法

例3

用文法定义一个含+、*、()的算术表达式。

分析：变量是表达式；若 E1 和 E2 是算术表达式，则 E1+E2，E1*E2，(E) 也是算术表达式。

例4

设字母表∑＝{a,b}，设计一个文法，描述语言 L={aa | n≥0}

直接推导：令 G 是一文法，一步推导 => 表示用某一规则的右部替换其左部。如果有 xAy => xαy，仅当 A→α 是 G 的一个规则（产生式），且 x、y ∈ (∪)*，称 xAy 直接推出 xαy。

推导：如果存在一个直接推导序列： => => … => 则称这个序列是从 到 的长度为 n 推导，记为=>+（这个符号其实是+在=>这个符号上面，这里表示不出来，==下面这个符号都用=>+表示==）

广义推导： =>*(这个符号其实是*在=>这个符号的上面，这里表示不出来，==下面这个符号都用=>*表示==) 表示从α0 出发，经过 0 步或多步可推导,也就是说 =>* 意味着： = 或者 =>+

直接推导的长度为1，推导的长度大于等于1，广义推导的长度大于等于0

句型与句子：

设有文法 G[S]，如果S=>*x, x∈(∪)*，则称符号串 x 为文法 G[S]的句型. 如果S==>*x, x∈，则称符号串 x 为文法 G[S]的句子。

语言：

文法 G[S] 产生的所有句子的集合称为文法 G 所定义的语言，记为 L(G[S]):L(G[S]) = { x | S=>+x 且 x∈ }，由语言定义可知： (1)当文法给定，语言也就确定； (2)L(G) 是 的子集。即属于的符号串不一定属于L(G)

例1

设有文法G[S]: S→01 | 0S1，求该文法所描述的语言

分析：问题归结为由识别符号 S 出发，将推导出什么样的句子，也就是说 L(G{S])是由一些什么样的符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。

即S >=+ 所以此文法定义的语言为 L(G[E]) = { | n≥1}

例2

设有文法G[S]: S→0S|1S|求该文法所定义的语言

例3

设有文法G[A]: A→yB,B→xB|x求该文法所定义的语言

文法所定义的任一句型和句子，都可以根据文法推导出来，但同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中所选择非终结符的次序无关。

为了使句子能按一种确定的推导序列来产生，以便对句子的结构进行确定性的分析。通常只考虑两种特殊推导：

最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。每个句子都有规范推导，但对句型此结论并不成立。

归约：推导的逆过程。归约是与推导相对的概念，推导是把句型中的非终结符用规则的一个右部来替换的过程，而归约是句型中的某个子串用一个非终结符来替换的过程.用 =>· （实际上·在=>这个符号上面，==下面均用=>·表示这个符号==）表示归约。

规范推导的逆过程，称为最左归约，也称为规范归约。

递归规则：所谓递归规则，是指在规则的左部和右部具有相同的非终结符的规则。

文法的递归性：文法的递归性，是指对文法中任一非终结符，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符本身，则文法是递归的，否则是无递归性的。

文法中使用递归规则，使得能用有限的规则去定义无穷集合的语言。

令 G 是一个文法，S 是文法的开始符号，假定αβδ是文法 G 的一个句型，如果是 S =>* αAδ 且 A =>+ β 则称 β 是相对于非终结符 A 的句型 αβδ 的短语。 特别是，如果有 S =>* αAδ 且 A => β 则称β是直接短语（简单短语）。

短语是句型的一部分。

一个句型的最左直接短语称为该句型的句柄。 句柄特征： (1)它是直接短语，即某规则右部 (2)它具有最左性。

短语、直接短语和句柄都是针对某一句型的，特指句型中的哪些符号串能构成短语和直接短语，离开具体的句型来谈短语、直接短语和句柄是无意义的。.

设有文法G[S]=({S,A,B},{a,b},P,S) S →AB A →Aa | bB B →a|Sb 求句型 baSb 的全部短语、直接短语和句柄

根据短语定义，可以从句型的推导过程中找出其全部短语、直接短语和句柄。建立句型的推导过程： S=>AB=>bBB=>baB=>baSb 最左推导 S=>AB=>ASb=>bBSb=>baSb 最右推导

对句型的推导过程给出一种图形表示，这种图形表示称为语法树，也称推导树。设文法 G=(，，S，P)，对 G 的任何句型都能构造与之关联的、满足下列条件的一棵语法树。

语法树的构造是从文法的开始符号出发，构造一个推导的过程，因为文法的每一个句型(句子)都存在一个推导，所以文法的每个句型(句子)都有一棵对应的语法树。

句型 (i+i)*i-i 的最左、最右推导得到的语法树完全相同，也就是说，一棵语法树表示一个句型的种种可能的(但未必是所有的)不同推导过程。

子树：语法树的子树是由某一个结点连同所有分支组成的部分。

简单子树：语法树的简单子树是指只有单层分支的子树。

根据子树的概念，句型的短语、直接短语和句柄的直观解释如下：

短语：子树的末端结点形成的符号串是相对于子树根的短语。 直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。 句柄：最左简单子树的末端结点形成的符号串是句柄。

因此可以由子树以及子树的末端节点直接看出短语、直接短语与句柄

如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左推导或有两个不同的最右推导，则称这个文法是二义的

二义性的文法将给编译程序的执行带来问题。对于二义性文法的句子，当编译程序对它的结构进行语法分析时，就会产生两种甚至多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。

解决二义性问题：构造一个等价的无二义性文法；即排除二义性的规则，改写原有的文法。

在改造文法的过程中，观察到推导步骤中的规律：靠前的推导，所用规则结合性弱；语法树上层次高；靠后的推导，所用规则结合性强，语法树上层次低。

也就是说，想要让一个规则结合性弱；就让它出现在推导序列前面（语法树的上层）；想要让一个规则结合性强；就让它出现在推导序列后面（语法树的下层），对于这样的强弱规律正好对应于运算的优先级规律，因此将运算符的优先顺序和结合规则，融合到原有文法中，可构造出无二义性文法

改造之后的语法树就变为了：

2 型文法(上下文无关文法)

若文法 G=(，，S，P)中的每条规则 A → β，其中 A∈，β∈(∪)*，则称 G 是 2 型文法，2 型文法描述的语言是 2型语言

由定义可见，利用规则将 A 替换成 β 时，与 A 的上下文环境无关，即无需考虑 A 在上下文中出现的情况。故又称为上下文无关文法，相应的语言称为上下文无关语言。 通常定义程序设计语言的文法是上下文无关文法。

3 型文法(正规文法)

右线形文法：若文法G=(，，S，P)中的每条规则A → αB 或 A → α，其中 A,B∈，α∈，则称 G 是右线形文法。 左线形文法：若文法G=(，，S，P)中的每条规则A → Bα 或 A → α，其中 A,B∈，α∈，则称 G 是左线形文法。

右线形文法和左线形文法都称为 3 型文法或正规文法，3型文法描述的语言称为 3 型语言或正规语言。通常定义程序设计语言词法规则的文法是正规文法。