# Shared Flashcard Set

## Details

Comp2010 - Flashcard Set 3 - Bottom Up Parsing
Comp2010 - Flashcard Set 3 - Bottom Up Parsing
10
Computer Science
Undergraduate 2
05/27/2013

## Cards Return to Set Details

Term
 What are the principles of LR(k) Bottom up parsing?
Definition
 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
Term
 What are the principles of Shift-reduce 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 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 |
Term
 What is a handle?
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
 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
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: add goto(I, X) to C UNTIL NO MORE SETS OF ITEMS CAN BE ADDED TO C
Term
 Give an example of an SLR Set of items computation
Definition
 [image]
Term
 What are the key aspects to consider when building an SLR table?
Definition
 [image]
Supporting users have an ad free experience!