parser
A parser checks whether a sequence of symbols can be generated by the grammar of the source language. A parser is expected to provide meaningful messages in case of syntax errors. In addition, a parser should handle commonly occurring errors in a way that allows it to continue processing the rest of the input. The figure illustrates the role of the parser in the compiler model.
Parsers for grammars can be divided into three categories: Universal parse methods, such as the Cocke-Younger-Kasami and Early algorithms, work for all grammars. However, these methods are too inefficient for practical use. The methods predominantly used in compilers can be classified as "top-down" or "bottom-up" methods. According to graph theory, a top-down parser starts the construction of the so-called parse tree with the leaves (top) and continues its work towards the root (bottom), while a bottom-up parser works its way up from the roots to the leaves. Both parser types read the symbols of the input successively from left to right.
The efficient top-down and bottom-up methods are restricted to subclasses of grammars. However, some of these subclasses, such as LL and LR grammars, are powerful enough to describe most syntactic constructs in programming languages. Parsers written by hand work predominantly with LL grammars. Automated tools usually generate parsers for the larger class of LR grammars.
In practice, a number of other tasks must be performed during the parse process. For example, information about the various symbols must be collected in the symbol table, type checking and other semantic analysis tasks must be performed, and intermediate code must be generated.