用 Rust Procedure Macro 实现 GLL Parser

背景

在编译原理课上,PA 框架采用的是 MashPlant/lalr1 ,是一个比较好用的 Lexer + Parser 的工具,它的大概语法见 一个完整的例子 。然后之前看到了 GLL Parser ,想着可不可以照着类似的语法也写一个 GLL 的 Parser Generator ,也是用 Rust Procedure Macro 的方法,就开始了研究。

尝试

首先是阅读 GLL 的论文,它并不长,大概的意思就是,LL(1) 文法需要考虑 PS 冲突的情况,而 GLL 的解决方法就是“都试一下”,然后为了效率,用了 GSS 表示解析过程和 SPPF 表示解析结果。然后就开始照着论文手写了不同版本的实现,见 jiegec/gll-test

第一种就是按照论文里第一段实现直接抄过来,每个可能性作为一个 Continuation 存下来,它有自己的栈和执行位置(Label)。这样 Work 以后呢,我又想到了 async/await ,用类似的方法又写了一遍,相对要简洁一些,也是很平常的递归下降的写法,而不是 Loop + Label 的形式。但这些都不能做到合并栈的目的,所以遇到十分有歧义的文法的时候会很糟糕。

然后开始按照论文中的 GSS 进行编写,基本还是按照论文进行翻译,然后一步一步做,做好以后把 GSS 画出来,和论文的图可以对的上;然后照着 GLL parse-tree generation 的论文把 SPPF 实现了,这时候就可以从 recongizer 变成一个 parser 了。

得到一份可行的代码以后,就要扩展到通用的情况上。学习了一下 MashPlant/lalr1 的实现,实现了一个 proc macro,它读取了用户的程序,从一个模板文件开始,往里面插入一些生成的代码,丢给编译器去编译。这时候就涉及到编译期和运行时的不同了,我把运行时一些通用的结构放到了 gll-pg-core 中,把编译期的代码放到了 gll-pg-macros

代码生成的时候,基本按照之前自己写的样子抄,只不过这个时候要按照用户编写的产生式进行生成了,各种名字都要规范化,变得可以复用,然后尽量减少命名空间的污染等等这些常见的写宏需要注意的操作。

不过,考虑到现在还没有实现 Lexer ,所以先用了 Logos 库作为 Lexer。但我其实不大喜欢它,因为它太简单,也没有行号的信息,不过暂且先这样吧,以后可能会自己实现。

然后 0.1.0 版本就诞生了,它的样例长这样:

//! This example is taken from MashPlant/lalr1

use gll_pg_core::LogosToken;
use gll_pg_macros::gll;
use logos::Logos;

#[derive(Logos, Debug, Eq, PartialEq, Clone)]
pub enum Token {
    #[end]
    End,
    #[error]
    Error,
    #[token = " "]
    _Eps,
    #[token = "+"]
    Add,
    #[token = "-"]
    Sub,
    #[token = "*"]
    Mul,
    #[token = "/"]
    Div,
    #[token = "%"]
    Mod,
    #[token = "("]
    LPar,
    #[token = ")"]
    RPar,
    #[regex = "[0-9]+"]
    IntLit,
}

#[gll(Expr, Token)]
impl Parser {
    #[rule(Expr -> Expr Add Expr)]
    fn expr_add(l: i32, _op: LogosToken<Token>, r: i32) -> i32 {
        l + r
    }
    #[rule(Expr -> Expr Sub Expr)]
    fn expr_sub(l: i32, _op: LogosToken<Token>, r: i32) -> i32 {
        l - r
    }
    #[rule(Expr -> Expr Mul Expr)]
    fn expr_mul(l: i32, _op: LogosToken<Token>, r: i32) -> i32 {
        l * r
    }
    #[rule(Expr -> Expr Div Expr)]
    fn expr_div(l: i32, _op: LogosToken<Token>, r: i32) -> i32 {
        l / r
    }
    #[rule(Expr -> Expr Mod Expr)]
    fn expr_mod(l: i32, _op: LogosToken<Token>, r: i32) -> i32 {
        l % r
    }
    #[rule(Expr -> Sub Expr)]
    fn expr_neg(_op: LogosToken<Token>, r: i32) -> i32 {
        -r
    }
    #[rule(Expr -> LPar Expr RPar)]
    fn expr_paren(_l: LogosToken<Token>, i: i32, _r: LogosToken<Token>) -> i32 {
        i
    }
    #[rule(Expr -> IntLit)]
    fn expr_int(i: LogosToken<Token>) -> i32 {
        i.slice.parse().unwrap()
    }
}

#[test]
fn gll() {
    let mut lexer = Token::lexer("1 + 2 * 3");
    let res = Parser::parse(&mut lexer);
    // two ways to parse
    assert_eq!(res, [7, 9]);
}

可以看到,它解析的结果是一个数组,对应所有可能出现的情况。这样比较简单,但是要求中间各种类型都是 Clone ,因为同一个结点可能会被用多次。它的计算方法就是在最终的 SPPF 上递归找到所有可能性,然后调用用户代码,最后放到一个 Vec 中。

