Compiler Series Part II: Compiler Basics

This is the second part in a series of articles on implementing a custom .NET compiler for a card game language called CGL. The project page for CGL, and a list of all the articles in the series can be found here.

In this article I'll introduce the concepts used as building blocks for the compiler and how they can be composed to match complex textual patterns. At the end of this article we'll be able to parse ordered bits of text and turn them into managed objects.

There are a number of ways to approach creating a compiler, but the one we'll be exploring here is a simple recursive decent parser where the grammar for the language is encoded in C# code rather than being described using formats such as EBNF. This is not really a theoretical series so I won't be going into detail on the type of compiler or discuss topics such as formal semantics, just the practical bits.

The main concept I'm building my compiler around is a delegate for parsing source code which returns a parse result of an arbitrary C# type. A number of these can then be composed together to match complex patterns and create a whole object graph. This concept is not something I've invented myself, it's based on a blog post by Louis DeJardin, the guy behind the Spark View Engine for ASP.NET MVC. This post is very similar to Louis', which can be found here, but in the next article and forward we use it for our own specialized grammar.

To get started we'll define the interfaces of the basic concepts we're going to need:

1. public delegate ParseResult<TValue> ParseAction<TValue>(Position position);
2.  
3. public class ParseResult<TValue>
4. {
5.     public Position Rest { get; }
6.     public TValue Value { get; }
7.     public ParseError Error { get; }
8. }
9.  
10. public class Position
11. {
12.     public int Line { get; }
13.     public int Column { get; }
14.     public string Context { get; }
15.  
16.     public char Peek();
17.     public string Peek(int length);
18.     public Position Advance(int offset);
19. }
20.  
21. public class ParseError
22. {
23.     public int Line { get; }
24.     public int Column { get; }
25.     public string Message { get; }
26. } 

The ParseAction delegate is a function which, given a position in the source code, yields either a result of the generic type or a parse error if the pattern did not match. The result of the parser is stored in a ParseResult object which hold either of the possible outcomes. It also contains the position in the source code where a subsequent parser would start off from. The Position object is an immutable description of a point in the source code and it can potentially wrap a source that is more complex than a string if needed.

Using these classes we can begin to create a Grammar class where we define the most basic patterns we want to match.

1. public class Grammar
2. {
3.     public static ParseAction<char> Ch(char match)
4.     {
5.         return delegate(Position input)
6.         {
7.             if (input.Peek() == match)
8.                 return new ParseResult<char>(input.Advance(1), match);
9.             return new ParseResult<char>("Encountered unexpected char", input.Line, input.Column);
10.         };
11.     }
12.  
13.    public static ParseAction<IList<TValue>> Rep<TValue>(ParseAction<TValue> parser)
14.     {
15.         return delegate(Position input)
16.         {
17.             Position rest = input;
18.             List<TValue> list = new List<TValue>();
19.             var results = new List<ParseResult<TValue>>();
20.             results.Add(parser(input));
21.             while (!results.Last().HasError)
22.             {
23.                 list.Add(results.Last().Value);
24.                 rest = results.Last().Rest;
25.                 results.Add(parser(rest));
26.             }
27.             return new ParseResult<IList<TValue>>(rest, list);
28.         };
29.     }
30.  
31.     public static ParseAction<TValue> Or<TValue>(ParseAction<TValue> parser1, ParseAction<TValue> parser2)
32.     {
33.         return delegate(Position input)
34.         {
35.             var result1 = parser1(input);
36.             if (result1.HasError) return parser2(input);
37.             return result1;
38.         };
39.     }
40.  
41.    public static ParseAction<Chain<TValue1, TValue2>> And<TValue1, TValue2>(ParseAction<TValue1> parser1, ParseAction<TValue2> parser2)
42.     {
43.       return delegate(Position input)
44.         {
45.             var result1 = parser1(input);
46.             if (result1.HasError)
47.                 return new ParseResult<Chain<TValue1, TValue2>>(result1.Error);
48.             var result2 = parser2(result1.Rest);
49.             if (result2.HasError)
50.                 return new ParseResult<Chain<TValue1, TValue2>>(result2.Error);
51.             var value = new Chain<TValue1, TValue2>(result1.Value, result2.Value);
52.             return new ParseResult<Chain<TValue1, TValue2>>(result2.Rest, value);
53.         };
54.     }
55. }

