gll-pg
A Parser Generator for GLL parser. It uses Logos as lexer.
Usage
Add to Cargo.toml:
[]
= "0.2"
= "0.2"
= "0.9"
Write a lexer using Logos:
use Logos;
Use gll-pg to generate parser:
Run it:
let mut lexer = lexer;
let mut parser = Parser ;
let res = parser.parse.unwrap;
// res is a StreamingIterator
let vec: = res.cloned.collect;
assert_eq!;
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:
// "" 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
- Migrate to Logos v0.11.
Release 0.3.0 2019-11-15
- Return a struct that impls StreamingIterator to give derivations lazily.
- Implement memoization for shared structure of derivations.
- Turn all clone calls to reference to arena objects.
- Implement diagnostics to catch type mismatch errors.
- Make errors in user code reported with correct line numbers.
Release 0.2.1 2019-11-13
- Improve documentation.
Release 0.2.0 2019-11-13
- Allow access to struct fields.
Release 0.1.0 2019-11-12
- Initial working version.
- The parser recursively clone & collect all possible derivations.
References
- Code generation and template is learned from
MashPlant/lalr1
. - Scott, E., & Johnstone, A. (2010). GLL parsing. Electronic Notes in Theoretical Computer Science, 253(7), 177-189.
- Scott, E., & Johnstone, A. (2013). GLL parse-tree generation. Science of Computer Programming, 78(10), 1828-1844.