RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Background

By now, you've seen strings derived via a context-free grammar and their representations as a parse tree. In this section, we'll explore the different types of string derivations and how they relate to parse trees.

Definitions

Definition

In a leftmost derivation, we always apply a production for the leftmost nonterminal in our sequence of symbols.

Definition

In a rightmost derivation, we always apply a production for the rightmost terminal in our sequence of symbols.

Example

Example

Let's say we have the following context-free grammar:

IFSTATEMENT → IF IFBODY ELSE ELSEBODY END
IF → if (CONDITION) {
CONDITION → x | y
IFBODY = func1();
ELSE = } else {
ELSEBODY = func2();
END = }

Σ = {if, (, ), x, y, func1();, "}", else, "{", func2();}

Let's say our input string is:

if (x) { func1(); } else { func2(); }

The leftmost derivation of this string is:

IFSTATEMENT → IF IFBODY ELSE ELSEBODY END → if (CONDITION) { IFBODY ELSE ELSEBODY END → if (x) { IFBODY ELSE ELSEBODY END → if (x) { func1(); ELSE ELSEBODY END → if (x) { func1(); } else { ELSEBODY END → if (x) { func1(); } else { func2(); END → if (x) { func1(); } else { func2(); }

Conversely, the rightmost derivation of this string is:

IFSTATEMENT → IF IFBODY ELSE ELSEBODY END → IF IFBODY ELSE ELSEBODY } → IF IFBODY ELSE func2(); } → IF IFBODY } else { func2(); } → IF func1(); } else { func2(); } → if (CONDITION) { func1(); } else { func2(); } → if (x) { func1(); } else { func2(); }

Now, observe the following parse tree:

Parse tree for the string if (x) { func1(); } else { func2() }. IFSTATEMENT is at the top of the parse tree. On the second level, IFSTATEMENT becomes 4 symbols: IF, IFBODY, ELSE, ELSEBODY, END. On the third level, IF becomes 5 symbols: if, (, CONDITION, ), {. On the third level, IFBODY becomes func1();. On the third level, ELSE becomes 3 symbols: }, else, {. On the third level, ELSEBODY becomes func2();. On the third level, END becomes }. On the fourth level, CONDITION becomes x.

If we observe the parse tree and compare it to the leftmost and rightmost derivations, we can see that the tree simultaneously illustrates both derivations.

To see the leftmost derivation within the tree structure, we can read the terminal (leaf) nodes from left to right and observe the parent nodes that represent the corresponding productions. In this case, we always apply the production needed to derive the leftmost terminal node that has not yet been derived.

For the rightmost derivation, we can apply this process in the opposite direction.

Conclusion

A parse tree is a good representation of a string derivation regardless of our choice of derivation. While a parse tree indicates the contextual meaning of our input string, our choice of derivation type corresponding to a parse tree does not.

Relevance

Certain types of parsers produce the leftmost derivation of valid strings while others produce the rightmost derivation. Understanding derivation types is helpful in understanding exactly how these different types of parsers work.