清华大学：《编译原理》课程教学资源_（英文译文）Chapter 5.1 Overview of Bottom-UpParsing

COMPILER CONSTRUCTION Principles and practice Kenneth C. louden

COMPILER CONSTRUCTION Principles and Practice Kenneth C. Louden

5. Bottom-Up Parsing PART ONE

5. Bottom-Up Parsing PART ONE

Contents PART ONE 5. 1 Overview of Bottom-Up Parsing 5.2 Finite Automata ofLR(O) Items and Lr(O) Parsing PART TWO 5.3 SLR(I Parsing 5.4 General lr(1) and lalr(1 Parsing 5.5 Yacc: An LaLR(I) Parser Generator PART THREE 5.6 Generation of a tINY Parser Using Yacc 5.7 Error Recovery in Bottom-Up Parsers

Contents PART ONE 5.1 Overview of Bottom-Up Parsing 5.2 Finite Automata of LR(0) Items and LR(0) Parsing PART TWO 5.3 SLR(1) Parsing 5.4 General LR(1) and LALR(1) Parsing 5.5 Yacc: An LALR(1) Parser Generator PART THREE 5.6 Generation of a TINY Parser Using Yacc 5.7 Error Recovery in Bottom-Up Parsers

5. 1 Overview of Bottom-Up Parsing

5.1 Overview of Bottom-Up Parsing

a bottom-up parser uses an explicit stack to perform a parse The parsing stack contains tokens, nonterminals as well as some extra state information The stack is empty at the beginning of a bottom-up parse, and will contain the start symbol at the end of a successful parse A schematic for bottom-up parsing: nputstring S S Startsymbol accept Where the parsing stack is on the left, The input is in the center, and The actions of the parser are on the right

• A bottom-up parser uses an explicit stack to perform a parse – The parsing stack contains tokens, nonterminals as well as some extra state information – The stack is empty at the beginning of a bottom-up parse, and will contain the start symbol at the end of a successful parse • A schematic for bottom-up parsing: $ InputString $ ……. $ StartSymbol $ accept – Where the parsing stack is on the left, – The input is in the center, and – The actions of the parser are on the right

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 )