第一章 引言

1.1从面向机器的语言到面向人类的语言

面向机器的语言：
机器指令：000 1100 0011 0101
汇编语言：MOV AX, [A]
面向人类的语言：
通用程序设计语言： x = a + b;
数据查询语言：select id from student
形式化描述：E：E’+E’ | E’ * E’

1.2语言之间的翻译

习惯称法：

1. 汇编语言－机器指令：汇编（或交叉汇编：在一个平台上生成另一个平台上的可执行代码）
2. 程序设计语言－汇编语言或机器指令：编译（或解释）
3. 高级语言之间：转换（或预编译）
4. 逆向：反汇编、反编译

1.3编译器和解释器

语言翻译的两种形式：

特点：

1. 编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数PL采用此种方法翻译；
2. 解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的Basic和现在的Python和Javascript等一般用解释方式翻译。

从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。

1.4编译器的工作原理与基本组成

1.4.1通用程序设计语言的主要成份

1．从语言抽象的演变看：
过程→抽象数据类型（ADT，模块）→ 类
2．共同特点：两大部分组成：声明＋操作＝完整定义
3．以过程式语言为例：
声明性语句：提供操作对象的性质，如数据类型、值、作用域等；
操作性语句：确定操作的计算次序，完成实际操作。
过程头＋过程体＝过程定义
4．编译器对两类语句的翻译：
声明：生成相应的环境，一般是配置存储空间。
操作：生成可执行的代码序列。

1.4.2 以阶段划分编译器

1.4.3 编译器各阶段的工作

源程序 —（词法分析）—> 记号流 —（语法分析）—> 语法树 —（语义分析）—> 符号表部分内容 —（中间代码生成）—> 中间代码 —（中间代码优化）—> 代码优化 —（目标代码生成）—> 目标代码

在上列阶段中都要做两件事：
（1）建表和查表；（2）出错处理；
所以编译程序中都要包括符号表管理和出错处理两部分
符号表管理：
在整个编译过程中始终都要贯穿着建表（填表）和查表的工作。即要及时地把源程序中的信息和编译过程中所产生的信息登记在表格中，而在随后的编译过程中同时又要不断地查找这些表格中的信息。
出错处理：
规模较大的源程序难免有多种错误，编译程序必须要有出错处理的功能。即能诊察出错误，并能报告用户错误的性质和位置，以便用户修改源程序。出错处理能力的大小是衡量编译程序质量好坏的一个重要指标。

1.4.4 编译器的分析/综合模式

第二章 词法分析

2.1词法分析中的若干问题

2.1.1 记号、模式与单词

单词基本分类：

• 关键字 keyword
• 标识符 id
• 字面量 literal
• 特殊符号 key symbol

模式（patten）：产生和识别元素的规则
记号（token）：按照某个模式（或规则）识别出的元素（一组）
单词（lexeme）：被识别出的元素自身的值（一个），也称为词值

2.1.2 记号的属性

记号 = 记号类别 + 记号的属性

2.1.3 词法分析器的作用与工作方式

特征：编译器中唯一与源程序打交道的部分
任务：

1. 滤掉源程序中的无用成分，如注释、空格、回车等
2. 处理与具体平台有关的输入（如文件结束符的不同表示）
3. 根据模式识别记号，并交给语法分析器
4. 调用符号表管理器或出错处理器，进行相关处理

工作方式：

1. 单独一遍扫描
   

2. 作为语法分析器的子程序
   

3. 并行方式

2.1.4 输入缓冲区

为什么：

1. 超前搜索
2. 方便实现读字符和退字符操作，提高词法分析器效率

2.2 模式的形式化描述

2.2.1 字符串与语言

语言L是有限字母表∑上有限长度字符串的集合。
字母表是组成字符串的所有字符的集合。

字符串的基本概念：

字符串集合的基本运算：

2.2.2 正规式与正规集

定义：
令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下:

1. ε是正规式，它表示集合L(ε)={ε}
2. 若a是Σ上的字符，则a是正规式，它表示集合L(a)={a}
3. 若正规式r和s分别表示集合L®和L(s)，则
   （a） r|s是正规式，表示集合L®∪L(s)，
   （b） rs是正规式，表示集合L®L(s)，
   （c） r是正规式，表示集合(L®)，
   （d）( r )是正规式，表示的集合仍然是L( r )。（加括弧改变优先级、结合性）

可用正规式描述的语言称为正规语言或正规集。

优先级：

1. 三种运算均具有左结合性质；
2. 优先级从高到低顺序排列为: 闭包运算、连接运算、或运算。则正规式中不必要的括号可以被省略。

若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q。

2.2.3 记号的说明

2.3 记号的识别－有限自动机

2.3.1 不确定的有限自动机NFA

定义：
NFA是一个五元组（5-tuple）：M =（S，∑，move，s0，F），其中：

