30. Grammars

Right words, wrong order

Give Drip’s scanner this line:

print + ; 3 (

It doesn’t complain. print is a keyword, +, ; and ( are fine tokens, and 3 is a number literal. Every word is spelled correctly. But the line means nothing, in the same way that “sat the on cat mat the” is made of good English words in a bad order.

The scanner can’t catch this. It looks at one token at a time, and the problem is in how the tokens are arranged. We need rules about order.

Rules for sentences

Here is a grammar for a very small piece of Drip: print statements that add numbers, with brackets allowed.

stmt → "print" expr ";"
expr → expr "+" item
expr → item
item → NUMBER
item → "(" expr ")"

Read each arrow as “can be made of”. The first rule says: a stmt can be made of the keyword print, then an expr, then a semicolon. Words in quotes are exact tokens. NUMBER in capitals stands for any token of type number, such as 3 or 4.25. The bare words stmt, expr and item are the blanks: names of other rules.

To check that a line fits the grammar, start from stmt and replace one name at a time with one of its rules, until only tokens are left. That is called a derivation:

Five rules, endless programs

Notice that expr → expr "+" item mentions expr on both sides. Each time you use it, you get one more + and still have an expr to fill in, so you can use it again. And item → "(" expr ")" puts a whole new expr inside brackets. With five rules, the grammar describes print 1;, print 1 + 2;, print ((1) + 2) + 3;, and infinitely many more.

This is recursion, as in chapter 9, and it needs a base case. If expr had only its recursive rule, every step would leave another expr behind and the derivation could never finish. expr → item and item → NUMBER are the ways out.

Now try it yourself. Each button applies one rule to the underlined nonterminal:

Writing grammars down: BNF

Grammars are written in a notation called BNF. There are a few dialects, but they share the same ideas, and most add a few shorthands. Here is the same grammar, shorter:

stmt → "print" expr ";"
expr → item ( "+" item )*
item → NUMBER | "(" expr ")"

| means “or”: it joins several rules for the same name into one line. * after a group means “zero or more times”, so an expr is an item followed by any number of + item pairs. That replaces the recursive rule with a repetition, and it describes exactly the same sentences. Later grammars also use ? for “optional: zero or one time”. You will also meet grammars that write a rule as <expr> ::= ..., with angle brackets around the names. It is the same idea in different spelling.

Here are a few of Drip’s real statement rules, written this way:

declaration → letDecl | statement
letDecl   → "let" IDENTIFIER
              ( "=" expression )? ";"
statement → printStmt | ifStmt | block
          | exprStmt
printStmt → "print" expression ";"
ifStmt    → "if" "(" expression ")"
              statement
              ( "else" statement )?
block     → "{" declaration* "}"

A block holds declarations, a declaration can be a statement, and a statement can be a block: that loop of rules is how blocks nest inside blocks. Drip’s grammar is Lox’s grammar from Crafting Interpreters, with let and fn for var and fun^[2].

Your turn

function isSum(ts) {
  // your code here
}

console.log(isSum(['number', '+',
  'number']));  // true
console.log(isSum(['number', '+']));
// false

function isCall(ts) {
  // your code here
}

console.log(isCall(['identifier', '(',
  'number', ')']));  // true

What you learned

• A grammar is a set of production rules saying which token sequences are valid. The scanner checks words; the grammar checks order.
• Terminals are tokens. Nonterminals are rule names, blanks to be filled in.
• A derivation replaces nonterminals with rules until only terminals are left.
• Recursive rules give infinitely many sentences, and need a non-recursive way out.
• BNF writes rules as name → pattern, with |, * and ? as shorthands.

Next: what a parser builds when a program fits the grammar.