Term
What are the principles of LR(k) Bottom up parsing? 

Definition
 A bottom up parser traces a rightmost derivation in reverse
 Considers the entire righthandside 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: pushdown stack
 Less constraints on grammar that can be parsed (more powerful than LL(k) parsing)
http://www.youtube.com/watch?v=cfsN0rDOWo 


Term
What are the principles of Shiftreduce parsing? 

Definition
 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 nonterminal to stack
 If it is legal to shift or reduce there is a Shiftreduce conflict  not as bad
 If there is a reducereduce 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 rightmost derivation
 The main idea is to split string into two substrings:
 Right substring is as yet unexamined by parsing
 Left substring has terminals and nonterminals
 Dividing point is marked by a . or 



Term

Definition
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 


Term
What are some characteristics immediately after reducing a handle? 

Definition
 Rightmost nonterminal on top of the stack
 Next handle must be to the right of rightmost nonterminal, because this is a rightmost derivation
 Sequence of shift moves needed to reach next handle



Term
How to construct parsing tables? 

Definition
 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



Term
What does the closure operation consist over the following example grammar?
[image] 

Definition
 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



Term
Define the goto(I, X) operation where I is a set of items and X is a grammar symbol 

Definition
 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}}



Term
How to compute the sets of items? 

Definition
 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:
 UNTIL NO MORE SETS OF ITEMS CAN BE ADDED TO C



Term
Give an example of an SLR Set of items computation 

Definition


Term
What are the key aspects to consider when building an SLR table? 

Definition

