Building a Language: The Parser

The lexer already hands over tokens. Now comes the piece that gives them shape: the parser.

From text to a tree

The lexer hands over a flat list of tokens. The parser turns it into a tree, the AST, and that tree answers the question the list can't: what goes with what?

In 1 + 2 * 3 the tokens are the same no matter how you read them, but the result isn't. Grouped as (1 + 2) * 3 it's 9; grouped as 1 + (2 * 3) it's 7. The parser doesn't compute anything. It only decides the groups, and everything that comes after depends on that decision.

Who keeps the 2

Codexivo's parser is a Pratt parser. The idea is simple: every operator has a strength. When a value sits between two operators, both pull on it, and the stronger one keeps it.

In 1 + 2 * 3, the 2 sits between + and *. Since * is stronger, the 2 goes with the *: 2 * 3 is grouped first, and that whole group is what gets added to the 1.

In the code, those strengths are a list:

export enum Precedence {
  LOWEST = 1,
  EQUALS = 2,
  LESS_GREATER = 3,
  SUM = 4,
  PRODUCT = 5,
  PREFIX = 6,
  CALL = 7,
}

A lower number is a weaker operator: == loses to <, < loses to +, + loses to *. That same day, in the commit that added si (if), y (and) and o (or) came in too. I added them at the end of the list, with y above o, as in almost every language:

  CALL = 7,
  OR = 8,
  AND = 9,

And I wrote their tests. Each one compares the code with the tree that should come out, written with parentheses (verdadero and falso are true and false):

['verdadero o falso y verdadero;', '(verdadero o (falso y verdadero))'],
['verdadero y falso o verdadero;', '((verdadero y falso) o verdadero)'],

Both pass.

A call is an operator too

What I like most about Pratt is how little the parser changes for things that don't look like operators. Every token can have two functions: one for when it shows up at the start of an expression, and one for when it shows up in the middle, after something already read.

A - at the start is a minus sign; in the middle, a subtraction. A ( at the start groups; in the middle, after a name, it's a call: doble(5) is doble followed by a ( operator whose strength is CALL, the highest in the table, so nothing takes the name away from it. Even si works that way: it's a start function that reads a condition, a block and, if there is one, a si_no (else). That's why in Codexivo an si is an expression and has a value.

Adding something to the language almost always comes down to two questions: what does this token do at the start? And in the middle, with what strength?

The pero_si

Later I added pero_si (else if), so you don't have to nest an si inside every si_no. The parser reads it in a loop: while the next token is pero_si, it reads a condition and a block and stores them as the si's alternative. At the end, if there's an si_no, it reads its block.

si (1 > 2) { 10 } pero_si (1 < 2) { 20 }

This program evaluates to 20. The tests cover the two cases I cared about, with and without si_no, and they pass:

['si (1 > 2) { 10 } pero_si (1 < 2) { 20 }', 20],
['si (1 > 2) { 10 } pero_si (1 > 2) { 20 } si_no { 30 }', 30],

What stays

The parser computes nothing, and still it's where the language decides how it reads. The precedence table looks like an implementation detail, but it's a design decision: it says what comes first when someone writes without parentheses, and whoever learns with Codexivo will never see it, only its consequences.

That's why I treat every strength as one more rule of the language, and I want few rules, each with a reason. * before +, because that's how it's taught in school. y before o, because that's how almost every language does it, and whoever moves from Codexivo to another language shouldn't have to relearn it.

Try it

This is the Codexivo interpreter. The construction view shows, step by step, how the tree for the same expression is built:

1 + 2 * 3

Next time: the evaluator, the part that finally does something with the tree.