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.
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.
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:
(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
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
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
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).
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
Ops.Seq( Prims.Digit, Ops.Start( Ops.Seq(Prims.Ch(','), Prims.Digit)))
Prims.Ch('x') will math the character
Prims.Ch(',') will match a comma. In this case, the Kleene star matches a more complex expression, namely
which matches a sequence of comma and digit.
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 s = "1,2,3,4";
Parser p = Ops.Seq(...);
StringScanner scan = new StringScanner(s);
ParserMatch m = p.Parse(s);
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
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... :
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.
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
public class MyActor
ArrayList digits; ...
public void RecordDigit(Object sender, ActionEventArgs args)
digits.Add( args.TypedValue );
Then, we add a digit recorder handler to each digit parser:
MyActor a = new MyActor();
Parser d = Prims.Digit;
d.Act += new ActionEventHandler( a.RecordDigit );
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.
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.
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:
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 parsers can be used to combine parsers, like sequence and star in the example. The
Ops class can be used to create such parsers.
ParserMatch class describes the parser match.
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.
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.
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:
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) |
In the above,
expression are Rule object that have been previously initliazed:
group = new Rule();
Note also, that the
| operator can be overriden in C#, therefore we use it to create an alternative parser.
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:
debug = new Debugger( Console.Out );
group.ID = "group";
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:
There are still a lot of features from Spirit that are not implemented in Spart:
- numeric parsers!
- parsers: list_p, confix_p
- dynamic rules,
Jonathan de Halleux is Civil Engineer in Applied Mathematics. He finished his PhD in 2004 in the rainy country of Belgium. After 2 years in the Common Language Runtime (i.e. .net), he is now working at Microsoft Research on Pex (http://research.microsoft.com/pex).