词法分析
为了把程序从一种语言翻译成另一种语言，编译器必须首先把程序分解并搞清相应的结构和含义，然后再用不同的方式把它们组合起来。编译器的前端负责分析，后端负责组合。
分析的类别
分析包含3类：
词法分析：将输入分解成单独的字或记号；
语法分析：分析程序中短语的结构；
语义分析：分析程序的含义。
词法分析器接收字符流，生成一系列的名字、关键字和标点符号，并舍弃了记号之间的空白符和注释。
那些随机出现的空白符和注释将分析过程复杂化了，这也是将词法分析单独分离出去的主要原因。
词法分析并不是很复杂，但是需要使用形式化的方法和工具来实现，类似的方法对于学习分析是很有好处的，类似的工具还可以应用在编译器外的其他地方。
词法记号
词法记号可以看做是编程语言语法单元的一系列字符。编程语言的词法记号分为有限的几种记号类型。
例如，有一些典型的编程语言的记号类型为：
| 类型 | 示例 |
|---|---|
| ID | foo、n14、last |
| NUM | 73 000 515 |
| REAL | 66.1 .5 10 1e67 5.5e-10 |
| IF | if |
| COMMA | , |
| LPAREN | ( |
| RPAREN | ) |
IF，VOID， RETURN 等由字母表中的字符组成的记号叫做“保留字”， 在大多数语言中， 它们不能被看成标识符。
下面是一组非记号的例子：
| 说明 | 示例 |
|---|---|
| 注释 | /*try again*/ |
| 预处理命令 | include<stdio.h> |
| 预处理命令 | #define NUMS 5， 6 |
| 宏 | NUMS |
| 空格、跳格和回车 |
因语言的功能不够强大，所以需要一个宏预处理，这个预处理对原始的字符流操作，并生成一个适合于词法分析器的新的字符流。
可以把宏处理和词法分析合二为一。
考虑如下的程序段：
float match 0(char*s)/*find azero*/
(if(!strncmp(s，“0.0”，3))
return 0.；
词法分析器将返回如下数据流：
FLOAT ID(match 0) LPAREN CHAR STAR ID(s) RPAREN
LB RACE IF LPAREN BANG ID(strncmp) LPAREN ID(s)
COMMA STRING(0.0) COMMA NUM(3) RPAREN RPAREN
RETURN REAL(0.0) SEMIR BRACEE OF
其中显示了每个记号的记号类型。它们中的一些记号，比如标识符和文字，本身都含有语义信息，需要在记号类型中给出附加的信息。
如何描述编程语言的词法规则呢?词法分析器可以用什么样的语言编写呢?
可以用英文来描述语言的词法记号。
标识符
以下是在C或Java中对标识符的描述：
标识符是由一系列的字母和数字组成的，必须以一个字母开头。下划线计为一个字母。标识符区分大小写，其中不能包括空格、跳格、回车和注释，除非它们列为单独的一类记号。但有时需要一些空格来分隔相邻的标识符、关键字和常量。
有很多用于实现词法分析器的语言，但是常用正则表达式来定义词法记号，用确定有限自动机来实现词法分析器并用某种机制来连接它们。
由此来实现一个简洁、具有可读性的词法分析器。
正则表达式
程序语言可以认为是一个字符串集，字符串是一个有限的符号集。符号本身就是有限的字母。
Pascal语言就是一个字符串集， 这些字符串组成了合法的Pascal程序；
素数语言是一个十进制数字的字符串集，它们代表素数；C语言中的保留字也是一个字符串集，它们不能被看做是C语言的标识符。Pascal语言和素数语言是无限集， 而Ｃ语言中的保留字则是一个有限集。在上述情况中， 字母表均以A SCI字符集加以表示。
若用这种方式谈论语言，那么字符串就失去了本身的意义，我们只是试图将每个字符串都归类到语言中。
为了用有限的描述来详细说明这些(很可能是无限的)语言，这里将使用称为正则表达式的符号表示法。
每个正则表达式代表一个字符串集。
基本概念
符号：对于语言字母表中的每个符号a，正则表达式a表示仅包含字符串a的语言。
或：对于给定的两个正则表达式M和N，用操作符或竖线 (|) 连接为一个新的正则表达式：M丨N。
若一个字符串属于语言Ｍ或语言N、那么此串也属于语言 M丨N。
因此， 语言 a|b 包含两个字符串a和b。
并：对于给定的两个正则表达式M和N，可以利用并操作符(·)将其连接为新的正则表达式M·N，设α是语言Ｍ的字符串，β是语言N的字符串，若一个字符串是α与β的并，那么这个字符串属于语言M·N：因此，正则表达式 (a|b)·a 定义包含两个字符串aa和ba的语言。
ε(epsilon)：正则表达式：代表了一个只包含空串的语言。因此 (a·b)|ε 表示语言{““，”ab”}。
重复：对于正则表达式M，其Kleene闭包是 M*。若一个字符串为空或者它是M中所有字符串经过并操作所得到的结果，那么它就属于 M*。
因此， ((a|b)·a)* 代表无限集 {““， “a a”， “ba”，”aaaa”， “baaa”，”aaba”， “baba”，”aaaaaa”，…}。
通过使用这些符号， 以及或、并、8和Kleene闭包， 就能够规定和编程语言的词法记号相对应的ASCII字符集。
例子
考虑下面的例子：
使用这种语言，就可以详述编程语言的词法记号(参见图2.2)。
如图2.2中第5行所示，词法分析器能够识别出注释和空白符、但并没有提交给词法分析器。
而是删除了这些空白，同时词法分析器重新开始分析。这里的注释以两个破折号开始，仅包含了一些字母字符，最后以回车结束。
最后，词法分析详述就完成了，但这一过程中常带有一些初始输人的字符串，可以通过匹配单一字符来实现这一过程。
这时，打印“illegal character”错误信息并继续执行。
这些规则有一点含糊不清。
例如，if8应看做是一个单独的标识符呢，还是两个记号if和8?
字符串if 89的起始部分是一个标识符呢， 还是一个保留字?
下面是两条在Lex、JavaCC、Sa-ble CC以及类似的词法分析生成器中常使用的重要规则：
重要规则
最长匹配：选择可以匹配正则表达式的、最长的初始输入字符串作为下一个记号。
优先规则：对于特定的初始子串，最先与之匹配的正则表达式决定了这个子串的记号类型。也就是说，正则表达式规则的书写顺序是很关键的。
因此，依据最长匹配规则，if8匹配为一个标识符。
而根据优先规则，if 匹配为一个保留字。
有限自动机
正则表达式对于确定词法记号是很方便的，但是常常需要一个计算机程序能够实现的形式化方法。
因此，需要引入有限自动机。有限自动机包含一个有限的状态集，状态由箭头连接，称为边；从一个状态指向另一个状态，每个边都有一个标记。
其中包含一个初始状态和若干个终结状态
图2.3给出了一些有限自动机的例子。在讨论中可以很方便地计算这些状态。每例中的状态1都是起始状态：一个标有很多字符的边是一些平行边的缩写形式，所以在ID机中，有26个边从状态1指向状态2，每个边都带有不同字母的标记。
DFA
在确定的有限自动机(DFA) 中， 不存在两个从同一状态出发且标记完全相同的边。
DFA接收或拒绝一个字符串的工作过程如下：从初始状态出发，对于每个输入字符串中的字符，自动机都沿着相应的边到达另一状态。边上必须标有输入字符。对于有n个字符的字符串，若在n次状态转换后，自动机到达了终结状态，那么自动机就接收了字符串。若未到达终结状态，或者找不到与输入字符相匹配的边，那么自动机就拒绝接收这个字符串。自动机所识别符号串的全体称为自动机所识别的语言。
例如、ID自动机所识别的语言中的任何字符串都必须以字母开头，任何转换到状态2的单个字符，会被接收为单个字符的字符串。若从状态2出发，又经若干数字或字母重新回到状态2，那么第一个字母与其后的这些字符也同样被接收。
事实上，图2.3所示的自动机接收与图2.2列出的正则表达式类似的语言。
图2.3中是6个独立的自动机，那么，它们是如何组合为一个自动机来进行词法分析的呢?
在下一章中将会详细地讨论这种方法，但是在这里，先做一下简单的介绍：如图2.4所示，每个终结状态都要标明有限自动机所接收的记号类型。
在该自动机中，状态2既有IF自动机状态2的特征，又有ID自动机状态2的特征。因为对于ID自动机，状态2是终结状态。IF自动机中状态3的情况和ID状态机中状态2的情况一样，依据优先原则，它们都是终结状态一将状态3标为IF，是因为希望这一记号被识别为保留字，而不是标识符。
还可以将自动机表示为一个转换矩阵：一个二维数组(一个向量)，下标表示状态号和输入字符。
另有一个停滞状态(状态0)，其任何输人字符都指回自身状态，用该状态来代替不存在的边。
ps: 其实确切的说是状态机可以和图进行转换，同理，图可以和矩阵进行替换。
还要有一个状态数组，作用是将状态号与作用一一对应。
识别最长的匹配
如图2.5所示，从中可以很容易判别自动机是否会接收某字符串，但是词法分析器的工作是找到原始的合法子字符串的最长匹配。
在解释转换过程中，词法分析器要一直追踪最长匹配的路径和匹配的位置。
追踪最长匹配路径就是用两个变量保存自动机上一次的结束状态：Last-Final(最近使用过的结束状态号) 和Input-Position-at-Last-Final。
每次到达终结状态时，词法分析器都要更新这些变量；当到达停滞状态时(无出口的状态)，这些变量会记录相匹配的记号和它结束的位置。
图2.5为词法分析器识别最长匹配的操作过程。
注意，当前输入位置可能和识别器最近到达的终结状态相距很远。
非确定有限自动机（NFA）
非确定有限自动机(NFA) 存F在多条从一个状态出发并且标记相同符号的边。
也可能存在标有e的边，即在不接收输人字符时可进行状态转换。
下面是一个NFA的例子：
对于初始状态，当输人a时，自动机可以向左或向右转换。若选择了向左转换，那么该字符串的长度为3的倍数时才能被接收，若选择了向右转换，那么只有偶数长度的字符串才能被接收因此、该NFA所能识别的语言是关于a的、长度为2的倍数或3的倍数的字符串集。
从初始状态开始时，自动机必须选择一个转换方向。若存在可以接收的字符串的选择路径.那么自动机就应该接收该字符串。因此，自动机必须进行某种“猜测”并且其结果不能够产生错误
当不接收输入字符时， 可能用到 e 边。
下面是另一个接收同样语言的NFA；
同样地，自动机必须选择要执行哪一个e边。
若一个状态既有e边，又有一些标有符号的边时，自动机可以选择接收一个输入符号(并选择标有相对应符号的边)，或者不接收符号而选择一个 e 边
正规文法转换为NFA
NFA是一个很有用的概念， 因为它很容易将一个(静态的、说明性的) 正则表达式转换成一个(仿真的、拟执行的) NFA。
这种转换算法可以将任何一个正则表达式转换为含有一个尾(初始状态)和一个头(终结状态) 的NFA。
例如，将单个字符的正则表达式a转换为NFA。
---a--->O
对于正则表达式ab(将a、b用并操作连接起来)，它对应的NFA也是由两个NFA连接起来的，即将a的头与b的尾连接起来。
最终得到的自动机包含一个用a标记的尾和一个用b边指向的头。
---a--->O---b-->O
通常情况下， 任何一个正则表达式M都会对应一些有头和尾的NFA：
M O
可以用归纳法来定义正则表达式到NFA的转换。
表达式可能是原语(单个符号或e) 或者由更小的表达式组成。
类似地， NFA也可以由基本元素或更小的NFA组成。
图2.6显示了正则表达式向NFA转换的规则。其中说明了图2.2中一些表达式的算法——记号IF、ID、NUM和错误。每个表达式都被转换为NFA，每个NFA的“头”状态都给出了不同
记号类型的标记， 所有表达式的尾都合并为一个新的初始节点。
图2.7显示了将一些等价的NFA状态合并后的结果。
NFA转换为DFA
如2.3节所述，用计算机程序实现DFA是很容易的。
但实现NFA就不那么容易了，因为大多数计算机都没有足够好的硬件可以进行“猜测”。
为了避免猜测路径，可以同时尝试每一条可能的路径。
下面用字符串in来试验一下图2.7中的NFA。从状态1开始，现在，不是去猜測执行哪条e路径，而是在这一个状态点上， NFA可能选择它们中的任何一条，可能是状态集(1，4，9，14)中的一个，因此需要计算(1)的g闭包。很明显，若不接收输人字符，就没有其他可到达的状态了。
现在，接收一个字符I。从状态1开始可以到达状态2，从状态4到达状态5，状态9则无相应转换，从状态14可以到达状态15。
于是得到状态集(2，5，15)。
另外e-closure(5) =(5，6，8) 、所以NFA必定在状态集(2， 5， 6， 8， 15) 中。
再接收字符n，从状态6到状态7，状态2、状态5、状态8以及状态15则无相应转换。
所以得到状态集(7)；e-closure(7) =(6， 7， 8) 。
现在字符串 in 已输人完， NFA是否到达了终结状态呢?
状态集中只有8是终结状态。
因此 in 是一个 ID 记号
下面给出e-closure的定义设edge(s， c) 表示从状态s出发， 沿着单边c可以到达的所有NFA状态的集合。对于状态S，closure(S) 表示从S出发，不经任何输人字符即可到达的状态集，也就是只通过 e 边：在数学上， closure(S) 是最小的， 可以把经e边的变换表述为T：
计算该集合的代价非常高，需要对源程序中进行词法分析的每个字符加以计算，这几乎是不可能的。但是预先计算这些状态是可行的。 将NFA转换为DFA时， 每个NFA的状态集都对应着DFA的一个状态。由于NFA包含有限的n个状态， 所以DFA也应为有限个状态(最多为2^n个) 。
一旦有了closure和DFAedge算法， 就容易构造DFA。DFA的初始状态d就是closure(si) ，这与NFA中的算法一样。
TODO: 这里的 DFA edge 算法后面单开一篇，此处暂时省略。
这一算法不包括DFA中不可达的状态：这一点很重要，因为原则上DFA有2^n个状态， 但实际上从初始状态出发，常常只能得到它们中的n个。这对于避免DFA解释器转换表的指数级膨胀是很重要的，而这个表就是编译器的一部分。
若状态d中包含NFA的终结状态，那么状态d在DFA中也是终结状态。仅仅找到终结状态是不行的，还需要找到它所识别的记号。
或许状态d中包含了多个NFA的终结状态在这种情况下，可以用组成词法规则的正则表达式中的、最先出现的记号类型来表示状态d.这就遵循了优先规则
DFA构造完以后，状态数组可能被丢弃，而转换数组则用于词法分析。
转换前的NFA参见图2.7，用构造算法转换后的DFA参见图2.8
这个自动机也不是最优的。也就是说，它不是识别同样语言的最小自动机。通常情况下，若从状态si出发可接收的字符串是c，当且仅当从状态s2出发可接收的字符串是w，那么状态s和sz是等价的。很容易看出，图2.8中，状态5，6，8，15 与状态 6，7，8 等价，状态 10.11，13，15 与状态 11，12，13等价。
若自动机存在两个等价状态st和sz，那么就把所有指向s的边都指向sy，然后删除s2。
那么，如何寻找等价状态呢?
当然，若s1和s2同是终结状态或同是非终结状态，且对于任一字符c，trans[s1，c]=trans[s2，c]， 那么很容易看出s1和s2等价， 10， 11， 13， 15和11， 12.13就满足这一规则。
但这一规则也不是万能的，考虑下面的例子：
这里状态2和状态4是等价的 但是 trans[2，a] ！= trans[4， a] 。
在构造完DFA之后，使用简化算法来化简DFA是很有必要的，参见习题2.6。
词法分析生成器
构造DFA是计算机很容易实现的一种机械性的工作，这对于实现自动将正则表达式翻译为DFA的词法分析生成器是很有意义的。
JavaCC和SableCC生成用于Java编写的词法分析器和语法分析器。词法分析器是通过词法归约生成的在下一章中将会看到、语法分析器是通过文法生成的。
对于JavaCC和SableCC，词法归约和文法都包含在同一文件中：2.5.1JAVACC图2.2中所描述的记号在JavaCC中都被明确化了，参见程序2.9。
JavaCC归约开始于一项可选列表，其后是位于PARSER_BEGIN(name) 和PARSER_END(name) 间的一个Java编译单元，分析器的名字(My Parser) 必须位于PARSER_BEGIN和PARSER_END之后。其中的编译单元必须包含一个与生成的分析器名字相同的类声明。
程序2.9 图2.2中记号的JavaCC归约
接下来是一个文法产生式的列表，包含以下几种类型：定义了一个记号的正则表达式生成式：
能够用于产生词法分析器的记号管理声明；用于定义生成分析器文法的两种其他类型。
词法归约使用的正则表达式产生式共有4种：记号(TOKEN) 、空指令(SKIP) 、其他类和特殊记号本书中只需要记号和空指令来实现编译器。
匹配后的字符串应转换为分析器识别的记号，记号类型就是用来制定这些匹配字符串的。
空指令类型是用来指定那些应删除的、匹配了的字符串在程序2.9中， ID， NUM和REAL的说明中都用到了简写的DIGIT。
以#开头的DIGIT定义说明了DIGIT只能用于其他记号的定义中
程序2.9的最后一部分是以void Start开头的。这里， 它代表一个产生式并可以以任何顺序识别4个定义了的记号。
下一章中会详细解释产生式。
SableCC
图2.2描述的记号已经在SableCC中明确给出了，参见程序2.10.一个SableCC归约文件包含6段(所有选择)：
1.包声明：明确SableCC生成的、所有类的包。
2.Helper声明：缩写词表。
3.状态声明：支持状态特征，例如GNU FLEX； 当分析器处于某一状态中时， 只有与此状态相关的记号才能被识别。状态可以有多种用途，包括检查状态的开始行，识别仅在开始行出现的记号。但本书中描述的编译器，不需要状态声明。
4.Token声明：每个记号用于表示那些应被转换为分析器所识别的记号的匹配字符串。
5.无关记号：用于表示应被忽略的匹配字符串。
6.产生式：用于定义分析程序产生的语言。
程序 2.10 图 2.2 中记号的 SablaCC 描述
进一步阅读
Lex是第一个基于正则表达式的词法分析生成器[Lesk 1975] ， 现在它仍被广泛使用。
通过保存一个状态队列或状态栈， e-closure可以更高效地被计算出来， 这些状态中的边都没有被-转换检查[Aho等人， 1986] 。正则表达式可以直接转换为DFA， 而无需经过NFA[Mc-Naughton和Yamada， 1960； Aho等人， 1986] 。
DFA转换表可能很大， 而且很稀疏。若用一个二维矩阵(状态×符号) 来表示这张表， 那么就浪费了太多的内存。实际上，表是经过压缩的。虽然这样降低了内存需求，但却延长了寻找下一-状态的时耗[Aho等人， 1986] 。
对于词法分析器，无论是自动产生还是手工书写，都必须有效地对输人进行管理。当然，输人首先被放人缓存，所以可以一次性获取成批的字符，然后分析器每次从缓冲区中取一个字符。分析器每次取字符时，都必须检查缓冲区是否已空。通过在缓冲区设置结束标记(一个不属于任何记号类型的字符)，这样，分析器就可以对每个记号检查一次，而不是对每个字符检查一次(Aho等人， 1986] 。Gray[1988] 使用了一种方案， 只需每行检查一次， 而不是每个记号检查一次、但是这不能解决包含行结束字符的记号问题。在Bum bulis和Cowan[1993] 的方案中， 只需每个DFA周期检查一次； 尤其在DFA中包含很长路径时， 将会大大减少检查次数。
自动生成的词法分析器常由于速度慢而遭到批评。原则上，有限自动机的操作是很简单的也应该是高效的， 但是在转换对表的解释时将会导致延时。
Gray[1988] 指出， 将DFA直接转换为可执行代码(实现说明的状态) 可以和手工代码分析的速度一样快。
例如， Flex“快速词法分析生成器”[Paxson， 1995] 其速度明显快于Lex。
个人收获
实际上本节核心内容在于 DFA/NFA，但是讲的理论过于晦涩。
实际上直接写一个简易版的 Regex 可能更能加深我们的理解。
拓展阅读
其他
输入==》输人
这里应该是 OCR 对应的模型不怎么滴。
参考资料
《现代编译原理 java》
