4
$\begingroup$

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:

Example Grammar (Figure 3.1)

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

Example Tree (Figure 3.2)

(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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

"Linearizing" here is equivalent to superimposing a total ordering on what is a partial order. If your grammar is context-free, this partial order can always be conveniently represented by a tree. Other types of grammars will be able to produce derivations orders that are not tree-like, and that is why we generally avoid them.

This total order is meant to allow for sequential algorithms to be written, because the input will be read sequentially. That's all, no magic here.

What happens is that different criteria for linearization will serve different algorithms: if you are going to reduce the input, you will go "from the bottom up", metaphorically, so the linear order that suits you (if you are reading the input left-to-right - because your language has an indo-european flavor), is postfix. If not, prefix.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I got the answer now - as far as I understood it, bottom-up parsers work with the rightmost derivation because that way they can determine which symbol evolved from which production rule. You got the best and only answer so far, tho... $\endgroup$
    – cadaniluk
    Nov 25, 2016 at 14:25
  • $\begingroup$ @Downvoter I should add that the output will also be generated sequentially, that's even more important. By the way, all languages that are rich enough have to use some form of linearization, both at the level of expression and at the level of content. $\endgroup$
    – André Souza Lemos
    Nov 25, 2016 at 15:25
  • $\begingroup$ 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? $\endgroup$
    – cadaniluk
    Nov 30, 2016 at 14:35
  • $\begingroup$ @Downvoter If you invert the original sequence, you will see that the derivations that comes first are the ones on the right side of the tree. Left-to-right is the order on which the input symbols are read, it favours languages that are left-prefixed: the grammar is simpler. That is why LR parsers are usually bottom-up, and LL parsers are usually top-down. $\endgroup$
    – André Souza Lemos
    Nov 30, 2016 at 15:11
  • 1
    $\begingroup$ The rightmost derivation corresponds to the leftmost reduction. $\endgroup$
    – André Souza Lemos
    Nov 30, 2016 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.