COMPILER CONSTRUCTION Principles and practice Kenneth C. louden
COMPILER CONSTRUCTION Principles and Practice Kenneth C. Louden
5. Bottom-Up Parsing PART TWO
5. Bottom-Up Parsing PART TWO
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(1 Parsing MoreI 5.4 General lr(1) and lalr(1 Parsing more] 5.5 Yacc: An Lalr(I) Parser Generator[More 5.6 Generation of a TINY Parser Using Yacc 5.7 Error Recovery in Bottom-Up Parsers More
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[More] 5.4 General LR(1) and LALR(1) Parsing [More] 5.5 Yacc: An LALR(1) Parser Generator[More] 5.6 Generation of a TINY Parser Using Yacc 5.7 Error Recovery in Bottom-Up Parsers[More]
LR(O Items of A grammar A"→A A→(A)a This grammar has eight items: A"→A A→A A→(A A→(A) A→(A) A→→(A) A A
LR(0) Items of A Grammar A' → A A → (A)|a This grammar has eight items: A' → ·A A' → A· A → ·(A) A → (·A) A → (A·) A → (A)· A → ·a A → a·
DFA and the lr(o Parsing of The grammar: A(A)a A Parsing stack input Action 1|$0 ((a))$shift 2|$0(3 a))$ shift 3s0(3(3 a )s shift 4|$0(3(3a2 )s| reduce a→a 5|$0(3(3A4 ))S shift $0(3(3A4)5 (A) 7$0(3A s shift 8|$0(3A4)5 reduce $0A1
DFA and the LR(0) Parsing of The grammar: A → ( A ) | a A’ →·A A →·(A) A →·a 0 A A’ →A· 1 A → a· 2 A →(·A) A →·(A) A →·a 3 A a A →(A)· 5 ) ( ( a A →(A·) 4 1 2 3 4 5 6 7 8 9 Parsing stack input Action $ 0 $ 0 ( 3 $ 0 ( 3 ( 3 $ 0 ( 3 ( 3 a 2 $ 0 ( 3 ( 3 A 4 $ 0 ( 3 ( 3 A 4 ) 5 $ 0 ( 3 A 4 $ 0 ( 3 A 4 ) 5 $ 0 A 1 ( (a) )$ ( a) )$ a )$ ) )$ ) )$ )$ )$ $ $ shift shift shift reduce A→a shift reduce A→(A) shift reduce A→(A) accept
The Lr(o) parsing table State Action Rule Input Goto A shift 2 012345 reduce A→A reduce|A→a shift 3 shift reduce|A→(A) 1. One column is reserved to indicate the actions for each state 2. A further column is used to indicate the grammar choice for the reduction: 3. For each token there is a column to represent the new state 4. Transitions on non-terminals are listed in the goto sections
The LR(0) parsing table 1. One column is reserved to indicate the actions for each state; 2. A further column is used to indicate the grammar choice for the reduction; 3. For each token, there is a column to represent the new state; 4. Transitions on non-terminals are listed in the Goto sections. State Action Rule Input Goto 0 1 2 3 4 5 shift reduce reduce shift shift reduce A’→A A→a A→(A) ( a ) A 3 3 2 2 5 1 4
5.3 SLR(1 Parsing
5.3 SLR(1) Parsing
SLR(I, called simple lr(1)parsing, uses the DFA of sets of lr(O) items as constructed in the previous section sLR(I increases the power of lr(o) parsing significant by using the next token in the input strin g First, it consults the input token before a shift to make sure that an appropriate dFa transition exists Second. it uses the follow set of a non -terminal to decide if a reduction should be performed
SLR(1), called simple LR(1) parsing, uses the DFA of sets of LR(0) items as constructed in the previous section SLR(1) increases the power of LR(0) parsing significant by using the next token in the input string – First, it consults the input token before a shift to make sure that an appropriate DFA transition exists – Second, it uses the Follow set of a non-terminal to decide if a reduction should be performed
5.3.1 The slr(1 Parsing Algorithm
5.3.1 The SLR(1) Parsing Algorithm
Definition of The sir(1) parsing algorithm(1) Let s be the current state actions are defined as follows 1. If state s contains any item of form A→Xβ where X is a terminal and X is the next token in the input string then to shift the current input token onto the stack and push the new state containing the item A→aX·阝 2. If state s contains the complete item A-Y and the next token in input string is in FollOw(A) then to reduce by the rule a-y
Definition of The SLR(1) parsing algorithm(1) Let s be the current state, actions are defined as follows: . 1.If state s contains any item of form A → α·Xβ where X is a terminal, and X is the next token in the input string, then to shift the current input token onto the stack, and push the new state containing the item A → αX·β 2. If state s contains the complete item A → γ·, and the next token in input string is in Follow(A) then to reduce by the rule A → γ