第三章-2-子集构造法

知识

单词识别

我们如何使用迄今为止开发的概念来帮助识别源语言的标记？

词法分析器还能做什么

注：

每个标记都有一个唯一的标记标识符来定义词素的类别

标记的正则表达式模式

构建单词的转换图

• 转换图（TD）用于表示单词
• 在读取字符时，使用相关的TDs尝试将词素与模式匹配
• 每个TD都有：
  • 状态：由圆圈代表
  • 动作：由状态之间的箭头表示
  • 开始状态：图案的开始（箭头）
  • 最终状态：图案结束（同心圆）
• 每个TD都是确定性的——无需在两个不同的动作之间进行选择！

示例TDs

>=的转换图

意思是：我们已经接受“>”并且已经阅读了其他必须未读的字符。

例3.7：所有重新操作

关系运算符的转换图

例3.8、3.10：id和delim

转换图标识符和关键字

• 识别令牌时，必须执行以下操作之一：
  • If关键字：返回0
  • 符号表中的If ID：返回符号表条目
  • 如果ID不在符号表中：安装ID并返回符号表的新条目
• 在符号表中放置关键字几乎是必不可少的，并且是手动编码的，或者将关键字放置在另一个称为关键字/保留字表的表中。

例3.9：未签名的

Pascal中无符号数的转换图

Questions: Is ordering important for unsigned #s ? 给定标记的词素必须尽可能长。“贪婪”

Why are there no TDs for then, else, if ? (the same as id)

问题:

包含每个元音的字符串的转换图（TD）按照严格的字典顺序是什么样的

答案

注意：如果字符不是cons或lex顺序中的元音，则采用错误路径。

词法分析器还能做什么

所有关键字/保留字都匹配为ID

• 匹配后，将参考符号表或特殊关键字表

• 关键字表包含所有关键字和相关单词值的字符串版本

• 当找到匹配项时，将返回单词及其符号值，即“then”，258

• 如果未找到匹配项，则假定已发现id

实现转换图

词法分析器的C代码

