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 \mathrm{\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:

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{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\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 *ϵ}$, then ${\displaystyle ϵ}$ is a member of ${\displaystyle \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\alpha )}$

Building instructions:

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

Note: The definition given here is suitable for LR(1) grammars. In general for LR(k), we define ${\displaystyle {\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}}_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{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(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{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(⟨\mathrm{g}\mathrm{o}\mathrm{a}\mathrm{l}⟩)}$ (a.k.a ${\displaystyle ⟨\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}⟩}$... same concept)
2. If ${\displaystyle A::=\alpha B\beta }$, then all members of ${\displaystyle \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\beta )}$—except ${\displaystyle ϵ}$—are also in ${\displaystyle \mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(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{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(A)}$ in ${\displaystyle \mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(B)}$)
4. (A combination of the above two rules) If ${\displaystyle A::=\alpha B\beta }$ and ${\displaystyle ϵ\in \mathrm{f}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}(\beta )}$, then all members of ${\displaystyle \mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(A)}$ are in ${\displaystyle \mathrm{f}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}(B)}$.

Example

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

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