用 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 以后很多操作都很方便。但代码还有很多地方可以优化，慢慢搞吧。

用 Rust Procedure Macro 实现 GLL Parser¶

背景¶

尝试¶

宏¶

记忆化¶

错误处理¶

总结¶

评论