• A bottom up parser traces a right-most derivation in reverse
• Considers the entire right-hand-side of a production rule and the next k tokens before deciding whether a production can be applied
• Requires memory to store tokens that have been read but cannot yet be processed: push-down stack
• Less constraints on grammar that can be parsed (more powerful than LL(k) parsing)

http://www.youtube.com/watch?v=cfsN0r-DOWo

• Shift - move | one place to the right
• Reduce - apply an inverse production at the right end of the left string
• Left string can be implemented by a stack (every shift pushes symbol on the stack. Reduce pops off symbols and pushes one non-terminal to stack
• If it is legal to shift or reduce there is a Shift-reduce conflict - not as bad
• If there is a reduce-reduce conflict then it is very bad
• If we have nBw and next reductionis X -> B, then w is a string of terminals, because nXw ->nBw is a step in a right-most derivation
• The main idea is to split string into two substrings:
• Right substring is as yet unexamined by parsing
• Left substring has terminals and non-terminals
• Dividing point is marked by a . or |

A reductin that also allows further reductions back to the start symbol.

In bottom up parsing we only want to reduce at handles such that

S -*> aXw -> aBw

• Right-most non-terminal on top of the stack
• Next handle must be to the right of right-most non-terminal, because this is a right-most derivation
• Sequence of shift moves needed to reach next handle

• Use the grammar for constructing a DFA that recognizes the viable prefixes of derivations
• Itermediate step entails computing the states of a NFA, from which the DFA is generate
• LR(0) ITems
• Correspond to the states of NFA recognizing viable prefixes
• Closure operation
• Set of states in NFA representing possible productions where a derivation can be in
• Goto operation
• Computes new valid items (i.e. NFA states) given some symbol
• Set of items computation
• Corresponds to the set of NFA states in the computation of DFAs from NFAs

What does the closure operation consist over the following example grammar?

[image]

• Given a set of items I apply the following rules:
• Initially, every item of I is added to closure(I)
• If A -> nBw is in closure(I) and B -> m is a production, then add item B -> .m to closure(I)
• Repeat previous step until no more items can be added to closure(I)
• Closure aggregates the NFA state where derivation can be in
• Example closure({E' -> .E$}) =
• { 
• {E' -> .E$}, 
• {E -> .E + T}, 
• {E -> .T}, 
• {T -> .id} 
• } = I0

• Defined as a closure of the set of all items A -> cX.B such that A -> c.XB is in I
• Example:
• goto(I0, E) = {{E' -> E.$}, {E -> E .+ T}}

• C = closure({S' -> .S$})
• REPEAT
• for each set of items I in C and grammar symbol X such that goto(I, X) is not empty and not in C:
• add goto(I, X) to C
• UNTIL NO MORE SETS OF ITEMS CAN BE ADDED TO C