CSCE 434 Lecture 12

« previous | Friday, September 20, 2013 | next »

Lecture Slides

Ambiguities

Classic "dangling else"

if a then if b then c else d

To which if does the else belong? (by convention the closest)

Top-down Parsing

Start at root of derivation tree and fill in

picks a production and tries to match input

may require backtracking

some grammars are backtrack-free (predictive)

Left-Factor Transformation

Cannot handle left recursion, so we perform a "factoring" on our grammar:

<foo> ::= <foo> a
        | b

Critical assumption: a and b do not start with <foo>. The grammar becomes

<foo> ::= b <bar>
<bar> ::= a <bar>
        | empty

Lookahead

"Knowing the future" can prevent bad decisions and backtracking.

Interesting subclasses: LL(1) and LR(1)

Predictive Parsing

We construct a first-set of tokens:

For some $\alpha$ in the RHS of a production rule, we define $\mathrm {first} (\alpha )$ as follows:

$x\in \mathrm {first} (\alpha )$ if and only if $\alpha \to *x\gamma$ for some $\gamma$

Bottom-Up Parsing

(will be covered more in-depth later)

• Start at leaves and fill in
• Start in a state valid for legal first tokens
• As input is consumed, change state to encode possibilities (i.e. recognize valid prefixes)
• Use stack to store state and sentential forms