41.2. LL Parsing¶

41.2.1. LL Parsing¶

41.2.1.1. LL(k) Parser¶

Top-down parser: starts with start symbol on stack, and repeatedly replace nonterminals until string is generated.
Predictive parser: predict next rewrite rule

NOTE: use lookahead for this
First L of LL means that we read input string left to right
Second L of LL means that we produce the leftmost derivation

Note

ASK TO SEE IF THEY KNOW WHAT THIS IS
$k$ : number of lookahead symbols used.

Sometimes more than one symbol is needed

41.2.1.2. LL parsing process¶

Convert CFG to PDA (different method than before)
Use the PDA and lookahead symbols
Lookahead symbol is next symbol in input string

Notes:

The PDA is nondeterministic, so we will lookahead to the next input symbol and use it to determine which rewrite rule to use.
Nondeterministic, could use back-tracking, but this could take forever.
Remember: cannot necessarily construct a deterministic PDA from a NPDA.

41.2.1.3. Convert CFG to NPDA¶

NOTE: This is not the same construction method we used before. This method will apply to any CFG, even those that are not in GNF.

Idea: To derive a string with a CFG, start with the start symbol and repeatedly apply production rules until the string is derived. In order to simulate this process with an NPDA, start by pushing the start symbol on the stack. Whenever a production rule $A \rightarrow w$ would be applied, the variable $A$ should be on top of the stack. $A$ is popped (or replaced) and the right hand side of the rule, $w$ , is pushed onto the stack. Whenever a terminal is on top of the stack, if it matches the next symbol in the input string, then it is popped from the stack. If it does not match, then this string is not in the language of the grammar. If starting with the start symbol $S$ , one can apply replacement rules, match all the terminals in the input string and empty the stack, then the string is in the language.

Note

Just mention this stuff and then draw NPDA.

The constructed NPDA:

Three states: $s, q, f$

As usual, start in state $s$

Push $S$ on stack, move into $q$

All rewrite rules in state $q$ : If left-hand-side of rewrite rule on top of stack, replace it with right-hand-side of rewrite rule and stay in state $q$

Additional rules in $q$ to recognize terminals: Read input symbol, pop input symbol, stay in state $q$

Pop $z$ from stack, move into $f$ , accept

Example 41.2.1

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

$S \rightarrow aSb \mid b$

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.

Note

Trace aabbb.

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

41.2.1.4. LL Parse Table: 2-dimensional array¶

When the grammar is large, the parsing routine will have many cases. Alternatively, store the information for which rule to apply in a table.

Rows: variables
Columns: terminals, $ (end of string marker)
LL[i,j] contains the right-hand-side of a rule. This right-hand-side is pushed onto the stack when the left-hand-side of the rule is the variable representing the $i$ th row and the lookahead is the symbol representing the $j$ th column.
If we can specify any CFG by this type of parse table, then we can use a generic parser to determine if strings are in this language.
Gets rid of use of states

41.2.1.5. A generic parsing routine¶

Idea: To replace a variable on the top of the stack with its appropriate right-hand-side, use the lookahead and the left-hand-side to look up the right-hand-side in the LL parse table. (LL[,] is the parse table.):

push(S)
read(symbol)                                         obtain the lookahead symbol
while stack not empty do
   case top-of-stack of
      terminal:
         if top-of-stack == symbol
            then { pop(); read(symbol) }             pop terminal and get next lookahead
         else
            error
      variable:
         if LL[top-of-stack, symbol] <> error
            then { pop(),                            pop the lhs
                   push(LL[top-of-stack,symbol]) }   push the rhs
            else
               error
      end case
end while
if symbol <> $, then error

Note

For previous example, try the following traces:

Parse the string: aabbb

Parse the string: b

We will use the following functions FIRST and FOLLOW to aid in computing the table.

41.2.1.6. To construct an LL parse table LL[rows,cols]¶

Note

Refresh memory as to what parse table is.

