编译原理第二弹——词法分析

学习完成编译原理基础之后，我们知道编译原理的第一步就是把源程序的单词进行分类处理，变成一个二元组token，包括单词的种类和值。

学习本章知识首先需要了解一些基本概念，不过编译原理这门课程学起来困难、枯燥的原因便是它概念非常的多，需要记忆的东西也很多，需要多多复习，理解记忆。

预备知识：（在这里我基本会采用一定的对比解释，方便理解）

字母表与串：这两个概念有一定的包含关系。

字母表：字母表∑是一个有穷符号集合，例如，{1，2，3，a，c}就是一个字母表，其中符号包括字母、数字、标点符号、…
字母表上的运算：乘积——∑1∑2 ={ab|a ∈ ∑1, b ∈ ∑2}，例: {0, 1} {a, b} ={0a, 0b, 1a, 1b}，其中默认：∑0 ={ ε }， ∑n =∑n-1 ∑ , n ≥ 1。例: {0, 1}3 ={0, 1} {0, 1} {0, 1}={000, 001, 010, 011, 100, 101, 110, 111}，字母表的n次幂:长度为n的符号串构成的集合

∑的正闭包——∑+ = ∑∪∑2∪∑3∪...，例:{a, b, c, d }+ = {a, b, c, d,aa, ab, ac, ad, ba, bb, bc, bd, ...,}，字母表的正闭包:长度正数的符号串构成的集合

∑的克林闭包——∑* = ∑0∪∑+ = ∑0∪∑∪∑2∪∑3∪...，例:{a, b, c, d }* = {ε, a, b, c, d,aa, ab, ac, ad, ba, bb, bc ...}，字母表的克林闭包:任意符号串(长度可以为零)构成的集合
串：设∑是一个字母表，x∈∑*，x称为是∑上的一个串。例如，{1，2，3，a，c}字母表，其中123就是串，串s的长度，通常记作|s|，是指s中符号的个数，例: |aab|=3，其中空串是长度为0的串，用 ε表示，ε|= 0
串上的运算：连接——如果 x和y是串，那么x和y的连接是把y附加到x后面而形成的串，记作xy ，例如，如果 x=dog且 y=house，那么xy=doghouse，其中，εs = sε = s，设x,y,z是三个字符串，如果 x=yz，则称y是x的前缀，z是x的后缀。

幂—— 串s的幂运算 s0= ε，sn = sn-1s , n ≥1，例:如果 s =ba，那么s1= ba，s2=baba， s3=bababa，...

文法的形式化定义，G=(VT ,VN ,P,S)
VT :终结符集合，终结符是文法所定义的语言的基本符号，例: VT = { apple, boy, eat, little }
VN:非终结符集合，非终结符是用来表示语法成分的符号，有时也称为“ 语法变量”，例: VN = { 句子, 名词短语, 动词短语, 名词 ... }，规定VT ∩VN=Φ，VT∪VN :文法符号集，
P :产生式集合，产生式描述了将终结符和非终结符组合成串的方法产生式的一般形式:α→β 读作:α定义为β
开始符号S∈VN。开始符号表示的是该文法中最大的语法成分，例:S = 句子，约定: 不引起歧义的前提下，可以只写产生式
符号约定（这部分需要记住，后期举例子，直接默认）

➢下述符号是终结符
(a) 字母表中排在前面的小写字母，如a、b、c
(b) 运算符，如+、*等
(c) 标点符号，如括号、逗号等 ➢(d) 数字0、1、. . . 、9
(e) 粗体字符串，如id、if等
➢下述符号是非终结符

(a) 字母表中排在前面的大写字母，如A、B、C

(b) 字母S。通常表示开始符号

(c) 小写、斜体的名字，如expr、stmt等
(d) 代表程序构造的大写字母。如E(表达式)、T(项) 和F(因子)

