Mouse: from Parsing Expressions to a practical parser

Version 1.5.1

Parsing Expression Grammar (PEG) is a new way to specify recursive-descent parsers with limited backtracking. The use of backtracking lifts the LL(1) restriction usually imposed by top-down parsers. In addition, PEG can define parsers with integrated lexing.
An example of PEG: 

Sum     = Space Sign Number (AddOp Number)* !_ {sum} ;
Number  = Digits? "." Digits Space {fraction}
        / Digits Space {integer} ;
Sign    = ("-" Space)? ;
AddOp   = [-+] Space ;
Digits  = [0-9]+ ;
Space   = " "* ;

Mouse is a tool to transcribe PEG into an executable parser written in Java. Unlike some existing PEG generators (e.g., Rats!), Mouse does not produce a storage-hungry "packrat parser", but a collection of transparent recursive procedures.
An example of parsing procedure generated by Mouse: 

//=====================================================================
//  Sum = Space Sign Number (AddOp Number)* !_ {sum} ;
//=====================================================================
private boolean Sum()
  {
    begin("Sum");
    Space();
    Sign();
    if (!Number()) return reject();
    while (Sum_0());
    if (!aheadNot()) return reject();
    sem.sum();
    return accept();
  }

An integral feature of Mouse is the mechanism for specifying semantics (also in Java). This makes Mouse a convenient tool if one needs an ad-hoc language processor. Being written in Java, the processor is operating-system independent.
An example of semantic procedure: 

//-------------------------------------------------------------------
//  Sum = Space Sign Number AddOp Number ... AddOp Number
//          0     1    2      3     4         n-2   n-1
//-------------------------------------------------------------------
void sum()
  {
    int n = rhsSize();
    int s = (Double)rhs(2).get();
    if (!rhs(1).isEmpty()) s = -s;
    for (int i=4;i<n;i+=2)
    {
      if (rhs(i-1).charAt(0)=='+')
        s += (Double)rhs(i).get();
      else
        s -= (Double)rhs(i).get();
    }
    System.out.println(s);
  }

Download user's manual / tutorial (PDF file).
Download the complete package (gzipped TAR file).

License: Apache Version 2.
 

Parsing Expression Grammar for Java 1.6

Based on Chapters 3 and 18 of Java Language Specification, Third Edition, with corrections based on other chapters and test results.

It is an updated version of the grammar used for experiments described in the paper Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking.

Download the grammar in Mouse format (text file).
 

Parsing Expression Grammar for Java 1.7

A preliminary version obtained by modifications to Java 1.6 grammar based on the document Enhancements in Java SE 7, analysis of JavacParser code and pure guesswork (no formal syntax definition has been published so far.)

Download the grammar in Mouse format (text file).
 

Parsing Expression Grammar for C

Based on ISO/IEC 9899.1999:TC2 standard without preprocessor directives,
meaning that it applies to preprocessed C source.

It is the grammar used for experiments described in the paper Some aspects of Parsing Expression Grammar. It has been tested against 100 preprocessed C files from different open source projects.

The typedef feature makes the syntax of C context-dependent, which cannot be expressed in PEG formalism. The problem is solved by semantic actions provided together with the grammar.

Download the grammar in Mouse format (text file).
Download semantic actions for the grammar (Java source).
 

Latest change 2012-01-06