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 {first} (\alpha )$ is the set of terminal symbols that begin strings derived from α

If $\alpha \Rightarrow ^{*}\epsilon$, then $\epsilon \in \mathrm {first} (\alpha )$.

Building $\mathrm {first} (X)$:

1. If $X$ is a terminal, $\mathrm {first} (X)=\left\{X\right\}$.
2. If $X::=\epsilon$, then $\epsilon \in \mathrm {first} (X)$
3. If $X::=Y_{1}\,Y_{2}\,\dots \,Y_{k}$, then put $\mathrm {first} (Y_{1})$ in $\mathrm {first} (X)$
4. If $X$ is a non-terminal and $X::=Y_{1}\,Y_{2}\,\dots \,Y_{k}$, then $a\in \mathrm {frist} (X)$ if $a\in \mathrm {first} (Y_{i})$ and $\epsilon \in \mathrm {first} (Y_{j})$ for $1\leq j<i$ (keep looking at the next $Y_{i}$ until we get one that can't go to $\epsilon$)

Follow Set

For nonterminal $A$, define $\mathrm {follow} (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 {eof}}\in \mathrm {follow} (\langle goal\rangle )$
2. If $A::=\alpha B\beta$, then put $\mathrm {first} (\beta )\setminus \left\{\epsilon \right\}$ in $\mathrm {follow} (B)$. We don't know enough about $A$, but this rule tells us something about $B$.
3. If $A::=\alpha B$, then put $\mathrm {follow} (A)$ in $\mathrm {follow} (B)$
4. If $A::=\alpha B\beta$ and $\epsilon \in \mathrm {first} (\beta )$, then put $\mathrm {follow} (A)$ in $\mathrm {follow} (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 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 \epsilon \in first(\alpha)} , add 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 ::= a} to 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 M[A,b]} for all terminals 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 b \in \mathrm{follow}(A)} .
4. If 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 \epsilon \in \mathrm{first}(\alpha)} and 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 eof \in \mathrm{follow}(A)} , add 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 ::= \alpha} to 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 M[A,\mathtt{eof}]} .
5. Set each undefined entry of 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 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 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} , teach distinct pair of 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 ::= \beta} and 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 ::= \gamma} satisfy the following condition: 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 \mathrm{first}(\beta) \cap \mathrm{first}(\gamma) = \emptyset} .

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 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} begins with a distinct terminal is a simple LL(1) grammar.