清华大学：《编译原理》课程教学资源_（英文译文）Chapter 5.3 SLR（1）Parsing

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 → γ