词法分析，是词法分析器将源程序转化为线性记号流的过程。该过程中会对各种符号进行分类，比如将变量名换为标识符。
词法分析的含义：
- 规定词形成的规则，定义什么词是合法的；
- 根据规则识别输入的序列（词法分析），识别合法单词、指出非法的输入序列。
词法分析
模式、记号、单词
- 模式（Pattern）： 产生和识别元素的规则。也就是定义的词法规则；
- 记号（Token）： 按照某个模式（即，规则）识别出的（一组）元素。进行词法分析时，词法分析器将程序代码中的各个部分转为一个个记号的过程，就是根据规则得到一个记号流的过程；
- 单词（lexeme）： 被识别出的元素自身的值（一个），也称为词值。可以理解为源程序中一个个的字符串。
上面三个词放一起理解：源程序里面是一个个单词，我们使用“模式”这个规则，对单词进行识别、分类，把它们放到相应的记号里面去。记号是一堆单词，Pascal 语言的记号举例如下：
| 记号的类别 | 单词举例 | 模式的非形式化描述 |
|---|---|---|
| const（01） | const | const |
| if（03） | if | if |
| relation（81） | <, <=, =, <>, >, >= | <, <=, =, ... |
| id（82） | pi, count, D2 | 字母打头的字母数字串 |
| num（83） | 3.1416, 0, 6.02E23 | 任何数值常数 |
| literal（84） | "core dumped" | 双引号间的任意字符串 |
| comment | { x is an integer } | 花括号间的任意字符串 |
- id: 标识符记号。这里“字母”需要进行严格的形式化描述；
- literal：字面量；
- comment：注释
单词的基本分类
- 关键字 kw（keyword， reserved word）
- 标识符 id （identifier）
- 字面量 literal
- 特殊符号 ks （key symbol， special symbol）
例：
记号
记号 = 记号的类别 + 记号的属性
例如，mycount > 25，由三个记号组成。类别就是上表中对应的类别编号
词法分析器的作用与工作方式
编译器中只有该部分直接接触源代码，其他的部分都是通过使用之前的工作成果来间接接触源代码。词法分析器要进行的工作包括：
- 去掉注释、空格一类的无用部分；
- 处理和平台有关的输入，比如文件结束符的不同表示；
- 根据模式识别记号，交给语法分析器；（主要功能）
- 调用符号表管理器/出错处理器，进行相关处理。
工作方式：
- 词法分析器单独进行扫描，生成记号流。再将整个记号流交给语法分析器；
- 词法分析器作为语法分析器的子程序进行工作，语法分析器调用词法分析器去读源程序，得到词法分析器返回的记号就拿来构造语法树。然后用掉了这个记号就再去调用词法分析器读新的记号，如此重复；
- 词法、语法分析器并行工作。两者有一个共享的记号流，前者不停读程序、把记号放入记号流，后者不停取记号流来构造语法树。
模式的形式化描述
字符串与语言
从词法分析角度来看，语言是记号的集合。
语言 L 是有限字母表 Σ 上有限长度字符串的集合，字母表是字符的集合。
字母表中的字符能够组成字符串。
例：字母表 Σ={ a, b, c }，则其上的语言 L = { ε, a, b, c, aa, ab, ac, ba, bb, bc, ... } （ε为空串，长度为0）
字符串的基本概念
| 术语 | 示例 |
|---|---|
| |S| | |abc| = 3 |
| ε | |ε| = 0 |
| S1S2 | abc def = abcdef |
| Sn | (abc)3 = abcabcabc |
| S 的前缀 X | abc 的前缀有：ε, a, ab, abc |
| S 的后缀 X | abc 的后缀有：ε, c, bc, abc |
| S 的子串 X | abc 的子串有：ε, a, b, c, ... |
| S 的真前缀 | abc 的真前缀有：a, ab（去掉空和全） |
| S 的真后缀 | （去掉空和全） |
| S 的真子串 | （去掉空和全） |
| S 的子序列 X | abdf 是 abcdef 的一个子序列（和原序列顺序相同，可去掉一些字母） |
| 术语 | 意义 |
|---|---|
| Φ | 空集合 |
| { ε } | 空串是唯一元素 |
| X = L ∪ M | 并： X = { s| s∈L or S ∈M } |
| X = L ∩ M | 交：X = { s | s∈L and S ∈M } |
| X = LM | 连接： X = { st|s∈L and t ∈ M } |
| X = L* | (星)闭包：X= L0∪L1∪L2∪... |
| X = L+ | 正闭包：X= L1∪L2∪L3∪... |
若 L = {a, b}, M = {c, d}, 则 LM = {ac, bc, ad, bd}, L∪M = Φ
L* = { ε, a, b, aa, bb, ab, ba, aaa, ... }
L+ = { a, b, aa, bb, ab, ba, aaa, ... }
正规式与正规集
正规式是用来描述词法规则的，也就是描述：记号该长成什么样子、数字该长成什么样子之类。
正规式（Regular Expression，也叫正则表达式）是在字母表之上的集合——正规式表示集合。
正规式表示的集合叫做正规集，而正规集是语言，因此正规式表示语言。
比如有个正规式是字母 a，那么正规式 a 表示集合 {a}，集合 {a} 就是语言 L(a)。
正规式表示正规集，正规集是与正规式对应的语言。
这两个概念是词法分析的基础。
正规式和正规集的递归定义
Σ 是有限字母表，则其上的正规式及其表示的集合（即正规集）递归定义如下：
- ε 是正规式，其表示集合（正规集） L(ε) = {ε}
- 若 a 是 Σ 上的字符，则 a 是正规式，它表示集合 L(a)={a}
-
若正规式 r 和 s 分别表示集合 L(r) 和 L(s)，则
- r|s 是正规式，表示集合 L(r) ∪ L(s)（“|”在正规式中表示“或”，也可以写作 r + s ）
- rs 是正规式，表示集合 L(r)L(s)（直接将两个语言拼接起来，也可以写作 r·s）
- r （正规式是一个星闭包）也是正规式，表示集合(L(r))（L(r)这个语言进行星闭包）
- (r) 是正规式，表示的集合仍然是 L(r)（也就是说正规式 r 外面括上括号得到的 (r) 仍然是正规式，加括号可以用来改变运算次序）
语言是字母表上字符串的集合，而正规式是语言，因此正规式是字母表上字符串的集合。
可以用正规式描述的语言，就是正规语言或正规集
定义的扩展说明
-
运算有优先级和结合性
- 三种运算都有左结合的性质（左结合的意思是，当多个同优先级符号连写时是从左往右算。如果从右往左算就叫右结合）
- 优先级从高到低：闭包、连接、或
正规式中不必要的括号（去掉了也不影响运算顺序）是可以省略的。
例：正规式： a|b*c 表示的语言有以下两种情况：
- 表示一个串：a
- 表示另一个串：以 0 到多个 b 开头，以 c 结尾
- 正规式的等价
长得不同的正规式可以表示同一个正规集（就像加法中的1+3、2+2都可以表示4一样），即，同一个正规集可以对应多个正规式。
正规式等价
定义：若正规式 P、Q 表示了同一个正规集，则称 P、Q 是等价的，记为 P = Q。
【例】： 设字母表 Σ={a, b, c}， 则 Σ 上有：
| 正规式 | 正规集 |
|---|---|
| a, b, c | {a}, {b}, {c} |
| a|b, b|a | {a}∪{b} = {a, b} |
| a(a|b)* | {a, aa, ab, aba, abb, aab, ...}，以 a 为首的 ab 串 |
| Σ* | {ε, a, b, c, aa, ab, ac, ba, bb, bc, ...} |
【例】：令 L(x) = {a, b}, L(y) = {c, d}
则 L(x|y) = {a, b, c, d}
L(y, x) = {a, b, c, d}
判断等价性，可以根据定义，证明两个正规式是否能表达同一个集合；也可以使用正规式的代数性质进行运算比较：
| 公理 | 公理 |
|---|---|
| r|s = s|r | ( r s ) t = r( s t ) |
| r|( s|t ) = ( r|s )|t | ε r = r ， r ε = r |
| r ( s|t ) = r s | r t | r* = ( r+ | ε ) |
| ( s|t ) r = s r | t r | r** = r* |
简言之，就是：
- |可交换、可结合；
- · 对 | 可分配；
- · 可结合；
- 幂等
记号的说明
先复读一遍模式、记号的概念：
- 模式（Pattern）： 产生和识别元素的规则，就是定义的词法规则；
- 记号（Token）： 按照某个模式（或规则）识别出的元素（一组）。进行词法分析时，将程序转为一个个的记号，就是根据规则得到一个记号流；
正规式可以用于严格地规定记号的模式。用正规式说明记号的公式：
记号=正规式 读作“记号定义为正规式” / “记号是正规式”。不引起混淆的情况下，可以直接把说明记号的公式叫做正规式/规则
e.g. id = a ( a | b )* 读作：“id定义为a(a|b)*”（这里的 id 就是一个标识符了。定义为a开头的ab串）
【例】记号 relation、id、num 分别是 Pascal 的关系运算符、标识符和无符号数，它们的正规式表示如下：
relation = < | <= | <> | > | >= | =
id = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)
(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|0|1|2|3|4|5|6|7|8|9)*
num = (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
(ε|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)
(ε|E(+|-|ε)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)其中，一些东西可以进行简化描述
简化描述
- 正闭包：r 表示 L(r) 的正规式，那么 r+ 就表示 (L(r))+的正规式。
即：r+ = rr = r*r, r = r+|ε
比如：(0|1...|9)(0|1...|9)* 可以化简为 (0|1...|9)+
- 可缺省：r? 表示 L(r)∪{ε} 的正规式。
即：r? = r|ε
比如： E(+|-|ε) 可改写为：E(+|-)?
上面这些运算中的 +、? 、* 的结合性、优先级相同。
-
字符组。字符组是正规式的一种形式：对于只由 | 构成的正规表达式 r，可以改写为[r']：
- r' 可以枚举：正规式 r = a|b|c 等价于 [abc]
- r' 可以分段：[0123456789abcdefghijklmnopqrstuvwxyz]等价于[0-9a-z]
- 非字符组。这里的“非”指的是非运算。也就是去掉某部分：
若 [r] 是字符组形式的正规式，则 [^r] 表示 Σ -L(r) 的正规式，例如：
若 Σ={a, b, c, d, e, f, g}，则 L(^abc)={d, e, f, g}
- 辅助定义。就是给已有的正规式起个名字，以后可以直接用这个名字指代。
（如果 digits 不加花括号，那 digits 就是“ digittttt.... ”）
optional_fraction：可选的小数位。小数点如果不加双引号，在这里表示任意一个字符。
optional_exponent：可选指数
上面的是 id，下面的是 num