Each of the above methods generate a ParseAction for a specific, useful purpose. The first matches a specific char while Rep matches a repeated sequence of a pattern. Using these, we can write the following code (I've removed the references to the Grammar class from the method calls to simplify the example):

1. var parseChar = Ch('c');
2. var parseChars = Rep(parseChar);
3.  
4. var result1 = parseChar(new Position("c"));
5. var result2 = parseChars(new Position("cccc"));

As you can see, we used one parser to create another. The Rep function keeps using the Ch('c') parser to match characters, which it stuffs into a List<char>. The methods Or and And does the same for matching one pattern or another, or one pattern followed by another, respectively. As a side note, you can see that I have supplied none of the type arguments for the generic function. This is because of the powerful type inference capability of the C# compiler.

1. var parseAnotherChar = Ch('k');
2. var parseEitherChar = Rep(Or(parseChar, parseAnotherChar));
3. var parseBothChars = Rep(And(parseChar, parseAnotherChar));
4.  
5. var result1 = parseEitherChar(new Position("kkkckckc"));
6. var result2 = parseBothChars(new Position("ckckckckck"));

Here, we define two parsers that matches series of characters. The one using Or matches a sequence where each char can either be c or k where the one using And matches only sequences of cs followed by a k. To end up with more fluent code, we can define a few useful extension methods:

1. public static class GrammarExtensions
2. {
3.     public static ParseAction<TValue> Or<TValue>(this ParseAction<TValue> parser1, ParseAction<TValue> parser2)
4.     {
5.         return Grammar.Or(parser1, parser2);
6.     }
7.  
8.     public static ParseAction<Chain<TValue1, TValue2>> And<TValue1, TValue2>(this ParseAction<TValue1> parser1, ParseAction<TValue2> parser2)
9.     {
10.         return Grammar.And(parser1, parser2);
11.     }
12. }
13.  
14. // Allows for the following
15. var parseEitherChar = Rep(parseChar.Or(parseAnotherChar));
16. var parseBothChars = Rep(parseChar.And(parseAnotherChar));

As you might have noticed, the And parser returns an object of the type Chain. This is simply a container for the results of the two parse actions. However, it introduces the problem of creating increasingly complex result types as your parsers become more complex. To reduce this problem we introduce the Build function which translates a complex result into a simpler one. It basically just takes the result of a parser and applies a function to it.

1. public static ParseAction<TValue2> Build<TValue1, TValue2>(ParseAction<TValue1> parser, Func<TValue1, TValue2> builder)
2. {
3.     return delegate(Position input)
4.     {
5.         var result = parser(input);
6.         if (result.HasError) return new ParseResult<TValue2>(result.Error);
7.         try
8.         {
9.             return new ParseResult<TValue2>(result.Rest, builder(result.Value));
10.         }
11.         catch (ParseException e)
12.         {
13.             return new ParseResult<TValue2>(e.Message, input.Line, input.Column);
14.          }
15.     };
16. }
17.  
18. var parseBothChars = And(parseChar, parseAnotherChar).Build(hit => hit.Left + hit.Down);

In this case, we use Build to change the result type from Chain<char,char> to string. Once again, the type inferral of the C# compiler comes to our rescue, providing us with proper intellisense on the properties on the Chain object. This will save your sanity when building from more complex chains. Also notice that we catch ParseException errors, a custom exception type which we can use to signal that some parse rule was broken when trying to build the object.

These, and more, are common building blocks for any grammar and, therefore, our primary job is now to create a Grammar class which holds all the basic parsers. To create a more specialized grammar you simply inherit from Grammar and add new parsers.

We're getting to the end of this article but hopefully you got the idea of how this all works. If not, I urge you to go read up on Louis' blog on the same topic. I've also uploaded some of the code from my compiler so you can see some of the other parsers to put in the Grammar class. The code won't compile as it relies on some other code of mine, but it should be possible to understand it regardless.

In the next article we'll begin to create a more specialized grammar for the CGL language using the building blocks presented here.