Lexical and syntax analysis: lexer, recursive descent, LL and LR

The first two phases of a compiler are lexical analysis and syntax analysis (parsing). The question that comes up most on the midterm: tracing the parse of an expression step by step with given recursive-descent functions. Also, removing left recursion and the pairwise disjointness test are short, clear points.

Golden rules:

1. The lexer produces tokens, the parser builds the tree.
2. In recursive descent every nonterminal is a function. { } is a while loop, [ ] is an if.
3. lex() is called once per token and puts the next token in nextToken.
4. Left recursion kills a top-down parser, it must be removed.
5. LL = top-down, LR = bottom-up.

Why two separate phases?

Lexical analysis

The lexer reads the source code character by character, gathers the characters into lexemes and gives each lexeme a token. It skips whitespace and comments, adds user-defined names to the symbol table, and reports errors (invalid characters).

result = rate * (count + 15);

IDENT(result) ASSIGN_OP(=) IDENT(rate) MULT_OP(*) LEFT_PAREN(()
IDENT(count) ADD_OP(+) INT_LIT(15) RIGHT_PAREN()) SEMICOLON(;)

10 lexemes. The lexer works like a finite automaton; the way to draw it is a state diagram:

            letter/digit
             ┌────┐
   letter    ▼    │
Start ─────► id ──┘ ── other character ──► return IDENT (or reserved word)
  │
  │ digit    digit
  │         ┌────┐
  └───────► int ◄┘ ── other character ──► return INT_LIT

Instead of drawing a separate arrow for every letter and digit, character classes are used: LETTER and DIGIT. Reserved words (if, while) do not get a separate state; they are recognized as identifiers and then separated by looking them up in a table.

Parsing: top-down and bottom-up

A parser does two jobs: finding syntax errors and producing the parse tree (or its information).

LL: Left-to-right scan, Leftmost derivation. LR: Left-to-right scan, Rightmost derivation (in reverse). General parsing algorithms for any unambiguous grammar are $O(n^3)$; the LL and LR parsers used in compilers work with a subclass of grammars and are $O(n)$.

Recursive descent

A function is written for each nonterminal. It maps very naturally to EBNF:

/* <expr> -> <term> {(+ | -) <term>} */
void expr() {
  term();
  while (nextToken == ADD_OP || nextToken == SUB_OP) {
    lex();
    term();
  }
}
/* <term> -> <factor> {(* | /) <factor>} */
void term() {
  factor();
  while (nextToken == MULT_OP || nextToken == DIV_OP) {
    lex();
    factor();
  }
}
/* <factor> -> id | int_constant | ( <expr> ) */
void factor() {
  if (nextToken == IDENT || nextToken == INT_LIT)
    lex();
  else if (nextToken == LEFT_PAREN) {
    lex();
    expr();
    if (nextToken == RIGHT_PAREN) lex();
    else error();
  }
  else error();
}

Rule: when a function is called, nextToken already holds the first token of that function. The program starts with lex(), then expr() is called.

Trace: (a + b) * c

Enter <expr>
  Enter <term>
    Enter <factor>            next = (  → lex, next = a
      Enter <expr>
        Enter <term>
          Enter <factor>      next = a  → lex, next = +
          Exit <factor>
        Exit <term>           + is not multiplication, term returns
        lex, next = b         expr's while saw +
        Enter <term>
          Enter <factor>      next = b  → lex, next = )
          Exit <factor>
        Exit <term>
      Exit <expr>             ) is not addition
      lex, next = *           factor was expecting ), found it
    Exit <factor>
    lex, next = c             term's while saw *
    Enter <factor>            next = c  → lex, next = EOF
    Exit <factor>
  Exit <term>
Exit <expr>

Count: factor entered 4 times, term 3 times, expr 2 times, lex called 7 times. When tracing on an exam, ask on every line “what is nextToken right now?” The loop condition always looks at the current nextToken.

PITFALL · which loop catches it? For x - y / 2, the - sign is caught by the loop of expr, not term (term looks only for * and /). The / is handled inside the second term() call. So the tree becomes x - (y / 2) and precedence comes out right by itself.

The same logic holds for <list> -> id { , id }: with the input id , id ,, after the last comma an id is expected but EOF arrives, an error.

Two problems of LL grammars

1. Left recursion

<expr> -> <expr> + <term> | <term>

expr() calls expr() as its first action, without consuming any token. Infinite recursion. The pattern for removing direct left recursion:

$A \to A\alpha \mid \beta \quad\Longrightarrow\quad A \to \beta A', \quad A' \to \alpha A' \mid \varepsilon$

<T>  -> <T> * <F> | <T> / <F> | <F>
⇓
<T>  -> <F> <T'>
<T'> -> * <F> <T'> | / <F> <T'> | ε

The new grammar produces the same language (id, id * id, id / id * id, …). Only the structure is different.

2. Pairwise disjointness

The parser must know which RHS to choose by looking at the next token. For this, the FIRST sets of the alternatives of a nonterminal must not intersect. FIRST(α) is the set of first terminals of the strings derived from α.

<A> -> a <B> | <B> b         FIRST(a<B>) = {a}
<B> -> a <C> | d             FIRST(<B>b) = FIRST(<B>) = {a, d}
                             {a} ∩ {a, d} = {a}  → TEST FAILS

The fix is left factoring: take the common prefix out.

<stmt> -> if <c> then <s> | if <c> then <s> else <s>
⇓
<stmt> -> if <c> then <s> <rest>
<rest> -> else <s> | ε

Bottom-up parsing

A bottom-up parser reads the input from the left, pushes tokens onto a stack (shift), and when the sequence on top of the stack matches an RHS, reduces it to the LHS (reduce). The correct substring to reduce is called the handle. The result is the rightmost derivation written in reverse:

id + id * id
<factor> + id * id         handle: the first id
<term> + id * id
<expr> + id * id
<expr> + <factor> * id
<expr> + <term> * id       here <expr> + <term> is not reduced, * is waiting
<expr> + <term> * <factor>
<expr> + <term>
<expr>

8 reductions. The hard part is choosing the handle correctly: <expr> + <term> is an RHS, but since * comes after it, reducing it now would bind the multiplication wrongly. LR parsers make this decision with a table (ACTION/GOTO); building the table is outside the midterm scope of this course, knowing the idea is enough.

Common mistakes

result = rate * (count + 15);

Enter <expr>
  Enter <term>
    Enter <factor>      next = x (IDENT) → lex, next = -
    Exit <factor>
  Exit <term>           - is not multiplication/division, term returns
  expr sees - → lex, next = y
  Enter <term> ... y / 2 is here (factor, lex /, factor)

<A> -> a <B> | <B> b
<B> -> a <C> | d
<C> -> c

<S> -> x <S> | <T> y | z
<T> -> w <T> | v

id + id * id
<factor> + id * id
<term> + id * id
<expr> + id * id
<expr> + <factor> * id
<expr> + <term> * id
<expr> + <term> * <factor>
<expr> + <term>
<expr>