Category:CSCE 434 Exam 1

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

Lexical Analysis (Scanning)

Syntax Analysis (Parsing)

LL Parsing

• Top-down parsers
• build parse tree from root to leaves

LR Parsing

• Bottom-up parsers
• build parse tree from leaves to root

LR(1)

• scan input from left to right (L)
• build rightmost derivation in reverse (R)
• use a single token lookahead to disambiguate (1)
• Simple, Table-driven, shift-reduce skeleton
• grammatical knowledge encoded in (parse lookup) tables
• In general, LR parsers are practical, efficient, and easy to build

Skeleton Parser code:

def lr_parse(toks):
    stack = Stack();
    tokiter = iter(toks)
    tok = tokiter.next()

    while True:
        curr_state = stack.top()

        # Possible values are:
        #   ("shift", state_id),
        #   ("reduce", production{lhs,rhs}), or
        #   ("accept", None)
        behavior, payload = action[curr_state, tok]

        if behavior == "shift":
            next_state = payload

            stack.push(tok)
            stack.push(next_state)
            tok = tokiter.next()

        elif behavior == "reduce":
            A = payload['lhs']
            b = payload['rhs']

            stack.pop(2*len(b))
            curr_state = stack.top()
            stack.push(A)
            push goto[curr_state, A]

        elif behavior == "accept"
            return

        else:
            error()

This has a running time of ${\displaystyle \Theta (k+l)}$, where ${\displaystyle k}$ is the number of shifts (the length of the input string), and ${\displaystyle l}$ is the number of reduces (depends on the grammar).

Example Tables

The following grammar:

1 <goal>   ::= <expr>
2 <expr>   ::= <term> + <expr>
3            | <term>
4 <term>   ::= <factor> * <term>
5            | <factor>
6 <factor> ::= id

gets translated into the following action and goto tables:

	action				goto
	id	+	*	$ (eof)	${\displaystyle \left\langle \mathrm {expr} \right\rangle }$	${\displaystyle \left\langle \mathrm {term} \right\rangle }$	${\displaystyle \left\langle \mathrm {factor} \right\rangle }$
${\displaystyle S_{0}}$	(shift, ${\displaystyle S_{4}}$)				${\displaystyle S_{1}}$	${\displaystyle S_{2}}$	${\displaystyle S_{3}}$
${\displaystyle S_{1}}$				(accept, _)
${\displaystyle S_{2}}$		(shift, ${\displaystyle S_{5}}$)		(reduce, ${\displaystyle \left\langle \mathrm {expr} \right\rangle ::=\left\langle \mathrm {term} \right\rangle }$)
${\displaystyle S_{3}}$		(reduce, ${\displaystyle \left\langle \mathrm {term} \right\rangle ::=\left\langle \mathrm {factor} \right\rangle }$)	(shift, ${\displaystyle S_{6}}$)	(reduce, ${\displaystyle \left\langle \mathrm {term} \right\rangle ::=\left\langle \mathrm {factor} \right\rangle }$)
${\displaystyle S_{4}}$		(reduce, ${\displaystyle \left\langle \mathrm {factor} \right\rangle ::=\mathrm {id} }$)	(reduce, ${\displaystyle \left\langle \mathrm {factor} \right\rangle ::=\mathrm {id} }$)	(reduce, ${\displaystyle \left\langle \mathrm {factor} \right\rangle ::=\mathrm {id} }$)
${\displaystyle S_{5}}$	(shift, ${\displaystyle S_{4}}$)				${\displaystyle S_{7}}$	${\displaystyle S_{2}}$	${\displaystyle S_{3}}$
${\displaystyle S_{6}}$	(shift, ${\displaystyle S_{4}}$)					${\displaystyle S_{8}}$	${\displaystyle S_{3}}$
${\displaystyle S_{7}}$				(reduce, ${\displaystyle \left\langle \mathrm {expr} \right\rangle ::=\left\langle \mathrm {term} \right\rangle +\left\langle \mathrm {expr} \right\rangle }$)
${\displaystyle S_{8}}$		(reduce, ${\displaystyle \left\langle \mathrm {term} \right\rangle ::=\left\langle \mathrm {factor} \right\rangle *\left\langle \mathrm {term} \right\rangle }$)		(reduce, ${\displaystyle \left\langle \mathrm {term} \right\rangle ::=\left\langle \mathrm {factor} \right\rangle *\left\langle \mathrm {term} \right\rangle }$)

First and Follow Sets

Used to build LR(1) tables.

First Set

Given a terminal or non-terminal grammar symbol ${\displaystyle \alpha }$, the first set ${\displaystyle \mathrm {first} (\alpha )}$ is the set of tokens (terminal symbols) that are the first symbol in all possible strings derivable from ${\displaystyle \alpha }$.

If ${\displaystyle \alpha \Rightarrow *\epsilon }$, then ${\displaystyle \epsilon }$ is a member of ${\displaystyle \mathrm {first} (\alpha )}$

Building instructions:

1. If ${\displaystyle X}$ is a terminal, then ${\displaystyle \mathrm {first} (X)=\left\{X\right\}}$.
2. If ${\displaystyle X::=\epsilon }$, then ${\displaystyle \epsilon \in \mathrm {first} (X)}$.
3. If ${\displaystyle X::=Y_{1}\,Y_{2}\,\dots \,Y_{k}}$, then put ${\displaystyle \mathrm {first} (Y_{1})}$ in ${\displaystyle \mathrm {first} (X)}$ (i.e. ${\displaystyle \mathrm {first} (X)\subseteq \mathrm {first} (Y_{1})}$).
4. In the rule above, suppose the first ${\displaystyle k}$ nonterminals ${\displaystyle Y_{1}\,\dots \,Y_{k}}$ all have ${\displaystyle \epsilon }$ in their first-sets , this tells us that if ${\displaystyle a\in \mathrm {first} (Y_{k+1})}$, then ${\displaystyle a}$ is a valid member of ${\displaystyle \mathrm {first} (X)}$ and each ${\displaystyle \left.\mathrm {first} (Y_{i})\right|_{i=1}^{k}}$

