正则表达式,编写玩具编译器,解析,评论卸妆

标记器本身通常使用描述所有可能的有效标记的大型DFA表来编写(类似的东西,标记可以以字母开头,后跟其他字母/数字后跟非字母,或带有数字后跟其他数字和非数字/点或点后跟至少1个数字然后是非数字等等).我构建我的方法是识别我的tokenizer将接受的所有正则表达式,将它们转换为DFA并将它们组合起来.

现在要“删除注释”,当你解析一个令牌时,你可以有一个注释令牌(用于解析注释的正则表达式,用语言来描述的时间太长),当你完成解析这个注释时,你只需要解析一个新的令牌,因此无视它.或者,您可以将它传递给编译器并让它处理它(或者忽略它).无论是aproach都会保留元数据,如行号和字符到线.

编辑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))是你的结局,成功节点.进入这些节点后,您将返回令牌.

因此,从一开始,如果您的令牌以字母开头,则必须继续使用一堆字母或数字,并以“空格”(空格,换行符,制表符等)结束.没有回溯,如果失败,则标记化过程失败并且您可以报告错误.你应该阅读一本关于错误恢复的理论书来继续解析,这是一个非常大的话题.

但是,如果您的令牌以数字开头,则必须跟随一串数字或一个小数点.如果没有小数点,则“空格”必须跟随数字,否则必须跟随一个数字,然后是一堆数字,后跟一个空格.我没有包含科学记数法,但并不难添加.

现在,为了解析速度,它会转换为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”将解析为开始 – > N1-> N2-> N3->数字 – >成功.如果您在任何时候点击“无”节点,则表示您有错误.

编辑2：该表实际上应该是node-> character->节点,而不是node-> node->字符,但无论如何它在这种情况下都能正常工作.自从我上次手工编写编译器以来已经有一段时间了.