# What does the term "top-most" mean in the context of formal grammars?

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:

• Top most refers to the root of the parse tree. In this case, Not top most refers to the nonterminal NTP. Commented Nov 22, 2019 at 19:27

## 1 Answer

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)

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.