I think I have an unhealthy obsession with parsing, I've overhauled the Heron parsing engine yet again, in the latest release of the Heron interpreter. 

Recently I decided to rewrite the Heron grammar so that it was more compact and elegant. The core change is that rules are now fields rather than functions.  What is  exciting me about the new grammar, is that I find it extremely compact and easy to modify.

Here is a sample of the new grammar taken from the recent 0.6 release of Heron :

public static Rule Field = Store("attribute", (Name + NoFail(Opt(TypeDecl) + Eos)));

public static Rule FunDecl = Store("fundecl", Name + ArgList + Opt(TypeDecl));

public static Rule EOSOrCodeBlock = Eos | CodeBlock;

public static Rule Method = Store("method", FunDecl + NoFail(EOSOrCodeBlock));

You can browse the full grammar online http://code.google.com/p/heron-language/source/browse/trunk/HeronEngine/HeronGrammar.cs.

One of the reasons I have been so obsessed with the Heron parsing engine, is that I am hoping that others with an interest in parsing and writing interpreters using C#, could reuse the code from Heron in their own projects, as-is or with modifications.   

To help achieve this goal, I'm going to try an explain how the parser works in a bit more detail.

How the Heron Parser Works

The Heron parsing engine is a recursive-descent  PEG  parser. The basic idea of a recursive descent PEG parser is similar to a parser combinator .  

The core of the Heron parsing engine is the  grammar which consists of a series rules, similar to the grammar production rules of a context free grammar (CFG) in Backus-Naur Form (BNF). However,  rather than describing how to generate valid strings in the language (like a BNF) these rules describe how to recognize valid strings in the language. This is essentially what a parsing expression grammar (PEG) is. 

A parsing rule (represented by the Rule class) is made up of other parsing rules combined using operators. The most common operators are the sequence operator (expressed using +) and the choice operator (expressed using |).  

A rule's main role is to provide an implementation of a Match() function. The Match() function takes an object, of type ParserState, which contains the input string and an index representing the current position. A Match() function returns true and advances the index of the ParserState if it succesfully matches the string in its input. If a Match() function fails, it generally restores the input index, to its previous position. 

If two rules are combined, for example using the sequence operator, then a new rule is created (for example the SeqRule). The SeqRule succeeds and advances the input position if all of it's sub-rules succeed in order. A similar process works for choice operators and ChoiceRules. The different RuleTypes in Heron are contained in the file PegRuleTypes.cs . 

In addition to rules and operators, Heron grammars can also contain actions. An action combines a rule and an action (but still derives from Rule). There are two common actions: the NoFail() action which throws an exception if its rule fails to match, and the Store() action which if matched will create a new node in the parse tree. The parse tree is managed by the ParserState object.