清华大学：《编译原理》课程教学资源_（英文译文）Chapter 4.1 Top-Down Parsing byRecursive-Descent

COMPILER CONSTRUCTION Principles and practice Kenneth C. louden

COMPILER CONSTRUCTION Principles and Practice Kenneth C. Louden

4. Top-Down Parsing PART TWO

4. Top-Down Parsing PART TWO

Contents PART ONE 4. 1 Top-Down Parsing by recursive-Descent 4.2Ll(I) Parsing More PART TWO 4.3 First and Follow Sets More 4.4A Recursive-Descent Parser for the tiny Language More 4. 5 Error recovery in Top-Down Parsers

Contents PART ONE 4.1 Top-Down Parsing by Recursive-Descent 4.2 LL(1) Parsing [More] PART TWO 4.3 First and Follow Sets [More] 4.4 A Recursive-Descent Parser for the TINY Language [More] 4.5 Error Recovery in Top-Down Parsers

4. 1 Top-Down Parsing by Recursive-Descent

4.1 Top-Down Parsing by Recursive-Descent

4.2LL(1) Parsing

4.2 LL(1) Parsing

4.2.1 The Basic Method oflL(1) Parsing

4.2.1 The Basic Method of LL(1) Parsing

Main idea LL(1 Parsing uses an explicit stack rather than recursive calls to perform a parse An example d a simple grammar for the strings of balance parentheses S→(S)S|e The following table shows the actions of a top down parser given this grammar and the string o

Main idea • LL(1) Parsing uses an explicit stack rather than recursive calls to perform a parse • An example: – a simple grammar for the strings of balanced parentheses: S→(S) S∣ε • The following table shows the actions of a top￾down parser given this grammar and the string ( )

Table of actions Steps Parsing Stack Input Action SS ()$ (S)S SS)S( ()$ match SS)S )$ →)￡ 4 SS) )$ match SS S→ε accept

Table of Actions Steps Parsing Stack Input Action 1 $S ( ) $ S→(S) S 2 $S)S( ( ) $ match 3 $S)S )$ S→ε 4 $S) )$ match 5 $S $ S→ε 6 $ $ accept

General schematic a top-down parser begins by pushing the start symbol onto the stack It accepts an input string if, after a series of actions, the stack and the input become empty A general schematic for a successful top-down parse S Start Symbol Inputstring s //one of the two actions one of the two actions acce

General Schematic • A top-down parser begins by pushing the start symbol onto the stack • It accepts an input string if, after a series of actions, the stack and the input become empty • A general schematic for a successful top-down parse: $ StartSymbol Inputstring$ … … //one of the two actions … … //one of the two actions $ $ accept

TWO Actions The two actions Generate: Replace a non-terminal a at the top of the stack by a string a(in reverse) using a grammar rule a-a, and Match: Match a token on top of the stack with the next input token The list of generating actions in the above table S→>(S)S[S→(S)S] (S[S→→8 ()[S → E Which corresponds precisely to the steps in a leftmost derivation of string This is the characteristic of top-down parsing

Two Actions • The two actions – Generate: Replace a non-terminal A at the top of the stack by a string α(in reverse) using a grammar rule A →α, and – Match: Match a token on top of the stack with the next input token. • The list of generating actions in the above table: S => (S)S [S→(S) S] => ( )S [S→ε] => ( ) [S→ε] • Which corresponds precisely to the steps in a leftmost derivation of string ( ). • This is the characteristic of top-down parsing