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 language) 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.

For example, a calculator program would look at an input such as " 12*(3+4)^2 " and split it into the tokens 12 , * , ( , 3 , + , 4 , ) , ^ , and 2 , each of which is a meaningful symbol in the context of an arithmetic expression. The parser would contain rules to tell it that the characters * , + , ^ , ( and ) mark the start of a new token, so meaningless tokens like " 12* " or " (3 " will not be generated.

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

Source: Wikipedia > Parsing