自定义解析器

2019 年 08 月 08 日

从设计角度上讲,程序和数据是分离的。所以通常我们使用配置文件来调整程序的行为。配置文件通常用一些常用格式,例如Json或者Toml等等。

但有时,我们需要把一些复杂的定义或者行为放到配置文件中,用常用格式是没办法表达这些复杂的定义或者行为的。这时就需要自行解析配置文件。这样的解析的复杂度可能会高于程序本身的复杂度。对于这种场景,通常需要定义一种语言,常见的例子是DSL(Domain-Specific Language)。

对于这样的解析,实际上用到了编译原理的知识。编译原理是一个非常成熟的知识体系,其中,词法分析/语法分析/语义分析这几部分,通常称为编译原理的前端。而源码优化/代码生成/目标代码优化等,通常称为编译原理的后端。我们实现解析器,通常只需要前端的部分即可。

编译原理前端的本质,实际上很简单,就是输入“要解析的源码”,得到一个“抽象语法树(Abstract Syntax Tree,AST)”。本质上这就是个可以用来方便的处理目标文本的数据结构。得到AST之后,就可以使用AST来抽取源码中的数据,或者分析和执行源码中指定的行为。

各种语言实现前端的部分很多,如果用C的话,最常见的是免费的flex+bison(对应最早的lex+yacc)。前者是词法分析,后者是语法分析。这两者是配合工作的。前者的输出是后者的输入。为了使其正常工作,除程序本身和作为数据的“源文件”,还需要一个“词法定义文件”,这里通常是用“上下文无关文法”定义这个文件的。简单来说,就是flex用“词法定义文件”和“源文件”生成一个Token数据流,而bison将这个Token数据流转化成AST。

不过这里我用Rust语言,所以不用flex+bison,而是使用lalrpop,顺便说一句这个命名,LALR其实是语法分析器的一种方法,对应的可以搜索LL/LR(1)/LALR等等。而lalrpop声称自己是LR(1)的。

lalrpop的教程在这里,简单说就是遵循以下几个步骤:

  1. 创建自己的工程,将lalrpop加入,并加入build.rs
  2. 在src目录下创建.lalrpop文件,即词法定义文件,编译时会自动在out目录生成对应的同名rs文件
  3. main.rs中使用生成的rs,将读取的源代码作为参数注入,得到AST
  4. 从根开始遍历得到的AST,执行需要的操作

需要注意的一点是教程里的calculator4应用,如果ast放在main.rs同目录下的ast.rs中,要编译通过的话,需要注意main.rs中要声明mod ast,否则out目录下生成的rs文件无法调用到。

Top