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.