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)
“Our goal as a parent is to give life to our children’s learning—to instruct, to teach, to help them develop self-discipline—an ordering of the self from the inside, not imposition from the outside. Any technique that does not give life to a child’s learning and leave a child’s dignity intact cannot be called discipline—it is punishment, no matter what language it is clothed in.”
—Barbara Coloroso (20th century)
“Most people, no doubt, when they espouse human rights, make their own mental reservations about the proper application of the word “human.””
—Suzanne Lafollette (1893–1983)