Editing Top-down parsing (section)

==Programming language application==
A [[compiler]] parses input from a programming language to an internal representation by matching the incoming symbols to [[Formal grammar#The syntax of grammars|production rules]]. Production rules are commonly defined using [[Backus–Naur form]]. An [[LL parser]] is a type of parser that does top-down parsing by applying each production rule to the incoming symbols, working from the left-most symbol yielded on a production rule and then proceeding to the next production rule for each non-terminal symbol encountered. In this way the parsing starts on the Left of the result side (right side) of the production rule and evaluates non-terminals from the Left first and, thus, proceeds down the parse tree for each new non-terminal before continuing to the next symbol for a production rule.

For example:

* <math>A \rightarrow aBC</math>
* <math>B \rightarrow c \mid cd</math>
* <math>C \rightarrow df \mid eg</math>

which produces the string ''A''=''acdf''

would match <math>A \rightarrow aBC</math> and attempt to match <math>B \rightarrow c \mid cd</math> next. Then <math>C \rightarrow df \mid eg</math> would be tried. As one may expect, some languages are more ambiguous than others. For a non-ambiguous language, in which all productions for a non-terminal produce distinct strings, the string produced by one production will not start with the same symbol as the string produced by another production. A non-ambiguous language may be parsed by an LL(1) grammar where the (1) signifies the parser reads ahead one token at a time. For an ambiguous language to be parsed by an LL parser, the parser must lookahead more than 1 symbol, e.g. LL(3).

The common solution to this problem is to use an [[LR parser]], which is a type of [[shift-reduce parser]], and does [[bottom-up parsing]].