Spart, a parser generator framework 100% C#

• Download source files - 73 Kb
• Download demo project - 125 Kb

Note: If you like this tool please remember to vote, as this will get other people interested and is more likely to help improve the final product
-- ToDoList organizer, Dan.G.

Introduction

The Spart library an object oriented recursive descent parser generator framework implemented in C#. In fact, it is a partial port of the excellent Spirit library, which is written in C++ and uses meta-programming.

The Spart framework enables a target grammar to be written exclusively in C#. An EBNF grammar can be closely match using C# code. In retrospect, conventional compiler-compilers or parser-generators have to perform an additional translation step from the source EBNF code to C or C++ code.

I have takened the liberty to use the structure (and some sentence) of the Spirit documentation. Along the article, some notes are added regarding some issues about the port to C#: Spirit-2-Spart Notes (SSN).

As always, this article presents an overview of the library. For deeper details, please refer to the NDoc documentation. The library also comes with a battery of NUnit tests.

Quick Start

Spart is designed to bring you parser capabilites quickly directly into your code. While it is not suited for creating parsers for entire language like C,C++, it is very effective for building micro-grammars in your code.

When you need to build a new parser, there are existing solution: a combination of ....Parse (like int.Parse) calls, or using regular expression (Regexp class) or a combination of both. However, these tools do not scale well when attempting to write more complex parsers: maintenance and readability become ackward.

So, as for Spirit, one of the main objective of Spart is to let you build easily grammar in C#. To fix this ideas, a few simple grammars illustrate Spart usage:

Trivial example #1:

Create a parser that will parse a digit:

Prims.Digit

(This is a trivial case, Char.IsDigit already does that). Prims is a static class, Digit is a property that create a new parser for digits. In fact, Prims is a helper class that creates primitive parsers for you and hides implementation details.

SSN: This parser is equivalent to num_p.

Trivial example #2:

Create a parser that will parse a sequence of two digits

Ops.Seq( Prims.Digit, Prims.Digit )

Here you see the familiar Prims.Digit parser enclosed in a Ops.Seq call. Like Prims, Ops is a static helper class that creates combine parsers for you. The Seq method creates a parser that is a sequence of two parsers (>> in Spirit):

Ops.Seq(a,b) <=> match a and b in sequence

Note: when we combine parsers, we end up with a "bigger" parser, But it's still a parser. Parsers can get bigger and bigger, nesting more and more, but whenever you glue two parsers together, you end up with one bigger parser. This is an important concept.

SSN: The operator >> does not accept arbitrary operands, they must be of integral type which restrict it's use.

Trivial Example #3

Create a parser that will accept an arbitrary number of digit. (Arbitrary means anything from zero to infinity).

Ops.Star(Prims.Digit)

This is like the regular expression Kleene Star.

SSN: * cannot be an unary operator in C#.

Less trivial example #4

Create a parser that parse a sequence of comma separated digits and record them in a collection (note this can easily be done using String.Split).

// spirit: num_p >> *( ch_p(',') >> num_p)
Ops.Seq( Prims.Digit, Ops.Start( Ops.Seq(Prims.Ch(','), Prims.Digit)))

Note that Prims.Ch('x') will math the character x. Prims.Ch(',') will match a comma. In this case, the Kleene star matches a more complex expression, namely

Ops.Seq(Prims.Ch(','), Prims.Digit)

which matches a sequence of comma and digit.

Note: the Ops.Sep(Prims.Ch(','),... expression can be simplified to Ops.Seq(',', ... to simplify notations.

Using the parser

Once we have built our parser, we want to use it. A parser can be used directly as is:

// string to parser
String s = "1,2,3,4";
// creating the parser as above
Parser p = Ops.Seq(...);
// creating a scanner of the string
StringScanner scan = new StringScanner(s);
// parsing the string through the scanner
ParserMatch m = p.Parse(s);

Notes:

• Parser is an abstract base class for all parsers. It contains the Parse method that can be used to parse some input.
• The parser does not work directly on string but rather on some modified stream (scanners). Therefore, it is possible to parse directly from files or stream. StringScanner implements the scanner interface and wraps the string s.
• ParserMatch is the parser result (see below)

Now that we have parsed the text, the ParserMatch object can help answer questions like: was the match successful, what was the match value, etc... :

if (m.Success)
    Console.Write("successfull match!");

Semantic Actions

Our parser above is nothing but a recognizer, it does no take any actions. It answers "did our data match the grammar?" but it does not record anything. Remember that we wanted to record the digits into a collection. For example, whenever we parse a digit, we wish to store the parsed number after a successful match. We now wish to extract information from the parser. Semantic actions do this. Semantic actions may be attached to any point in the grammar specification. They through events and event handler.

The Parser class has an event, Act, that is called on a successful match. We need to add a event handler on the Prims.Digit parser that records the digit into a collection. First, we write an actor that will record the digits

// A digit recorder actor
public class MyActor
{
    ArrayList digits; // digits collection
    ...
    public void RecordDigit(Object sender, ActionEventArgs args)
    {
        // record the digit into the digits collection
        digits.Add( args.TypedValue );
    }
}

Then, we add a digit recorder handler to each digit parser:

MyActor a = new MyActor();

// digit parser
Parser d = Prims.Digit;
// register actor
d.Act += new ActionEventHandler( a.RecordDigit );

// create parser
Parser p = Ops.Seq( d, Ops.Start( Ops.Seq(',', d)));

This is the same parser as above but now, MyParser.RecordDigit is called on each successfull digit match and therefore, the collection is filled.

Basic concepts

Spart follows the concepts of Spirit. There are a few fundamental concepts that need to be understood well: 1) The Parser, 2) the Match, 3) The Scanner, and 4) Semantic Actions. These basic concepts interact with each other, and the functionalities of each interweave throughout the entire framework to make it one coherent whole.

