一·预备知识（编译概述）

翻译程序是指这样一个程序,它把一种语言(源语言)所写的程序(源程序)翻译成等价的另一种语言(目标语言)的程序(目标程序)。

编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。其工作过程一般可划分为如下五个阶段：

1：词法分析

词法分析阶段的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个一个具有独立意义的单词( 也称单词符号, 简称符号 )。

注：词法规则就是单词符号的形成规则,它规定了哪样的字符串构成一个单词符号。

2：语法分析

语法分析的任务是在词法分析的基础上, 根据语言的语法规则从单词符号串中识别出各种语法单位 ( 如表达式、说明、语句等 ) ,并进行语法检查,即检查各种语法单位在语法结构上的正确性。

注：语言的语法规则规定了如何从单词符号形成语法单位，语法规则是语法单位的形成规则。

3：语义分析和中间代码生成

语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式 (比源语言更接近于目标语言的一种中间代码或直接用目标语言 ) 来描述这种语义。

4：代码优化

代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效即省时间和空间的目标代码。优化主要包括局部优化和循环优化等，例如上述四元式经局部优化后得

5：目标代码生成

目标代码生成的任务是将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。

二：文法和语言（形式语言理论）

语法是对语言结构的定义。 语义是描述了语言的含义 。 语用则是从使用的角度去描述语言。 对每个具体语言,都有语法和语义两个方面，形式语言是指不考虑语言的具体意义，即不考虑语义。

1. 字母表 ：

元素的非空有穷集合 ，例如，∑={ a, b, c }

2. 符号（字符）：

字母表中的元素称为符号或称为字符。

3. 符号串（字）：

符号的有穷序列称为符号串，不包含任何符号的符号串, 称为空符号串，用ε表示。

4：形式语言：

形式语言是某个字母表上按某种规则构成的所有符号串（序列）的集合。反之，任何一个字母表上符号串的集合均可定义为一个形式语言。

5：规则（产生式）：

规则是一个符号与一个符号串的有序对（A,β），通常写作：A→β（或A∷＝ β) 。规则的作用是告诉我们如何用规则中的符号生成语言中的序列。规则中出现的符号分为两类，一类是终结符号，另一类是非终结符号。

非终结符号是出现在规则左部能派生出符号或符号串的那些符号，即每个非终结符号表示一定符号串的集合，用大写字母表示或用尖括号把非终结符号括起来。例如，上例中的A。

终结符号是不属于非终结符号的那些符号, 它是组成语言的基本符号，是一个语言的不可再分的基本符号，通常用小写字母表示。

6：文法：

规则的非空有穷集合，通常表示成四元组G={VN,VT, P, S }

VN是规则中非终结符号的集合，VT是规则中终结符号的集合，P 是文法规则的集合，S是特别的非终结符，称为文法的开始符号，它至少要在一条规则中作为左部出现。由它开始，识别出我们所定义的语言

为了书写方便，对于若干个左部相同的规则，将它们缩写为：A→a1 | a2 | … | an，其中每个ai有时也称为是A的一个候选式

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

定义语言L的文法G[S]=( V_N，V_T，P，S )

其中非终结符集合V_N={A, B, D}，终结符集合V_T={a, b}，文法开始符号S =A

文法规则集合：P={ A→aa|aaB|bb|bbD

                                         B→aa|aab

                                         D→bb | bbD}

描述一个语言的文法并不唯一,如上例的其他答案

P‘ : {A→B | D

         B→aa | aBa

         D→bb | bDb}

7.:句型和句子

自己动手实现简单编译器之（一）形式语言理论