Bison - nonterminal useless in grammar

Question

I am trying to create a simple grammar with Bison, but I am getting a warning saying that a nonterminal is useless (additive_expr).

My code looks like:

%%
multiplicative_expr:
CONSTANT_INTEGER
| multiplicative_expr MULTIPLICATION CONSTANT_INTEGER 
;
additive_expr:
multiplicative_expr
| additive_expr ADDITION multiplicative_expr

I have seen many similar questions and I had thought that it was because it is not used in other expressions, but I created a new expression including this one and the warning continued.

Answer 1

A Bison's grammar is made up of symbols and rules connecting them in a way that can be understood with the phrase "that symbol is the synthetic form of those ones". Likewise, in the inverse sense you'd say "those symbols are the expanded form of this one".

A symbol can synthesize something as elementary as indivisible units, known as “terminal symbols”, or as complex as other symbols that in turn are the synthesis of more things, in which case the latter and the former are known as “nonterminal symbols”.

All this about synthesization and expansions can be thought as a ways of represent a same thing through different forms. Each time the form changes according to a rule belonging on the grammar, it’s said to be a rewriting, just like the notion of expressing the same thing in a different manner.

Relaying on common sense here (and what texts about parsers, Bison, etc. says), it just doesn't make much sense to go rewritting symbols randomly. A sequence of rewrites should be driven towards an established end, succeeding or failing to meet it but always capable to detect either situation and stop with a result at hands. Bison's approach is that the user (programmer) highlight one among a grammar's set of symbols and it's deemed to utterly sinthesize any valid string of symbols alongside with invalid strings not being found a way to be rewritten into it. This is called start symbol.

Beside the point, in a typical grammar's layout not that all symbols participate with start simbol explicitly at respective right and left-hand side of a rule. Connections with the start symbol from the rest are constructed such way that any symbol is connected with another by participating in a same rule and this construction is made one or more times with one of them making the connection with the start symbol.

Following the above, it's useless to have grammar symbols without connection with the start symbol. Because the rewrites are driven by the pursuit of reaching the start symbol and a disconnected symbol will never make for it, it will never be used. A warning on "useless symbol" is announced then, of course at parser generation phase, because the problem here is not with a symbol string instance but with the grammar symbols (symbol type).

With terminal symbols the control is not enforced because Bison let terminals be arround here for other purposes (eg. establish precedence without necessarily be used to tell how symbol groups are made), with nonterminals instead, useless are always this, and warning is raised while an option or directive doesn't set this otherwise.

The report hasn’t error severity because it's accepted that you could want it be there for whatever reason although Bison will otherwise ignore it. Still, the warning is intended to be paid attention because it could mean a typing error leading to a grammar not reflecting and parser not doing what you want.

Before going on the solution, some considerations:

• Your grammar defines groupings for additive_exp and multiplicative_exp, which sound like about the math operations + and *.

• Your grammar follows well Bison's recommendations on recursivity, i.e., in face of evidence that the esense is the same with either multiplicative_expr MULTIPLICATION CONSTANT_INTEGER or CONSTANT_INTEGER MULTIPLICATION multiplicative_expr, yours is conveniently the former construction. (Bison manual, § 3.3.3 Recursive Rules).

• Your grammar correctly avoids Bison's reduce/reduce and shift/reduce conflict, on the same breath it makes in accordance with the math sense of the higher precedence of * over +.

Considering the above is true, I will suggest just a bit of tricks for the specific problem of the "useless symbol".

Bison doesn’t require any specific order for the rules. With exception of the first rule that has the privilege to be the one from which start symbol is chosen, Bison doesn’t mind if a rule mention symbols that aren't defined but latter in the grammar. If you swap rules so that additive_exp appears first, it will become the start symbol, and because this does expands into the other and not the opposite, the warning will be gone. Or place a %start additive_exp before the %% at the top of the grammar, having it exactly the same effect.

Other approach arises considering your grammar has a rule additive_exp: multiplicative_exp. Following bibliography, a rule of this form is commonly known as "single production", and quoting it: “A common situation in which single productions arise occurs when a grammar is used to describe the precedence levels and associativities of operators”. [...] “It turns out that the single productions which arise in the representation of operator precedence or associativity can always be eliminated” (“LR Parsing”, “A.V. Aho” and “S.C. Johnson”). What bibliography says here perfectly fits your case because your grammar has no more features compared whith the one that you'd have using bare exp rather than additive_exp and multiplicative_exp, this will left you with a start symbol that is in turn the only nonterminal in place, setting down the possibility of nonterminal useless, and more important, preserving your grammar's meaning.

Bison helps you making this simplification by means of its directives %prec, %left and %right, and especially the order they appear in the directive section. Informally, its about operator precedence, but more accurately, what’s actually being altered is Bison’s parsers deciding to group immediately or delay for latter as a symbol is encountered that gives place to both possibilities. Bison’s manual has detailed information on them, so does Yacc’s manual (usually bundled in Bison distributions for the reason that both are very related), possibly even in more detail about how precedence is attached to grammar rules. (Bison manual, § 3.7.3 Operator Precedence, and Yacc's manual, § 6: Precedence).

Using directives for precedence where you can, might help Bison saving some time by avoiding some optimisations it would normally do as it builds your parser. Again, based on the same source (“LR Parsing”, “A.V. Aho” and “S.C. Johnson”): “the ambiguous grammar generates the reduced parser immediately, without needing this optimizing algorithm”.