The role of the parser

The input for the parser is a stream of tokens from lexical analysis and output is a parse tree, in which tokens are grouped hierarchically with collective meaning. It should report: any syntax errors, recover from commonly occurring errors, collecting information about various tokens, performing type checking, generating intermediate code, etc.

The most efficient top-down and bottom-up methods work only for subclasses of grammars, but several of these classes, particularly, LL and LR grammars, are expressive enough to describe most of the syntactic constructs in modern programming languages. Parsers implemented by hand often use LL grammars; for example, the predictive-parsing approach works for LL grammars. Parsers for the larger class of LR grammars are usually constructed using automated tools.


Types of parsers for grammar are: top-down: build parse tree from root to the leaves and bottom-up: build parse tree from leaves to the root. Input the parser is scanned from left to right, one symbol at a time.

0 comments