Left and Right most Derivation

programming-languagestheory

So i understand the semantics of derivations as far as Backus Naur Form goes. One thing I cannot find in any text book or the various lecturers' notes that are on-line is this.

When would a right most derivation be beneficial over a left most derivation? Would a compiler or generator always use either left, or right, or would it use both?

So here's an example:

Suppose we had the following language sentence: A = B + C * A

Example Language Grammar Permitting the Above:

<assign>  <id> = <expr> 
<id>  A | B | C
<expr>  <expr> + <term>
        |<term>
<term> <term> * <factor> 
       |<factor>
<factor>  ( expr )
        | <id>

Left Most Derivation:

<assign>   => <id> = <expr>
              => A = <expr> + <term>
              => A = <term> + <term>  
              => A = <factor> + <term> 
              => A = <id> + <term> 
              => A = B + <term> 
              => A = B + <term> * <factor>
              => A = B + <factor> * <factor>
              => A = B + <id> * <factor>
              => A = B + C * < term>
              => A = B + C * <factor>
              => A = B + C * <id>
              => A = B + C * A

Right Most Derivation:

<assign>  => <id> = <expr>
      => <id> = <expr> + <term>
      => <id> = <expr> + <term>   * <factor>
      => <id> = <expr> + <term> * <id>
      => <id> = <expr> + <term> * A
      => <id> = <expr> + <factor> * A
      => <id> = <expr> + <id> * A
      => <id> = <expr> + C * A
      => <id> = <term> + C * A
      => <id> = <id> + C * A
      => <id> = B + C * A
      =>  A = B + C * C

Best Answer

The way it was explained in my compiler class, well over thirty years ago, is that a leftmost derivation scheme works best with a top-down (e.g. recursive descent) parser, while a rightmost derivation scheme works best with a bottom-up (e.g., SLR(1), LALR(1), YACC et al) parser. Using a leftmost derivation scheme with a bottom-up parser requires the parser to "stack up" the entire sentence, then process it from the right end, rather than recognizing short phrases at a time. Ditto the opposite pairing.

My Green Dragon Book and Red Dragon Book are currently in storage, or I'd go looking to see if they have examples or better explanations.

After thinking some more about it, the above discussion is about left recursive and right recursive grammars, but I think the effect is the same. At the time, I found the result very satisfying, in that it said there wasn't one "best" way to do a grammar, but rather it depended on how your parser worked as well.

Related Solutions

Programming Languages – Advantages of Left-to-Right Language Syntax

The basic advantage is that parsing is simpler and unique. Note that after the line is parsed, the compiler will know what the exact type is, so from there on, how the type was defined is irrelevant.

Any function that returns an argument of array type, or function pointer type are hard to read currently:

// common way of obtaining the static size in elements of an array:
template <typename T, int N>
char (&array_size_impl( T (&)[N] ))[N];
// alternative parser:
template <typename T, int N>               // this would probably be changed also
array_simple_impl function( T [N] & ) char [N] &;

And there would be less chance for misunderstanding (as the most-vexing-parse):

// Current C++
type x( another_type() );      // create an instance x of type passing a
                               // default constructed another_type temporary?
                               // or declare a function x that returns type and takes as argument
                               // a function that has no arguments and returns another_type
// How the compiler reads it:
x function( function() another_type ) type;

// What many people mean:
x type { another_type{} };

Using a similar approach to uniform initialization in C++0x (i.e. {} to identify initialization). Note that with a left to right approach it is much clearer what we are defining. Many people (me for sure) have been bitten at any point by this parsing error in the past (more than once), and that would not be the case with a left-to-right syntax.

Programming Languages – What is Left Recursion in Layman’s Terms

A rule R is left-recursive if, in order to find out whether R matches, you first have to find out whether R matches. This happens when R appears, directly or indirectly, as the first term in some production of itself.

Imagine a toy version of the grammar for mathematical expressions, with only addition and multiplication to avoid distraction:

Expression ::= Multiplication '+' Expression
            || Multiplication

Multiplication ::= Term '*' Term
                 || Term

Term ::= Number | Variable

As written, there's no left-recursion here — we could pass this grammar to a recursive-descent parser.

But suppose you tried to write it this way:

Expression ::= Expression '*' Expression
            || Expression '+' Expression
            || Term

Term ::= Number | Variable

This is a grammar, and some parsers can cope with it, but recursive descent parsers and LL parsers can't — because the rule for Expression begins with Expression itself. It should be obvious why in a recursive-descent parser this leads to unbounded recursion without actually consuming any input.

It doesn't matter whether the rule refers to itself directly or indirectly; if A has an alternative that starts with B, and B has an alternative that starts with A, then A and B are both indirectly left-recursive, and in a recursive-descent parser their matching functions would lead to endless mutual recursion.

Best Answer

Related Solutions

Programming Languages – Advantages of Left-to-Right Language Syntax

Programming Languages – What is Left Recursion in Layman’s Terms

Related Topic