RE to CFG
expr = abc (same)
expr = a(b|c)
becomes
expr = a aux
aux = b
aux = c
expr = (a b c)*
becomes
expr = E
expr = (abc)expr
closure: fancy way of saying (keep expanding until done)
goto(state, input): returns the state you create when you get the input
i.e., the state you goto when you get the input
LL(1)
predictive parsing table has no duplicates
construct nullable sets
weakness of LL: must predict
LR: postpone decision
have seen entire right-hand side, and k lookahead
parser working bottom-up. starts with raw input, then tries to make rules.
LR(0): no lookahead. shift into state as get input
S => .x
S => .(
we could be in front of a x or (
sort of like the {1,2,3} states in the NFA => DFA conversion
exactly like that... this is the set of states we could be in
compute first set... where could this lead? what possible paths could we
be going down?
if we get to a terminal state, with a match, then we can execute the
reduction. then we GOTO the previous state, and continue parsing. goto
skips past the item once it has been parsed
S' => .S$ (state 1)
S' => S.$ (state 4)
go to state 4 after the S is parsed.
same rule all the way across
I => J (on a X)
X: terminal (shift into state J)
X: non-term goto state J
if duplicate entry, not LR
SLR: simple LR
construction almost same as LR
put reduce actions only where indicated in follow set (not all the
way across)
follow set of LEFT HAND SIDE!!!
ambiguity in grammar:
E -> T + E
E -> T
If see a T, do we shift a + or reduce the T on the spot?
follow set of E!!!
SLR grammars are those with no conflicts (multiple entries)
LR(1)
Like LR(0), but have a lookahead
LALR(1): look ahead LR(1). merge states that are identical except for
lookahead (if lookahead ignored)
for some grammars, LALR(1) can have reduce-reduce conflicts, although the
LR(1) table does not.
