Rightmost DerivationEdit
Rightmost derivation is a fundamental concept in the theory of formal languages, describing a way to obtain strings from a start symbol by repeatedly rewriting the rightmost nonterminal in the current sentential form. In the study of context-free grammars, rightmost derivations provide a complementary perspective to leftmost derivations, and together they illuminate how a grammar can generate exactly the strings in its language. In practical terms, rightmost derivations underpin some parsing techniques, especially those that work by reversing a derivation to build a string from its components.
In a formal setting, the idea rests on the notion of a sentential form and a production rule. A derivation is a sequence of steps where each step applies a grammar rule to replace a nonterminal with a string of symbols. A rightmost derivation specifically requires that, at every step, the nonterminal chosen for replacement is the rightmost nonterminal present in the current form. The result is a derivation that corresponds to a particular path in the associated parse tree, typically from the root toward the leaves when read in a right-to-left fashion. See context-free grammar for the general framework, and parse tree for the visualization of how the derivation expands.
Formal definition
Let G = (V, Σ, R, S) be a context-free grammar, where V is the set of nonterminals, Σ is the set of terminals, R is the set of production rules, and S ∈ V is the start symbol. A derivation is a sequence α0 ⇒ α1 ⇒ … ⇒ αn of sentential forms, where α0 = S and each αi+1 is obtained from αi by applying a production A → β with A ∈ V and β ∈ (V ∪ Σ)*, replacing A in αi by β. A rightmost derivation is a derivation in which, at each step, the replacement is performed on the rightmost nonterminal of αi.
Example: Grammar: - S → AB - A → a - B → b
Rightmost derivation of the string "ab": - S ⇒ AB - AB ⇒ aB (rewrite the rightmost nonterminal B) - aB ⇒ ab (rewrite B using B → b)
A slightly more involved example, illustrating how a rightmost derivation handles recursion, uses the grammar: - S → aS | a
Rightmost derivation of "aaa": - S ⇒ aS - aS ⇒ aaS - aaS ⇒ aaa
If a string w ∈ Σ* can be derived from S by a sequence of productions, then there exists a rightmost derivation for w in one of the grammars that generate w. Conversely, every rightmost derivation corresponds to a parse tree whose root is S and whose leaves, read left to right, yield w.
Relationship to leftmost derivation and parse trees
A key result in the theory of CFGs is that, for any string in the language of an unambiguous grammar, there exists both a leftmost derivation and a rightmost derivation that generate that string. The choice between leftmost and rightmost derivations affects the order in which nonterminals are expanded, but not the set of strings generated by the grammar. When a grammar is unambiguous, there is a unique parse tree for each string, and both derivation orders trace the same tree in opposite directions. See leftmost derivation for the corresponding concept and parse tree for the graphical representation.
In cases where grammars are ambiguous, multiple distinct parse trees can generate the same string, and different derivations—leftmost, rightmost, or otherwise—may realize different trees. This is an important area of study in formal language theory, influencing how grammars are designed for programming languages and other formal systems.
In parsing and compiler design
Parsing strategies—the algorithms that analyze strings according to a grammar—often draw a direct connection to derivation order. LL parsers, which perform top-down parsing, implement a form of leftmost derivation in real time, attempting to predict which production to apply based on the current lookahead. In contrast, bottom-up parsers, including various LR parsing algorithms, effectively reconstruct a rightmost derivation in reverse. By reducing substrings to nonterminals in a way that mirrors reversing a rightmost derivation, LR parsers can efficiently handle a wide class of grammars and are central to many practical compilers and interpreters. See LR parsing and bottom-up parsing for more on these approaches.
Rightmost derivations also connect to parsing formalisms like Chomsky normal form, where derivations have a structured, uniform shape that often makes reverse derivation approaches especially natural to implement. Related decision procedures, such as the CYK algorithm, rely on grammars in normal forms and implicitly leverage the correspondence between derivations and parse structures. See Chomsky normal form for more on the normal form and CYK algorithm for a parsing technique that uses such forms.
Significance and scope
Rightmost derivations help formalize how grammars generate languages and provide a bridge between theoretical characterizations and practical parsing techniques. They reinforce the view that the expressive power of context-free grammars is closely tied to the structure of derivations and parse trees, rather than to any single derivation order. In teaching and research, contrasting rightmost with leftmost derivations clarifies why certain grammars admit straightforward parsing strategies while others require careful grammar design to avoid ambiguity or inefficiency. See context-free grammar and parse tree for foundational context.