lexeme_beginning = forward; 
state = 0; 
token nexttoken()
{ while(1) {//重复此操作，直到出现“返回”为止
	switch (state) {
	case 0: c = nextchar();
		/* c is lookahead character */
		if (c== blank || c==tab || c== newline) {
			state = 0;
			lexeme_beginning++;
				/* advance beginning of lexeme */
		}
		else if (c == ‘<‘) state = 1;
		else if (c == ‘=‘) state = 5;
		else if (c == ‘>’) state = 6;
		else state = fail();
		break;
		… /* cases 1-8 here */

.............
//案例编号对应于过渡图状态！
case 25; c = nextchar();
if (isdigit(c)) state = 26;
else state = fail();
break;
case 26; c = nextchar();
if (isdigit(c)) state = 26;
else state = 27;
break;
case 27; retract(1); lexical_value = install_num();
return ( NUM );
.............

.............
case 9: c = nextchar();
if (isletter(c)) state = 10;
else state = fail();
break;
case 10; c = nextchar();
if (isletter(c)) state = 10;
else if (isdigit(c)) state = 10;
else state = 11;
break;
case 11; retract(1); lexical_value = install_id();
return ( gettoken(lexical_value) );//从ST读取令牌名称
.............

发生故障时：

C代码查找下一个启动状态

Init fail()
{ start = state;
	forward = lexeme beginning;
	switch (start) {
		case 0: start = 9; break;
		case 9: start = 12; break;
		case 12: start = 20; break;
		case 20: start = 25; break;
		case 25: recover(); break;
		default: /* lex error */
	}
	return start;//切换到下一个转换图
}

有限自动机

• 一种语言的识别器是一个接受字符串x的程序，如果x是该语言的一个句子，它会回答“是”，否则回答“否”。
• 我们称单词识别器为有限自动机。
• 有限自动机可以是：确定性（DFA）或非确定性（NFA）
• 这意味着我们可以使用确定性或非确定性自动机作为词法分析器。
• 确定性和非确定性有限自动机都能识别正则集。
• 哪一个？
  • 确定性–更快的识别器，但可能占用更多空间
  • 非确定性–速度较慢，但占用的空间可能较少
  • 确定性自动机是广泛使用的词法分析器。
• 首先，我们为标记定义正则表达式；然后我们将它们转换为DFA，以获得标记的词法分析器。
  • 算法1：正则表达式➔ NFA➔ DFA（两步：先到NFA，然后到DFA）
  • 算法2：正则表达式➔ DFA（直接将正则表达式转换为DFA）

有限自动机

接受输入字符串并确定其是否为该语言的有效句子的识别器

非确定性

对同一输入符号有多个可选操作。

确定性

对于给定的输入符号，最多有一个动作。

NFAs和DFAs

非确定性有限自动机（NFA）很容易表示正则表达式，但精度稍低。

确定性有限自动机（Deterministic Finite Automata，DFA）需要更高的复杂性来表示正则表达式，但提供了更高的精度。

我们将回顾两种plus转换算法，即NFA→ DFA和DFA→ NFA

有限自动机与正则表达式之间的强关系

转换：记录从一种状态到另一种状态的变化，根据一个或多个字符的匹配进行标记。

开始状态：识别过程开始绘制一条未标记的箭头线，指向“不知从何而来”

接受状态：表示识别过程的结束。在图中，在状态周围画一条双线

非确定性有限自动机

NFA是一种数学模型，包括：

• ε-NFA中允许过渡。换句话说，我们可以在不使用任何符号的情况下从一个状态移动到另一个状态。

• NFA接受字符串x，当且仅当存在一条从起始状态到其中一个接受状态的路径，使得沿该路径的边标签拼出x。

代表NFA

过渡图：数字状态（圆）、弧、最终状态…

转换表：更适合在计算机中表示

我们将看到这两个例子！

NFA是如何工作的？

• 给定一个输入字符串，我们跟踪移动

• 如果没有更多输入&处于最终状态，请接受

处理未定义的转换

我们可以通过定义另一个状态“死亡”状态来处理未定义的转换，并将所有以前未定义的转换转换到该死亡状态。

NFA——R、E和汇编

正则表达式的NFA存在问题：

1. 可能不接受有效的输入

2. NFA在同一输入上可能表现不同

NFA与汇编的关系：

1. NFA“认可”的正则表达式

2. 正则表达式是“标记”的“模式”

3. 标记是词法分析的基础

4. 词法分析器可以用NFA集合来描述。每个NFA代表一种语言标记。

替代解决方案策略

现在您已经有了单独的图表，或者“它们如下所示：

使用“或”NFA的空转换

其他问题

并非所有路径都会导致接受。

确定性有限自动化（DFA）

DFA是NFA，有以下限制：

• ∈ 不允许搬家

• 针对每个状态∈ S、 对于每个输入符号a，从S到a只有一条路径∈ ∑

模拟DFA

让我们假设字符串的结尾用一个特殊的符号（比如eof）标记。识别算法如下：（高效实现）（算法3.1 p116）

实施NFA

模拟算法3.3汤普森构造的NFA

这种算法效率不高。

将NFA转换为DFA

• 给定任意NFA，构造等效DFA（即，接受完全相同字符串的DFA）需要：

  1. 消除ε-跃迁

  ε-闭包：一个或多个状态的ε-变换所能达到的所有状态的集合。

  2. 在单个输入字符上从一个状态进行多次转换。

• 跟踪通过匹配单个字符可以访问的状态集。

• 这两个过程都引导我们考虑一组状态而不是单个状态。因此，我们构造的DFA将原始NFA的状态集作为其状态集并不奇怪。

• 这种算法被称为子集构造(子集构造法或子集法).

转换：NFA→ DFA

• 算法从NFA构建DFA的转换表

• DFA中的每个状态对应于NFA的一组状态

• 为什么会发生这种情况？

  • ∈ 移动
  • 非决定论

  两者都要求我们描述接受同一字符串时出现的多种情况。

  （回忆一下：同一输入在NFA中可以有多条路径）

• 关键问题：调和歧义！

算法概念

NFA状态的操作

算法/技术利用这三种操作来促进转换过程。

子集构造算法

子集构造

put ε-closure({s0}) as an unmarked state into the set of DFA (DStates)
//ε-闭包（{s0}）是通过ε-跃迁从s0可以访问的所有状态的集合。
while (there is one unmarked S1in DStates) do 
	begin
		mark S1
		for each input symbol a do
			begin
				S2 ← ε-closure(move(S1,a))//set of states to which there is a transition on a from a state s in S1
				if (S2 is not in DStates) then
					add S2 into DStates as an unmarked state
				transfunc[S1,a] ← S2
			end
		end

DFA的起始状态是ε-闭包（{s0}）

如果S中的状态是NFA的接受状态，则DStates中的状态S是DFA的接受状态

计算∈-闭包

push all states in T onto stack;
initialize ∈-closure(T) to T;
while stack is not empty do begin
	pop t, the top element, off the stack;
	for each state u with edge from t to u labeled  do 
		if u is not in ∈-closure(T) do begin
			add u to ∈-closure(T) ;
			push u onto stack
	end
end

例题

正则表达式：（a | b）*abb

字符串“aabb”的移动：

DFA

(a|b) * abb

回想一下最初的NFA：

DFA接受(a|b) * abb

NFA

NFA的转移图

有限自动机的转移表

给定正则表达式：(a (b*c)) | (a (b | c${}^{+}^+$)?)

找到一个能识别它的转换图NFA。

将NFA转换为DFA

从NFA开始：（a | b）*abb

NFA N for (a|b)*abb

从状态0开始，我们可以在不消耗任何输入的情况下移动到哪里？

这形成了一个新状态：0,1,2,4,7这个新状态定义了什么转换？

DFA的转换表Dtran

应用子集构造的结果

课堂练习

DFA

该DFA识别的语言也是a（a | b）*b，求出DFA的转换图。

DFA accepting a (a|b) * b

NFA

该NFA识别的语言是（a | b）*a b，求出NFA的转换图和转换表。

NFA的转移图

有限自动机的转移表

NFA 2

该NFA识别的语言是a（a | b）*b，求出NFA的转换图和转换表。

作业

1

1. 使用子集构造法构造DFA.

The language recognized by this DFA is also a(a|b) *b,
figure out a transition graph of DFA.

Using subset construction to construct DFA from NFA.