Eto.Parse

A recursive descent LL(k) parser framework for .NET

Links

• Chat in picoe/Eto on gitter
• Download using nuget

Description

Eto.Parse is a highly optimized recursive decent parser framework that can be used to create parsers for context-free grammars that go beyond the capability of regular expressions.

You can use BNF, EBNF, or Gold Meta-Language grammars to define your parser, code them directly using a Fluent API, or use shorthand operators (or a mix of each).

Why not use RegEx?

Regular Expressions work great when the syntax is not complex, but fall short especially when dealing with any recursive syntax using some form of brackets or grouping concepts.

For example, creating a math parser using RegEx cannot validate (directly) that there are matching brackets. E.g. "((1+2)*3)", or "{ 'my': 'value', 'is' : {'recursive': true } }"

Matching

The framework has been put together to get at the relevant values as easily as possible. Each parser can be named, which then builds a tree of named matches that represent the interesting sections of the parsed input. You can use events on the named sections to perform logic when they match, or just parse the match tree directly.

Left Recursion

One rather cumbersome issue to deal with using recursive descent parsers is left recursion. Eto.Parse automatically identifies left recursive grammars and transforms them into a repeating pattern.

Performance

Eto.Parse has been highly optimized for performance and memory usage. For example, here's a comparison parsing a large JSON string 1000 times (times in seconds):

Speed

Test | Parsing | Slower than best | Warmup | Slower than best ----------------- | ------: | :--------------: | ------: | :--------------: Eto.Parse | 2,327s | 1,00x | 0,008s | 1,00x Newtonsoft Json | 2,523s | 1,08x | 0,068s | 8,08x ServiceStack.Text | 2,854s | 1,23x | 0,066s | 7,78x Irony | 25,401s | 10,92x | 0,188s | 22,28x bsn.GoldParser | 11,186s | 4,81x | 0,013s | 1,49x NFX.JSON | 11,847s | 5,09x | 0,187s | 22,10x SpracheJSON | 92,774s | 39,88x | 0,189s | 22,37x

(Warmup is the time it takes to initialize the engine for the first time and perform the first parse of the json string).

Memory & Objects

Framework | Allocated | More than best | # Objects | More than best ---------------- | ----------: | :------------: | --------: | :------------: Eto.Parse | 553.99 MB | 1.00x | 15268050 | 1.00x Newtonsoft.Json | 1,074.27 MB | 1.94x | 21562432 | 1.41x ServiceStack.Text| 2,540.91 MB | 4.59x | 15738493 | 1.03x Irony | 4,351.44 MB | 7.85x | 94831118 | 6.21x bsn.GoldParser | 2,012.16 MB | 3.63x | 74387176 | 4.87x

Example

For example, the following defines a simple hello world parser in Fluent API:

// optional repeating whitespace
var ws = Terminals.WhiteSpace.Repeat(0);

// parse a value with or without brackets
var valueParser = Terminals.Set('(')
	.Then(Terminals.AnyChar.Repeat().Until(ws.Then(')')).Named("value"))
	.Then(Terminals.Set(')'))
	.SeparatedBy(ws)
	.Or(Terminals.WhiteSpace.Inverse().Repeat().Named("value"));

// our grammar
var grammar = new Grammar(
	ws
	.Then(valueParser.Named("first"))
	.Then(valueParser.Named("second"))
	.Then(Terminals.End)
	.SeparatedBy(ws)
);

Or using shorthand operators:

// optional repeating whitespace
var ws = -Terminals.WhiteSpace;

// parse a value with or without brackets
Parser valueParser = 
	('(' & ws & (+Terminals.AnyChar ^ (ws & ')')).Named("value") & ws & ')')
	| (+!Terminals.WhiteSpace).Named("value");

// our grammar
var grammar = new Grammar(
	ws & valueParser.Named("first") & 
	ws & valueParser.Named("second") & 
	ws & Terminals.End
);

Or, using EBNF:

var grammar = new EbnfGrammar().Build(@"
(* := is an extension to define a literal with no whitespace between repeats and sequences *)
ws := {? Terminals.WhiteSpace ?};

letter or digit := ? Terminals.LetterOrDigit ?;

simple value := letter or digit, {letter or digit};

bracket value = simple value, {simple value};

optional bracket = '(', bracket value, ')' | simple value;

first = optional bracket;

second = optional bracket;

grammar = ws, first, second, ws;
", "grammar");

These can parse the following text input:

var input = "  hello ( parsing world )  ";
var match = grammar.Match(input);

var firstValue = match["first"]["value"].Value;
var secondValue = match["second"]["value"].Value;

firstValue will equal "hello", and secondValue will equal "parsing world".

License

Licensed under MIT.

See LICENSE file for full license.