Note: The definition given here is suitable for LR(1) grammars. In general for LR(k), we define ${\displaystyle \mathrm {first} _{k}(\alpha )}$ as the leading ${\displaystyle k}$ tokens (not just 1) that begin strings derived from ${\displaystyle \alpha }$.

Follow Set

Given a non-terminal grammar symbol ${\displaystyle A}$, the follow set ${\displaystyle \mathrm {follow} (A)}$ is the set of terminals that can appear immediately after ${\displaystyle A}$:

Suppose both ${\displaystyle \alpha A\beta }$ and ${\displaystyle \alpha A\gamma }$ appear as valid sentential forms (RHS of some other productions). Then ${\displaystyle \beta }$ and ${\displaystyle \gamma }$ are both members of the follow set of ${\displaystyle A}$.

Building instructions:

1. Place eof in ${\displaystyle \mathrm {follow} (\left\langle \mathrm {goal} \right\rangle )}$ (a.k.a ${\displaystyle \left\langle \mathrm {start} \right\rangle }$... same concept)
2. If ${\displaystyle A::=\alpha B\beta }$, then all members of ${\displaystyle \mathrm {first} (\beta )}$—except ${\displaystyle \epsilon }$—are also in ${\displaystyle \mathrm {follow} (B)}$.
3. If ${\displaystyle A::=\alpha B}$, then anything that follows ${\displaystyle A}$ can follow ${\displaystyle B}$ (i.e. put all members of ${\displaystyle \mathrm {follow} (A)}$ in ${\displaystyle \mathrm {follow} (B)}$)
4. (A combination of the above two rules) If ${\displaystyle A::=\alpha B\beta }$ and ${\displaystyle \epsilon \in \mathrm {first} (\beta )}$, then all members of ${\displaystyle \mathrm {follow} (A)}$ are in ${\displaystyle \mathrm {follow} (B)}$.

Example

In the grammar above, the first and follow sets of each symbol are:

Symbol	first	follow
${\displaystyle \left\langle \mathrm {goal} \right\rangle }$	${\displaystyle \left\{\mathrm {id} \right\}}$	${\displaystyle \left\{\mathrm {eof} \right\}}$
${\displaystyle \left\langle \mathrm {expr} \right\rangle }$	${\displaystyle \left\{\mathrm {id} \right\}}$	${\displaystyle \left\{\mathrm {eof} \right\}}$
${\displaystyle \left\langle \mathrm {term} \right\rangle }$	${\displaystyle \left\{\mathrm {id} \right\}}$	${\displaystyle \left\{\mathrm {eof} ,+\right\}}$
${\displaystyle \left\langle \mathrm {factor} \right\rangle }$	${\displaystyle \left\{\mathrm {id} \right\}}$	${\displaystyle \left\{\mathrm {eof} ,+,*\right\}}$
${\displaystyle +}$	${\displaystyle \left\{+\right\}}$	${\displaystyle \emptyset }$
${\displaystyle *}$	${\displaystyle \left\{*\right\}}$	${\displaystyle \emptyset }$
${\displaystyle \mathrm {id} }$	${\displaystyle \left\{\mathrm {id} \right\}}$	${\displaystyle \emptyset }$

LR(k) Items

Table construction algorithms use LR(k) items to represent the set of possible states in a parse.

an LR(k) item is a pair ${\displaystyle [\alpha ,\beta ]}$ where

• ${\displaystyle \alpha }$ is a production rule from ${\displaystyle G}$ with a ${\displaystyle \cdot }$ at some position in the RHS
• ${\displaystyle \beta }$ is a lookahead string containing ${\displaystyle k}$ symbols (terminals or eof)

(two cases of interest here are when ${\displaystyle k=0}$ and ${\displaystyle k=1}$:

• LR(0) items play a key role in SLR(1) table construction
• LR(1) items play a role in LR(1) and LALR(1) construction

A sentential form is a partially expanded parse (mixed terminals and nonterminals) that might appear as the RHS of a production rule, for example. In particular, a right-sentential form is a sentential form in which only the right side has been expanded.

A handle is a substring in a rule. For example, ${\displaystyle A::=\beta }$ (or simply just ${\displaystyle \beta }$) provides a handle for ${\displaystyle \alpha \beta \omega }$ since ${\displaystyle \beta }$ could be reduced to form ${\displaystyle \alpha A\omega }$.

A viable prefix is the prefix of a right sentential form that could potentially appear on the stack of a shift-reduce parser. In other words, it does not continue past the end of the handle for that sentential form. Note that in the example above, ${\displaystyle \omega }$ must consist only of terminal symbols, and viable prefixes consist of initial substrings of ${\displaystyle \alpha \beta }$.

Table Construction Algorithms

1. SLR(1)
   • grammar space: smallest class of grammars
   • table size: smallest number of states
   • performance: simple, fast construction
2. LR(1)
   • grammar space: full set of LR(1) grammars
   • table size: largest number of states
   • performance: slow, large construction
3. LALR(1)
   • grammar space: intermediate sized set of grammars
   • table size: same as SLR(1) — small
   • performance: canonical construction is slow and large

Better construction techniques exist