Parser in Top Down Parsing

Role of Parser

Accepts string of tokens from scanner

Verifies that the string can be generated by the grammar for the source language

In this scenario we can compare the parser with a MASTER and the scanner with a SERVANT. The scanner generates and returns tokens only when asked by the parser like SERVANT performing a task when it is entrusted by his MASTER

This can be pictorially represented as,

Generally when parser is parsing it's input, it must

Report any syntax error in an understandable way and should also recover from common errors automatically to continue processing the remainder of it's input

That means the parser should not stop immediately after encountering the first error but must proceed by making some corrections and parse the remaining input that produce errors present in the entire input

Syntax Errors

Errors can be

Lexical: Misspelled identifier, keyword or operator

Syntactic: Expressions with unbalanced parentheses

Semantic: Mismatching between operand and operator

Logical: Infinite loop

Parsing Techniques or Algorithms:
1. Earley's Algorithm
2. Cocke-Younger-Kasami Algorithm
3. Top Down Parsing Method
4. Bottom Up Parsing Method

• The first two can parse any grammar, but are inefficient in production of compilers
• The last two can parse only a class of grammars, which can describe most of the syntactic construct in programming language
• In Top down parsing method, parse tree is constructed from top to bottom whereas in bottom up it is constructed from bottom to top
• In both Top down and Bottom up methods the input is scanned from left to right, one symbol at a time

Parse Trees

Home

Top Down Parsing Methods