1. S是有限个状态（state）的集合；
2. ∑是有限个输入字符（包括ε）的集合；
3. move是一个状态转移函数的集合，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；
4. s0是唯一的初态（也称开始状态）；
5. F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。

2.3.2 确定的有限自动机DFA

限制1：没有ε状态转移
限制2：同一状态下没有重复字符的状态转移

2.3.3 有限自动机的等价

若有限自动机M和M’识别同一正规集，则称M和M’是等价的，记为M=M’。

2.4 从正规式到词法分析器

2.4.1 从正规式到NFA

Thompson 算法：


通过ε转移， 状态q可以直接到达N(s)或N(t)的初态。而N(s)或N(t)原来的终态也可以通过ε转移直接到达整个NFA的新终态。

N(s)的初态成为新的NFA的初态。 原来N(s)的终态成为N(t)的初态。而原来N(t)的终态成为新的NFA的终态。

将新表达式的初态和终态以及夹在中间的子表达式的NFAN(s)连接起来的ε转移使得可以选择经过或者不经过子表达式。而从N(s)的终态到初态的ε转移使得s可以重复任意多次。

示例：
r=(a|b)*abb的NFA

2.4.2 从NFA到DFA

smove(S, a)：从状态集S出发，标记为a的下一状态全体。与move(s, a)的唯一区别：用状态集取代状态
ε-闭包(T)：从状态T出发，不经任何字符达到的状态全体。

子集法：
示例：

2.4.3 最小化DFA

示例：

第三章 语法分析

3.1 语法分析的若干问题

3.1.1 语法分析器的作用

它的主要作用有两点：

1. 根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树），这是本章的重点，在以后各节中详细讨论；
2. 检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理，下边简单介绍语法错误处理的基本原则，而在以后的讨论中忽略此问题。

3.2 上下文无关文法CFG

3.2.1 CFG的定义与表示

CFG是一个四元组G =（N，T，P，S），其中

1. N是非终结符（Nonterminals）的有限集合；
2. T是终结符（Terminals）的有限集合，且N∩T=Φ；
3. P是产生式（Productions）的有限集合,A→α，其中A∈N（左部），α∈(N∪T)*（右部），若α=ε，则称A→ε为空产生式（也可以记为A →）；
4. S是非终结符，称为文法的开始符号（Start symbol）。

3.2.2 CFG产生语言的基本方法－推导

1. 对于任意α，有α=*>α，即推导具有自反性；
2. 若α=>β，β=>γ，则α=*>γ，即推导具有传递性。

由CFG G所产生的语言L(G)被定义为:
L(G) = { ω┃S=+>ω and ω∈T* }，

L(G)称为上下文无关语言（Context Free Language, CFL），ω称为句子。若S=>α，α∈(N∪T)，则称α为G的一个句型。

最左（最右）推导：每次直接推导均替换句型中最左（最右）边的非终结符。
由最左（最右）推导产生的句型被称为左（右）句型。
最右推导也被称为规范推导。

3.2.3 推导、分析树与语法树

对CFG G的句型，分析树被定义为具有下述性质的一棵树。

1. 根由开始符号所标记；
2. 每个叶子由一个终结符、非终结符、或ε标记；
3. 每个内部结点由一个非终结符标记；
4. 若A是某内部节点的标记，且X1，X2，…，Xn是该节点从左到右所有孩子的标记，则A→X1X2…Xn是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子。

分析树与语言和文法的关系：
① 每一直接推导（每个产生式），对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子；
② 分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。

对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树:

1. 根与内部节点由表达式中的操作符标记；
2. 叶子由表达式中的操作数标记；
3. 用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。

3.2.4 二义性与二义性的消除

若G对同一句子产生不止一棵分析树，则称G是二义的。

消除二义性：

1. 改写二义文法为非二义文法；
2. 规定二义文法中符号的优先级和结合性，使仅产生一棵分析树。

3.3 语言与文法简介

3.3.1 正规式与上下文无关文法

正规式所描述的语言结构均可用CFG描述，反之不一定。

正规式到CFG的转换

步骤：

1. 构造正规式的NFA；
2. 若0为初态，则A0为开始符号；
3. 对于move(i,a)=j，引入产生式Ai→aAj；
4. 对于move(i,ε)=j，引入产生式 Ai→Aj；
5. 若i是终态，则引入产生式Ai →ε。

为什么用正规式而不用CFG描述词法

① 词法规则简单，用正规式描述已足够；
② 正规式的表示比CFG更直观、简洁、易于理解；
③ 有限自动机的构造比下推自动机简单，且分析效率高；
④ 区分词法和语法，为编译器前端的模块划分提供方便。

3.3.2 上下文有关语言 CSL

程序设计语言中除了CFG可以描述的结构之外，还有一些是CFG无法描述的所谓上下文有关的结构。
典型的这类语言结构包括：变量的声明与引用、过程调用时形参与实参的一致性检查等。
描述它们的文法被称为上下文有关文法（Context Sensitive Grammar, CSG）。