记忆化

但是,上面的做法有一个很大的问题,就是,虽然 SPPF 的空间复杂度是有限的,但所有可能的解析树可以有很多,如果把每一个情况都完整的存在一个 Vec 中,空间要求是很高的,中间也有很多重复计算的情况。所以需要做记忆化,然后每次给出一个。因为依赖自己内部的状态,所以不能是 Iterator 只能是 StreamingIterator 。

记忆化也花了我一番功夫,现在用了一个比较土的办法,在每个结点上记录了当前遇到过的所有可能,这个是逐渐构造的,意味着如果只需要第一种解析树,不需要额外的空间。然后逐渐扩张,如果有可以重用的结构就重用,把涉及的所有的结构都放在一个 Vec 中,用完之后一起 drop 掉。

当然了,这个时候,各种东西都变成了引用:

//! This example is taken from MashPlant/lalr1

use gll_pg_core::*;
use gll_pg_macros::gll;
use logos::Logos;

#[derive(Logos, Debug, Eq, PartialEq, Clone)]
enum Token {
    #[end]
    End,
    #[error]
    Error,
    #[token = " "]
    _Eps,
    #[token = "+"]
    Add,
    #[token = "-"]
    Sub,
    #[token = "*"]
    Mul,
    #[token = "/"]
    Div,
    #[token = "%"]
    Mod,
    #[token = "("]
    LPar,
    #[token = ")"]
    RPar,
    #[regex = "[0-9]+"]
    IntLit,
}

#[derive(Default)]
struct Parser {
    literals: Vec<i32>,
}

#[gll(Expr, Token)]
impl Parser {
    // you can omit self
    #[rule(Expr -> Expr Add Expr)]
    fn expr_add(l: &i32, _op: &LogosToken<Token>, r: &i32) -> i32 {
        *l + *r
    }
    // you can use &self
    #[rule(Expr -> Expr Sub Expr)]
    fn expr_sub(&self, l: &i32, _op: &LogosToken<Token>, r: &i32) -> i32 {
        *l - *r
    }
    // you can use &mut self as well
    // but all of these have &mut self in fact
    #[rule(Expr -> Expr Mul Expr)]
    fn expr_mul(&mut self, l: &i32, _op: &LogosToken<Token>, r: &i32) -> i32 {
        *l * *r
    }
    #[rule(Expr -> Expr Div Expr)]
    fn expr_div(l: &i32, _op: &LogosToken<Token>, r: &i32) -> i32 {
        *l / *r
    }
    #[rule(Expr -> Expr Mod Expr)]
    fn expr_mod(l: &i32, _op: &LogosToken<Token>, r: &i32) -> i32 {
        *l % *r
    }
    #[rule(Expr -> Sub Expr)]
    fn expr_neg(_op: &LogosToken<Token>, r: &i32) -> i32 {
        -*r
    }
    #[rule(Expr -> LPar Expr RPar)]
    fn expr_paren(_l: &LogosToken<Token>, i: &i32, _r: &LogosToken<Token>) -> i32 {
        *i
    }
    // so you can make your IDE happy with &mut self here
    #[rule(Expr -> IntLit)]
    fn expr_int(&mut self, i: &LogosToken<Token>) -> i32 {
        let lit = i.slice.parse().unwrap();
        self.literals.push(lit);
        lit
    }
}

#[test]
fn ambiguous() {
    let mut lexer = Token::lexer("1 + 2 + 3");
    let mut parser = Parser { literals: vec![] };
    let res = parser.parse(&mut lexer).unwrap();
    // two ways to parse
    let res: Vec<_> = res.cloned().collect();
    assert_eq!(res, vec![6, 6]);
}

这时候就是 0.3.0 版本,基本达到了我一开始想要的程度。

错误处理

在之前写编译原理 PA1 的时候,遇到的一个问题就是,如果自己的代码有错,因为宏展开以后丢失了位置信息,所以报错都会在错误的位置。一番查找以后,找到了解决方案:原样记录下原来的代码(syn::Block),然后通过 quote 宏直接拼接到最终的 TokenStream 中,这样在结果里,虽然代码还是那些代码,但部分的 Token 就有了正确的位置,这样就很方便用户代码的修改了。不过还是不方便找模板部分的代码错误,毕竟那部分确实在原来的代码中没有出现过。

对于模板中的代码错误,我最终的解决方案是 cargo-expand ,把我的测试代码和展开后的代码拼接起来,然后在茫茫的无关报错下去找我的错误的地方。虽然不是很好用,但毕竟还是 work 的。另外,宏还需要对用户代码的一些类型进行检查,比如上面的 Expr 对应 i32 ,这个就需要在各处都保持一致,但这个就需要自己进行检查了。使用了一下 proc_macro_diagnostic 的 API ,还不是很好用,等它 stable 吧。

总结

终于自己手写了一个 Procedure Macro ,感觉现有的工具已经比较成熟了,有 syn quote 以后很多操作都很方便。但代码还有很多地方可以优化,慢慢搞吧。

comments powered by Disqus