Parsing Expressions

https://craftinginterpreters.com/parsing-expressions.html

Ambiguity

How can we determine which is correct? Do we execute the / first or the -

Formal rules

• Precedence - Order of operations

• Associativity - Do we execute from left to right (left-associative) or right to left (right-associative). Aka, 1 - 2 - 3 becomes (1 - 2) - 3 or 1 - (2 - 3)

Associativity Table

Formalised Grammar in Notation Form

This does not describe the AST - this describes how the AST is made - the productions.

// Highest Presidence
expression     → equality ;
equality       → comparison ( ( "!=" | "==" ) comparison )* ;
comparison     → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term           → factor ( ( "-" | "+" ) factor )* ;
factor         → unary ( ( "/" | "*" ) unary )* ;
unary          → ( "!" | "-" ) unary
               | primary ;
primary        → NUMBER | STRING | "true" | "false" | "nil"
               | "(" expression ")" ;

Recursive Descent Parsing

This is one of the most common approaches. We start at the lowest precedence, and work our way down.

We can translate our Grammar Notation into code like so.

The Parser Class

We can consider each notation to represent a method within our parser class.

We can consider the approach like a zig-zag.

For each layer in our formalised grammar in notation a method. Each method is essentially exactly what is described in the notation. The pattern is follow down the first name until you reach a terminal, and then move up until you get to a production that matches the next char.

For example 1 + 2 you would go:

expression → equality → comparison → term → factor → unary → primary → NUMBER (1)

term (+) ← factor ← unary ← primary

term → factor → unary → primary → NUMBER (2)

expression ← equality ← comparison ← term ← factor ← unary ← primary

Example for equality:

a == b == c == d == e

Syntax Errors

It must do the following:

1. Detect and report the error

2. Avoid crashing or hanging for example on seg faults or infinite loops

3. Be Fast - as in milliseconds fast

4. Report as many errors as possible

5. Do not report errors that are a consequence of prior errors

Note that 4 and 5 are in conflict

Panic Mode

This is the method for showing all known errors while not showing cascaded errors.

The approach is to jump out of production and synchronise; meaning to skip ahead tokens until you reach the token that the next production can continue with, as if no issue ever occurred.

We an determine when we are at the next statement using chars like ; or key words like for as anchors.

Example method

 private void synchronize() {
    advance();

    while (!isAtEnd()) {
      if (previous().type == SEMICOLON) return;

      switch (peek().type) {
        case CLASS:
        case FUN:
        case VAR:
        case FOR:
        case IF:
        case WHILE:
        case PRINT:
        case RETURN:
          return;
      }

      advance();
    }
  }

The entry points to expect

    List<Token> tokens = scanner.scanTokens();
    Parser parser = new Parser(tokens);
    Expr expression = parser.parse();

    // Stop if there was a syntax error.
    if (hadError) return;

    System.out.println(new AstPrinter().print(expression));