Example 10.2.1

Note that this is nondeterministic. You have to use the lookahead to decide which transition to take, in a sense adding determinism by using extra information.

• symbol is a buffer that holds next input symbol (not processed right away)

• We have gotten rid of the nondeterminism by using the lookahead symbol.

A parsing routine for this grammar:

symbol is the lookahead symbol and $ is the end-of-string marker:

state = s
push(S)
state = q
read(symbol)                               obtain the lookahead symbol
while top-of-stack <> z do                 while stack is not empty
   case top-of-stack of
   S: if symbol == a then                  cases for variables
            { pop(); push(aSb) }           replace S by aSb
         else if symbol == b then
            { pop(); push(b) }             replace S by b
         else error
      a: if symbol <> a, then error        cases for terminals
         else { pop(); read(symbol) }      pop a, get next lookahead
      b: if symbol <> b, then error
         else { pop(); read(symbol) }      pop b, get next lookahead
      end case
end while
pop()                                      pop z from the stack
if symbol <> $ then error
state = f

What are the drawbacks?

• For a larger grammar, case statement can get quite long

• Can put the case statement into a generic routine

Example 10.2.2

Parse table for

Example 10.2.3

In this example, it is clear that when $S$ is on the stack and $a$ is the lookahead, replace $S$ by $aSb$. When $S$ is on the stack and $b$ is the lookahead, there is an error, because there must be a $c$ between the $a$ ‘s and $b$ ‘s. When $S$ is on the stack and $ is the lookahead, then there is an error, since $S$ must be replaced by at least one terminal. When $S$ is on the stack, and $c$ is the lookahead, then $S$ should be replaced by $c$.

Example 10.2.4

When the grammar has a $\lambda$-rule, it can be difficult to compute parse tables. In this example, $A$ can disappear (due to $A \rightarrow \lambda$), so when $S$ is on the stack, it can be replaced by $Ac$ if either “a” or “c” are the lookahead, or it can be replaced by $Bc$ if “b” is the lookahead.

Example 10.2.5

We have already calculated FIRST and FOLLOW for this Grammar:

To Compute the LL Parse Table for this example:

• For $S \rightarrow aSc$,

  $\mbox{FIRST}(aSc) = \{a\}$, so add $aSc$ to LL[S,a] by step 1a.
• For $S \rightarrow B$,

  $\mbox{FIRST}(B) = \{b, \lambda \}$

  $\mbox{FOLLOW}(S) = \{\$, c\}$

  By step 1a, add $B$ to LL[S,b]

  By step 1b, add $B$ to LL[S,c] and LL[S,$]
• For $B \rightarrow b$,

  $\mbox{FIRST}(b) = \{b\}$, so by step 1a add $b$ to LL[B,b]
• For $B \rightarrow \lambda$

  $\mbox{FIRST}(\lambda) = \{ \lambda \}$ and $\mbox{FOLLOW}(B) = \{\$, c\}$, so by step 1b add $\lambda$ to LL[B,c] and add $\lambda$ to LL[B,$].

LL(1) Parse Table

Parse string: $aacc$

where $a'$ is the second $a$ in the string and symbol is the lookahead symbol. This table is an LL(1) table because only 1 symbol of lookahead is needed.

Example 10.2.6

Trace $aabcc$

where $a'$ is the second $a$ in the string and symbol is the lookahead symbol. This table is an LL(1) table because only 1 symbol of lookahead is needed.

Example 10.2.7

$S \rightarrow AcB$

$A \rightarrow aAb$

$A \rightarrow \lambda$

$B \rightarrow aBb$

$B \rightarrow c$

• For $S \rightarrow AcB$,

  $\mbox{FIRST}(AcB) = \{a, c\}$ so add $AcB$ to LL[S,a] and LL[S,c]
• For $A \rightarrow aAb$,

  $\mbox{FIRST}(aAb) = \{a\}$ so add $aAb$ to LL[A,a]
• For $A \rightarrow \lambda$,

  $\mbox{FIRST}(\lambda) = \{\lambda\}$ and $\mbox{FOLLOW}(A) = \{b, c\}$ so add $\lambda$ to LL[A,b] and LL[A,c]
• For $B \rightarrow aBb$,

  $\mbox{FIRST}(aBb) = \{a\}$ so add $aBb$ to LL[B,a]
• For $B \rightarrow c$,

  $\mbox{FIRST}(c) = \{c\}$ so add $c$ to LL[B,c]
• All other entries are errors.

parse string: $abcacb$

parse string: $cc$

parse string: $abcab$ (not in language)

Example 10.2.8

Note that FIRST and FOLLOW are quite easy to calculate since there are no $\lambda$ rules! In this case, you don’t need FOLLOW to construct the parse table.

Try to construct LL(1) Parse table

Note that you don`t know which rewrite rule to apply to replace $A$ and $B$ with just one lookahead symbol. $A$ has two choices and both use a lookahead of ‘a’. There are two entries in the LL(1) parse table for T[A,a]. Thus, there is no LL(1) parse table. This means the grammar is not LL(1)!. We will try to use 2 symbols of lookahead.

For example, the string $aabbcaacbb$ cannot be parsed with just one lookahead.

LL(2) Parse Table:

There are no conflicts (only one rule in each entry of the table). This is an LL(2) parser - need two lookahead symbols.

parse string: $aabbcacb$

Note the leftmost derivation! Also note that the two lookahead symbols are used whenever there is a variable on top of the stack.

An LL(k) parser needs $k$ lookahead symbols.

Example 10.2.9

$L = \{a^n: n \ge 0 \} \cup \{a^nb^n: n \ge 0 \}$

$S \rightarrow A$

$S \rightarrow B$

$A \rightarrow aA$

$A \rightarrow \lambda$

$B \rightarrow aBb$

$B \rightarrow \lambda$

This grammar cannot be recognized by an LL(k) parser for any $k$! Consider the string $aabb$. You would need 3 lookahead to realize that you want to use $S \rightarrow B$. Consider the string $aaabbb$, you would need 4 lookahead. Consider string $a^nb^n$, you would need $n$ lookahead. There is no (constant) $k$ such that $k$ lookahead works for every string in the language.

Example 10.2.10

An LL(11) parser will work since all strings have 10 or fewer $a$ ‘s.

Example 10.2.11

This grammar is LL(5). We don’t know which S rule to apply with the string $bbccd$ or $bbcc\$$ until you have seen the fifth symbol.

This grammar cannot be recognized by an LL(k) parser.

When the lookahead is $b$, don’t know which rule to apply, either the second or third.