PEG Parser in Java

PEG Parser on

Parsing Expression Grammar is "an alternative, recognition-based formal foundation for describing machine-oriented syntax" to generative system of grammars, like context-free grammars and regular expressions.

It is simple to learn and use, and I find it very handy for small to medium grammars that I want to be able to read, comprehend and maintain manually. It's also farily good for parsing small-ish amounts of source text, like single line expressions or DSL source code of up to a few hundred lines of code. All this does not mean you can't use it for more than that, it's just that I haven't and so I can't really claim anything beyond limits stated above.

All that being said, I quite like it, and when the need arised for implementing a parser for a small DSL for a project, I did it in Haxe (because the project was in Haxe). Fast forward years later to today, I decided to port that Haxe source code to Java, which turned out to be a simple and straightforward task, thanks to the Haxe language syntax which draws its roots from ActionScript and JavaScript.

The peg-parser Java library allows you to define your PEG-based grammar in either open text source or in Java code. Once defined, you can then use an instance of the grammar and apply it to source text you want to parse. If all goes well (no syntax errors) this produces abstract syntax tree of the source text, which you can then inspect and do what ever it is you need to do in your Java application or library.

There are also a few utility classes, like Parser class, you can use to shorten the amount of boilerplate code.

PEG is known for its not ideal suitability for syntax error reporting and paring error recovery, among other things (like i.e. parsing speed being affected by need to backtrack a lot in large or badly specified grammars).

This library includes a syntax error report either in a form of a Java record containtin error information, or in a form of a human-readable error message. Syntax error is reported for the longest recognized grammar chain which, while it may or may not be an exact place of the error, provides the best guess of where the error may be, since it is the case where parser consumes most of the source tex.

That is the only enhancement, if you will, provided by this Java library, there is no implementaion of parsing error recovery, which means parsing will stop with the first error and that is the only reported error, nor are there any parsing optimizations implemented, like for example using memoization. So, this library is not the ulitmate champion of PEG parsers, but it is usable, as previously said, for mini and small source texts, i.e. one-line expressions or small sections of DSL source.

And that's pretty much it.

For more details on how to use the library you can check out the library's repository README, and here you can find just a...

Few quick examples

A very simple PEG definition:

Grammar <- Typespec Eof
Typespec <- "int" / "bool" / "float"
Eof <- !.

can be defined in source using Peg utility class like so:

var eof = Peg.Definition(
  "Eof", Peg.Not( Peg.Any( "end of text" ) )
);
var typespec = Peg.Definition(
  "Typespec", Peg.Choice(List.of(
    Peg.Literal( "int" ),
    Peg.Literal( "bool" ),
    Peg.Literal( "float" )
  ))
);
var grammar = Peg.Definition(
  "Grammar", Peg.Sequence(List.of(
    typespec, eof
  ))
);

Then, you need an AST root node to attach the generated abstract syntax tree to, and you need an instance of SourceScanner:

var source = "bool";
var ast = new ASTNode( "ROOT" );
var scanner = new SourceScanner( source );

To parse a source text, you call apply() method on the grammar which returns true if parisng succeeds:

if( ! grammar.applyTo( scanner, ast ) ) {
  // syntax_error_info is for your code to consume, and...
  System.out.println( scanner.syntax_error_info() );
  // ...syntax_error_message is human-readable form of the above info
  System.out.println( scanner.syntax_error_message() );
} else {
  // you can do this, which
  // prints the ROOT node too...
  // ast.print( System.out );

  // ...or you can do this,
  // which prints the tree starting
  // with the "Grammar" node,
  // which is the first (and only)
  // child of the ROOT and
  // which is what we actually need
  ast.nodes.get( 0 ).print( System.out );
}

Running above code will produce this output:

Grammar  [1:1 - 1:4]
  Typespec  [1:1 - 1:4]
    #PegLiteralString : 'bool'  [1:1 - 1:4]
  Eof

which is printout of this AST:

Grammar
  +-- Typespec
  |   +-- LiteralString : 'bool'
  +-- Eof

You can also define your PEG via source and use the Parser utility class like so:

var grammar = """
Grammar <- Typespec Eof
Typespec <- "int" / "bool" / "float"
Eof <- !.
""";
try {
  var parser = Parser.fromSource( grammar );
} catch ( ParserSyntaxError ex ) {
  ex.printStackTrace();
}

and then you can parse a source text that this grammar recognizes using the Parser.parse() method:

try {
  var parser = Parser.fromSource( grammar );
  var source = "int";
  var ast = parser.parse( source );
  ast.print( System.out );
} catch ( ParserSyntaxError ex ) {
  ex.printStackTrace();
}

The library also provides two grammar rule definition modifiers:

• @ - "squash" modifier
• ~ - "reduce" modifier

and the ASTNode.prune() method, all of which help with managing overgrown abstract syntax trees.

For more details on that too, check out the library's repository README.