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 topdown 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