Programming Language Application
A compiler parses input from a programming language to assembly language or an internal representation by matching the incoming symbols to 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:
would match and attempt to match next. Then 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.
Read more about this topic: Top-down Parsing
Famous quotes containing the words programming, language and/or application:
“If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.”
—Melinda M. Marshall (20th century)
“...I ... believe that words can help us move or keep us paralyzed, and that our choices of language and verbal tone have something—a great deal—to do with how we live our lives and whom we end up speaking with and hearing; and that we can deflect words, by trivialization, of course, but also by ritualized respect, or we can let them enter our souls and mix with the juices of our minds.”
—Adrienne Rich (b. 1929)
“By an application of the theory of relativity to the taste of readers, to-day in Germany I am called a German man of science, and in England I am represented as a Swiss Jew. If I come to be regarded as a bête noire the descriptions will be reversed, and I shall become a Swiss Jew for the Germans and a German man of science for the English!”
—Albert Einstein (1879–1955)