LL(1) Parsing

Introduction

LL(1) parsing is also called predictive parsing. To construct an LL(1) parser for some given grammar, we need to follow these steps -

  1. Remove left recursion and perform left factoring
  2. Computer the first and follow of the non terminals
  3. Construct the predictive parsing table
  4. Optionally parse an example input string to verify

Left recursion

A grammar is said to be left recursive if it contains some production rule with a non terminal such that, there exists a rule .

Elimination

For some left recursive grammar , we can eliminate left recursion by rewriting it as

Example for left recursion elimination:

Rewrting the above as described, we will get:

Left factoring

Left factoring is done to transform the grammar into a form that is more suitable for recursively parsing.
For a production rule of the form , we factor out and rewrite it as

First and follow

Note

Remove any possible left recursion and left factoring before calculating the first and follow for any given grammar.

First

first(X) is the set of terminals that are the beginnings of strings that are derived from X. If X derives somewhere down the line, then is also included in first(X). The following rules have to be applied until no further elements can be added to first(X).

  1. If X is a terminal, then first(X) is
  2. If , then add to first(X)
  3. If then add to first(X)
  4. If then look at the first symbol . Add the first symbol's first to first(X).
    1. If is produced by , move on to and repeat
    2. If not, stop

Follow

follow(Y) is the set of terminals that occur immediately to the right of in some form or the other. The following rules have to be applied until no further elements can be added to follow(Y).

  1. For the start symbol, add to its follow
  2. For some , it is obvious that whatever comes after X, will also come after Y, so add follow(X) to follow(Y)
  3. For some
    1. If B is terminal, then add it to follow(Y)
    2. If not
      1. If first(B) does not contain , it should be added to follow(Y)
      2. If it does contain , then we need to add first(B) without and follow(X) to follow(Y). This makes sense, as will mean that we use rule 4 from First. (More formally

Construction of predictive parsing table

To construct the predictive parsing table, the following rules have to be used -

  1. For every production rule, , mark the table entry at with the production rule itself
  2. For every production rule, , mark the table entry at with the production rule itself