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 (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \Rightarrow^+ A} ) or ε productions (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A ::= \epsilon} )

The outer loop cycles through nonterminals in order, and the inner loop ensures that a production expanding Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_i} has no non-terminal Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_j} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j < i} (forward-substituted away).

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

Invariant: for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k < i} , there does not exist a production expanding Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_k} that has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_l} in its RHS for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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