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