# Bottom-Up Parser With Leftmost Derivation

I'm reading the book Parsing Techniques by Dick Grune et al. and in section 3.1.3 "Linearization of the Parse Tree" they introduce the notion of linearization:

[...] a parser can produce a list of rule numbers instead, which means that it linearizes the parse tree. There are three main ways to linearize a tree, prefix, postfix and infix.

Those are explained using the following grammar:

and this particular production tree (the grammar is spuriously ambiguous):

(The numbers at the nodes are semantic attributes.)

Prefix notation is explained first:

In prefix notation, each node is listed by listing its number followed by prefix listings of the subnodes in left-to-right order; this gives us the leftmost derivation [...]:

leftmost: 2 2 1 3c 1 3e 1 3a

Postfix notation follows:

In postfix notation, each node is listed by listing in postfix notation all the subnodes in left-to-right order, followed by the number of the rule in the node itself; this gives us the rightmost derivation [...]:

rightmost: 3c 1 3e 1 2 3a 1 2

Before the linearizations, there is a "leftmost" and "rightmost," respectively. Does that mean prefix notation only works with top-down and postfix notation with bottom-up parsing? But then why? If we start from the rightmost non-terminal and build the parsing tree from the top down, wouldn't the linearization with the "leftmost" in front be the result? Aren't the notations semantically independent?

Furthermore, I've read about LL and LR parsers, which yield a leftmost or rightmost derivation and use a top-down or bottom-up algorithm, respectively. Does that mean a bottom-up parser can only work with a rightmost derivation? Why not with a leftmost one? I don't see the problem with that, similarly to how prefix notation seems to imply a leftmost derivation.

• I have one more question: why isn't the linearization for the rightmost derivation not 3a 1 2 3e 1 3c 1 2? Isn't this what rightmost derivation means, expanding the rightmost non-terminal first? But then what is the difference between "left-to-right" and leftmost derivation? Nov 30 '16 at 14:35