gll-pg

GLL解析器的解析生成器。它使用Logos作为词法分析器。

用法

添加到Cargo.toml

[dependencies]
gll-pg-macros = "0.2"
gll-pg-core = "0.2"
logos = "0.9"

使用Logos编写词法分析器

use logos::Logos;

#[derive(Logos, Debug, Eq, PartialEq, Clone)]
pub enum Token {
    End, // must not change this
    #[error]
    Error,
    #[token(" ")]
    _Eps, // must not change this, will be skipped
    #[token("a")]
    Ta,
}

使用gll-pg生成解析器

struct Parser {}

#[gll(S, Token)]
impl Parser {
    #[rule(S -> S Ta)]
    fn s1(s: &usize, _a: &LogosToken<Token>) -> usize {
        *s + 1
    }
    #[rule(S ->)]
    fn s2() -> usize {
        0
    }
}

运行它

let mut lexer = Token::lexer("aaa");
let mut parser = Parser {};
let res = parser.parse(&mut lexer).unwrap();
// res is a StreamingIterator
let vec: Vec<usize> = res.cloned().collect();
assert_eq!(res, vec![3]);

示例

模糊计算器

对于以下语法

E -> E + E
E -> E * E
E -> - E
E -> ( E )
E -> int

对于输入"1 + 2 * 3"，它给出[7, 9]。对于输入"1 + (2 * -3)"，它给出[-5]。

详细信息请见tests/src/arith.rs。

递归

它可以处理递归语法

S -> a
S -> S S
S -> S S S

代码片段

#[gll(S, Token)]
impl Parser {
    #[rule(S -> Ta)]
    fn s1(_a: &LogosToken<Token>) -> usize {
        1
    }
    #[rule(S -> S S)]
    fn s2(s1: &usize, s2: &usize) -> usize {
        s1 + s2
    }
    #[rule(S -> S S S)]
    fn s3(s1: &usize, s2: &usize, s3: &usize) -> usize {
        s1 + s2 + s3
    }
}

// "" gives []
// "a" gives [1]
// "aa" gives [2]
// "aaa" gives [3,3,3]
// "aaaa" gives [4, 4, 4, 4, 4, 4, 4, 4, 4]

详细信息请见tests/src/crazy.rs。

变更日志

版本 0.4.0 2021-01-17

1. 迁移到Logos v0.11。

版本 0.3.0 2019-11-15

1. 返回一个实现了StreamingIterator的结构体，以懒方式提供推导。
2. 为推导的共享结构实现记忆化。
3. 将所有clone调用转换为引用到竞技场对象。
4. 实现诊断以捕获类型不匹配错误。
5. 以正确的行号报告用户代码中的错误。

版本 0.2.1 2019-11-13

1. 改进文档。

版本 0.2.0 2019-11-13

1. 允许访问结构体字段。

版本 0.1.0 2019-11-12

1. 初始工作版本。
2. 解析器递归地克隆和收集所有可能的推导。

参考文献

1. 代码生成和模板是从MashPlant/lalr1学习的。
2. Scott, E., & Johnstone, A. (2010). GLL parsing. Electronic Notes in Theoretical Computer Science, 253(7), 177-189.
3. Scott, E., & Johnstone, A. (2013). GLL parse-tree generation. Science of Computer Programming, 78(10), 1828-1844.