Crate prattle

Introduction

This crate implements a configurable and general-purpose Pratt parser.

A Pratt parser is also known as a Top-Down Operator Precedence parser, aka TDOP parser. The general algorithm was discovered and outlined by Vaughn Pratt in 1973 in his paper[1].

It differs from recursive-descent classes of parsers by associating parsing rules to tokens rather than grammar rules.

This is especially valuable when parsing expression grammars with operator precedence without significant descent and type costs.

Consider the following expression:

a + b * c

So which variables are to be associated with which operators? A recursive-descent parser would need to implement two layers of grammar rules which are recursive with each other. This leads to potential infinite loops if your parser follows the wrong rule and doesn't backtrack effectively.

Whereas with a Pratt Parser, you need just three rules and three binding powers: null denotation of Variable => Node::Simple(token); left denotation of Add => Node::Composite(token: token, children: vec![node, parser.parse_expr(5)]); left denotation of Mul => Node::Composite(token: token, children: vec![node, parser.parse_expr(10)]); lbp of Variable = 0; lbp of Add = 5; lbp of Mul = 10;

And now it will correctly associate 'b' and 'c' tokens with the mul operator, and then the result of that with the 'a' token and the add operator.

It also executes with far fewer parse calls, creating a minimal stack depth during execution.

Example

fn main() {
    let mut spec = ParserSpec::new();
 
    add_null_assoc!(spec,  
        PrecedenceLevel::Root, 
        ("a".to_string(), "b".to_string(), "c".to_string(),)
        => |_, tk: String, _|{
            Ok(Node::Simple(tk.clone()))
    });
    spec.add_left_assoc(
        "+".to_string(), 
        PrecedenceLevel::First, 
        |parser, token, lbp, node| {
            Ok(Node::Composite{token: token.clone(), children: vec![
                node, 
                parser.parse_expr(lbp)?]})
    });
    spec.add_left_assoc(
        "*".to_string(), 
        PrecedenceLevel::Second, 
        |parser, token, lbp, node| {
            Ok(Node::Composite{token: token.clone(), children: vec![
                node, 
                parser.parse_expr(lbp)?]})
    });
 
    let lexer = LexerVec::new(vec![
        "a".to_string(), 
        "+".to_string(), 
        "b".to_string(), 
        "*".to_string(), 
        "c".to_string()
    ]);
 
    let mut parser = GeneralParser::new(spec, lexer);
 
    let res = parser.parse();
    println!("{:?}", res);
}

Capabilities

This crate enables a very fast and simple parser, with simple rules, that is easy to understand and maintain. Most of the work is in implementing the required traits on your Token type.

More complex examples

Run:

cargo run --example token_spec

examples/token_spec.rs shows an example of how to implement the traits for the token type so it can be used to lookup the parse rules (uses HashMap).

Citations

[1] Vaughan R. Pratt. 1973. Top down operator precedence. In Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '73). ACM, New York, NY, USA, 41-51. DOI=http://dx.doi.org/10.1145/512927.512931

Modules

errors	Errors Module
lexer	Lexer trait and simple implementation
macros	Utility Macros
node	Node enum
parser	Parser
precedence
spec	ParserSpec

Macros

add_left_assoc
add_left_right_assoc
add_null_assoc