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