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

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}(\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 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 X} is a non-terminal 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 X ::= Y_1 \, Y_2 \, \dots \, Y_k} , then 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 \in \mathrm{frist}(X)} 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 a \in \mathrm{first}(Y_i)} 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 \epsilon \in \mathrm{first}(Y_j)} for $1\leq j<i$ (keep looking at the next 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 Y_i} until we get one that can't go 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 \epsilon} )

Follow Set

For nonterminal 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} , define 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{follow}(A)} as the set of terminals that can appear immediately to the right 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 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. 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 \mathtt{eof} \in \mathrm{follow}(\langle goal \rangle)}
2. 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 A ::= \alpha B \beta} , then put 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) \setminus \left\{ \epsilon \right\}} in 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{follow}(B)} . We don't know enough about 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} , but this rule tells us something about 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} .
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 A ::= \alpha B} , then put 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{follow}(A)} in 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{follow}(B)}
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 A ::= \alpha B \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 \epsilon \in \mathrm{first}(\beta)} , then put $\mathrm {follow} (A)$ in 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{follow}(B)} (almost the same thing as above; if nothing follows 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} , then anything that follows 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} can follow 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} by this rule)

Constructing a Parse Table

1. For any production 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} , perform steps 2–4
2. for any terminal a 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 ::= \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,a]}
3. If $\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 $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.