Parser, Parser

Looking for Parsing?

The parser often uses a separate lexical analyser to create tokens from the sequence of input characters. Parsers may be programmed by hand or may be semi-automatically generated (in some programming languages) by a tool (such as Yacc) from a grammar written in Backus-Naur form.

Informally, the reason is that the memory of such a language is limited. The grammar cannot remember the presence of a construct over an arbitrarily long input; this is necessary for a language in which, for example, a name must be declared before it may be referenced. More powerful grammars that can express this constraint, however, cannot be parsed efficiently. Thus, it is a common strategy to create a relaxed parser for a context-free grammar which accepts a superset of the desired language constructs (that is, it accepts some invalid constructs); later, the unwanted constructs can be filtered out.

LL parsers will generate a leftmost derivation and LR parsers will generate a rightmost derivation (although usually in reverse).

Source: Wikipedia > Parsing