文章目录
词法分析
这一章，简而言之就是如何实现词法分析器，完成以下的流程
如何实现？词法单元如下，我们要将字符流提取出词素
以下面这个举例：我们要从下面的字符流中提取出 常量，变量，预保留字，如何扫描一次就能区分？
return ( initial <= 10 ) ? 100 : ( position + initial ** 2 ) ;
为了能够更容易的区分，变量的定义要以下划线或字符开始，只能由字符，数字，下划线组成。这就是为什么我们在写程序的时候，变量要这么定义，目的是为了编译！
下面是解析的举例过程
当forward指向（ 时，什么都不符合了。从Ps 至 (forword - 1)的串, 为一个保留字。保留字优先变量。
我们可以得到一个结论，常量和变量很容易提取出来，保留字的提取就要根据特定的正则表达式了。return符合特定的保留字正则表达式，所以被认为保留字提取了出来。我想之后的也能被提取。
首先明白语法分析的三个概念
词法单元（和类相似）
自定义符号：变量(数据和函数），常量（数值和字符串）
预定义符号：if，for，while，++，+
词素（和实例相似）
词法单元的实例，比如说，123是数值的实例，abc是数据变量的实例
预定义符的实例只有一个
词法单元的模式（类的构成法则）
第一个问题来了，如何判断哪个词素属于哪个词法单元？这是非常重要的问题，123321我们判断为数值，还是变量，还是预定义符？
我们要根据词法单元的模式进行区分，也就是词法单元本身的构成规则来找到匹配的模式，我们用正则表达式来描述这种匹配规则，来描述字符串的集合
正则表达式
正则语言是一门最简单的语言，用它描述目标语言的词法单元及其构成法则，其本质是描述字符串的集合
正则表达式运算方式有：
并运算 例如：L∪M = L | M= {s| s∪L 或者s∪M｝
连接运算 例如：｛st ｜s∈L ，t∈M｝
闭包运算 例如：L*=∪i=0∞Li
下面是要记住的正则表达式例子，将用来进行词法分析
letter_ → [A- Z a - z _ ] 字母和下划线
digit → [0 - 9] 数字0到9
id → letter_ (letter_ | digit)* 自定义变量
digits → digit+ 0到正无穷
number → digits (.digits )?( E [± ]?digits)? 常量
C语言的语法工构成法则为
lexicalRule → reservedWord | id | numberConst|stringConst | note | blankSpace | crlfLexeme
语法构成为：预定义符，变量，数字常量，字符常量，注释，空格，回车
正则表达式的状态图
将字符流切分成词素流，表达了一个词素的获取过程
正则表达式: id → letter_ (letter_ | digit)*
正则表达式: if → if
我们知道了C语言的词法分析可以由一个正则表达式来表示，且正则表达式有唯一的状态图，那我们就可以用一个状态图来描述C语言的词法分析
如果用代码来表示状态图之间的变换？
状态图的数据结构是：
class State( currentState INT， driverChar CHAR，nextState INT， type CHAR（CHECK VALUE IN('0','M','E','I'); category VARCHAR IN ('reserved','id','num','string'); );
0’: 起始状态，‘M’：中间状态，‘E’：匹配状态(不包含exclude），‘I’：匹配状态(包含include)
基于状态转换图的词法分析框架，所有的语言都是类似的
现在问题转化成了如何得出正则表达式的状态转换图？
有穷计算机
将状态转换图形式化，上升为一种理论知识，被称作有穷自动机，分为下面两类
非确定有穷自动机NFA（Nondeterministic Finite Automata）
特点：一个驱动符号（即边上的符号）可以引出多条边，ε可以是边上的符号
下面是 (a|b)*abb正则表达式的NFA
确定性有穷自动机DFA（Deterministic Finite Automata）
特点：有且仅有一条出边。驱动符号不包含ε
下面是 (a|b)*abb正则表达式的DFA
由正则表达式到NFA，再由NFA到DFA，再由DFA到状态图转换程序，这就是上面的答案，并且我们每一步都要完成
正则表示式到NFA
对于单个字符的表达式r = a，构建其NFA
对于表达式r =s | t ，构建其NFA
对于表达式r =s t ，构建其NFA
对于表达式r =s + ，构建其NFA
对于表达式r =s* = ε| s+ ，构建其NFA
对于表达式：r =s？=s | ε
NFA到DFA
对正则表达式的NFA，并不能用于词法分析器的构造。因为NFA中存在不确定
使用穷举办法，把所有可能情况列举出来，把不确定性转变成确定性
例如：
一系列转化过程后，得到转换表，以及最后的结果
值得注意的是，这个得到DFA并不是最简的状态，还能继续简化，可以使用相同的操作，穷举
在构建运算符的NFA时，消去或者减少ε边，就会得到最简的DFA
从正则表达式到DFA，看似不难，却又无从下手。一个由空字符ε驱动的状态迁移，从表面上来看，显得多此一举，毫无意义。但它把问题梳理得直观易懂了，很有说服力了，条理很清晰了。它使得正则表达式到NFA有个一一对应关系，NFA到DFA也有个一一对应关系。这就是数学思维的魅力，艺术的魅力。
DFA到状态图转换程序
留给我们之后具体实现
