编译器笔记6-词法分析-有穷自动机
一 有穷自动机 (Finite Automata)
- 简介
有穷自动机(Finite Automata，FA)由两位神经物理学MeCuloch和Pitts于1948年首先提出，是对 一类处理系统建立的数学模型。这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）。
系统只需要根据当前所处的状态 和 当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部 状态也将发生改变。
- FA的典型例子
电梯控制装置
输入：顾客的乘梯需求（所要到达的层号）
状态：电梯所处的层数+
电梯控制装置并不需要记住先前全部的服务要
求，只需要知道电梯当前所处的状态以及还没
有满足的所有服务请求。
- FA模型
FA模型.png
输入带 (input tape) ：用来存放输入符号串。
读头 (head) ：从左向右逐个读取输入符号，不能修改（只读）、不能往返移动。
有穷控制器 ( finite control ) ：具有有穷个状态数，根据当前的
状态和当前输入符号控制转入 下一状态。
- FA的表示
转换图.png
- FA定义(接收)的语言
FA定义(接收)的语言.png
- 最长子串匹配原则 (Longest String Matching Principle)
最长子串匹配原则.png
二 有穷自动机的分类
确定的FA (Deterministic finite automata, DFA)
非确定的FA (Nondeterministic finite automata, NFA)
确定的有穷自动机 (DFA)
M = (S，Σ，δ，s0，F)
DFA.png
例：一个DFA
M = (S，Σ ，δ，s0，F)
DFA.png
非确定的有穷自动机(NFA)
M = (S，Σ，δ，s0，F)
NFA.png
例：一个NFA
M = (S，Σ，δ，s0，F)
NFA.png
DFA和NFA的等价性
对任何非确定的有穷自动机N，存在定义同一语言的确定的有穷自动机D。对任何确定的有穷自动机D，存在定义同一语言的非确定的有穷自动机N。
DFA和NFA可以识别相同的语言
DFA和NFA.png
带有“ε-边”的NFA
M = (S，Σ，δ，s0，F)
带有“ε-边”的NFA.png
带有和不带有“ε-边”的NFA 的等价性
例.png
DFA的算法实现
DFA的算法实现.png
三 从正则表达式到有穷自动机
从正则表达式到有穷自动机.png
从正则表达式到NFA相对直接到DFA比较简单,再从NFA转到DFA。
- 根据RE构造NFA
根据RE构造NFA.png
fa.png
例 r=(a|b)* abb 对应的NFA
r=(a|b)* abb.png
四 从NFA到DFA的转换
例1.png
例2.png
子集构造法 （subset construction ）
与NFA等价的DFA的每个状态都是NFA状态的一个子集
子集构造法.png
move(T,a)获得的是一个状态集合U，ε-closure（move(T,a)）即为ε-closure(U)对应上表的第二个操作。所以理解上述函数关键是理解closure(T),该操作其实就是求得一个状态集合只通过ε转换得到的另外一个集合。
计算 ε-closure (T )
计算 ε-closure (T ).png
五 识别单词的DFA
- 识别标识符的DFA
标识符的正则定义.png
- 识别无符号数的DFA
识别无符号数的DFA.png
- 识别各进制无符号整数的DFA
识别各进制无符号整数的DFA.png
- 识别注释的DFA
识别注释的DFA.png
- 识别Token的DFA
识别Token的DFA.png
- 词法分析阶段的错误处理
词法分析阶段的错误处理.png
- 错误处理
错误处理.png
- 错误恢复策略
错误恢复策略.png
