COMPILER CONSTRUCTION Principles and practice Kenneth C. louden
COMPILER CONSTRUCTION Principles and Practice Kenneth C. Louden
4. Top-Dowm Parsing PART ONE
4. Top-Dowm Parsing PART ONE
The outline of this chapter
The outline of this chapter
Concept of Top-Down Parsing (1) It parses an input string of tokens by tracing out the steps in a leftmost derivation And the implied traversal of the parse tree is a preorder traversal and thus occurs from the root to the leaves The example number number. and corresponds to the parse tree number
Concept of Top-Down Parsing(1) • It parses an input string of tokens by tracing out the steps in a leftmost derivation. – And the implied traversal of the parse tree is a preorder traversal and, thus, occurs from the root to the leaves. • The example: – number + number, and corresponds to the parse tree exp exp op exp number + number
Concept of Top-Down Parsing(2) The example: number number, and corresponds to the parse tree The above parse tree is corresponds to the leftmost derivations d) exp=>exp op exp (2) number op exp (3) number exp (4) number+ number number
Concept of Top-Down Parsing(2) The example: number + number, and corresponds to the parse tree • The above parse tree is corresponds to the leftmost derivations: (1) exp => exp op exp (2) => number op exp (3) => number + exp (4) => number + number exp exp op exp number + number
Two forms of Top-Down Parsers Predictive parsers attempts to predict the next construction in the input string using one or more look-ahead tokens Backtracking parsers try different possibilities for a parse of the input backing up an arbitrary amount in the input if one possibility fails It is more powerful but much slower, unsuitable for practical compilers
Two forms of Top-Down Parsers • Predictive parsers: – attempts to predict the next construction in the input string using one or more look-ahead tokens • Backtracking parsers: – try different possibilities for a parse of the input, backing up an arbitrary amount in the input if one possibility fails. – It is more powerful but much slower, unsuitable for practical compilers
Two kinds of Top - Down parsing algorithms Recursive-descent parsing is quite versatile and suitable for a handwritten parser LLO parsing The first L refers to the fact that it processes the input from left to right The second"L refers to the fact that it traces out a leftmost derivation for the input string The number 1 means that it uses only one symbol of input to predict the direction of the parse
Two kinds of Top-Down parsing algorithms • Recursive-descent parsing: – is quite versatile and suitable for a handwritten parser. • LL(1) parsing: – The first “L” refers to the fact that it processes the input from left to right; – The second “L” refers to the fact that it traces out a leftmost derivation for the input string; – The number “1” means that it uses only one symbol of input to predict the direction of the parse
Other contents Look-Ahead sets First and Follow sets: are required by both recursive descent parsing and ll(1) parsing A TNY Parser It is constructed by recursive-descent parsing algorithm Error recovery methods ne error recovery methods used in iop-Down parsing e describe d
Other Contents • Look-Ahead Sets – First and Follow sets: are required by both recursivedescent parsing and LL(1) parsing. • A TINY Parser – It is constructed by recursive-descent parsing algorithm. • Error recovery methods – The error recovery methods used in Top-Down parsing will be described
Contents PART ONE 4. 1 Top-Down Parsing by recursive-Descent More 4.2Ll(I) Parsing More PART TWO 4.3 First and follow sets 4.4A Recursive-Descent Parser for the tiny anguage 4. 5 Error recovery in Top-Down Parsers
Contents PART ONE 4.1 Top-Down Parsing by Recursive-Descent [More] 4.2 LL(1) Parsing [More] PART TWO 4.3 First and Follow Sets 4.4 A Recursive-Descent Parser for the TINY Language 4.5 Error Recovery in Top-Down Parsers
4. 1 Top-Down Parsing by Recursive-Descent
4.1 Top-Down Parsing by Recursive-Descent