' $
J. Xue
Lecture 5: Top-Down Parsing: Table-Driven
1. LL(1) table-driven parsing
2. Parser generators
3. Recursive-descent parsing revisited
4. Error recovery
Grammar G
Eliminating left recursion & common prefixes
The Transformed Grammar G′
Constructing First, Follow and Select Sets for G′
A Recursive-Descent Parser The LL(1) Parsing Table
The LL(1) Table-Driving Parser
• The red parts done last week
• The the blue parts today
& %
COMP3131/9102 Page 263 March 29, 2010
' $
J. Xue
Predictive Non-Recursive Top-Down Parsers
• Recursion = Iteration + Stack
• Recursive calls in a recursive-descent parser can be
implemented using
– an explicit stack, and
– a parsing table
• Understanding one helps your understanding the other
& %
COMP3131/9102 Page 264 March 29, 2010
' $
J. Xue
The Structure of a Table-Driven LL(1) Parser
• Input parsed from left to right
• Leftmost derivation
• 1 token of lookahead
Stack
token
source tree
Scanner Parser
code
get next token
grammar LL(1) Table Parsing Table
Generator
• LR(1) parsers (almost always table-driven) also built this way
& %
COMP3131/9102 Page 265 March 29, 2010
' $
J. Xue
The Model of an LL(1) Table-Driven Parser
I NPUT a + b $
X LL(1) Output
S TACK
Y Parsing Program S → T
Z T → XY Z
$ ···
LL(1)
Parsing Table
Output:
• The productions used (representing the leftmost derivation), or
• An AST (Lecture 6)
& %
COMP3131/9102 Page 266 March 29, 2010
' $
J. Xue
The LL(1) Parsing Program
Push $ onto the stack
Push the start symbol onto the stack
WHILE (stack not empty) DO
BEGIN
Let X be the top stack symbol and a be the lookahead symbol in the input
IF X is a terminal THEN
IF X = a then pop X and get the next token /* match */
ELSE error
ELSE /∗ X is a nonterminal ∗/
IF T able[X, a] nonblank THEN
Pop X
Push T able[X, a] onto stack in the reverse order
ELSE error
END
The parsing is successful when the stack is empty and no errors reported
& %
COMP3131/9102 Page 267 March 29, 2010
' $
J. Xue
Building a Table-Driving Parser from a Grammar
Grammar G
Eliminating left recursion & common prefixes (Slide 247)
The Transformed Grammar G′
Constructing First, Follow and Select Sets for G′
Constructing the LL(1) Parsing Table
The LL(1) Table-Driving Parser
• Follow Slide 247 to eliminate left recursion to get a BNF grammar
• Can build a table-driven parser for EBNF as well (but not considered)
& %
COMP3131/9102 Page 268 March 29, 2010
' $
J. Xue
The Expression Grammar
• The grammar with left recursion:
Grammar 1: E → E + T | E − T | T
T → T ∗ F | T /F | F
F → INT | (E)
• The transformed grammar without left recursion:
Grammar 2: E → T Q
Q → +T Q | − T Q | ǫ
T → FR
R → ∗F R | /F R | ǫ
F → INT | (E)
& %
COMP3131/9102 Page 269 March 29, 2010
' $
J. Xue
First and Follow Sets for Grammar 2
• First sets:
First(T Q) = First(F R) = {(, i}
First(Q) = {(+, −, ǫ}
First(R) = {(∗, /, ǫ}
First(+T Q) = {+}
First(−T Q) = {−}
First(∗F R) = {∗}
First(/F R) = {/}
First((E)) = {(}
First(i) = {i}
• Follow sets:
Follow(E) = {$, )}
Follow(Q) = {$, )}
Follow(T ) = {+, −, $, )}
Follow(R) = {+, −, $, )}
Follow(F ) = {+, −, ∗, /, $, )}
& %
COMP3131/9102 Page 270 March 29, 2010
' $
J. Xue
Select Sets for Grammar 2
Select(E→T Q) = First(T Q) = {(, INT}
Select(Q→ + T Q) = First(+T Q) = {+}
Select(Q→ − T Q) = First(−T Q) = {−}
Select(Q→ǫ) = (First(ǫ) − {ǫ}) ∪ Follow(Q) = {), $}
Select(T →F R) = First(F R) = {(, INT}
Select(R→ ∗ F R) = First(+F R) = {∗}
Select(R→/F R) = First(/F R) = {/}
Select(R→ǫ) = (First(ǫ) − {ǫ}) ∪ Follow(T ) = {+, −, ), $}
Select(F →INT) = First(INT) = {INT}
Select(F →(E)) = First((E)) = {(}
& %
COMP3131/9102 Page 271 March 29, 2010
' $
J. Xue
The Rules for Constructing an LL(1) Parsing Table
For every production of the A→α in the grammar, do:
for all a in Select(A→α), set T able[A, a] = α
& %
COMP3131/9102 Page 272 March 29, 2010
' $
J. Xue
LL(1) Parsing Table for Grammar 2
INT + − ∗ / ( ) $
E TQ TQ
Q +T Q −T Q ǫ ǫ
T FR FR
R ǫ ǫ ∗F R /F R ǫ ǫ
F INT (E)
The blanks are errors.
& %
COMP3131/9102 Page 273 March 29, 2010
' $
J. Xue
An LL(1) Parse on Input i+i: INT ⇐⇒ i
S TACK I NPUT P RODUCTION D ERIVATION
$E i+i$ E→T Q E=⇒lm T Q PARSE T REE
$QT i+i$ T →F R =⇒lm F RQ
E
$QRF i+i$ F →i =⇒lm iRQ
$QRi i+i$ pop and go to next token
$QR +i$ R→ǫ =⇒lm iQ T Q
$Q +i$ Q→ + T Q =⇒lm i + T Q
$QT + +i$ pop and go to next token F R + T Q
$QT i$ T →F R =⇒lm i + F RQ
$QRF i$ F →i =⇒lm i + iRQ
i ǫ F R ǫ
$QRi i$ pop and go to next token
$QR $ R→ǫ =⇒lm i + iRQ
$Q $ Q→ǫ =⇒lm i + iQ i ǫ
$ $
& %
COMP3131/9102 Page 274 March 29, 2010
' $
J. Xue
An LL(1) Parse on an Erroneous Input ”()”
S TACK I NPUT P RODUCTION D ERIVATION
$E ()$ E→T Q E=⇒lm T Q
$QT ()$ T →F R E=⇒lm F RQ
$QRF ()$ F →(E) E=⇒lm (E)RQ
$QR)E( ()$ pop and go to next token
$QR)E )$ ∗ ∗ ∗ Error: no table entry for [E, )]
A better error message: expression missing inside ( )
& %
COMP3131/9102 Page 275 March 29, 2010
' $
J. Xue
LL(1) Grammars and Table-Driven LL(1) Parsers
• Like recursive descent, table-driven LL(1) parsers can
only parse LL(1) grammars. Conversely, only LL(1)
grammars can be parsed by the table-driven LL(1) parsers.
• Definition of LL(1) grammar given in Slide 241
• Definition of LL(1) grammar – using the parsing table:
A grammar is LL(1) if every table entry contains at most
one production.
& %
COMP3131/9102 Page 276 March 29, 2010
' $
J. Xue
Why Table-Driven LL(1) Parsers Cannot Handle Left Recursions?
• A grammar with left recursion:
hexpri → hexpri + id | id
• Select Sets:
Select(hexpri+id) = {id}
Select(id) = {id}
• The parsing table:
id $
hexpri hexpri + id
id
T able[hexpri, id] contains two entries!
• Any grammar with left recursions is not LL(1)
& %
COMP3131/9102 Page 277 March 29, 2010
' $
J. Xue
Why Table-Driven LL(1) Parsers Cannot Handle Left Recursions (Cont’d)?
• Eliminating the left recursion yields an LL(1) grammar:
hexpri → id hexpr-taili
hexpr-taili → ǫ | + id hexpr-taili
• Select Sets:
Selecthexpri→id hexpr-taili) = {id}
Select(hexpr-taili→hexpri) = = {$}
Select(hexpr-taili→+id hexpr-taili) = {+}
• The parsing table for the transformed grammar:
id + $
hexpri id hexpr-taili
hexpr-taili + id hexpr-taili ǫ
& %
COMP3131/9102 Page 278 March 29, 2010
' $
J. Xue
Why LL(1) Table-Driven Parsers Cannot Handle Common Prefixes?
• A grammar with a common prefix:
S → if (E) S | if (E) S else S | s
E → e
• Select sets:
Select(S→if (E) S) = {if}
Select(S→if (E) S else S) = {if}
• Any grammar with common prefixes is not LL(1)
• Eliminating the common prefix does not yield an LL(1) grammar:
S → if (E) SQ | s
Q → else S | ǫ
E → e
& %
COMP3131/9102 Page 279 March 29, 2010
' $
J. Xue
Why LL(1) Table-Driven Parsers Cannot Handle Common Prefixes (Cont’d)?
• Select sets:
Select(S→if(E)SQ) = {if}
Select(S→s) = {s}
Select(Q→elseS) = {else}
Select(Q→ǫ) = {else, ǫ}
Select(E→e) = {e}
• The parsing table:
if ( e ) s else $
S if E then SQ s
E e
Q else S ǫ
ǫ
• This modified grammar, although having no common prefixes, is still ambiguous.
You are referred to Week 6 Tutorial. To resolve the ambiguity in the grammar, we make the
convention to select else S as the table entry. This effectively implements the following rule:
Match an else to the most recent unmatched then
& %
COMP3131/9102 Page 280 March 29, 2010
' $
J. Xue
Recognise Palindromes Easily
• Grammar:
S → (S) | ǫ
• Parsing Table:
( ) $
S (S) ǫ ǫ
• Try to parse the following three inputs:
a. (())
b. (()
c. ())
• Cannot design a DFA/NFA to recognise the language L(S)
& %
COMP3131/9102 Page 281 March 29, 2010
' $
J. Xue
Lecture 5: Top-Down Parsing: Table-Driven
√
1. LL(1) table-driven parsing
2. Parser generators
3. Recursive-descent parsing revisited
& %
COMP3131/9102 Page 282 March 29, 2010
' $
J. Xue
The Expression Grammar
• The grammar with left recursion:
Grammar 1: E → E + T | E − T | T
T → T ∗ F | T /F | F
F → INT | (E)
• Eliminating left recursion using the Kleene Closure
Grammar 3: E → T (”+” T | ”-” T )∗
T → F (”*” F | ”/” F )∗
F → INT | “(” E “)”
All tokens are enclosed in double quotes to distinguish
them for the regular operators: (, ) and ∗
• Compare with Slide 269
& %
COMP3131/9102 Page 283 March 29, 2010
' $
J. Xue
Parser Generators (Generating Top-Down Parsers)
Recursive-Descent
Parser
Grammar G Parser Generator
LL(k) Parsing Tables
Tool Grammar Accepted Parsers and Their Implementation Languages
JavaCC EBNF Recursive-Descent LL(1) (with some LL(k) portions) in Java
COCO/R EBNF Recursive-Descent LL(1) in Pascal, C, C++,, Java, etc.
ANTLR Predicated LL(k) Recursive-Descent LL(k) in C, C++,, Java
• These and other tools can be found on the internet
• Predicated: a conditional evaluated by the parser at run time to
determine which of the two conflicting productions to use
Q → if (lookahead is ”else”) else S | ǫ
where the condition inside the box resolves the dangling-else problem.
& %
COMP3131/9102 Page 284 March 29, 2010
' $
J. Xue
Parser Generators (Generating Bottom-Up Parsers)
Grammar G Parser Generator LALR(1) Parsing Tables
Tool Grammar Accepted Parsers and Their Implementation Languages
Yacc BNF LALR(1) table-driven in C
JavaCUP BNF LALR(1) table-driven in Java
• These and other tools can be found on the internet
• Likely to deal with LR parsing at the end of the semester
& %
COMP3131/9102 Page 285 March 29, 2010
