COMPILER CONSTRUCTION Principles and practice Kenneth C. louden
COMPILER CONSTRUCTION Principles and Practice Kenneth C. Louden
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
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