I will go quickly over those concepts since they are very well explained in the Spirit documentation and I recommend you take a look there first.

The parser

Central to the framework is the parser. The parser does the actual work of recognizing a linear input stream of data read sequentially from start to end by the scanner. The parser attempts to match the input following a well-defined set of specifications in the form of grammar rules. The parser reports the success or failure to its client through a match object. When successful, the parser calls a client-supplied semantic action. Finally, the strategically-placed semantic action extracts structural information depending on the data passed to it by the parser and the heirarchical context of the parser it is attached to.

Parsers come in a lot of flavors and usually you don't need to write your own parser. Spart has a collection of built-in parsers that you can combine to create your grammars. The built-in parsers come in two (main) flavors:

Primitives

Primitive parsers can be used to match characters, string, lower case character, digits, etc... The Prims class can be used to create such parsers.

Combination

Combination parsers can be used to combine parsers, like sequence and star in the example. The Ops class can be used to create such parsers.

The match

The ParserMatch class describes the parser match.

The Scanner

Like the parser, the scanner is also an abstract concept, represented by the IScanner interface. The task of the scanner is to feed the sequential input data stream to the parser. The scanner is of an input source and a cursor. The cursor is moved along by the parsers. Parsers extract data from the scanner and position the iterator appropriately through its member functions.

Semantic actions

A composite parser forms a hierarchy. Parsing proceeds from the topmost parent parser which delegates and apportions the parsing task to its children recursively to its childeren's children and so on until a primitive is reached. By attaching semantic actions to various points in this hierachy, in effect we can transform the flat linear input stream into a structured representation. This is essentially what parsers do.

The Rule

The Rule class represents a non-terminal parser. Basically, it is a wrapper around another parser. This aspect will be illustrated in the example below.

The Classic Calculator Example

There is still a lot to say about Spirit and Spart but I will cut to a final example. A better documentation should appear in a near future as this library is totally new!

The favorite grammar example in the Spirit documentation is a calculator grammar:

• EBNF:

  group       ::= '(' expression ')'
  factor      ::= integer | group
  term        ::= factor (('*' factor) | ('/' factor))*
  expression  ::= term (('+' term) | ('-' term))*

• Spirit (C++):

  group       = '(' >> expression >> ')';
  factor      = integer | group;
  term        = factor >> *(('*' >> factor) | ('/' >> factor));
  expression  = term >> *(('+' >> term) | ('-' >> term));

Let us now show how to build this grammar with Spart (you can find in the demo applciation). Passing aside some initialization details, the C# code would look as follows:

group.Parser       = Ops.Seq('(',Ops.Seq(expression,')'));
factor.Parser      = integer | group;
term.Parser        = Ops.Seq( factor, Ops.Klenee( 
                        Ops.Seq('*',factor) | Ops.Seq('/',factor) ));
expression.Parser  = Ops.Seq(term,Ops.Klenee(Ops.Seq('+',term) | 
                        Ops.Seq('-',term) ))

In the above, group, factor, term and expression are Rule object that have been previously initliazed:

// declaration 
Rule group; 
...
group = new Rule();

Note also, that the | operator can be overriden in C#, therefore we use it to create an alternative parser.

Debugging

It can be usefull to trace the scanner state and the parser matches. Similarly to Spirit, you can attach a tracer that will output a lot of interresting info:

// declaration in the Calculator class
Debugger debug;
...
// in the constructor
// create a debugger that outputs to the console
debug = new Debugger( Console.Out ); 

// setting rules name for debugging purpose
group.ID = "group"; 
...

// tracing rules
debug += group;
debug += expression;
...

The output is formated as follows:

• the output is indented to reflect the parser tree,
• parser name: ... reflects the start of the parsing and the current scanner input
• / parser name: ... reflects that the parser has successfully mathed
• # parser name: ... reflects that there was not mathch.

For example, when launching the parser on the string (5+2)*(4*2), it will output something like this:

expression: (5+2)*(4*2)
    term: (5+2)*(4*2)
        factor: (5+2)*(4*2)
            group: (5+2)*(4*2)
                expression: 5+2)*(4*2)
                    term: 5+2)*(4*2)
                        factor: 5+2)*(4*2)
                            group: 5+2)*(4*2
                            #group: 5+2)*(4*
                            integer: 5+2)*(4
                            /integer: +2)*(4
                        /factor: +2)*(4*2)
                    /term: +2)*(4*2)
                    term: 2)*(4*2)
                        factor: 2)*(4*2)
                            group: 2)*(4*2)
                            #group: 2)*(4*2)
                            integer: 2)*(4*2
                            /integer: )*(4*2
                        /factor: )*(4*2)
                    /term: )*(4*2)
                /expression: )*(4*2)
            /group: *(4*2)
        /factor: *(4*2)
        factor: (4*2)
            group: (4*2)
                expression: 4*2)
                    term: 4*2)
                        factor: 4*2)
                            group: 4*2)
                            #group: 4*2)
                            integer: 4*2)
                            /integer: *2)
                        /factor: *2)
                        factor: 2)
                            group: 2)
                            #group: 2)
                            integer: 2)
                            /integer: )
                        /factor: )
                    /term: )
                /expression: )
            /group:
        /factor:
    /term:
/expression:

ToDo List

There are still a lot of features from Spirit that are not implemented in Spart:

• numeric parsers!
• closures,
• directives,
• parsers: list_p, confix_p
• dynamic rules,
• etc...

References

• Boost, http://boost.sourceforge.net/
• Spirit, http://spirit.sourceforge.net/