词法分析

读入源程序的输入字段，组成词素，生成并输入一个词法单元序列。每个词法单元对应一个词素

常见的做法：

由语法分析器调用，需要的时候不断读取，生成词法单元（而不是一次性全部读取）

概念

词素

源程序中的字符序列，和某些词法单元的模式匹配，词法单元的实例

词法单元

包含单元名和可选的属性值

通过单元名即可确定结构

必须通过属性来传递附加的信息

词法单元的规约

使用正则表达式

**字母表：**一个有限的符号集合，例如二进制、ASCII、Unicode等等

**串：**字母表中的符号组成的一个有限序列

**语言：**给的字母表上一个任意的可数的串的集合

串有关的术语

前缀：删去一个串的最后的连续几个字符得到的串
后缀：删去一个串的前面几个连续字符得到的串
子串：一个串中可以截取出的连续的串
子序列：一个串中可以选取部分字符，将其按原来的顺序拼接后得到的串

串的运算

xy相当于x和y拼接

正则表达式

描述词素的重要表示方法

可由较小的正则表达式递归构建

基本部分：

ε是一个正则表达式，L()=()
如果a是Σ上的一个符号，那么a是正则表达式

知识点

?表示前面的字符出现0次或1次，例如abc?可以是abc或者ab
*表示前面的字符可以出现0次或多次，例如abc*可以是ab，abc或abccc
+表示前面的字符出现1次或多次，例如
{}可以指定前面一个字符出现的次数，例如abc{3}只能匹配abccc，而abc{2,4}则可以匹配abcc，abccc，abcccc
()可以将多个字符括起来，作为一个整体来操作，例如(ab){3}可以匹配ababab
\转义字符，可以转义各种特殊字符
|是或运算，在它前面加个括号可以表示括号左边的内容或右边的内容，例如a(b|c)可以匹配ab或ac，但是ab|c匹配的是ab或c
[]方括号表示此处的内容只能取自方括号中的内容，例如[abc]可以匹配abcaba，babcbc等，但是不能匹配bcd
-减号可以在方括号内部指定数据的范围，例如[A-Za-z]表示从A到Z，a到z的所有字符
方括号中的^{可以匹配所有除方括号内的字符以外的字符，例如[}ABC]可以匹配D，但不能匹配A、B、C
元字符：预先被定义好的字符，大多以反斜杠开头
\d表示数字字符，0到9
\w代表单词字符(数字、英文字符、下划线)（注意是一个字符不是一个完整单词）
\s表示空白字符(空格，tab，换行符)
\b表示单词的开头或结尾
\D表示非数字字符，\W表示非单词字符，\S表示非空白字符
.表示任意字符(不包含换行符)
^{表示某个字符串的开头，例如}abc表示以abc开头的字符串。aabc无法被匹配
$表示某个字符串的结尾，例如abc$ 可以匹配aabc，但是不能匹配abcc

注意点

+会去匹配尽可能多的字符，例如使用<>去匹配<a><b>会匹配的是<a><b>而不是单个的<a>。解决方法：使用+?，将其从贪婪匹配转换为懒惰匹配
匹配一个数字串可以使用\d+，如果要匹配固定取值范围内的数字，需要分类讨论，例如如果想要在0到255之间，那么先是25开头，后面只能是0到5，就是25[0-5]，如果是2开头，那么就是只能是2[0-4]\d，其他情况下就是[01]?\d\d?

例题：

字母表{a,b}上以aa结尾的所有字符串：/[ab]*aa$/
能被四整除的所有二进制数：/(^1[01]*00 $,^0$ )/

词法单元的识别

词法分析器要求能够检查输入字符串，在前缀中找出和某个模式匹配的因素

最重要的思想：有限状态机

状态转换图：状态（圆圈）/边（带箭头）

从0开始，接收到<进入状态1，此时再接收到=就返回relop，LE，如果是>就返回relop，NE，否则返回relop，LT。等于和小于号以此类推

保留字和标识符的识别：识别标识符的状态转换图也会识别保留字

为保留字建立单独的状态转换图，例如关键字if，接收到i的时候进入状态1，，再识别到f就输出if关键字

有穷自动机

本质上等价于状态转换图，区别在于自动机是识别器，对每个输入串回答yes或no（能不能到达接收状态）

不确定的有穷自动机NFA：一个状态一个符号标记离开可能有多条边；并且可以有边的标号是ε（空边）
确定的有穷状态自动机DFA：拿到一个输入，确定输出下一个状态是什么（一个状态离开只有一条边）；并且没有ε边

NFA的组成：

一个有穷的状态集合S
开始状态0
接收状态集合3{3}
转换函数(0,a)=1，即状态0经过a边可以到状态1

转换表：

符号串认为被NFA接受：存在从开始状态到接受状态的路径

L(A):从开始状态到某个接受状态的所有路径上的符号串集合

DFA

一个NFA被称为DFA，如果

没有ε
每个状态s和每个输入符号a，有且只有一条标号为a的边

NFA转换成DFA：子集构造法

DFA每个状态<–>NFA一个状态集

并行的模拟NFA在遇到一个给定输入串时可能执行的所有动作。构造得到的DFA每个状态和NFA的状态子集对应

s表示N中的单个状态，T代表N的一个状态集

操作	描述
ε-closure(s)	能够从NFA的状态s开始只通过ε转换(任意次)到达的NFA状态集合
ε-closure(T)	能够从T中某个NFA状态s开始只通过ε转换到达的NFA状态集合
move(T,a)	能够从T中某个状态s出发通过标号a的转换到达的NFA状态的集合
Dtran[A,a]	ε-closure(move(A,a))，也就是先经过a边到达下一个状态，然后经过任意的ε可以到达的状态的集合

NFA到DFA转换的示例：

先定义一个container，先存放一个{A}

A:=ε-closure(0)={01247}，此时A没有标记，因此计算Move(A,a),算它的结果的闭包B
B=Dtran[A,a]=ε-closure(move(A,a))=…={1234678}，也加入container中，现在有{A,B}。然后计算A的下一个符号C。
C=Dtran[A,b]=…={124567}，加入container，得到{A,B,C}。此时A的状态已经做完了，将A标记，得到结论：Dtrans(A,a)=B;Dtrans(A,b)=C.此时得把container其他未标记的元素拿出来，即B和C。由于Move(B,a)={3,8}，因此ε-closure(3,8)肯定等于B，而B已经存在于container中了，因此无需命名一个新状态。然后再算move(B,b)。
D=Dtran[B,b]=…={1245679}，放入container中，{ABCD}
E=Dtran[D,b]=…

以此类推。直到container中全部元素都已标记。

就可以得到DFA的转换表