概念

lexical analyise

词法单元=词法单元名+可选属性值词素：与某个词法单元的模式匹配，并被词法分析器识别为该词法单元的一个实例。

词法单元的分类

关键字：一个关键字一个词法单元（常见）e.g. < if > < KEY_WORD, while >运算符：每个运算符是一个词法单元或和上面一样分成一类。标识符：表示所有的标识符，分成一类。常量：表示一个或多个常量的词法单元，比如数字和字符串，< const, 100 > < const, “abcde” >标点符号: 每个标点符一个词法单元 < , > <; >

词法错误分析

如果一个单词和任何一个模式都不匹配，进行错误恢复。

错误的模式：

恐慌模式：一直删，直到遇到一个合理的词法单元。删除下一个字符插入一个遗漏的字符

词法单元的说明

正规式

正则表达式

可以使用的字符叫做符号(symbols)对于模式$r$的语言集合称作$L(r)$符号的集合称作字符表，写作$\sum$

e.g. $L(a) = \{a\}$

e.g. $L(\xi) = \{ \xi \}$

正规式操作

选择：|连接：”并列写”, e.g. ab重复（闭包）：*

选择操作

r|s，整体匹配$r$能够匹配的串或$s$能够匹配的串。

$L(a|b) = L(a) \lor L(b)$

连接操作

rs，匹配$r$紧接着$s$能够匹配的串

$L((a|b)c) = L(ac) \lor L(bc)$

重复操作

r*，匹配r模式的任意次。

$L(a*) = \xi \lor L(a) \lor L(aa) \lor L(aaa) …$

$L((ab)*) = \xi \lor L(ab) \lor L(abab) …$

$L((a|b)*) = \xi \lor L(a) \lor L(b) \lor L(ab) \lor L(aabbbaaa)…$

优先级

重复 > 连接 > 选择

* > connect > |

元符号

表达元符号使用转义字符 \\

特殊的操作

+ 表示1次多次r? 出现1次或不出现[0-9]、[a-z]、[A-Z]、[a-zA-Z]表示一类字符

二义性

Ambiguity

关键字和表示符的冲突，关键字的识别在前，然后是表示符运算符匹配采用最长子串优先

向前看

向前看一个符号多个字符向前看（不常见）

e.g.

12DO99I=1,10DO99I=1.10

先前看多个字符，看到,和.才知道是循环还是赋值。

词法单元识别

状态转换图

Transition diagram

状态转换图：描述状态之间的转换关系。

开始状态，接收状态（双线圆圈）

基于状态转换图的词法分析器

分支语句实现（纯模拟，略）表驱动实现

表驱动实现

使用状态转换表表示

状态模式是否是接受状态advanced 是否保留 优势：实现不冗余劣势：表可能很大

有限自动机

Finite Antomata: 描述算法的执行流程。

e.g. 上面的状态转换图

非确定的有限自动机（NFA）确定的有限自动机（DFA）

非确定有限自动机

NFA

有字母表，状态集合，状态装欢

$S \times (\sum U \{ \xi \} \to \rho(S))$