Bottom Up Parsing Basics CS780 Prasad L13BUPBasic 1 Example Rightmost Derivation S ABc A Aa a B bF b F f F f Input String aaabffc S A A a S ABc AbFc AbfFc Abffc A a Aabffc aaabffc a CS780 Prasad L13BUPBasic B c b F f F f 2 Example Symbol Stack Input String aa abffc Symbol Stack A The symbol stack summarizes the consumed string S Input String aaab ffc Symbol Stack Ab Input String aaabff c Symbol Stack AbF Input String aaabff c Symbol Stack AB A A a A a a CS780 Prasad L13BUPBasic B c b F f F f 3 Example Item NFA state Input String aa abffc NFA State A A a Input String aaab ffc NFA State Input String B b F aaabff c NFA State B bF Input String aaabff c NFA State S AB c CS780 Prasad The NFA state shows the part of a rule reachable using the consumed string S A A a L13BUPBasic A a a B c b F f F f 4 Example State transitions Input String aaa bffc aaab ffc aaabf fc B c A b F c A b f F c S A S A State Transition S B B CS780 Prasad A Bc b B b F B b bF F f F b F f L13BUPBasic A a A a a B c b F f F f 5 Symbol stack and State stack Input String aaa Symbol Stack b A f b fc f State stack S ABc A Aa A a reduce CS780 Prasad A Bc A A a B bF B b S A b L13BUPBasic B b F B b F F fF f f F f F F f shift 6 Note 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 7 Why trace the entire symbol stack It is not possible to determine the current production state by merely inspecting a fixed number of stack symbols Input 1 aaa a Symbol Stack State CS780 Prasad S A B A a A a B a B a Input 2 aaa a aaa A a A A a L13BUPBasic Symbol Stack State aaa B a B B a 8 DFA State Input strings with eqvt history RHS of rules sharing a prefix Input String1 ab ffc Input String2 ab ge The DFA state captures all possible rule prefixes reachable from the start symbol using the consumed input Symbol Stack A b B b F S ABc ADe A Aa a B bF b D bg dB F f F f CS780 Prasad B b State F F fF f D b g L13BUPBasic 9 Stacking states is adequate S A B c A b S c 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 Bc B B b CS780 Prasad S AB c b b B b S A De d D d B D dB D dB B b B D D bg S AD e L13BUPBasic 10 Note 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 11 Relation to Grammars The DFA naturally corresponds to a left linear grammar S A Bc B b Q b B b Grammar Rule P Q b P The DFA state is obtained from the NFA states using the standard construction CS780 Prasad L13BUPBasic 12