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