# 词法分析

## 正则表达式

1. 程序以字符串的形式传递给编译器，词法分析将输入字符串识别为*有意义的字串*(词法单元token)，判断字串的种类(name)、可帮助解释和理解该字串的属性(attribute)、可描述具有相同特征的字串的模式(pattern)

2. 词法单元token由一个记号名和一个可选的属性值(可为空)组成，属性记录词法单元的附加属性

3. 词素lexeme，记号名(关键字、标识符、常量、运算符、分界符)，模式

4. 正整数的正则表达式

```re
digit -> 0|1|2|3|4|5|6|7|8|9
digits -> digit digit*
```

5. 有限自动机Finite Automata

```mermaid
graph LR
 开始状态--digit-->接受状态--digit-->接受状态-- other-->识别出一个数
```

6. 小数的正则表达式

```re
digit -> 0|1|2|3|4|5|6|7|8|9
整数部分digits -> digit digit*
小数部分digits -> digit digit*
带小数的数字串number -> digit digit* . digit digit*
```

```re
digit -> [0-9]
整数部分 digits -> digit+
小数部分 digits -> digit+
带小数的数字串 number -> digit+ . digit+
```

```mermaid
graph LR
开始状态--digit-->B[中间状态]--digit-->B[中间状态]--.-->中间状态--digit-->接受状态--digit-->接受状态-- other-->识别出一个数
```

7. 串和语言
   - 术语
     - 字母表，符号的有限集合
     - 串，符号的又穷序列
     - 语言，字母表上的一个串集
     - 句子，属于语言的串
   - 运算
     - 连接(积)
     - 指数(指数)
   - 语言的运算，幂>连接>并
     - 并，$L\cup M=\{s|s\in L或s\in M\}$
     - 连接，$LM=\{st|s\in L且t\in M\}$
     - 幂，$L^0=\{\varepsilon\}$，$L^i=L^{i-1}L$
     - 闭包，$L^*=L^0\cup L^1\cup L^2\cup\cdots$
     - 正闭包，$L^+=L^1\cup L^2\cup L^3\cup\cdots$

8. 正则表达式，闭包>连接>选择

9. 正则表达式可用来表示简单的语言

10. 正则定义，自底向上

```re
letter_ -> A|B|C|...|Z|a|b|c|...|z|_
digit -> 0|1|2|3|4|5|6|7|8|9
id -> letter_ (letter_|digit)*
```

```re
digit -> [0-9]
digits -> digit+
optional_fraction -> (. digits) | ε
optional_exponent -> (E (+|-|ε) digits) | ε
numbers -> digits optional_fraction optional_exponent
```

```re
numbers -> digit+ (. digit+)? (E [+-]? digit+)?
```

```re
while -> while
do -> do
relop -> <|<=|=|<>|>|>=
letter_ -> [A-Za-z_]
id -> letter_ (letter_|digit)*
number -> digit+ (. digit+)? (E [+-]? digit+)?
delim -> blank | tab | newline
ws -> delim+
```

## 有限自动机

1. 转换图

```re
relop -> <|<=|=|<>|>|>=
```

```mermaid
graph LR
0-- < -->1 -- = -->LE
1-- > -->NE
1-- other -->*LT
0-- = -->EQ
0-- > -->6-- = -->GE
6-- other -->*GT
```

2. 最长匹配原则，如果$x_1\ldots x_i\in L(R)$且$x_1\ldots x_k\in L(R)$又$i<k$则取后者

3. 优先匹配原则，如果$x_1\ldots x_i\in L(R_j)$且$x_1\ldots x_i\in L(R_k)$又$j<k$则选$R_j$

4. 词法分析器对源程序采用非常局部的观点，紧急方式的错误恢复，错误修补

5. **不确定的**有限自动机NFA, Non-deterministic Finite Automation
   - 包括
     - 有限的状态集合$S$
     - 输入符号集合$\Sigma$
     - **转换函数**${\rm move}:S\times(\Sigma\cup\{\varepsilon\})\to P(S)$
     - 唯一的开始状态$s_0$
     - 接受状态集合$F\subseteq S$
   - 此处的不确定性体现在*相同输入可能有不同的状态转移，且输入$\varepsilon$也可能发生状态转移，因此需要试错*

```re
(a|b)*ab
```

```mermaid
graph LR
0--a-->0--b-->0--a-->1--b-->2

```

6. **确定的**有限自动机DFA, Deterministic Finite Automation
   - 包括
     - 有限的状态集合$S$
     - 输入符号集合$\Sigma$
     - **转换函数**${\rm move}:S\times\Sigma\to S$, 且可以是部分函数
     - 唯一的开始状态$s_0$
     - 接受状态集合$F\subseteq S$

```re
(a|b)*ab
```

```mermaid
graph LR
0--a-->1--b-->2--b-->0--b-->0
2--a-->1--a-->1
```

7. NFA和DFA都可以识别正则语言，但DFA更快，NFA更简洁

## 分析器自动生成

1. 三步：正则表达式->NFA->DFA->化简DFA

2. 语法制导的NFA构造算法，以下构造的NFA均仅一个接受状态，没有向外的转换
   - 步骤：
     1. 构造识别$\varepsilon$和字母表中一个符号$a$的NFA
     2. 构造识别主算符为选择的正则表达式的NFA
     3. 构造识别主算符为连接的正则表达式的NFA
     4. 构造识别主算符为闭包的正则表达式的NFA
   - 如此构造得到的NFA有如下性质
     - 状态最多为算符和符号的数量的两倍
     - 每个状态都有一条$\Sigma$中符号的转换或是最多两个$\varepsilon$的转换

3. 子集构造法
   - DFA的一个状态是NFA的一个状态集合
   - 读入输入$a_1a_2\cdots a_n$后，NFA可以到达$s_1,s_2,\ldots,s_k$，而DFA可以到达$\{s_1,s_2,\ldots,s_k\}$
   - 引入$\varepsilon$**-闭包**：状态$s$的$\varepsilon$-闭包是$s$经过$\varepsilon$转换所能到达的状态集合
   - NFA的初始状态的$\varepsilon$-闭包对应DFA的初始状态
   - 针对每个DFA状态-NFA状态子集$A$，求输入每个$a_i$后能到达的NFA的$\varepsilon$-闭包并集$\varepsilon-{\rm closure}({\rm move}(A,a_i))$，这对应DFA中的一个状态
   - 包含NFA接受状态的DFA状态就是DFA接受状态

4. DFA的化简
   - 状态的可区分与不可区分：两个状态读入相同的输入到达相同的状态，则这两个状态不可区分，但如果两个状态读入相同的输入到达不同的状态，则这两个状态可区分
   - 先按是否接受状态来区分，如果非接受状态可区分，则继续分解

5. 如何判定两个正则表达式等价？可考虑生成最简DFA来比较