在创建 DFA 后实现识别令牌的词法分析器

Question

我想了解一些关于实现词法分析器的知识，我不想使用扫描仪生成器。从我所读到的内容中，我使用正则表达式确定了语言的规范，每个表达式都用于不同的标记。然后我应该制作一个大的正则表达式 ORing 所有令牌的表达式，对吗？！然后创建NFA，然后创建这个大正则表达式的DFA，对吗？！如果是这样，那么当一个词与最终的 DFA 匹配时，我怎么知道这个词代表哪个标记？！

Answer 1

基于 FSM 的词法分析器

手动编写有限状态机 (FSM) 词法分析器，循环输入中的字符并使用两级 switch 语句对其进行处理：

• 外层switch语句是开启状态；
• 内部 switch 语句正在打开读取的字符。

这是处理令牌的有限状态机的实现。这样做的缺点是维护起来可能会变得复杂，特别是如果有很多状态需要处理每个令牌。好处是更容易重构以利用有限状态机（例如使用转换表而不是 switch 语句）。

转换表就像 switch 语句：行定义状态，列定义数据值，单元格定义要转换到的下一个状态（类似于-1停止处理的信号）。通过这种方法，最终状态可用于确定令牌类型。在这里，您将拥有一个token_type tokens[N_STATES];数组，然后您可以执行token = tokens[current_state]该数组来获取令牌。

非 FSM 词法分析器

另一种方法是打开第一个字符，然后读取该标记中的其余字符作为该 case 语句的一部分。这可以更容易阅读和更简单地编写。

您还可以将字符分为不同的类别（例如数字、字母、减号和小于号），您可以将其定义为 256 项查找表。这可以简化 case 语句。

常用表达

正如您所指出的，使用大的正则表达式是有问题的，因为您无法获取令牌类型。这里的一种方法是拥有一个与标记匹配的正则表达式列表，并将其与标记类型相关联。例如，在Python中：

_tokens = [
    (re.compile('\\s+'), WhiteSpace),
    (re.compile('[a-zA-Z_][a-zA-Z0-9_]*'), Identifier),
    (re.compile('[0-9]+'), Integer),
]

您需要正确排序（例如，将关键字匹配放在标识符之前）。