precedence versus C grammar

[happy]

I have heard many people saying that don't rely strictly on operator
precedence, instead evaluate expression
using C grammar rules.
They often give example about ternary operator.

But I still don't understant how ternary operator is not in accordance
with precedence.
I searched but couldn't find a satisfactory answer.
Please explain to me how that ternary operator is an exception.

And what are the other cases which don't follow precedence but rely on
grammar rules ?

 

[Eric Sosman]

I have heard many people saying that don't rely strictly on operator
precedence, instead evaluate expression
using C grammar rules.
They often give example about ternary operator.

But I still don't understant how ternary operator is not in accordance
with precedence.
I searched but couldn't find a satisfactory answer.
Please explain to me how that ternary operator is an exception.

And what are the other cases which don't follow precedence but rely on
grammar rules ?

There are many ways to describe a grammar. The ISO Standard
describes C's grammar with a version of Backus-Naur Form (also
known as Backus Normal Form, or BNF). This type of description
can be very precise, and has other advantages as well.

But BNF has disadvantages, too. One of them is that you can't
analyze a snippet of code in isolation to determine whether it's
syntactically correct or what it's meaning might be; you must parse
the entire translation unit to be sure. That's inconvenient for a
programmer who's looking at a single expression in the middle of
a big program, wondering whether `x << 4 + y' means '(x << 4) + y'
or `x << (4 + y)'.

"Precedence" and "associativity" are used in a different but
equivalent description of (part of) C's grammar. We can answer the
question of the previous paragraph by memorizing a simple rule: We say
that `+' has "higher precedence" or "binds more tightly" than `<<'.
Therefore the second interpretation above is the right one: The `+'
"takes precedence" over the `<<', just as `*' "takes precedence" over
`+' in `a + 3 * b'. This is a quicker route to comprehension than

assignment-expression
::= conditional-expression
::= logical-OR-expression
::= logical-AND-expression
::= inclusive-OR-expression
::= exclusive-OR-expression
::= AND-expression
::= equality-expression
::= relational-expression
::= shift-expression
::= shift-expression `<<' additive-expression
...

At this point (having identified just *one* of the expression's
five tokens!) we might take the shortcut of observing that the
`+' must be part of `additive-expression', so that its effect
is already incorporated in whatever the `<<' manipulates -- but
even with the shortcut, we've made a lot more steps and done a
lot more work than the easier notion of precedence required. If
we didn't see the opportunity for a shortcut, there would be even
more steps and even more work before we'd figured things out.

So: "Precedence" and "associativity" are alternative ways to
describe that part of C's grammar that deals with expressions,
with operators and operands. Humans have an easier time working
with the memorized P&A rules than with trying to parse expressions
using a BNF grammar, which is why little tables of P&A rules are
popular. But the outcome -- the way the expression decomposes
into its parts -- must be the same under a P&A analysis as would
be obtained by a different parsing algorithm: If the two disagreed,
at least one of them would be wrong and hence not useful as a
short-hand summary of the other.

I'm not sure what example you have in mind concerning the `?:'
operator. Perhaps if you'd post it, someone will exhibit how it's
generated from the formal grammar and how it's analyzed by P&A.

 

[Ben Bacarisse]

I have heard many people saying that don't rely strictly on operator
precedence, instead evaluate expression
using C grammar rules.
They often give example about ternary operator.

I think you mean "parse" rather than "evaluate" here. I prefer to call
?: the conditional operator. C has only one ternery operator but that
does not seem enough to name a specific thing (the conditional operator)
with a generic term like this.

But I still don't understant how ternary operator is not in accordance
with precedence.
I searched but couldn't find a satisfactory answer.
Please explain to me how that ternary operator is an exception.

OK, how about this:

t ? f ? 3 : 4 : 5

It is not clear for precedence and associativity helps to parse this.
Another example is:

t ? x = y : 0

where the part of the conditional seems to include an expression of
lower precedence with no parentheses.

The precedence and associativity usually given for ?: really relates to
a whole family of operators of the form "? expression :". Only then
does it make sense.

And what are the other cases which don't follow precedence but rely on
grammar rules ?

The expressions:

1 + x << y
1 + x && y

are parsed like this:

(1 + x) << y
(1 + x) && y

because << and && have relatively low precedence. Now, lets replace &&
with = which has even lower precedence:

1 + x = y

The syntax tells us that this is a syntax error:

assignment-expression:
conditional-expression
unary-expression assignment-operator assignment-expression

1 + x can't be an unary-expression and the alternative:

additive-expression:
multiplicative-expression
additive-expression + multiplicative-expression

