Representing Code

Representing Code · Crafting Interpreters

To dwellers in a wood, almost every species of tree has its voice as well as its feature. Thomas Hardy, Under the Greenwood Tree

https://craftinginterpreters.com/representing-code.html#enhancing-our-notation

We can a tree structure where each leaf is an operand and each inner node is an operation. This allows us to easily evaluate the solution.

Context-Free Grammars

Some Definitions

Phrase	Definition
Regular Language	Clump chars into Tokens
Context-Free Grammar	Takes a set of atomic pieces called an “alphabet”, and has a (typically infinite) set of allowed strings allowed in the grammar.

We can consider the tokens the alphabet; and the grammar is our expressions.

Rule for Grammars

Of course it is impossible to create a context free grammar using an infinite set of rules. Instead we can use a limited set of rules that define small parts of strings, those groupings can be assembled into strings.

Some more Definitions

Phrase	Definition
Derivations	Strings derived from a set rules from the grammar.
Productions	Rules used to produce the derivations.
Head	The name of the production.
Body	The thing that describes the production.
Terminal	A node that does not reference any other notes.
Non-Terminal	A node that references non-terminals or terminals.

breakfast  → protein "with" breakfast "on the side" ;
breakfast  → protein ;
breakfast  → bread ;

protein    → crispiness "crispy" "bacon" ;
protein    → "sausage" ;
protein    → cooked "eggs" ;

crispiness → "really" ;
crispiness → "really" crispiness ;

cooked     → "scrambled" ;
cooked     → "poached" ;
cooked     → "fried" ;

bread      → "toast" ;
bread      → "biscuits" ;
bread      → "English muffin" ;

This meta-language is used to define our grammars. We start with breakfast and populate protein and breakfast we repeat this process until we have reached terminals; aka bread.

When we have recursion we can be confident that the language is context-free.

More advanced notation

We can simplify the notation defined above using some syntactic sugar.

breakfast → protein ( "with" breakfast "on the side" )?
          | bread ;

protein   → "really"+ "crispy" "bacon"
          | "sausage"
          | ( "scrambled" | "poached" | "fried" ) "eggs" ;

bread     → "toast" | "biscuits" | "English muffin" ;

Select one of the following

bread → "toast" | "biscuits" | "English muffin" ;

Select one of the following then postfix with “eggs”

protein → ( "scrambled" | "poached" | "fried" ) "eggs" ;

1 “really” then 0 to many “really”

crispiness → "really" "really"* ;

1 to many “really”

crispiness → "really"+

? means 0 to 1 times

breakfast → protein ( "with" breakfast "on the side" )? ;

Lox Expression Grammar Example

expression     → literal
               | unary
               | binary
               | grouping ;

literal        → NUMBER | STRING | "true" | "false" | "nil" ;
grouping       → "(" expression ")" ;
unary          → ( "-" | "!" ) expression ;
binary         → expression operator expression ;
operator       → "==" | "!=" | "<" | "<=" | ">" | ">="
               | "+"  | "-"  | "*" | "/" ;

Note this does produce some wacky stuff, you can make things like (!!nil) but it will do for now.

Implementing our Abstract Syntax Tree

We will have 4 types of expression as you can see above.

We can create an abstract class that holds these expression types like so.

We bundle them up like this so we can easily find them.

Token is always a terminator, expressions are the non-terminators.

While below code is in Java; in c# records would be a more natural fit.

abstract class Expr { 
  static class Binary extends Expr {
    Binary(Expr left, Token operator, Expr right) {
      this.left = left;
      this.operator = operator;
      this.right = right;
    }

    final Expr left;
    final Token operator;
    final Expr right;
  }

  // Other expressions... unary, literal, grouping
}

Working with Trees

Expression Problem

Consider the data types listed vertically; and the methods listed horizontally.

Consider in OOP you want to add a new class, this is easy you implement the methods listed. But what if you want to add a new method, you would now have to open each class and create a new method for each. The natural pattern to follow with this is the Interpreter Pattern.

In functional programming, you pattern match on the data, thus adding a new function is easy. But if you want to add a new data type, then you will again have to go to each place to add a new data type. The natural OOP pattern to follow with this is the Visitor Pattern.

This problem is known as the expression problem; because it was coined when some folks were trying to create an AST. Typically we are more likely to add new functions so the Visitor Pattern is the better approach.

Visitor Pattern

Visitor