compiler-construction - 编写编译器，词法分析？

Question

我对编写编译器完全陌生。所以我目前正在启动项目(用Java编码)，在编码之前，我想更多地了解词法分析部分。我在网上研究过，我发现他们中的大多数都使用分词器。

该项目要求我不使用它们(标记器)，而是使用有限状态自动机。我很困惑，我是否需要使用链表来实现它？或者一个简单的嵌套 switch case 就可以了。我对实现有限自动机不是很熟悉，有什么优点？

Answer 1

Regular Expression Matching Can Be Simple And Fast作者 Russ Cox 很好地介绍了使用有限状态机构建识别器。他展示了如何从正则表达式到非确定性有限自动机，再到确定性有限自动机。他的引用实现使用了 directed graph (类似于链表，但每个节点可以有多个“出”引用，并且可以引用包括自身在内的任何其他节点)与链表。还有其他建模状态机的方法，包括:

Big switch statements and transition tables

A virtual machine

您可以通过组合多个识别器来构建词法分析器/扫描器。例如，想象一个只赋值的语言，它具有由正则表达式定义的以下标记:

标识符:[a-zA-Z]+

赋值:=

号码:[0-9]+

关键字:和

当您从左到右扫描输入时，根据当前符号在每个 token 的机器中移动。当一个符号没有有效的转换时，选择最后一个处于接受状态的机器。在该状态之前扫描的所有符号都是 token 的一部分。在最后接受的符号之后的符号处再次开始扫描。如果新标记没有有效的转换，则输入无效，词法分析器应报告错误。如果有不止一台机器处于接受状态，那么优先规则应该决定使用哪个 token 。

注意:这些步骤描述了一个总是返回最长可能匹配的词法分析器。您还可以设计一个词法分析器，一旦其中一台机器处于接受状态，它就会返回一个 token 。

样本输入的结果:

a=10 : (标识符 a)(赋值 =)(数字 10)

a = 10 : 无效 - 我们的 token 定义中不接受空格

25=xyz : (number 25)(assignment)(identifier xyz)

25and42 : (number 25)(keyword and)(number 42) - 假设关键字优先于标识符

b=1+2 : 无效 - 我们的 token 定义中不接受“+”

andx=8 : (identifier andx)(assignment)(number 8) - 最长匹配给我们(标识符andx)与(关键字and)(标识符x)

请注意，词法分析只返回标记。它不知道 token 是否被正确使用。 '25=xyz' 可能没有任何意义，但我们必须等到解析阶段才能确定。

作为附加资源，Dick Grune 提供了 Parsing Techniques - A Practical Guide 的第一版。作为后记和PDF。