Example Rightmost Derivation Input String aaabffc S ABc A Aa a B bF b F f F f Bottom Up Parsing Basics S A S ABc AbFc AbfFc Abffc Aabffc aaabffc A a A a B b F f F a CS780 Prasad L13BUPBasic 1 Example Symbol Stack Input String aa abffc Symbol Stack A Input String aaabff c Symbol Stack AB L13BUPBasic Input String The symbol stack summarizes the consumed string S A A a A a a CS780 Prasad f L13BUPBasic 2 Example Item NFA state Input String aaab ffc Symbol Stack Ab Input String aaabff c Symbol Stack AbF CS780 Prasad c B c b F A A a Input String aaab ffc NFA State Input String NFA State Input String f F NFA State f 3 aa abffc NFA State CS780 Prasad The NFA state shows the part of a rule reachable using the consumed string B b F aaabff c S A B bF A a aaabff c A a S AB c a L13BUPBasic B c b F f F f 4 1 Example State transitions Symbol stack and State stack Input String aaa bffc aaab ffc aaabf fc S A B c A b F c A State Transition CS780 Prasad b B b F B b F f F F f A a A a B c S ABc b F A Aa A a f F a reduce f L13BUPBasic 5 b A f b fc f CS780 Prasad A S A Bc A A a b B bF B b B b F f F f F B b F f F f F F f shift L13BUPBasic 6 Why trace the entire symbol stack 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 It is not possible to determine the current production state by merely inspecting a fixed number of stack symbols Input 1 Symbol Stack State The state stack is used for efficiency It avoids running the entire DFA containing production fragments to determine the next state each time L13BUPBasic aaa State stack Note 1 Redundancy CS780 Prasad Symbol Stack S A b f F c S A Bc B bF B b Input String 7 CS780 Prasad aaa a aaa A a A A a L13BUPBasic S A B A a A a B a B a Input 2 Symbol Stack State aaa a aaa B a B B a 8 2 DFA State Input strings with eqvt history Stacking states is adequate RHS of rules sharing a prefix Input String1 ab ffc Input String2 ab ge Symbol Stack A b The DFA state captures all possible rule prefixes reachable from the start symbol using the consumed input B b F S ABc ADe A Aa a B bF b D bg dB F f F f CS780 Prasad B b F f F F f L13BUPBasic 9 b S AB c S A De d D bg D CS780 Prasad D d B B b b B B b D dB S AD e L13BUPBasic 10 Relation to Grammars 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 make the transition In practice the synthesized semantic attribute associated with a stack symbol is allocated and computed on a parallel stack L13BUPBasic B D dB D b g Note 2 Redundancy CS780 Prasad S A D e A d B c A d b c The effect of reduction by B b depends on the previous state S A Bc B b State S A B c A b c 11 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 3