a bottom-up parser has two possible actions(besidesaccept ): Shift a terminal from the front of the input to the top of the stack Reduce a string a at the top of the stack to a nonterminals, given the bnf choice A→→a a bottom-up parser is thus sometimes called a shift-reduce parser One further feature of bottom-up parsers is that, grammars are always augmented with a new start symbol s"→S
• A bottom-up parser has two possible actions (besides "accept"): Shift a terminal from the front of the input to the top of the stack Reduce a string α at the top of the stack to a nonterminal A, given the BNF choice A→α • A bottom-up parser is thus sometimes called a shift-reduce parser • One further feature of bottom-up parsers is that, grammars are always augmented with a new start symbol S' → S
Example 5. 1 The augmented grammar for balanced parentheses: s"→S s→(S)SE a bottom-up parser of the string (using this grammar is given in following table Parsing stack Input Action OS shift SO reduce S→e 234567 S(S )S shift S(S reduce s→E S(S)s Reduce S→(S)S s reduce S→S S accept
• Example 5. 1 The augmented grammar for balanced parentheses: S' → S S → (S)S|ε • A bottom-up parser of the string ( ) using this grammar is given in following table 1 2 3 4 5 6 7 Parsing stack Input Action $ $( $(S $(S) $(S)S $S $S’ ( )$ )$ )$ $ $ $ $ shift reduce S→ε shift reduce S→ε reduce S → (S)S reduce S' → S accept
Example. 5.2 The augmented grammar for rudimentary arithmetic expressions E’→E E→→E+n|n a bottom-up parse of the string n+ n using this grammar is given in following table. Parsing stack input Action ntns shift Sn + nS reduce E→n 234567 SE nS shift SE+ S shift SE+n S| reduce→E+n SE reduce E→E SE S accept
• Example. 5.2 The augmented grammar for rudimentary arithmetic expressions: E’→E E→E + n | n • A bottom-up parse of the string n + n using this grammar is given in following table. 1 2 3 4 5 6 7 Parsing stack input Action $ $n $E $E+ $E+n $E $E’ n+n$ +n$ n$ $ $ $ $ shift reduce E→n shift shift reduce E→E + n reduce E’→E accept
The handle of the right sentential form: A string, together with The position in the right sentential form where it occurs and The production used to reduce it Determining the next handle is the main task of a shift-reduce parser. Parsing stack input Action n+nS shift + nS reduce E→n 234567 nS shift SE+ s shift SE+n reduce e→E+n SE S| reduce e→E SE accept
• The handle of the right sentential form: – A string, together with – The position in the right sentential form where it occurs, and – The production used to reduce it. • Determining the next handle is the main task of a shift-reduce parser. 1 2 3 4 5 6 7 Parsing stack input Action $ $n $E $E+ $E+n $E $E’ n+n$ +n$ n$ $ $ $ $ shift reduce E→n shift shift reduce E→E + n reduce E’→E accept
Note The string of a handle forms a complete right-hand side of one production; The rightmost position of the handle string is at the top of the stack To be the handle, it is not enough for the string at the top of the stack to match the right-hand side of a production. Indeed, if an 8-production is available for reduction, as in Example 5.1, then its right-hand side (the empty string)is always at the top of the stack. Reductions occur only when the resulting string is indeed a right sentential form For example, in step 3 of Table 5.1 a reduction by S8 could be performed, but the resulting string(s s)is not a right sentential form, and thusais not the handle at this position in the sentential form(s)
• Note: – The string of a handle forms a complete right-hand side of one production; The rightmost position of the handle string is at the top of the stack; – To be the handle, it is not enough for the string at the top of the stack to match the right-hand side of a production. • Indeed, if an ε-production is available for reduction, as in Example 5.1 ,then its right-hand side (the empty string) is always at the top of the stack. • Reductions occur only when the resulting string is indeed a right sentential form. – For example, in step 3 of Table 5.1 a reduction by S→ε could be performed, but the resulting string( S S ) is not a right sentential form, and thusεis not the handle at this position in the sentential form ( S )