Bottom-Up Parsing BasicsExample: Rightmost DerivationExample: Symbol StackExample: Item (NFA state)Example: State transitionsSymbol stack and State stackNote 1 : RedundancyWhy trace the entire symbol stack?DFA State : Input strings with eqvt. history : RHS of rules sharing a prefixStacking states is adequateNote 2 : RedundancyRelation to GrammarsCS780(Prasad) L13BUPBasic 1 Bottom-Up Parsing BasicsCS780(Prasad) L13BUPBasic 2 Example: Rightmost DerivationS -> ABc A -> Aa | aB -> bF | bF -> f F | fInput String: aaabffc S A B c A a b FA a f Fa fS => ABc => AbFc => AbfFc => Abffc => Aabffc =>* aaabffcCS780(Prasad) L13BUPBasic 3 Example: Symbol StackInput String: aa | abffcSymbol Stack: A S A B c A a b FA a f Fa fInput String: aaab | ffcSymbol Stack: Ab Input String: aaabff | cSymbol Stack: AbF Input String: aaabff | cSymbol Stack: AB The symbol stack summarizes the consumed string.CS780(Prasad) L13BUPBasic 4 Example: Item (NFA state)Input String: aa | abffcNFA State : A -> A.a S A B c A a b FA a f Fa fInput String: aaab | ffcNFA State : B -> b.F Input String: aaabff | cNFA State : B -> bF. Input String: aaabff | cNFA State : S -> AB.c The NFA state shows the part of a rule reachable using the consumed string.CS780(Prasad) L13BUPBasic 5 Example: State transitionsInput String: aaa | bffcaaab|ffc aaabf|fc S A B c A a b FA a f Fa fS => A . B c => A b . F c => A b f . F c S -> A.BcB -> .bFB -> .b …B -> b.FB -> b.F -> .f FF -> .f …b State TransitionCS780(Prasad) L13BUPBasic 6Symbol stack and State stackS -> .ABcA -> .AaA -> .aInput String: $ aaa b f | fcSymbol Stack: $ A b fS -> A . BcA -> A.aB -> .bFB -> .bB -> b.FB -> b. F -> . f FF -> . fF -> f.FF -> f. Ab fState stackreduce shiftCS780(Prasad) L13BUPBasic 7Note 1 : Redundancy•The state stack can be generated from the sequence of symbols on the symbol stack, by tracing the derivation from the start symbol, using the productions.–The state stack is used for efficiency.–It avoids running the entire DFA (containing production fragments) to determine the next state each time.CS780(Prasad) L13BUPBasic 8Why trace the entire symbol stack? S -> [ A ] | { B }A -> a A | aB -> a B | a It is not possible to determine the “current” production (state)by merely inspecting a fixed number of stack symbols.Input 1: $ [ a a a | a ]Symbol Stack: $ [ a a a State: A -> a . AA -> .aInput 2: $ { a a a | a }Symbol Stack: $ { a a a State: B -> a . BB -> .aCS780(Prasad) L13BUPBasic 9 DFA State : Input strings with eqvt. history : RHS of rules sharing a prefix Input String1: ab | ffcInput String2: ab | geSymbol Stack: $ A b State B -> b.FB -> b. F -> . f FF -> . fD -> b.g …The DFA state captures all possible rule prefixes reachable from the start symbol using the consumed input. S -> ABc | ADeA -> Aa | aB -> bF | bD -> bg | dBF -> f F | fCS780(Prasad) L13BUPBasic 10Stacking states is adequateS => A B c => A b c S => A D e => A d B e => A d b e The effect of reduction by B -> b depends on the previous state. S -> A.BcB -> .b S -> AB.c D -> d.BB -> .b B -> b.BbD -> dB.BS -> A.DeD -> .dBD -> .bgdbS -> AD.eDCS780(Prasad) L13BUPBasic 11Note 2 : Redundancy•The state stack contains enough information to regenerate the symbol stack. Note that all arcs into a DFA state carry the same symbol label.–As a consequence, the symbol stack can be avoided by making the “reduce”-entry in the parse table specify the number of stack elements (length of RHS) to be popped and the (LHS) nonterminal to be pushed to make the transition.–In practice, the (synthesized) semantic attribute associated with a stack symbol is allocated and computed on a parallel stack.CS780(Prasad) L13BUPBasic 12Relation to Grammars• The DFA naturally corresponds to a left-linear grammar.S -> A.BcB -> .b B -> b. bGrammar Rule: P  Q bQP• The DFA state is obtained from the NFA states using the standard