➢字母表中排在后面的大写字母(如X、Y、Z) 表示文法符号(即终结符或非终结符)
➢字母表中排在后面的小写字母(主要是u、v、. . . 、z) 表示终结符号串(包括空串)
➢ 小写希腊字母，如α、β、γ，表示文法符号串(包括空串 ➢除非特别说明，第一个产生式的左部就是开始符号

终结符非终结符文法符号

句型和句子，对于一个文法（规则），通过该规则推导到最终产生的符号中只要终结符，则最后的符号为句子，过程中产生的符号为句型。

语言，由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言，记为L(G )。即
Chomsky 文法分类体系

➢0型文法，α →β，又称无限制文法，顾名思义，这种文法对于左右两边没有任何的限制

➢ 1型文法，又称上下文有关文法，满足∀α → β∈P，|α|≤|β|，产生式的一般形式: α1Aα2 → α1βα2 ( β≠ε )

➢ 2型文法α →β，又称上下文无关文法，满足∀α → β∈P，α∈VN ，产生式的一般形式:A→β，即保证A一定为非终结符

➢ 3型文法，又称正则文法，正则文法能描述程序设计语言的多数单词，要求相对严格，与后面的正则表达式、有限自动机等价

四种文法之间的关系

CFG 的分析树，上下文无关文法的语法分析树，分析树是推导的图形化表示

                            ➢ 根节点的标号为文法开始符号
                            ➢ 内部结点表示对一个产生式A→β的应用，该结点的标号是此产生式左部A 。
                            ➢ 叶结点的标号既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串称为是这棵树的产出

编译原理第二弹——词法分析

(句型的)短语

➢给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语
➢ 如果子树只有父子两代结点，那么这棵子树的边缘称为该句型的一个直接短语

正则表达式，这是一个非常常见的概念，我们在学习编程语言的时候多少都会涉及这个知识。

正则表达式是一种用来描述正则语言的，例:r = a(a|b)*( ε | (.| _)(a|b)(a|b)* )，正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 r定义一个语言，记为L(r )。

正则表达式的定义 ε是一个RE，L(ε) = {ε}

如果 a∈∑，则a是一个RE，L(a) = {a}

正则文法与正则表达式等价

对任何正则文法 G，存在定义同一语言的正则表达式 r

对任何正则表达式 r，存在生成同一语言的正则文法 G

现在进入正题，在编译器中一般采用词法分析器进行词法分析，也就是我们说的有穷自动机。

有穷自动机
有穷自动机 ( FA )，主要根据当前状态，以及输入字符进行状态的切换。

FA使用转换图进行表示，结点:FA的状态、初始状态(开始状态):只有一个，由start箭头指向、终止状态(接收状态):可以有多个，用双圈表示、带标记的有向边:如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a

编译原理第二弹——词法分析

该FA定义(或接收)的语言，记为L(M )
一般自动机都遵循，最长子串匹配原则，当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配在到达某个终态之后，只要输入带上还有符号， DFA就继续前进，以便寻找尽可能长的匹配
FA的分类

确定的FA (DFA)

确定的有穷自动机 (DFA)
M = ( S，Σ ，δ，s0，F )
S:有穷状态集
Σ:输入字母表，即输入符号集合。假设ε不是 Σ中的元素
δ:将S×Σ映射到S的转换函数。 s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态。
s0:开始状态 (或初始状态)，s0∈ S F:接收状态(或终止状态)集合，F⊆ S
通俗的理解就是，DFA每个状态中处理能接收的字符，进行跳转的选择是唯一的。

非确定的FA (NFA)

非确定的有穷自动机(NFA)

M = ( S，Σ ，δ，s0，F )
S:有穷状态集
Σ:输入符号集合，即输入字母表。假设ε 不是Σ中的元素
δ:将S×Σ映射到2S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合
s0:开始状态 (或初始状态)，s0∈ S F:接收状态(或终止状态)集合，F⊆ S
通俗的理解就是，NFA每个状态中处理能接收的字符，进行跳转的选择是不唯一的。

DFA和NFA的等价性

对任何非确定的有穷自动机N ，存在定义同一语言的确定的有穷自动机

对任何确定的有穷自动机D ，存在定义同一语言的非确定的有穷自动机N

DFA和NFA可以识别相同的语言
由于等价，我们有办法实现正则表达式与NFA，NFA与DFA的转换。理解这两个过程最好的办法就是举例子。

正则表达式到NFA

这里需要使用五条规则

编译原理第二弹——词法分析