For each rule $A \rightarrow w$
1. For each a in FIRST(w)
  
  add w to LL[A,a]
2. If $\lambda$ is in FIRST(w)
  
  add $w$ to LL[A,b] for each $b$ in FOLLOW(A)
  
  where $b \in T \cup \{\$\}$
Each undefined entry is an error.

Example 41.2.5

$S \rightarrow aSc \mid B$

$B \rightarrow b \mid \lambda$

We have already calculated FIRST and FOLLOW for this Grammar:

$\begin{split}\begin{array}{c|l|l} & FIRST & FOLLOW\\ \hline \hline S & a, b, \lambda & \$, c \\ B & b, \lambda & \$, c \\ \end{array}\end{split}$

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

$\begin{split}\begin{array}{c||c|c|c|c} & a & b & c & \$ \\ \hline \hline S & aSc & B & B & B \\ \hline B & \mbox{error} & b & \lambda & \lambda \end{array}\end{split}$

Parse string: $aacc$

$\begin{split}\begin{array}{lcccccccc} &&&&a \\ &&a&&S &S &B \\ &&S& S& c& c& c& c \\ \mbox{Stack:} & \underline{S} & \underline{c} & \underline{c} & \underline{c} & \underline{c} & \underline{c} & \underline{c} & \underline{c} \\ \mbox{symbol:} & a & a & a' & a' & c & c& c& c' \\ \end{array}\end{split}$

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 41.2.8

$L = \{a^nb^nca^mcb^m: n \ge 1, m \ge 1 \}$

S→AcB
A→aAb
A→ab
B→aBb
B→acb

$\begin{split}\begin{array}{c|l|l} & \mbox{FIRST} & \mbox{FOLLOW} \\ \hline \hline S & a & \$ \\ \hline A & a & c,b \\ \hline B & a & b,\$ \\ \end{array}\end{split}$

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

$\begin{split}\begin{array}{c||c|c|c|c} &a &b &c & \$ \\ \hline \hline S &AcB &\mbox{error} &\mbox{error} &\mbox{error} \\ \hline A &aAb &\mbox{error} &\mbox{error} &\mbox{error} \\ &ab & & & \\ \hline B &aBb &\mbox{error} &\mbox{error} &\mbox{error} \\ & acb & & & \\ \end{array}\end{split}$

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:

$\begin{split}\begin{array}{c||c|c|c|c|c|c|c} &aa &ab &ac & a\$ & b & c & \$ \\ \hline \hline S &AcB &AcB & error & error &error &error &error \\ \hline A &aAb &ab & error & error &error &error &error \\ \hline B &aBb &error & acb & error &error &error &error \\ \end{array}\end{split}$

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$

$\begin{split}\begin{array}{lcccccccccccc} &&&a&&a \\ &&&A&A&b&b\\ &&A & b& b& b& b& b&&&a\\ &&c&c&c&c&c&c&c&&c&c\\ \mbox{Stack:} & \underline{S} & \underline{B}& \underline{B}& \underline{B} & \underline{B}& \underline{B}& \underline{B}& \underline{B}& \underline{B} & \underline{b} & \underline{b} & \underline{b} \\ \mbox{symbol:} & aa & aa &aa & ab & ab & bb & bc& ca& ac &ac & cb & b\$ \\ \end{array}\end{split}$

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.

Note

Mention that LL parser doesn’t work if the grammar is left recursive.

Comments:

There are some CFL’s that have no LL(k) Parser

There are some languages for which some grammars have LL(k) parsers and some don’t.

OpenDSA Complete Catalog

Chapter 41 Parsing

41.2. LL Parsing¶

41.2.1. LL Parsing¶

41.2.1.1. LL(k) Parser¶

41.2.1.2. LL parsing process¶

41.2.1.3. Convert CFG to NPDA¶

41.2.1.4. LL Parse Table: 2-dimensional array¶

41.2.1.5. A generic parsing routine¶

41.2.1.6. To construct an LL parse table LL[rows,cols]¶