3
$\begingroup$

Backus-Naur Form specifications for the grammars of languages like like C or C++ build up expressions with counter-intuitive definitions. For instance, a multiplication expression like

5 * 3

is also a logical-or-expression and an equality-expression and a bunch of other things it doesn't actually look like, because the grammar makes it an:

  • expression
    • consisting of an assignment-expression
      • consisting of a conditional-expression
        • consisting of a logical-or-expression
          • consisting of a logical-and-expression
            • consisting of an inclusive-or-expression
              • consisting of an exclusive-or-expression
                • consisting of an and-expression
                  • consisting of an equality-expression
                    • consisting of a relational-expression
                      • consisting of a shift-expression
                        • consisting of an additive-expression
                          • consisting a multiplicative-expression.

A snippet from the grammar looks like:

<exclusive-or-expression> ::= <and-expression>
                            | <exclusive-or-expression> ^ <and-expression>
<and-expression> ::= <equality-expression>
                   | <and-expression> & <equality-expression>
<equality-expression> ::= <relational-expression>
                        | <equality-expression> == <relational-expression>
                        | <equality-expression> != <relational-expression>

So if I were to write a parser that just followed these productions, I'd end up having to interpret the expression 5 * 3 12 different ways, e.g. by making it an instance of a MultiplicativeExpression class which derives from AdditiveExpression... all the way up to a base Expression class. And that seems very wasteful, since those classes would implement adding, AND-ing, OR-ing, etc. but would simply no-op for the single-term case.

By comparison, the Wikipedia example of BNF makes more sense:

<postal-address> ::= <name-part> <street-address> <zip-part>
<name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> 
              | <personal-part> <name-part>
<personal-part> ::= <initial> "." | <first-name>
...

The Wikipedia example reads like "a postal address consists of a [...]", whereas C-like language grammars read more like "a [...] can be treated as an expression". Why are C-like language grammars so "polymorphic"?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I think you meant "naive parser" but I'm not sure what a naive parser would be. The lexer just divides the input character stream into tokens and it has no idea about any kind of expression production. $\endgroup$ – rici Jan 16 '17 at 22:31
  • $\begingroup$ What do you think the grammar should look like instead? $\endgroup$ – Derek Elkins Jan 17 '17 at 1:45
  • $\begingroup$ This grammar simply implements the operator precedence rules. $\endgroup$ – Yuval Filmus Jan 17 '17 at 6:57
2
$\begingroup$

Why are C-like language grammars so "polymorphic"?

Because that's the way algebra works :-).

The arguments to (for example) a relational expression could be shifts or sums or products (or, for that matter, variables or constants, to say nothing of a variety of unary operator expressions), and all combinations are possible. So you could write out all nine possibilities (and then sixteen possibilities for equality expressions, etc.) (not counting the unary/base possibilities) but the quadratic explosion gets annoying. It's easier to consider each precedence level to include all the more tightly-binding levels as well.

I wouldn't call this polymorphism, really, although you might implement the expression type from a base Expression and individual derived types for each operator. The semantic value of every *-expression production is then a derived type of Expression, and it is not semantically necessary to know which one; the production labels are no longer needed.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ A relational expression whose arguments could be shifts/sums/products makes sense, but in a "child" case like 5 * 3, the relational expression isn't a relation -- and doesn't have arguments; it simply consists of one sub-expression. So relational expressions may be a < b or a > b or... a shift expression instead of a relation. The shift expression is also just 1 expression, an additive expression. The additive expression is just the multiplicative expression; there's no addition in this additive-expression. So the hierarchy the grammar suggests seems awkward. $\endgroup$ – mgiuffrida Jan 17 '17 at 1:36
  • $\begingroup$ @rici You could improve your answer by discussing the issues with the other extreme, namely having all these "types" of expressions just be different productions of one expression nonterminal. $\endgroup$ – Derek Elkins Jan 17 '17 at 1:47
1
$\begingroup$

Context-free derivations are trees. Used to represent the syntactic structure of the sentences of a concrete language - hierarchically, as they must - they give rise to somewhat arbitrary taxonomies of substructures, that are not always intuitive (as your example shows), but better than using just letters or symbols.

This is a problem of knowledge representation, which is an art of compromise. Large hierarchies are often problematic in that way. When you think about how awkward it can get for a computational language (or a file system), remember that in the taxonomy of mammals, the hippopotamus and the blue whale are close cousins.

|cite|improve this answer
$\endgroup$

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.