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: