Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Top Down Parsing

Example

 When we are parsing, we produce a unique syntax tree from a legal
sentence
...

 So, if we are trying to recognise a sentence, what we are trying to do
is grow a parse tree corresponding to that sentence

— We will always be looking at the leftmost nonterminal
...

 If at any time there is no candidate production corresponding to the
state of the parse, we must have made a wrong turn at some earlier
stage and we will need to backtrack
...
Maciunas, Charles Lakos

S→ E
E → T | E+T
T → F | T*F
F → unit | (E)
and the expression:
1+2*3

— We are trying to find the leftmost derivation
...
e
...
S
1+2*3
only one rule: S → E
2
...
E+T
1+2*3
choose E → E+T
4
...
E+T+T+T
1+2*3
choose E → E+T

...
Maciunas, Charles Lakos

© 2003, 2004 Kevin J
...
S
1+2*3
only one rule: S → E
2
...
E+T
1+2*3
choose E → T → F→ unit
4
...
1+T
2*3
choose T → F→ unit
6
...
1+2
*3
✸WRONG

Slide 3

 We could rearrange the productions so that the left recursive ones
come at the end, and always choose the first matching production
...
The left
recursive ones are at the end of the list!
 Note that this is not an easy task in general since mutually
recursive grammars have the same problems:
A→B|CD
C→E|AF
 In general, rearranging productions will not help – the parser will
still have problems
...

 What we need is a way to deterministically parse a grammar in a
top down fashion without backtracking
...
Maciunas, Charles Lakos

Slide 4

Eliminating left recursion


Example of eliminating left recursion

An algorithm to eliminate arbitrary left recursion (by replacing it
with right recursion) is as follows:



Consider the productions:
A → a | Ba
B → b | Cb

C → c | Ac

1
...


1
...
Apply the following steps to the productions for N1, then N2,
...
For Ni :
a) For all productions Ni → Nk α, where k < i and if the productions
for Nk are Nk → β1 | β2 | β3 |
...
e
...

b) If the productions for Ni are now
Ni → α1 | α2 |
...

(where the first few are not left recursive while the latter are)
then replace them with
Ni → α1 Ni’ | α2 Ni’ |
...


2
...
Consider the productions for B: no change

CC&P 2004

© 2003, 2004 Kevin J
...
Consider the productions for C:
a) Replace C → Ac by C → ac | Bac
a) Replace C → Bac by C → bac | Cbac
Productions for C are now: C → c | ac | bac | Cbac
b) Replace the productions for C by:
C → cC’ | acC’ | bacC’

C’ → ε | bacC’

CC&P 2004

© 2003, 2004 Kevin J
...

 The only information which we can use to make the
correct decision is the input stream itself
...

— Left to right scan of input
— Left most derivation
— k symbols of look-ahead
 The grammar that an LL(k) parser recognizes is an LL(k) grammar
and any language that has an LL(k) grammar is an LL(k) language
...

— So the question is How do we know when we have an LL(1)
grammar?
 We also have LR(k) grammars and other variations, but our focus is
currently on LL(1) grammars
...


 If we are going to look ahead in order to make the correct
decision, we need a buffer in which to store the next few
symbols
...


CC&P 2004

© 2003, 2004 Kevin J
...
Maciunas, Charles Lakos

Slide 8

Definition of LL(1)

Definition of First
 To compute FIRST(X) for all grammar symbols X, apply
the following algorithm until no more terminals or ε can be
added to any FIRST set
...
If X is a terminal, then FIRST(X) is {X}
2
...
If X is a nonterminal and X → Y1 Y2
...
, FIRST (Yi-1 );
that is Y1 Y2
...

If ε is in FIRST(Yj ) for all j = 1, 2,
...
For example, everything in FIRST(Y1) is surely
in FIRST(X)
...


 When faced with a production such as:
A → α1 | α2 | α3
 We chose one of the αi uniquely by looking at the
next input symbol
...

Recall:
 First(X) is the set of all terminal symbols that can
“start” the production X
 Follow(X) is the set of terminal symbols that can
follow an “X”

CC&P 2004

© 2003, 2004 Kevin J
...
Maciunas, Charles Lakos

Definition of LL(1) property

 To compute FOLLOW(A) for all nonterminals A, apply the
following algorithm until nothing can be added to any
FOLLOW set
...
Place $ in FOLLOW(S), where S is the start symbol and
$ is the input right endmarker
...
If there is a production A → α B β then everything in
FIRST(β) except for ε is placed in FOLLOW(B)
...
If there is a production A → αB or a production A → α Bβ
where FIRST(β) contains ε (i
...
, β ⇒ * ε), then
everything in FOLLOW(A) is in FOLLOW(B)
...
Maciunas, Charles Lakos

Slide 11

Definition: A grammar G is LL(1) if and only if for all rules
A → α1 | α2 |
...
Maciunas, Charles Lakos

Slide 12

Making Grammars LL(1)

Fixing the problem

 We can't always make a grammar which is not LL(1) into
an equivalent LL(1) grammar
...

Consider the grammar
S→T
T → L B | L C array
L → long | ε
C→B |ε
B → real | integer

S→T
T → L B | L C array
L → long | ε
C→B |ε
B → real | integer
2

Transform the grammar by factorisation:
S→T
T→LX
X → B | C array
L → long | ε
C→B |ε
B → real | integer

© 2003, 2004 Kevin J
...
Maciunas, Charles Lakos

Slide 14



---