Channels ▼

Christopher Diggins

Dr. Dobb's Bloggers

A new release of Heron and an update of the Parsing Engine

October 18, 2009

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

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. 




Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.