0
$\begingroup$

Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the language generated by a grammar.

Apart from practical considerations, such as implementation difficulty and orderliness of derivations, is there any other reason why we usually do not discuss about arbitrary derivations (not rightmost or leftmost)?

$\endgroup$
1
$\begingroup$

The main reason is that context-free grammars, once introduced, were quickly adapted to provide a theoretical basis for program language compilation. For this usage, the goal is to parse as quickly as possible using as little storage as possible. For that the best approach is to scan the input source once from 'left-to-right' [we interpret the source as a sequence of characters all on a single line], and be done with the parse exactly when done scanning the source. Two derivation patterns naturally fit into this protocol: leftmost-first derivations performed top-down in forward order, and rightmost-first derivations performed bottom-up in reverse order.

$\endgroup$
  • $\begingroup$ Seems overly narrow. GLR parsers can give you all derivations, but still only use a single scan. $\endgroup$ – James Koppel May 4 '17 at 21:58
  • 1
    $\begingroup$ @JamesKoppel: The leftmost and rightmost derivations of an unambiguous grammar describe the same tree. (Both LL and LR parsers only work with unambiguous grammars.) GLR parsers can produce all trees, so they will work with ambiguous grammars, but every tree is generated as a rightmost derivation (in reverse) because GLR is still a bottom-up technique. $\endgroup$ – rici May 5 '17 at 5:21
  • $\begingroup$ Well....then I evidently have a misconception about what rightmost derivation means. $\endgroup$ – James Koppel May 12 '17 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.