Re: top-down and bottom-up

Rob wrote:
> I would like to know if a parse tree created by a top-down parser
> differs from a parse tree created by a bottom-up parser given that the
> grammar is the same.


Some grammars can be ambiguous, even though they become unambiguous when
imposing the condition of using the leftmost derivation (as in LL,
top-down parsing) or rightmost derivation (as in LR, bottom-up, parsing).


Take the "calculator" grammar G = (T, N, P, E), terminals T = {i, `+',
`*', `(', `)'}, nonterminals N = {E, T, F}, sentence symbol E, and the
set of productions P containing:
        P_1: E -> T
        P_2: E -> E `+' T
        P_3: T -> F
        P_4: T -> T `*' F
        P_5: F -> i
        P_6: F -> `(' F `)'


The expression i + i*i has several parses, for example the leftmost (as in
LL, top-down, parsing) and rightmost (as in LR, bottom-up parsing):
        E E
        -> E + T -> E + T
        -> T + T -> E + T * F
        -> F + T -> E + T * i
        -> i + T -> E + F * i
        -> i + T * F -> E + i * i
        -> i + F * F -> T + i * i
        -> i + i * F -> F + i * i
        -> i + i * i -> i + i * i
So this grammar is ambiguous, even though when imposing the condition that
the rightmost or leftmost derivation should be used, the ambiguity
disappears: So LL parsers (if removing left recursion) and LR parsers
would not complain. (Strictly speaking, LL parsers cannot generally handle
left recursion, so then one may have to rewrite the grammar. So for the
example above to work, one has to pretend there is a push-down autamaton
that can produce the leftmost derivation.)


The example above also has a mixed derivation (neither leftmost nor
rightmost). I got from the book by Waite & Goos, "Compiler Construction",
p. 107.


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.math.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

Return to the comp.compilers page.
Search the comp.compilers archives again.