Creating a Domain Specific Language for Parsing
dotnet, geek, insanity, programming, tech May 15th, 2008It’s with some trepidation that I start on what is sure to be the most geeky post I’ve created to date. First a little background. I thought it would be a worth-while exercise to create a view engine for the Asp.Net Mvc framework. This is a result of a series of comments I took part in on Haack’s blog post about using lambdas from aspx.
The specific comment I made was in response to a green-field question about what an ideal view engine would look like in your mind. For me, based on my experience with NVelocity and the MVC pattern in MonoRail, the less you put in the view the better and a simplistic view language is actually a strength because it encourages that.
I’ve also had some difficulty working with aspx as text because what you have are two formats, csharp and xml, both of which have a natural flow and indentation which can’t coexist peacefully. Angles, percents, and curly braces become a disordered chaos where nothing lines up rationally. (Readability is vital to maintainability.)
So I proposed something like the following.
<var i="0"/>
<var css="new string[] {'row', 'row-alt'}"/>
<table>
<for each="var hobby in Hobbies" i="i+1">
<tr class="$css[i%2];">
<td>$i;</td>
<td>$hobby.Title;</td>
<td>$Html.Function("arg","arg");</td>
</tr>
</for>
</table>
See, the theory is you use the same syntactical conventions for both markup and code and they’ll no longer fight each to dominate the file format. It’s very zen. And the editor’s normal assistance with colorization and indentation of xml helps you close loops, represent scope, etc. Since I’m the sort of person who feels he should put his brain where his mouth is, e.g. a fool or a masochist, I set out to implement exactly such a view engine.
I should mention before going further that the source for this post can be downloaded in zip format, or you can use svn and the trac site.
The first step goes swimmingly, the Asp.Net Mvc libraries are very extensible and the MvcContrib Nhaml view engine is an excellent example of how to organize such a thing. Then I hit the point which is the inspiration for this post. Parsing the view file! I believe from the beginning this will not be a “well formed” xml grammar so using an existing xml parser is a shortcut that’s out of the question. For example if you have something as simple as an if-else construct you’ll never be able to keep the resulting start and end elements matching each other.
<!--normal xml parser won't like this file -->
<div>
<if cond="i<3">
<p class="topthree">
</if>
<else>
<p class="normal">
</else>
$yadda;
</p>
</div>
So I search the internet for some parser theory. I’ve written parsers before but I felt a little light reading upfront would save some time and thrashing down the road. It’s also mainly a learning exercise so I have no interest in putting more work than it takes into the code.
I couldn’t find a parser compiler for dotnet, which is fine, but I did find an excellent write-up on Parsing expression grammar on wikipedia. It provides an solid mental model and vocabulary around the concept of creating a parser. It also addresses a key problem of the brute force or regex parsing approach: context. If you have <span>$i<0?”foo”:”bar”;</span> in a file the rule “less-than-starts-an-element” doesn’t apply within a rule “dollar-blah-semicolon-is-code” range. Plus a dollar-blah-semicolon can appear inside the text of an attribute. All told this problem is way out of regular expression’s league.
So that’s all fine and good but it still takes a practical implementation of a PEG to move forward. I implemented a few abstract classes to act as the base of a parsing rule engine. Then I strike gold at Luke H’s weblog. Monadic Parser Combinators using C# 3.0.
And so inspired we are finally to the place where I can start talking about the subject of this post! Creating a language for the specific domain of declaring a parser grammar! First we start with a delegate declaration and it’s return type.
public delegate ParseResult<TValue> ParseAction<TValue>(Position position);
public class ParseResult<TValue>
{
private readonly Position _rest;
private readonly TValue _value;
public ParseResult(Position rest, TValue value)
{
_rest = rest;
_value = value;
}
public Position Rest
{
get { return _rest; }
}
public TValue Value
{
get { return _value; }
}
}
You’ll notice I differ from Luke’s example already in that I’m using the actual class Position instead of the generic parameterized type TInput. I figure I’ll be having enough problems without trying to introduce the idea of a type-agnostic input stream.
A delegate is a reference to a method which can be invoked, and it is used as a type of a variable. This is a fairly typical construct in many languages to allow function objects to be passed as arguments or stored as member variables to be invoked at appropriate times.
This particular delegate is a single parser designed to take an input position, and if the contents at that position meets the rules expectations it will return a non-null result. That result contains the “value” of whatever type the parser pulled out and the “position” following whatever the parser consumed.
Consider the following example of using a function to declare a parser of any single numeric character.
[TestFixture]
public class GrammarTester
{
public ParseResult<char> ParseDigit(Position input)
{
if (input.Peek() < '0' || input.Peek() > '9')
return null;
return new ParseResult<char>(input.Advance(1), input.Peek());
}
[Test]
public void SimpleDigitExample()
{
// note "myparser" is a variable to a delegated function where
// the value in the result is of type char
ParseAction<char> myparser = ParseDigit;
Position myinput = new Position(new SourceContext("55407"));
// here is where we're invoking the function behind the
// "myparser" variable and the result is stored in the "myresult" variable
ParseResult<char> myresult = myparser(myinput);
Assert.AreEqual('5', myresult.Value);
Assert.AreEqual("5407", myresult.Rest.Peek(4));
}
}
Or we can get rid of the explicit ParseDigit function and assign the variable with an inline delegate.
ParseAction<char> myparser = delegate (Position input)
{
if (input.Peek() < '0' || input.Peek() > '9') return null;
return new ParseResult<char>(input.Advance(1), input.Peek());
};
In fact let’s go one step further and create a new function that takes a character testing rule, a predicate, as an argument and returns an instance of a parser.
public class Grammar
{
public static ParseAction<char> Ch(Func<char, bool> predicate)
{
return delegate(Position input)
{
if (predicate(input.Peek()) == false) return null;
return new ParseResult<char>(input.Advance(1), input.Peek());
};
}
}
Func in this case is a delegate takes a char as an argument and returns a bool. You can see it’s used in the if statement of the new delegate to test the next character at the input position. So we can use Ch(yadda) to create a single-character parser.
So: how is this a domain specific language? It’s not! This is actually a heck of a lot of work to parse a single character. To build a language you’ll need to introduce language and operators that deal with the basics of the domain in question. Based on the stellar example of Luke’s blog entry and the wikipedia description of the operators of a PEG let’s do just that!
Let’s go for an easy one. Given a parser returning type TValue, create another parser which calls it repeatedly as long as it’s returning results. This second parser will return an IList of TValue, and also return the final position after the last valid parse.
public class Grammar
{
public static ParseAction<IList<TValue>> Rep<TValue>(ParseAction<TValue> parser)
{
return delegate(Position input)
{
Position rest = input;
List<TValue> list = new List<TValue>();
var result = parser(input);
while (result != null)
{
list.Add(result.Value);
rest = result.Rest;
result = parser(rest);
}
return new ParseResult<IList<TValue>>(rest, list);
};
}
}
Simple, eh? Rep is now a function that takes a parser of TValue as an argument and returns a new parser of IList<TValue>. Now we’re starting to build some momentum. We can parse entire lengths of characters that pass a given predicate.
[Test]
public void RepeatingCharacters()
{
var parseNumber = Grammar.Rep(Grammar.Ch(char.IsNumber));
Position input = new Position(new SourceContext("123-4567"));
var result = parseNumber(input);
Assert.AreEqual(3, result.Value.Count);
Assert.AreEqual('1', result.Value[0]);
Assert.AreEqual('2', result.Value[1]);
Assert.AreEqual('3', result.Value[2]);
Assert.AreEqual("-4567", result.Rest.Peek(5));
}
Now for a new term: monad. From the definition in wikipedia it’s used in a case where “although a function cannot directly cause a side effect, it can construct a value describing a desired side effect that the caller should apply at a convenient time”. This is seen in the way the Position class is created – the Advance(int count) method returns a new Position instance describing the advanced position but does not modify the existing position class. This new Position is returned as the Rest property of the parser’s result.
The reason this is important is because of the following scenario. This is where several parsers may be invoked in series, but at the end of that series a step may ultimately fail and return null for that particular parser. The net result of this failure is moot because the original Position has not changed, and that position can be used to try additional potentially valid constructs.
This quality enables us to construct the following PEG operators for sequence (And) and ordered choice (Or) situations.
public static ParseAction<TValue> Or<TValue>(
ParseAction<TValue> parser1,
ParseAction<TValue> parser2)
{
return delegate(Position input)
{
var result = parser1(input);
if (result == null) result = parser2(input);
return result;
};
}
If the first parser has returned null it’ll try the second parser using the same input position. The method can also be written using the ?? operator which executes the right-hand expression if the left-hand expression is null.
public static ParseAction<TValue> Or<TValue>(
ParseAction<TValue> parser1,
ParseAction<TValue> parser2)
{
return delegate(Position input)
{
return parser1(input) ?? parser2(input);
};
}
Or if you’re a fan of lambda => syntax it can even be:
public static ParseAction<TValue> Or<TValue>(
ParseAction<TValue> parser1,
ParseAction<TValue> parser2)
{
return input => parser1(input) ?? parser2(input);
}
So that’s what gives you the ordered-choice, and here’s what gives you the sequence (And) operator. Note that in this case the two values parsed may not be of the same type, and both of them must be preserved, so we also introduce a new Chained
public class Chain<TLeft, TDown>
{
private readonly TLeft _left;
private readonly TDown _down;
public Chain(TLeft left, TDown down)
{
_left = left;
_down = down;
}
public TLeft Left
{
get { return _left; }
}
public TDown Down
{
get { return _down; }
}
}
public static ParseAction<Chain<TValue1, TValue2>> And<TValue1, TValue2>(
ParseAction<TValue1> parser1,
ParseAction<TValue2> parser2)
{
return delegate(Position input)
{
var result1 = parser1(input);
if (result1 == null) return null;
var result2 = parser2(result1.Rest);
if (result2 == null) return null;
var value = new Chain<TValue1, TValue2>(result1.Value, result2.Value);
return new ParseResult<Chain<TValue1, TValue2>>(result2.Rest, value);
};
}
Now I agree this is all getting a bit harsh on the noggin, but in a nutshell you call And with two parser delegates as arguments and it returns a new parser delegate which will invoke them in sequence. The advanced position returned by the first parser is used as the input position to the second parser, so they must both succeed back-to-back for this new “and” parser to succeed. And the return value is the chained values of both parsers. So if you have a long line of And rules they’ll build an equally long line of linked values.
So here’s an example
[Test]
public void CompoundAnd()
{
var phoneNumber = Grammar.And(Grammar.And(
Grammar.Rep(Grammar.Ch(char.IsNumber)),
Grammar.Ch(c=>c=='-')),
Grammar.Rep(Grammar.Ch(char.IsNumber)));
Position input = new Position(new SourceContext("123-4567"));
var result = phoneNumber(input);
Assert.AreEqual(3, result.Value.Left.Left.Count);
Assert.AreEqual('-', result.Value.Left.Down);
Assert.AreEqual(4, result.Value.Down.Count);
}
So can this be called a domain specific language? I don’t think so. It’s still virtually impossible to read even the simplest expression. We simply can’t start off any given expression with a bunch of And and Or binary (two argument) functions and rely on exactly correct placement of parenthesis and commas to stitch the logic together.
Fortunately Luke provides us with an example to solve exactly that problem. You can use extension methods to introduce what appear to be new functions onto an existing object type. It’s all just an optical illusion – they’re still really just static functions to the compiler – but it allows you to change something like p = Grammar.And(Grammar.And(p1,p2),p3) into something like p = p1.And(p2).And(p3). So our phone number example starts to look much better.
public static class ParseActionExtensions
{
public static ParseAction<Chain<TValue1, TValue2>> And<TValue1, TValue2>(
this ParseAction<TValue1> parser1,
ParseAction<TValue2> parser2)
{
return Grammar.And(parser1, parser2);
}
public static ParseAction<TValue> Or<TValue>(
this ParseAction<TValue> parser1,
ParseAction<TValue> parser2)
{
return Grammar.Or(parser1, parser2);
}
}
[Test]
public void InfixAnd()
{
var phoneNumber =
Grammar.Rep(Grammar.Ch(char.IsNumber))
.And(Grammar.Ch(c => c == '-'))
.And(Grammar.Rep(Grammar.Ch(char.IsNumber)));
Position input = new Position(new SourceContext("123-4567"));
var result = phoneNumber(input);
Assert.AreEqual(3, result.Value.Left.Left.Count);
Assert.AreEqual('-', result.Value.Left.Down);
Assert.AreEqual(4, result.Value.Down.Count);
}
And here’s another secret I’ve been keeping: the Grammar class is intended to be used as a base class for other classes which build the actual grammar expressions. So all of this Grammar.Ch() nonsense is supposed to be Ch() when you use it. Here’s an example.
class PhoneGrammar : Grammar
{
public PhoneGrammar()
{
var localNumber =
Rep(Ch(char.IsNumber)).And(Ch('-')).And(Rep(char.IsNumber));
}
}
Now that’s starting to look like a domain-specific language! There’s still a big problem with the use of the automatic type ‘var’ to hold the delegate type. It tells the compiler hey, you’re the computer, you tell me what type this is and run with that. But if we want to use the parser from outside the constructor it’ll need to be a member variable, and that variable will need an explicit type, and that explicit type will be ugly. In this case it’s a:
ParseAction<Chain<Chain<IList<char>, char>, IList<char>>>
I know. Insane.
So let’s use an extension method to add a Build operation like we did with the And and Or. The goal here is to provide a simple mechanism to convert the cumulative result into something sane.
public static ParseAction<TValue2> Build<TValue1, TValue2>(
this ParseAction<TValue1> parser,
Func<TValue1, TValue2> builder)
{
return delegate(Position input)
{
var result = parser(input);
if (result == null) return null;
return new ParseResult<TValue2>(result.Rest, builder(result.Value));
};
}
What we have here is a fairly basic thing. This Build method takes a parser for TValue1 and it returns a parser for TValue2. It also takes a function in the builder argument that accepts a TValue1 argument and returns a TValue2. The parser it’s returning will call the parser that already exists, uses the builder method to create the second type from the first, and returns the converted value along with the advanced position.
That said what this does for us is allow quick and simple creation of clean results from the exposed parsers instead of the fairly arcane chained types that the compiled accumulates after a long series of And’s have been traversed.
So we can now use simple expressions to create a grammar that parses out simple types. These can be combined in very expressive ways.
public class PhoneNumber
{
public string AreaCode { get; set; }
public string Prefix { get; set; }
public string Body { get; set; }
}
public class PhoneGrammar : Grammar
{
public PhoneGrammar()
{
var number =
Rep(Ch(char.IsNumber))
.Build(hit => new string(hit.ToArray()));
var localNumber =
number.If(hit=>hit.Length == 3)
.And(Ch('-'))
.And(number.If(hit=>hit.Length == 4))
.Build(hit => new PhoneNumber {
Prefix = hit.Left.Left,
Body = hit.Down});
var longDistanceNumber =
Ch('(')
.And(number.If(hit=>hit.Length == 3))
.And(Ch(')'))
.And(localNumber)
.Build(hit => new PhoneNumber {
AreaCode = hit.Left.Left.Down,
Prefix = hit.Down.Prefix,
Body = hit.Down.Body});
ParsePhoneNumber = localNumber.Or(longDistanceNumber);
var phoneNumberIgnoringWhitespace =
Rep(Ch(' ')).And(ParsePhoneNumber).And(Rep(Ch(' ')))
.Build(hit => hit.Left.Down);
ParsePhoneNumberList = Rep(phoneNumberIgnoringWhitespace);
}
public ParseAction<PhoneNumber> ParsePhoneNumber;
public ParseAction<IList<PhoneNumber>> ParsePhoneNumberList;
}
[Test]
public void TestPhoneNumbers()
{
PhoneGrammar grammar = new PhoneGrammar();
ParseResult<PhoneNumber> number1 = grammar.ParsePhoneNumber(
new Position(new SourceContext("555-1212")));
ParseResult<PhoneNumber> number2 = grammar.ParsePhoneNumber(
new Position(new SourceContext("(612)555-1212")));
Assert.IsNull(number1.Value.AreaCode);
Assert.AreEqual("555", number1.Value.Prefix);
Assert.AreEqual("1212", number1.Value.Body);
Assert.AreEqual("612", number2.Value.AreaCode);
Assert.AreEqual("555", number2.Value.Prefix);
Assert.AreEqual("1212", number2.Value.Body);
ParseResult<IList<PhoneNumber>> list1 = grammar.ParsePhoneNumberList(
new Position(new SourceContext("(612)555-1212 123-4434")));
Assert.AreEqual("612", list1.Value[0].AreaCode);
Assert.AreEqual("555", list1.Value[0].Prefix);
Assert.AreEqual("1212", list1.Value[0].Body);
Assert.IsNull(list1.Value[1].AreaCode);
Assert.AreEqual("123", list1.Value[1].Prefix);
Assert.AreEqual("4434", list1.Value[1].Body);
}
So it’s pretty easy to imagine how a set of expressions that are each fairly understandable can be combined to create a remarkably sophisticated “great big” rollup parser. The phone example here could possibly be handled with a regular expression, if you know exactly what you’re doing, but once you started taking into account all of the places whitespace could occur and various international notations things would get out of hand very quickly. In fact with the .Build delegate you could add something like a PhoneNumberType enum property to the resulting class so you could determine which individual format rule produced any member in the list.
And in conclusion I should probably bring us back to the original reason for this entire thing. Which is a parser that understands a variant of standard xml markup. Here’s the code which will return a list of nodes. The text you see in comments are the expressions which came directly from the xml specification. You can see how the domain-specific language is close enough to a standard expression syntax that it was pretty easy to convert the text of the spec directly into parser grammar.
public MarkupGrammar()
{
var Apos = Ch('\'');
var Quot = Ch('\"');
var Lt = Ch('<');
var Gt = Ch('>');
//var CombiningChar = Ch('*');
//var Extener = Ch('*');
//[4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' | CombiningChar | Extender
var NameChar = Ch(char.IsLetterOrDigit).Or(Ch('.', '-', '_', ':'))/*.Or(CombiningChar).Or(Extener)*/;
//[5] Name ::= (Letter | '_' | ':') (NameChar)*
var Name =
Ch(char.IsLetter).Or(Ch('_', ':')).And(Rep(NameChar))
.Cast(hit => hit.Left + new string(hit.Down.ToArray()));
//[7] Nmtoken ::= (NameChar)+
var NmToken =
Rep1(NameChar)
.Cast(hit => new string(hit.ToArray()));
//[3] S ::= (#x20 | #x9 | #xD | #xA)+
Whitespace = Rep1(Ch(char.IsWhiteSpace));
//[25] Eq ::= S? '=' S?
var Eq = Opt(Whitespace).And(Ch('=')).And(Opt(Whitespace));
Text =
Rep1(ChNot('&', '<', '$'))
.Cast(hit=>new TextNode(hit));
//[68] EntityRef ::= '&' Name ';'
Entity =
Ch('&').And(Name).And(Ch(';')).Left().Down()
.Cast(hit=>new EntityNode(hit));
//todo: understand csharp - this is NOT right
var Expression = Rep1(ChNot(';','}'));
var Code1 = Ch('$').And(Expression).And(Ch(';')).Left().Down().Cast(hit=>new ExpressionNode(hit));
var Code2 = Ch("${").And(Expression).And(Ch('}')).Left().Down().Cast(hit => new ExpressionNode(hit));
var Code3 = Ch('$').Cast(hit => new TextNode(new char[] { '$' }));
Code = AsNode(Code1).Or(AsNode(Code2)).Or(AsNode(Code3));
//[10] AttValue ::= '"' ([^<&"] | Reference)* '"' | "'" ([^<&'] | Reference)* "'"
var AttValueSingleText = Rep1(ChNot('<', '&', '\'', '$')).Cast(hit => new TextNode(hit));
var AttValueSingle = Apos.And(Rep(AsNode(AttValueSingleText).Or(AsNode(Entity)).Or(AsNode(Code)))).And(Apos);
var AttValueDoubleText = Rep1(ChNot('<', '&', '\"', '$')).Cast(hit => new TextNode(hit));
var AttValueDouble = Quot.And(Rep(AsNode(AttValueDoubleText).Or(AsNode(Entity)).Or(AsNode(Code)))).And(Quot);
var AttValue = AttValueSingle.Or(AttValueDouble).Left().Down();
//[41] Attribute ::= Name Eq AttValue
Attribute =
Name.And(Eq).And(AttValue)
.Cast(hit => new AttributeNode(hit.Left.Left, hit.Down));
//[40] STag ::= '<' Name (S Attribute)* S? '>'
//[44] EmptyElemTag ::= '<' Name (S Attribute)* S? '/>'
Element =
Lt.And(Name).And(Rep(Whitespace.And(Attribute).Down())).And(Opt(Whitespace)).And(Opt(Ch('/'))).And(Gt)
.Cast(hit => new ElementNode(hit.Left.Left.Left.Left.Down, hit.Left.Left.Left.Down, hit.Left.Down != default(char)));
//[42] ETag ::= '</' Name S? '>'
EndElement =
Lt.And(Ch('/')).And(Name).And(Opt(Whitespace)).And(Gt)
.Cast(hit => new EndElementNode(hit.Left.Left.Down));
//[11] SystemLiteral ::= ('"' [^"]* '"') | ("'" [^']* "'")
var SystemLiteral =
Quot.And(Rep(ChNot('\"'))).And(Quot).Or(Apos.And(Rep(ChNot('\''))).And(Apos))
.Cast(hit=>new string(hit.Left.Down.ToArray()));
//[13] PubidChar ::= #x20 | #xD | #xA | [a-zA-Z0-9] | [-'()+,./:=?;!*#@$_%]
var PubidChar1 = Ch(char.IsLetterOrDigit).Or(Ch(" \r\n-()+,./:=?;!*#@$_%".ToArray()));
var PubidChar2 = PubidChar1.Or(Apos);
//[12] PubidLiteral ::= '"' PubidChar* '"' | "'" (PubidChar - "'")* "'"
var PubidLiteral =
Quot.And(Rep(PubidChar2)).And(Quot).Or(Apos.And(Rep(PubidChar1)).And(Apos))
.Cast(hit => new string(hit.Left.Down.ToArray()));
//[75] ExternalID ::= 'SYSTEM' S SystemLiteral | 'PUBLIC' S PubidLiteral S SystemLiteral
var ExternalIDSystem =
Ch("SYSTEM").And(Whitespace).And(SystemLiteral)
.Cast(hit=>new ExternalIdInfo {ExternalIdType= hit.Left.Left, SystemId=hit.Down});
var ExternalIDPublic =
Ch("PUBLIC").And(Whitespace).And(PubidLiteral).And(Whitespace).And(SystemLiteral)
.Cast(hit => new ExternalIdInfo { ExternalIdType = hit.Left.Left.Left.Left, PublicId = hit.Left.Left.Down, SystemId = hit.Down });
var ExternalID = ExternalIDSystem.Or(ExternalIDPublic);
//[28] doctypedecl ::= '<!DOCTYPE' S Name (S ExternalID)? S? ('[' intSubset ']' S?)? '>'
DoctypeDecl =
Ch("<!DOCTYPE").And(Whitespace).And(Name).And(Opt(Whitespace.And(ExternalID).Down())).And(Opt(Whitespace)).And(Ch('>'))
.Cast(hit => new DoctypeNode { Name = hit.Left.Left.Left.Down, ExternalId = hit.Left.Left.Down });
AnyNode = AsNode(Text).Or(AsNode(Entity)).Or(AsNode(Element)).Or(AsNode(EndElement)).Or(AsNode(Code)).Or(AsNode(DoctypeDecl));
Nodes = Rep(AnyNode);
}
public ParseAction<IList<char>> Whitespace;
public ParseAction<IList<Node>> Nodes;
public ParseAction<Node> AnyNode;
public ParseAction<DoctypeNode> DoctypeDecl;
public ParseAction<TextNode> Text;
public ParseAction<EntityNode> Entity;
public ParseAction<Node> Code;
public ParseAction<ElementNode> Element;
public ParseAction<EndElementNode> EndElement;
public ParseAction<AttributeNode> Attribute;
Recent Comments