Unformatted text preview:

1CS780(Prasad) L13BUPBasic 1Bottom-Up Parsing BasicsCS780(Prasad) L13BUPBasic 2Example: Rightmost DerivationS -> ABcA -> Aa | aB -> bF | bF -> f F | fInput String: aaabffcSA B cA a b FA a f Fa fS => ABc=> AbFc=> AbfFc=> Abffc=> Aabffc =>* aaabffcCS780(Prasad) L13BUPBasic 3Example: Symbol StackInput String: aa | abffcSymbol Stack: ASA B cA a b FA a f Fa fInput String: aaab | ffcSymbol Stack: AbInput String: aaabff | cSymbol Stack: AbFInput String: aaabff | cSymbol Stack: ABThe symbol stack summarizes the consumed string.CS780(Prasad) L13BUPBasic 4Example: Item (NFA state)Input String: aa | abffcNFA State : A -> A.aSA B cA a b FA a f Fa fInput String: aaab | ffcNFA State : B -> b.FInput String: aaabff | cNFA State : B -> bF.Input String: aaabff | cNFA State : S -> AB.cThe NFA state shows the part of a rulereachable using the consumed string.2CS780(Prasad) L13BUPBasic 5Example: State transitionsInput String: aaa | bffcaaab|ffc aaabf|fcSA B cA 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…bState Transition CS780(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.AbfState 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 entiresymbol 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 aState:A -> a . AA -> .aInput 2: $ { a a a | a }Symbol Stack: $ { a a aState:B -> a . BB -> .a3CS780(Prasad) L13BUPBasic 9DFA State : Input strings with eqvt. history: RHS of rules sharing a prefixInput String1: ab | ffcInput String2: ab | geSymbol Stack: $ A b StateB -> 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 c => A d b cThe 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 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 usingthe standard


View Full Document

Wright CS 780 - Bottom-Up Parsing Basics

Download Bottom-Up Parsing Basics
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Bottom-Up Parsing Basics and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Bottom-Up Parsing Basics 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?