4

我对编写编译器完全陌生。所以我目前正在启动项目（用Java编码），在编码之前，我想更多地了解词法分析部分。我在网上进行了研究，发现其中大多数都使用标记器。

该项目要求我不使用它们（标记器），而是使用有限状态自动机。我很困惑，我需要使用链表来实现它吗？或者一个简单的嵌套开关案例就可以了。我对实现有限自动机并不是很熟悉，有什么好处？

4

2 回答 2

1

鉴于对标记器的人为禁令，我认为这是一项任务。

“使用有限状态自动机的词法分析”有很多谷歌匹配项。这些缺少什么？

您是否在了解如何将有限状态自动机用于词法分析时遇到问题？还是自己写一个自动机？知道它们也被称为有限状态机（FSM）可能会有所帮助

分词器很可能在其内部使用 FSM，所以我不明白您为什么说必须使用 FSM 而不是分词器——这是否意味着您不能使用自己编写的分词器而必须自己编写？

正则表达式匹配器的实现通常也是一个有限状态机，所以这可能是一个需要考虑的领域。

lex（及其最近的关系flex）是可以使用源代码的词法分析器。你可以看看那些想法

于 2010-12-09T17:26:29.763 回答
1

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

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

  • 标识符：[a-zA-Z]+
  • 分配：=
  • 号码：[0-9]+
  • 关键字：和

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

注意：这些步骤描述了一个总是返回最长匹配的词法分析器。您还可以设计一个词法分析器，它在其中一台机器处于接受状态时立即返回一个令牌。

样本输入的结果：

  • a=10 : (标识符 a)(赋值 =)(数字 10)
  • a = 10 : 无效 - 我们的令牌定义中不接受空格
  • 25=xyz : (数字 25)(赋值)(标识符 xyz)
  • 25and42 : (number 25)(keyword and)(number 42) - 假设关键字优先于标识符
  • b=1+2 : 无效 - '+' 在我们的令牌定义中不被接受
  • andx=8 : (identifier andx)(assignment)(number 8) - 最长匹配给我们 (identifier andx) 与 (keyword and)(identifier x)

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

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

于 2010-12-14T23:44:33.483 回答