is also wrong because x = y can't be a multiplicative expression.

Compilers that choose to use an operator precedence table to parse this
will parse it as (1 + x) = y and report that 1 + x is not a valid
lvalue, but it would be quite correct to report a syntax error. The
standard requires a diagnostic, but it does not require that syntax
errors be diagnosed as syntax errors, merely that they be diagnosed.

No expression form whose operator precedence lies between (and
including) the operators in a unary expression and the conditional
operator can be an lvalue so there is no practical reason to make the
distinction, but it is there in the grammar and not in the precedence
tables usually given.

[Aside: this sort of asymmetry can be represented y giving operators two
precedences: a left and a right precedence but that is another story.]

 

[happy]

@eric
Actually I saw
http://groups.google.co.in/group/uw...k=gst&q=conditional+operator#758b6930356f18b8
and asked this question.
In the above mentioned thread, I didn't quite understand chris
torrek's explanation about conditional expression.
So I want to know what does conditional expression mean?
Why it can't hold assignment operator ?

 

[Eric Sosman]

@Eric

Then you ought to have replied to my message, not to Ben's.

Actually I saw
http://groups.google.co.in/group/uw...k=gst&q=conditional+operator#758b6930356f18b8
and asked this question.
In the above mentioned thread, I didn't quite understand chris
torrek's explanation about conditional expression.

There are only two R's in "Chris Torek."

So I want to know what does conditional expression mean?

"conditional-expression" is a non-terminal symbol in the Standard's
formal grammar for C. (If you don't know what "non-terminal symbol"
means, most of the answers to your question will be incomprehensible.
You need to learn about formal grammars, and probably about parsing
algorithms, before they'll make sense.) Very approximately, a parser
recognizes the tokens of a source program as forming higher-level
constructs, which in turn combine to form even higher-level constructs,
and so on until the entire thing is recognized as a "translation-unit"
(or is found to be syntactically invalid).

Why it can't hold assignment operator ?

1) Because the grammar says so.

2) Because if the grammar allowed unrestricted "expression" to
appear both before and after the `:', the grammar would be ambiguous:
It would be possible to construct a token sequence that had more than
one possible parse. There's nothing inherently wrong with ambiguous
grammars, but they're not much used in programming languages: One wants
to associated a parse with a meaning (usually by talking about what the
non-terminal symbols mean), so an expression with two possible parses
has two possible meanings. When you start reading about grammars and
parsing, look up the "dangling else" problem; this restriction on the
third operand of ?: amounts to avoiding the dangling else.

 

[Tim Rentsch]

[snip]

There are many ways to describe a grammar. The ISO Standard
describes C's grammar with a version of Backus-Naur Form (also
known as Backus Normal Form, or BNF). This type of description
can be very precise, and has other advantages as well.

But BNF has disadvantages, too. One of them is that you can't
analyze a snippet of code in isolation to determine whether it's
syntactically correct or what it's meaning might be; you must parse
the entire translation unit to be sure. [snip]

This comment seems peculiar to me. It's true that a snippet of C
code can't be syntactically analyzed in isolation, but that's
because of the language itself, not because the syntax is specified
using a BNF-style grammar. The same result would be true for any
kind of syntactical specification that accepts the same language
('language' in the sense of the set of strings that legally
belong to it).

 

[Eric Sosman]

[snip]

There are many ways to describe a grammar. The ISO Standard
describes C's grammar with a version of Backus-Naur Form (also
known as Backus Normal Form, or BNF). This type of description
can be very precise, and has other advantages as well.

But BNF has disadvantages, too. One of them is that you can't
analyze a snippet of code in isolation to determine whether it's
syntactically correct or what it's meaning might be; you must parse
the entire translation unit to be sure. [snip]

This comment seems peculiar to me. It's true that a snippet of C
code can't be syntactically analyzed in isolation, but that's
because of the language itself, not because the syntax is specified
using a BNF-style grammar. The same result would be true for any
kind of syntactical specification that accepts the same language
('language' in the sense of the set of strings that legally
belong to it).

Hmm. Okay, the ability to parse a fragment doesn't arise
from the way that the grammar is described, but from the built-in
assumption that "I'm looking at an expression, and just assuming
that the surrounding context is such that this is a valid place
for an expression to appear." That viewpoint is implicit in the
"I'm looking at operators and operands, and using precedence et
al. to decide what goes with what," which one wouldn't do if
looking at a function declaration, say. But you're right: The
assumption "I'm looking at something that's supposed to match
`expression', and I can parse it according to the BNF from here
on down without reference to the surroundings" is equivalent.