Crate gramatica

This crate provides a binary to compile grammars into Rust code and a library implementing Earley's parsing algorithm to parse the grammars specified.

Usage

This crate is gramatica. To use it you should install it in order to acquire the gramatica_compiler binary and also add gramatica to your dependencies in your project's Cargo.toml.

[dependencies]
gramatica = "0.1"

Then, if you have made a grammar file example.rsg execute gramatica_compiler example.rsg > example.rs. Afterwards you may use the generated file example.rs as a source Rust file.

Example: calculator

The classical example is to implement a calculator.

extern crate gramatica;
use std::cmp::Ordering;
use std::io::BufRead;
use gramatica::{Associativity,EarleyKind,State,Parser,ParsingTablesTrait,AmbiguityInfo};

re_terminal!(Num(f64),"[0-9]*\\.?[0-9]+([eE][-+]?[0-9]+)?");
re_terminal!(Plus,"\\+");
re_terminal!(Minus,"-");
re_terminal!(Star,"\\*");
re_terminal!(Slash,"/");
re_terminal!(Caret,"\\^");
re_terminal!(LPar,"\\(");
re_terminal!(RPar,"\\)");
re_terminal!(NewLine,"\\n");
re_terminal!(_,"\\s+");//Otherwise skip spaces

nonterminal Input(())
{
    () => (),
    (Input,Line) => (),
}

nonterminal Line(())
{
    (NewLine) => (),
    (Expression(value), NewLine) =>
    {
        println!("{}",value);
    },
}

nonterminal Expression(f64)
{
    (Num(value)) => value,
    #[priority(addition)]
    #[associativity(left)]
    (Expression(l),Plus,Expression(r)) => l+r,
    #[priority(addition)]
    #[associativity(left)]
    (Expression(l),Minus,Expression(r)) => l-r,
    #[priority(multiplication)]
    #[associativity(left)]
    (Expression(l),Star,Expression(r)) => l*r,
    #[priority(multiplication)]
    #[associativity(left)]
    (Expression(l),Slash,Expression(r)) => l/r,
    #[priority(addition)]
    #[associativity(left)]
    (Minus,Expression(value)) => -value,
    #[priority(exponentiation)]
    #[associativity(right)]
    (Expression(l),Caret,Expression(r)) => l.powf(r),
    (LPar,Expression(value),RPar) => value,
}

ordering!(exponentiation,multiplication,addition);

fn main()
{
    let stdin=std::io::stdin();
    for rline in stdin.lock().lines()
    {
        let line=rline.unwrap()+"\n";
        println!("line={}",line);
        match Parser::<Token,ParsingTables>::parse(&line,None)
        {
            Err(x) => println!("error parsing: {:?}",x),
            Ok(x) => println!("parsed correctly: {:?}",x),
        };
    }
}

Advanced Lexer

To define terminal tokens not expressable with regular expressions you may use the following.

terminal LitChar(char)
{
    fn _match(parser: &mut Parser<Token,ParsingTables>, source:&str) -> Option<(usize,char)>
    {
        let mut characters=source.chars();
        if (characters.next())==(Some('\''))
        {
            let mut c=characters.next().unwrap();
            let mut size=3;
            if c=='\\'
            {
                c=(characters.next().unwrap());
                size=4;
            }
            if characters.next().unwrap()=='\''
            {
                Some((size,c))
            }
            else
            {
                None
            }
        }
        else
        {
            None
        }
    }
}

Since version 0.1.0 there is also a keyword_terminal! macro:

keyword_terminal!(Const,"const");

Parsing values as match clauses

Each rule is written as a match clause, whose ending expression is the value that the nonterminal token gets after being parsed. For example:

nonterminal Stmts(Vec<StmtKind>)
{
    (Stmt(ref stmt)) => vec![stmt.clone()],
    (Stmts(ref stmts),Stmt(ref stmt)) =>
    {
        let mut new=(stmts.clone());
        new.push(stmt.clone());
        new
    },
}

Reductions only execute if they are part of the final syntactic tree.

Precedence by annotations

To avoid ambiguities you have two options: to ensure the grammar does not contain them or to priorize rules by introducing annotations. In the example of the calculator we have seen two kinds: - #[priority(p_name)] to declare a rule with priority p_name. Later there should be a ordering!(p_0,p_1,p_2,...) macro-like to indicate that p_0 should reduce before p_1. - #[associativity(left/right)] to decide how to proceed when nesting the same rule.

Structs

AmbiguityInfo
Parser
State
StateSet

Enums

Associativity
EarleyKind
ParsingError

Traits

ParsingTablesTrait