编译原理：词法分析与有穷自动机

type

status

date

slug

summary

词法分析器简析

什么是词法分析器？

读入字符流，组成词素，输出词法单元序列

过滤空白、换行、制表符、注释等

将词素添加到符号表中

在逻辑上独立于语法分析，但是通常和语法分析器处于同一趟中

为什么要设立独立的词法分析器？

简化编译器的设计

提高编译器效率

增强编译的可移植性

词法分析的基本概念

1 词法单元（token）

<词法单元名、属性值（可选）>

单元名是表示词法单位种类的抽象符号，语法分析器通过单元名即可确定词法单元序列的结构。

2 模式

描述了一类词法单元的词素可能具有的形式

3 词素

源程序中的字符序列

他和某个词法单元的模式匹配，被词法分析器识别为该词法单元的实例

词法单元的归约(正则表达式)

正则表达式

正则表达式可以高效简洁地描述处理词法单元时用到的模式类型。

字母表Σ上的正则表达式的定义

基本部分

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

归纳步骤

选择：(r)|(s)，L((r)|(s)) = L(r)  L(s)
连接：(r)(s)，L((r)(s)) = L(r)L(s)
闭包：(r)，L((r)) = (L(r))*
括号：(r)，L((r)) = L(r)

运算的优先级：* > 连接 > |，如(a) | ((b)(c)) = a | bc

正则集合 (regular set)：可用一个正则表达式定义的语言

正则表达式的等价

如果L(r) = L(s)，正则表达式r和s等价 (equivalent)

正则表达式的扩展

基本运算符：选择、连接、Kleene闭包

扩展的运算符

一个或多个实例：单目后缀+

r+等价于rr*

零个或一个实例：？

r?等价于ε | r

字符类

[a1a2…an]等价于a1 | a2 | … | an
使用−符号，如：[a−e]等价于a | b | c | d | e

使正则表达式更简洁，但不会使其描述能力增强

正规文法与正规式

1.正规式到正规文法的转换

将文法中的规则写成关于每个非终结符的正规式方程，得到一个方程组；

求解规则：

若A = αA∣β，则解为A = α∗β; 若A = Aα∣β，则解为A = βα∗;

2.正规式到正规文法的转换

ㅤ	文法产生式	正规式
规则1	A—>xB，B—>y	A=xy
规则2	A—>xA，A—>y	A=x*y
规则3	A—>x，A—>y	A=x或y

词法单元的识别（状态转换图）

词法分析器要求能够够检查输入字符

0 状态转换图 (transition diagram)

状态转换图

结点：FA的状态
初始状态（开始状态）：只有一个，由start箭头指向
终止状态（接收状态）：可以有多个，用双圈表示
带标记的有向边：如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a

Finite Automata定义(接收)的语言

给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收
由一个有穷自动机M接收的所有串构成的集合称为是该FA定义（或接收）的语言，记为L(M （machine）)

1 确定有穷自动机DFA

M = ( S，Σ ，δ，s0，F ),

S：有穷状态集

Σ：输入字母表，即输入符号集合。假设ε不是 Σ中的元素

δ：将S×Σ映射到S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态。

s0：开始状态 (或初始状态)，s0∈S

F：接收状态（或终止状态）集合，F⊆ S

例如下图所展示的一个DFA

2 非确定的有穷自动机NFA

M = ( S，Σ ，δ，s0，F )

S：有穷状态集

Σ：输入符号集合，即输入字母表。假设ε 不是Σ中的元素

δ：将S×Σ映射到2S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合

s0：开始状态 (或初始状态)，s0∈S

F：接收状态（或终止状态）集合，F⊆ S

例如下图所展示的一个NFA

DFA与NFA的区别在于：如上图用红色方框标出的位置，DFA的每一次输入只对应一个结果，而NFA的依次输入可能对应多个结果，形成一个结果集，后面将使用子集法将NFA构造为DFA。

起始状态

状态函数

4 根据正规式RE构造NFA

ε对应的NFA

字母表Σ中符号a对应的NFA

r = r1r2对应的NFA

r = r1|r2对应的NFA

r = (r1)*对应的NFA

例:r=(a|b)*abb 对应的NFA

从正则表达式到自动机的转换

1 确定化：NFA转化为DFA

DFA状态转换矩阵

ㅤ	ㅤ	0	1
A	{S}	{V,Q}	{Q,U}
B	{V,Q}	{Z,V}	{Q,U}
C	{Q,U}	{V}	{Q,U,Z}
D	{V}	{Z}
E	{Z,V}	{Z}	{Z}
F	{Q,U,Z}	{Z,V}	{Q,Z}
G	{Z}	{Z}	{Z}
H	{Q,Z}	{Z}	{Q,Z}

DFA图：

DFA状态转换矩阵

	ㅤ	0	1	2
X	ε{A}={ABC}	ε{A}={ABC}	ε{B}={BC}	ε{C}={C}
Y	ε{BC}		ε{B}={BC}	ε{C}={C}
Z	ε{C}			ε{C}={C}

DFA图

2 最小化：DFA的化简

即寻找一个状态数比M少的DFA M‘，使得L（M）=L（M’）。

化简了的DFA满足两个条件：

没有多余状态。（输入串无法到达）

它的状态集中没有两个状态是相互等价的。

设 DFA M = ( Q ,Σ , f , S 0 , F ), s , t ∈ Q 。 若对任何 α ∈ Σ * , f ( s , α ) ∈ F 当且仅当 f ( t , α )∈ F ,则称状态 s 和 t 是等价的 。如果 s 和 t 不等价,则称 s 和 t 是可区别的。例如,终态与非终态是可区别的。因为终态有一条到达自身的 ε 道路,而非终态没有到达终态的 ε 道路。