I was learning about disambiguating grammars. In particular I was learning about enforcing right associativity on the sum language here:

$$ \mathit{Sum} ::= 0 \mid 1 \mid \mathit{Sum} + \mathit{Sum} \mid ( \mathit{Sum} )$$

I think I understand the intuition that in a string like:

$$ 0+1+0 $$

we want the 1 to be an argument to the left plus, so we put some sort of wall so that the symbol + cannot be right next to the 1. So something like this:

\begin{align} \mathit{Sum} &::= \mathit{Ntp} \mid \mathit{Ntp} + \mathit{Sum}\\ \mathit{Ntp} &::= 0 \mid 1 \mid ( \mathit{Sum} )\end{align}

From my understanding this always enforces to put a parenthesis on the left side of any sum. Thus, putting a wall literally using the symbol (.

However, what I don't understand is that the 2nd rule is supposed to mean:

Not top-most plus.

But I don't understand what "top-most" is supposed to mean. What does that mean?

Also, can someone give me a clearer argument to why the above grammar is indeed left associative? I feel my argument is a little to hand wavy or unclear to really be convincing.

Cross posted:

  • 2
    $\begingroup$ Top most refers to the root of the parse tree. In this case, Not top most refers to the nonterminal NTP. $\endgroup$ – Yuval Filmus Nov 22 '19 at 19:27

In the context of context-free languages, "top-most" refers to the root of a parse tree. Your rules guarantee that a sum of the form $1+1+1$ is parsed as $1+(1+1)$ rather than the opposite, since the nonterminal Ntp ("not top-most") doesn't allow + to be the top-most operator (you should imagine a parse tree in which + labels the root).

Consider the following two parse trees: (generated using Syntax Tree Generator)

[+ [+ 1 1] 1] [+ 1 [+ 1 1]]

On the left, the left child of the root has + as the top-most operator.

On the right, the right child of the root has + as the top-most operator.

Your grammar only allows the second parse tree, since the left child of + must not have + as the top-most operator.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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