CSCE 434 Lecture 16

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

Lecture Slides

Tangent: Recursive Programs

Speed: Recursion is not usually fast.

1. Create stack frame
2. push arguments onto stack
3. execute function call
4. pop stack

Some compilers convert them to loops instead of recursion.

Optimizing a for-loop is easier than a while-loop because a for-loop is bounded. (something about GPUs) Both are difficult, but an unbounded while-loop is harder.

Predictive parsing

• tables built from specification
• state stack
• parser reads from tables; process is an implementation of a finite state machine

LL(1) Parse Algorithm

int tos = 0;
stack[tos++] = eof;
stack[tos++] = start_symbol;
Token token = next_token();
Token X = Stack[tos];
do {
  if (X is a terminal || X == eof) {
    if (X == Token) {
      pop X;
      token = next_token();
    } else error();
  } else {  // X is a non-terminal
    if (M[X,token] == "X ::= { Y[1], Y[2], ..., Y[k] }")
      pop X;
      push Y[k], Y[k-1], ..., Y[1]
    } else error()
  }
  X = stack[tos];
} while (X != eof)

LL(1) Table for our grammar

	id	num	+	-	*	/	eof
<goal>	<g> ::= <e>	<g> ::= <e>
<expr>	<e> ::= <t> <e'>	<e> ::= <t> <e'>
<expr'>			<e'> ::= + <t> <e'>	<e'> ::= - <t> <e'>			<e'> ::= ε
<term>	<t> ::= <f> <t'>	<t> ::= <f> <t'>
<term'>			<t'> ::= ε	<t'> ::= ε	<t'> ::= * <f> <t'>	<t'> ::= / <f> <t'>	<t'> ::= ε
<factor>	<f> ::= id	<f> ::= num

First Set

$\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\alpha )$ is the set of terminal symbols that begin strings derived from α

If $\alpha {\Rightarrow }^{*}ϵ$, then $ϵ\in \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\alpha )$.

Building $\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(X)$:

1. If $X$ is a terminal, $\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(X)=\left\{X\right\}$.
2. If $X::=ϵ$, then $ϵ\in \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(X)$
3. If $X::=Y_1{Y}_2\dots Y_k$, then put $\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(Y_1)$ in $\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(X)$
4. If $X$ is a non-terminal and $X::=Y_1{Y}_2\dots Y_k$, then $a\in \mathrm{f}\mathrm{r}\mathrm{i}\mathrm{s}\mathrm{t}(X)$ if $a\in \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(Y_i)$ and $ϵ\in \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(Y_j)$ for $1\le j<i$ (keep looking at the next $Y_i$ until we get one that can't go to $ϵ$)

Follow Set

For nonterminal $A$, define $\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(A)$ as the set of terminals that can appear immediately to the right of $A$ in some sentential form.

Thus a non-terminal's follow set specifies the tokens that can legally appear after it

A terminal symbol has now follow set.

To build:

1. $\mathtt{e}\mathtt{o}\mathtt{f}\in \mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(⟨goal⟩)$
2. If $A::=\alpha B\beta$, then put $\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\beta )\setminus \left\{ϵ\right\}$ in $\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(B)$. We don't know enough about $A$, but this rule tells us something about $B$.
3. If $A::=\alpha B$, then put $\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(A)$ in $\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(B)$
4. If $A::=\alpha B\beta$ and $ϵ\in \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\beta )$, then put $\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(A)$ in $\mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(B)$ (almost the same thing as above; if nothing follows $B$, then anything that follows $A$ can follow $B$ by this rule)

Constructing a Parse Table

1. For any production $A::=\alpha$, perform steps 2–4
2. for any terminal a in first(\alpha), add $A::=\alpha$ to $M[A,a]$
3. If $ϵ\in first(\alpha )$, add $A::=a$ to $M[A,b]$ for all terminals $b\in \mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(A)$.
4. If $ϵ\in \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\alpha )$ and $eof\in \mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(A)$, add $A::=\alpha$ to $M[A,\mathtt{e}\mathtt{o}\mathtt{f}]$.
5. Set each undefined entry of $M$ to error

If this fails, the grammar is not LL(1), so we can make it LL(1) by adding non-terminals:

Adding non-terminals to the grammar does not change the language it accepts.

LL(1) Grammars

A grammar is LL(1) if and only if for all non-terminals $A$, teach distinct pair of productions $A::=\beta$ and $A::=\gamma$ satisfy the following 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 }$.

Properties:

• no left-recursive grammar is LL(1)
• no ambiguous grammar is LL(1)
• LL(1) parsers operate in linear time
• epsilon-free grammar , where each alternative expansion for $A$ begins with a distinct terminal is a simple LL(1) grammar.