编写编译器，词法分析？

Question

我对编写编译器完全是个新手。因此，我目前正在启动这个项目(用Java编写)，在编码之前，我想了解更多关于词法分析部分的信息。我在网上搜索过，我发现他们中的大多数都使用标记器。

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

Answer 1

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

• Big switch statements and transition tables
• A virtual machine

您可以通过组合几个识别器来构建词法分析器/扫描器。例如，设想一种仅用于赋值的语言，其中包含由正则表达式定义的以下标记：

关键字标识: a-zA-Z+

• assignment：=

• ：0-9+

：

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

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

样本输入的结果：

definitions

• 25=xyz：(标识符a)(赋值=)(编号10 )

• a=10：(标识符a)(赋值=)(编号10)

• a =10:无效-我们的令牌中不接受空格definitions

• 25=xyz：(编号25)(赋值)(标识符xyz)

• 25和42：(编号25)(关键字

)(编号42) -假定关键字优先于identifier

• b=1+2 :无效-我们的令牌definitions

• andx=8：(标识符

x)(赋值)(编号8)不接受'+‘--最长匹配给我们(标识符和x)与(关键字和)(标识符x)

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

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

Answer 2

我假设这是一个赋值，给出了对标记器的人为禁令。

谷歌上有很多与"lexical analysis using finite state automata“匹配的单词。这些都少了些什么？

你在理解有限状态自动机如何用于词法分析时有问题吗？或者自己写一个自动机？了解它们也称为有限状态机(FSM)可能会有所帮助

记号赋予器可以很好地在其内部使用FSM，所以我不明白为什么你说你必须使用FSM，而不是记号赋予器-这是否意味着你不能使用你编写的记号赋予器，而必须自己编写？

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

lex (及其最新的关系flex)是词法分析器，其源代码是可用的。你可以从这些东西中寻找想法