正则表达式，编写玩具编译器，解析，注释删除器

Question

我目前正在努力阅读这本书: http://www1.idc.ac.il/tecs/

我目前所在的部分的练习规模是为一种非常简单的类似 java 的语言创建一个编译器。 这本书总是说明需要什么，但没有说明如何如何(这是一件好事)。我还应该提到，它讨论了 yacc 和 lex，并特别指出为了自己学习，在书中的项目中避免使用它们。

我正在阅读第 10 章，并开始编写标记器。

1)任何人都可以给我一些一般性建议 - 正则表达式是标记源文件的最佳方法吗？

2)我想在解析之前从源文件中删除注释 - 这并不难，但大多数编译器会告诉您发生错误的行，如果我只是删除注释，这会弄乱行数，有没有简单的方法保留行数同时仍然删除垃圾的策略？

提前致谢!

Answer 1

标记器本身通常使用一个大型 DFA 表来编写，该表描述了所有可能的有效标记(例如标记可以以字母开头，后跟其他字母/数字，后跟非字母，或者以数字开头，后跟非字母)其他数字和非数字/点或点后跟至少 1 个数字，然后是非数字，等等)。我构建我的方法是识别我的分词器将接受的所有正则表达式，将它们转换为 DFA 并将它们组合起来。

现在要“删除评论”，当你解析一个标记时，你可以有一个评论标记(解析评论的正则表达式，太长而无法用文字描述)，当你完成解析这个评论时，你只需解析一个新 token ，因此忽略它。或者，您可以将其传递给编译器并让它处理它(或按其意愿忽略它)。任何一种方法都会保留元数据，例如行号和行内字符。

编辑DFA理论:

出于性能原因，每个正则表达式都可以转换(并且正在转换)为 DFA。这消除了解析它们时的任何回溯。 This link让您了解如何完成此操作。首先将正则表达式转换为 NFA(具有回溯功能的 DFA)，然后通过膨胀有限自动机来删除所有回溯节点。

构建 DFA 的另一种方法是使用一些常识来手动构建。以可以解析标识符或数字的有限自动机为例。这当然还不够，因为您很可能也想添加注释，但它会让您了解底层结构。

          A-Z       space
->(Start)----->(I1)------->((Identifier))
     |         | ^
     |         +-+
     |        A-Z0-9
     |
     |          space   
     +---->(N1)---+--->((Number)) <----------+
      0-9  | ^    |                          |
           | |    | .       0-9       space  |
           +-+    +--->(N2)----->(N3)--------+
           0-9                   | ^
                                 +-+
                                 0-9

有关所用符号的一些注释，DFA 从(开始)节点开始，并在从文件中读取输入时沿着箭头移动。在任何一点它只能匹配一条路径。任何丢失的路径都默认为“错误”节点。 ((Number)) 和 ((Identifier)) 是您的结束、成功节点。一旦进入这些节点，您就返回您的 token 。

因此，从一开始，如果您的 token 以字母开头，它必须以一堆字母或数字继续，并以“空格”结尾(空格、换行符、制表符等)。没有回溯，如果失败，标记化过程就会失败，您可以报告错误。你应该读一本关于错误恢复的理论书才能继续解析，这是一个非常大的话题。

但是，如果您的 token 以数字开头，则后面必须跟一串数字或一个小数点。如果没有小数点，则数字后面必须有一个“空格”，否则必须跟随一个数字，然后是一堆数字，然后是一个空格。我没有添加科学计数法，但添加起来并不难。

现在，为了提高解析速度，它会转换为 DFA 表，所有节点都位于垂直线和水平线上。像这样的事情:

             I1            Identifier  N1      N2      N3      Number
start        letter        nothing     number  nothing nothing nothing
I1           letter+number space       nothing nothing nothing nothing
Identifier   nothing       SUCCESS     nothing nothing nothing nothing
N1           nothing       nothing     number  dot     nothing space
N2           nothing       nothing     nothing nothing number  nothing
N3           nothing       nothing     nothing nothing number  space
Number       nothing       nothing     nothing nothing nothing SUCCESS

运行此程序的方式是存储起始状态，并在逐个字符读取输入时在表格中移动。例如，输入“1.2”将解析为 start->N1->N2->N3->Number->SUCCESS。如果在任何时候您遇到“无”节点，则会出现错误。

编辑2:表实际上应该是节点->字符->节点，而不是节点->节点->字符，但无论如何在这种情况下它工作得很好。自从我上次手工编写编译器以来已经有一段时间了。