如何使用有限自动机实现扫描仪
How to use Finite Automaton to implement a scanner
我正在构建一个简单的扫描仪。假设我为我的语言定义了以下标记：
!, !=, !==, <, <<, {
现在我可以使用正则表达式指定它们，所以：
!=?=? | { | <<?
然后我用http://hackingoff.com构建了NFA和DFA。每台机器现在都可以确定输入是否使用正则表达式的语言。但是我的程序是一系列标记，而不是一个标记：
!!=!<!==<<!{
我的问题是我应该如何使用机器将字符串解析为标记？我对方法而不是实现感兴趣。
最常见的规则是 "maximal munch"，它总是选择尽可能长的标记。
一般来说，使用 DFA 扫描单个标记的算法如下：（要标记输入，重复此算法直到到达输入末尾，每次扫描从输入光标左侧开始通过之前的扫描。）
将DFA状态设置为开始状态。然后，对于序列中的每个输入字符：
如果 DFA 对角色有转换，则移动到 iindicated 状态。如果那个状态是接受状态，记录当前输入光标和状态号。
否则，将输入倒回到最后记录的接受位置和return记录的状态编号。
此处，接受状态编号用于指示遇到了哪个令牌。在实践中，通常将每个接受状态与令牌代码相关联，因为某些令牌类型将具有不止一种接受状态。
并非总是需要使用上述回溯算法。在某些情况下，对 DFA 的分析将揭示最后的接受状态总是在紧接在前的输入位置。但是，很多语言都需要回溯。
例如，. 和 ... 都是标记但不是 .. 的语言（例如 C）必须回溯输入 ..1，这应该被标记为 .、.1。在此输入的标记化中，第一次扫描将接受第一个 .，继续第二个 .（这不是接受状态），然后无法在输入 [=18] 上找到转换=].然后它会报告它找到了一个 .（记录的已接受令牌）并将输入光标重置到第二个字符位置，以便下一次扫描将看到令牌 .1.
我正在构建一个简单的扫描仪。假设我为我的语言定义了以下标记：
!, !=, !==, <, <<, {
现在我可以使用正则表达式指定它们，所以：
!=?=? | { | <<?
然后我用http://hackingoff.com构建了NFA和DFA。每台机器现在都可以确定输入是否使用正则表达式的语言。但是我的程序是一系列标记，而不是一个标记：
!!=!<!==<<!{
我的问题是我应该如何使用机器将字符串解析为标记？我对方法而不是实现感兴趣。
最常见的规则是 "maximal munch"，它总是选择尽可能长的标记。
一般来说，使用 DFA 扫描单个标记的算法如下：（要标记输入，重复此算法直到到达输入末尾，每次扫描从输入光标左侧开始通过之前的扫描。）
将DFA状态设置为开始状态。然后，对于序列中的每个输入字符：
如果 DFA 对角色有转换，则移动到 iindicated 状态。如果那个状态是接受状态，记录当前输入光标和状态号。
否则，将输入倒回到最后记录的接受位置和return记录的状态编号。
此处，接受状态编号用于指示遇到了哪个令牌。在实践中，通常将每个接受状态与令牌代码相关联，因为某些令牌类型将具有不止一种接受状态。
并非总是需要使用上述回溯算法。在某些情况下，对 DFA 的分析将揭示最后的接受状态总是在紧接在前的输入位置。但是，很多语言都需要回溯。
例如，. 和 ... 都是标记但不是 .. 的语言（例如 C）必须回溯输入 ..1，这应该被标记为 .、.1。在此输入的标记化中，第一次扫描将接受第一个 .，继续第二个 .（这不是接受状态），然后无法在输入 [=18] 上找到转换=].然后它会报告它找到了一个 .（记录的已接受令牌）并将输入光标重置到第二个字符位置，以便下一次扫描将看到令牌 .1.