Writing a small parser / interpreter (Part 3: Semantic processing and simple WPF MVVM UI)

In the previous two steps we crafted a scanner and a parser for a subset of the LOGO programming language:

But, besides recognizing tokens and legal sentences, we also need to put semantic meaning into the LOGO programs. 

Semantic recordings

For this purpose we will use semantic records. A semantic record is introduced to remember context while parsing the LOGO sentences.

Take a look at the following (parser) code-snippet:
private ILogoCommand ParseLogoSentence()
  ILogoCommand result = null;
  Token nextToken = scanner.NextToken();
  switch (nextToken)
    case Token.FORWARD:
    case Token.BACK:
    case Token.LEFT:
    case Token.RIGHT:
      var numberRecord = new NumberRecord(nextToken, scanner.ScanBuffer);
      if (nextToken == Token.FORWARD || nextToken == Token.BACK)
        result = new LogoMoveCommand(numberRecord);
        result = new LogoTurnCommand(numberRecord);

When parsing simple LOGO constructs, we're using a NumberRecord to remember the number associated with a distance or angle and we're using LogoCommands to compose a record for later interpretation. One could argue that the NumberRecord seem redundant in this simple case, but actually we're using the NumberRecord for deciding the direction represented by the number.

public class NumberRecord
  public int Number { get; private set; }
  public NumberRecord(Token directionToken, string numberAsString)
    Number = int.Parse(numberAsString);
    if (directionToken == Token.BACK || directionToken == Token.RIGHT)
      Number = (-1)*Number;

The LogoCommands stores direction and angle information and provide means for calculating the geometry behind the sentence (its semantic meaning) through an interface:

public interface ILogoCommand
  TurtleSituation CalculateSituation(TurtleSituation currentSituation);

A TurtleSituation is just a placeholder remembering the current state of the geometry behind the LOGO program.

public class TurtleSituation
  private static readonly DefaultTurtleSituation defaultSituation = new DefaultTurtleSituation();
  public virtual int Angle { get; set; }
  public virtual int TurnAngle { get; set; }
  public virtual Position Position { get; set; }
  public static DefaultTurtleSituation DefaultSituation
    get { return defaultSituation; }
  #region Nested type: DefaultTurtleSituation endregion#

Should we at some point need more complex sentences supporting e.g. routines, variables or the like, we could introduce a symbol-table to store identifier information. When dealing with more complexity it is also common to push the semantic records on an (explicit) semantic stack making it possible for the parser methods to query information discovered previously. One could of course also use the C# stack, pushing records as method arguments – in fact, we do that when returning LogoCommands from the parser methods.


All though the premise for these blogs were parsing techniques it would be a shame not to take the last step, writing a consumer of the LogoCommand records produced by the parser.

So, with the choice of a WPF MVVM kind of UI and a bit of Cartesian geometry, the Logo parser gets a graphical face. The MVVM pattern helps separate the UI view from the view logic using merely data binding and simple commands.

Please look to the code at the end of the blog for details.

Overview and recap

Over this series we have created a layered design utilizing simple parsing techniques. The scanner transforms received characters to tokens and the parser adds meaning to the sentences outputting commands. The commands are interpreted and ends up in simple line drawing instructions shown on the UI.

The above illustration hides details like how the ViewModel exposes the actual command that calls the application logic and invokes the parser. Also, the overall data bindings between the View and the ViewModel (not just the command binding) is left out for brevity.

Check out and modify the source, and please chip in and improve the CodePlex Open Source project at http://mhslogo.codeplex.com

Comments are closed