1

我目前正在阅读“Dragon Book”（编译器：原理、技术和工具），我有点卡在使用 DFA（确定性有限自动机）的词法分析章节。

DFA 是一个二维数组，第一维包含状态，第二维包含转换符号。这意味着每个 DFA 状态都包含该语言的所有符号。书中的例子使用了一种小语言（通常是两个符号），它们在本章末尾做了如下注释：“因为一个典型的词法分析器在其 DFA 中有数百个状态，并且涉及 128 个输入字符的 ASCII 字母表，数组消耗不到一兆字节”。

但是，对于匹配字符串，我想匹配所有字符，这意味着整个字符集，并且很多输入文件使用 UTF-8 编码。这导致字母表以及 DFA 的大小大幅增加。

这就是我卡住的地方。词法分析器或正则表达式模拟器通常如何处理这个问题？

谢谢！

4

2 回答 2

1

我对这个问题有了顿悟。在词法分析中，您想要匹配超出 ASCII 范围的字符的唯一时间是在进行通配符匹配时，例如在字符串或注释中。因为这些仅在通配符中使用，而不是单独使用，所有值为 128 或更高的字符都可以表示为单个“其他”值。这样，字母表和 DFA 仍然很小，而我仍然可以使用转换表并匹配整个 unicode 字符集。

于 2013-09-19T20:34:41.883 回答
0

这是一个有趣的工具，可以将正则表达式转换为非确定性有限自动机。

于 2013-09-17T15:14:40.373 回答