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