CSCE 434 Lecture 13

« previous | Monday, September 23, 2013 | next »

Lecture Slides

Top-Down Parsing

1. At node $A$, select production with $A$ on LHS and for each symbol in RHS, construct appropriate child.
2. When terminal is added to fringe that doesn't fit the input string, backtrack
3. Find next nonterminal node to be expanded

How to select right production rule in step 1? → should be guided by input string

Suppose we choose to expand <expr> ::= <expr> + <term> every time:

1. <expr>
2. <expr> + <term>
3. <expr> + <term> + <term>
4. <expr> + <term> + <term> + <term>
5. …

Cannot handle left-recursion

Left Factoring

Input: Non-terminals in some order (impose any arbitrary order)

for i from 1 to n
  for j from 1 to i-1
    replace each production of the form
      Ai ::= Aj γ with the productions
      Ai ::= δ1 γ | δ2 γ | ... | δk γ
      where all current Aj productions are
        Aj ::= δ1 | δ2 | ... | δk
  eliminate any immediate left recursion on Ai using the direct transformation

This assumes that the grammar has no cycles ($A\Rightarrow ^{+}A$) or ε productions ($A::=\epsilon$)

The outer loop cycles through nonterminals in order, and the inner loop ensures that a production expanding $A_{i}$ has no non-terminal $A_{j}$ with $j<i$ (forward-substituted away).

Any new nonterminals are added to the end of the order and only involve right recursion

Invariant: for all $k<i$, there does not exist a production expanding $A_{k}$ that has $A_{l}$ in its RHS for $l<K$.

Note: Come up with an algorithm to prove that the output of an integer sorting algorithm is indeed sorted (i.e. it is a permutation of the input) Don't Google it!

Predictive Parsing

If we have one token lookahead, we can determine the step to take based only on the prefix and the next token:

Left factoring algorithm:

For each non-terminal A, find the longest prefix $\alpha$ common to two or more of its alternatives...

Can we determine whether an equivalent grammar exists that is not left-recursive and can be predictively parsed? No. Undecidable.

Looks up rules in a parsing table (encoding of automata states and rules); stack for holding states.

Both of the following lookahead grammars are predictive

• LL(1): Left to right; leftmost derivation; lookahead 1
• LR(1): Left to right; reverse rightmost derivation; lookahead 1