gll-pg

A Parser Generator for GLL parser. It uses Logos as lexer.

Usage

Add to Cargo.toml:

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

Write a lexer using 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,
}

Use gll-pg to generate parser:

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
    }
}

Run it:

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]);

Example

Ambiguous Calculator

For the grammar below:

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

For input "1 + 2 * 3", it gives [7, 9]. For input "1 + (2 * -3)", it gives [-5].

See tests/src/arith.rs for detail.

Recursive

It can handle recursive grammars:

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

Code snippet:

#[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]

See tests/src/crazy.rs for detail.

Changelog

Release 0.4.0 2021-01-17

1. Migrate to Logos v0.11.

Release 0.3.0 2019-11-15

1. Return a struct that impls StreamingIterator to give derivations lazily.
2. Implement memoization for shared structure of derivations.
3. Turn all clone calls to reference to arena objects.
4. Implement diagnostics to catch type mismatch errors.
5. Make errors in user code reported with correct line numbers.

Release 0.2.1 2019-11-13

1. Improve documentation.

Release 0.2.0 2019-11-13

1. Allow access to struct fields.

Release 0.1.0 2019-11-12

1. Initial working version.
2. The parser recursively clone & collect all possible derivations.

References

1. Code generation and template is learned from 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.