CSCE 434 Lecture 18

« previous | Friday, October 4, 2013 | next »

Lecture Slides

Review of Top-Down LL(1) Parsing

Grammar is LL(1) if and only if, for all non-terminals $A$, each distinct pair of productions $A::=\beta$ and $A::=\gamma$ satisfy the condition $\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\beta )\cap \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\gamma )=\mathrm{\varnothing }$

In other words, for a production rule $A::={\alpha }_1\mid {\alpha }_2\mid \dots \mid {\alpha }_n$

1. all first-sets of all production rules are pairwise disjoint
2. If ${\alpha }_j{\Rightarrow }^{*}ϵ$, then $\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(a_j)\cap \mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(A)=\mathrm{\varnothing }$, for all $1\le j\le n$, $i\ne j$.

Bottom-up (LR) Parsing

• start at leaves and use production rules to reduce to goal
• Key problem: Choosing RHS of production to use
• LR parsers use stack and lookahead to choose production.
  • Lookahead is just extra decoration for state; each state has more information.
• LR is generally more powerful than LL

Starting with start symbol $S$, any string $\alpha$ such that $S{\Rightarrow }^{*}\alpha$ is called a sentential form

• If $\alpha$ contains only terminals, then $\alpha$ is a sentence in $L(G)$
• If $\alpha$ contains at least one non-terminal, then it is just a sentential form.

Bottom-up parser repeatedly matches RHS of a productino against a substring in the current right-sentential form.

In other words, if our grammar has $A::=ab$, and we have $ab$ at the top of our stack, then we can replace the $ab$ with $A$.

Example

Consider the grammar

1 <goal> ::= a <A> <B> e
2 <A> ::= <A> b c
3       | b
4 <B> ::= d

and the input sentence abbcde

Production	Sentential Form	Handle
—	abbcde	3, 2
3	a<A>bcde	2, 4
2	a<A>de	4, 3
4	a<A><B>e	1, 4
1	<goal>	—

Handles

Definition:

• a tuple containing the matching production rule and the position in the sentence where it matches.
• a substring $\alpha$ of the current right-sentential form where $\alpha$ matches some production $A::=\alpha$ and reducing $\alpha$ to $A$ is one step in the reverse rightmost derivation

Invariant: The substring of a handle contains only terminal symbols.

Provable fact: If $G$ is unambiguous, then every right-sentential form has a unique handle.

Proof. $G$ is unambiguous, then rightmost derivation is unique. This implies that a unique production $A::=\beta$ applied to take ${\gamma }_{i-1}$ to ${\gamma }_i$. Next a unique position $k$ at which $A::=\beta$ is applied. The result is a handle $(A::=\beta ,k)$

Shift-Reduce Parsing

• Simple to understand
• Have simple, table-driven, shift-reduce skeleton
• grammatical knowledge encoded in tables

Algorithm

1. Initialize stack with "$"
2. Repeat the following until the top of the stack is the goal symbol and the input token is "end of file"
   1. Find the handle. If we don't have a handle, shift an input symbol onto the stack
   2. Prune the handle. If we have a handle $(A::=\beta ,k)$ on the stack, then reduce
      1. pop $|\beta |$ symbols off the stack
      2. push $A$ onto the stack

LR(1)

Everyone's favorite parser

Describe a proper superset of languages recognized by LL (predictive) parsers

Token token = next_token();
while (true) {
    Token s = top of stack
    if (action[s,token] == "shift s[i]") {
        push token;
        push s[i];
        token = next_token();
    } else if (action[s, token] == "reduce A ::= b") {
        pop 2 * |b| symbols;
        s = top of stack;
        push A;
        push goto[s,A];
    } else if (action[s, token] == "accept") {
        return;
    } else error();
}