CS 460 Notes 05

Lecture

Chapter 4.20

Example: $S -> A B C$ $A -> aA | \epsilon $ $B -> bB | \epsilon $ $C -> cC | \epsilon $

$ w = abbc $

Left-most: $S -> ABC -> aABC -> aBC -> abBC -> abbBC -> abbC -> abbcC -> abbc$

Right-most: $S -> ABC -> ABcC -> ABC -> AbBc -> AbbBc -> Abbc -> aAbbc -> abbc$

NOTE: FOR RIGHT-MOST DERIVATIONS, MUST REFER TO HOW IT WAS DERIVED ON THE LEFT-MOST.

Reverse rightmost derivation of $abbc$

$ -> AbbBc -> Abbc-> aAbbc -> abbc$

First Attempt for a LR parser:

R := w
do {
  if there exists a substring $\beta$ in R such that 
  - $B -> \beta$
  - $R = \alpha\beta\alpha$
  - $\alpha\beta\alpha$ is the previous right-sentential form, then 
    $R = {\alpha}B{\alpha}$
} until (R is the start symbol S)

Problem:

For sentential form, which RHS is the handle?

Example: $E -> E + T | T$ $T -> T * F | F$ $F -> id$

$w = id + id$

$id + id <- F + id <- T + id <- E + id <- E + F <- E + T <- E $

NOTE: ALWAYS STAY ON THE LEFT MOST UNTIL IT IS DONE, THEN GO TO THE NEXT TO FINISH THE RHS

Stack Problem for RHS

Code for Stack:

stack v = []
repeat {
  if( there is a handle \beta on top of the stack v) {
    B -> \beta a prod
    pop \beta from v
    push B
  } else
    push the next token from input
} until (v = [s] or out of input and no handle on the stack)

if( v = [s] and out of input ) 
  success
else
  not success

Term: Viable Prefix

• found on page 182 chapter 4

Example 4.9.1 LR(0) Items

Let G be a CFG. $A -> \alpha$ a prodct An LR(0) item of $A -> \alpha$ is: $[A -> \alpha]$

LOOK AT CANVAS NOTES: The dot tells you how much work you have done on the right hand side.

Example: S -> E E -> E + T | T T -> T * F | F F -> id | (E)

input: (id + id) * id [S -> E] -> [S -> E] /
[E -> *E+T] [E -> T] - > [E->T] we pick the second one ([E -> T]) /
[T->TF] [T->F] / |
[T->TF] -> [T->TF] ->F [T -> TF] [T->TF] [T->F] -> [T->F] /
[F->id] [F->(E)]

an asterik represents a dot.

Creating an NFA based on a CFG

$G = (V, \sigma, P, S) $

Definition 4.9: Create $G' = (V \cup { S' }, \sigma, P \cup {S' -> s}, S' )$

Make NFA $M = (Q, V \cup \sigma, \delta, q_0, F)$

Steps:

1. $\delta(q_0, \sigma) = { [S' -> •s] | s'->s \in p }$
3. $\delta([A -> \alpha • X\beta, x) = { [A -> \alpha x • \beta] | x \in V \cup \sum }$

V \cup sum represents the terminals and nonterminals.

Look at page 186 for more examples of this process.

Parsing w/ the DFA

Look at canvas notes

The numbers shown on the stack represent what state it is in.

If a lookahead is 0, then you are not allowed to look at the input.