Velocity Reviews > Operator precedence.

# Operator precedence.

somenath
Guest
Posts: n/a

 05-07-2012
Hi All,

While browsing through the old article in this group I have come
across one article by Chrish Torek.
http://groups.google.com/group/gnu.g...7a0f655e96ce16

In this article he said.

"Finally, let me say one last time that the Standard C grammar DOES
NOT use operator precedence. (At most, one can say that the grammar
"implies" a precedence. I believe the word "specifies" is too
strong, despite its appearance in a non-normative footnote."

So the following expression

2+3*5;
is equal to 17. For human * has higher precedence than + so *
operator will be first operated on 3*5 and then the resultant will be
added to 2. So the result will be 2+(3*5) .

Then my question is how C compiler with out bothering about precedence
produce the same result as 2+(3*5).

I tried to explain myself the outcome of 2+3*5 the way Chris Torek
has explained the expression -- - x but I am not able to construes
how the precedence of * will be enforced by the C grammar with out
using operator precedence.

Regards,
Somenath

somenath
Guest
Posts: n/a

 05-07-2012
On May 7, 8:10*am, somenath <somenath...@gmail.com> wrote:
> Hi All,
>
> While browsing through the old article in this group I have come
> across *one article by Chrish Torek.http://groups.google.com/group/gnu.g...ad/thread/3175...
>

I apologize . This I did not found in CLC but in different group. But
as the article was for standard C I think the question will not be off
topic for CLC.

Stefan Ram
Guest
Posts: n/a

 05-07-2012
somenath <> writes:
>2+3*5;
>Then my question is how C compiler with out bothering about precedence
>produce the same result as 2+(3*5).

That whole expression cannot be parsed as a multiplicative expression,
because »2+3« is not a multiplicative expression (see N1570 6.5.5p1),
so it has to be an additive expression (6.5.6p1) with »3*5« being a
multiplicative expression (6.5.5p1).

James Kuyper
Guest
Posts: n/a

 05-07-2012
On 05/06/2012 11:10 PM, somenath wrote:
> Hi All,
>
> While browsing through the old article in this group I have come
> across one article by Chrish Torek.
> http://groups.google.com/group/gnu.g...7a0f655e96ce16
>
>
> In this article he said.
>
> "Finally, let me say one last time that the Standard C grammar DOES
> NOT use operator precedence. (At most, one can say that the grammar
> "implies" a precedence. I believe the word "specifies" is too
> strong, despite its appearance in a non-normative footnote."
>
> So the following expression
>
> 2+3*5;
> is equal to 17. For human * has higher precedence than + so *
> operator will be first operated on 3*5 and then the resultant will be
> added to 2. So the result will be 2+(3*5) .
>
> Then my question is how C compiler with out bothering about precedence
> produce the same result as 2+(3*5).

Without going into the details, let me state that 2, 3, and 5 all
qualify as "cast-expressions".

The relevant grammar rules are:

multiplicative-expression:
cast-expression
multiplicative-expression * cast-expression

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

The parse tree is as follows (monospaced font required):

2 + 3 * 5
cast-expression + cast-expression * cast-expression
cast-expression +(multiplicative-expression * cast-expression)
multiplicative-expression + multiplicative-expression
(additive-expression + multiplicative-expression)
additive-expression

These grammar rules encode the equivalent of operator precedence in the
fact that the grammar rules for a additive expression require
multiplicative expressions as operands, whereas multiplicative
expressions do not allow additive expressions as operators. If the C
grammar followed a similar pattern for all of the operators, it would be
equally accurate to describe it in terms of precedence or grammar rules.

However, the grammar rules for the conditional expressions do not allow
for a simple precedence-based interpretation:

conditional-expression:
logical-OR-expression
logical-OR-expression ? expression : conditional-express

Any kind of expression can occur between the ? and the :, which would
imply that conditional expressions have the lowest possible precedence.
However, neither the first nor the third operand of a conditional
expression can be an assignment expression or a comma expression, which
would imply that it has higher precedence than assignment operators or
the comma operator.
--
James Kuyper

Kaz Kylheku
Guest
Posts: n/a

 05-07-2012
On 2012-05-07, somenath <> wrote:
> has explained the expression -- - x but I am not able to construes
> how the precedence of * will be enforced by the C grammar with out
> using operator precedence.

Like this example grammar:

expression := term
| expression + term
| expression - term

term := factor
| term * factor
| term / factor

factor := ( expression )
| number
| identifier

No associativity or precedence is expressed directly by the grammar.

The precedence of * and / is implicity higher than that of + and -
because * and / occur only inside a term, and an expression is made
of terms separated by + or -. The rules are implicitly hierarchical.

Associativity is implicitly left to right because the rules are
left recursive. There is no ambiguity because we do not have ambiguous
rules like this:

expression := expression + expression

but rather

expression := expression + term

So if you have this:

1 + 2 + 3

the only way it can match the pattern "expression + term" is if "1 + 2"
is "expression" and "3" is "term". So it means that 3 is added to the
sum of 1 + 2.

James Kuyper
Guest
Posts: n/a

 05-07-2012
On 05/07/2012 05:48 AM, pete wrote:
> somenath wrote:

....
>> I tried to explain myself the outcome of 2+3*5 the way Chris Torek
>> has explained the expression -- - x but I am not able to construes
>> how the precedence of * will be enforced by the C grammar with out
>> using operator precedence.

>
> I can't do it either.
> I use the precedence table in chapter 2 of K&R instead.

What does that table say about the relative precedence of ||, ?:, =, and
the comma operator? Using that table and the corresponding information
about the associativity of the operators, how do you parse the two
following expressions:

a || b ? d , e : f ? g : h
a ? b : c ? d , e : f = g

Try to determine the correct parsings before reading any farther. The
correct parsings according to the C grammar cannot both be reproduced by
applying a single consistent precedence order to all of the relevant
operators. They are:

(a || b) ? (d , e) : (f ? g : h)
(a ? b : (c ? (d , e) : f)) = g

The second one is a constraint violation - the C standard requires both
that it be parsed that way, and that having been so parsed, it must be
diagnosed as a constraint violation.

Those particular expressions were chosen for a message I sent out
several months ago explaining the differences between C and C++ in the
parsing of such expressions. If you're interested, try the C++ examples:

a || b ? d , e : f = g
a ? b : c ? d , e : f , g

The peculiar spacing was chosen to allow enough room to insert the
parentheses needed to indicate the correct parse, and to line up the
corresponding variables when viewed in a monospaced font.
--
James Kuyper

Ben Bacarisse
Guest
Posts: n/a

 05-07-2012
James Kuyper <> writes:

> On 05/07/2012 05:48 AM, pete wrote:
>> somenath wrote:

> ...
>>> I tried to explain myself the outcome of 2+3*5 the way Chris Torek
>>> has explained the expression -- - x but I am not able to construes
>>> how the precedence of * will be enforced by the C grammar with out
>>> using operator precedence.

>>
>> I can't do it either.
>> I use the precedence table in chapter 2 of K&R instead.

>
> What does that table say about the relative precedence of ||, ?:, =, and
> the comma operator? Using that table and the corresponding information
> about the associativity of the operators, how do you parse the two
> following expressions:
>
> a || b ? d , e : f ? g : h
> a ? b : c ? d , e : f = g
>
> Try to determine the correct parsings before reading any farther. The
> correct parsings according to the C grammar cannot both be reproduced by
> applying a single consistent precedence order to all of the relevant
> operators. They are:
>
> (a || b) ? (d , e) : (f ? g : h)
> (a ? b : (c ? (d , e) : f)) = g

How do you get this second parse? It's a complex expression but it's
only the top level of it that's bugging me.

> The second one is a constraint violation - the C standard requires both
> that it be parsed that way, and that having been so parsed, it must be
> diagnosed as a constraint violation.

<snip>
--
Ben.

James Kuyper
Guest
Posts: n/a

 05-07-2012
On 05/07/2012 08:18 AM, Ben Bacarisse wrote:
> James Kuyper <> writes:

....
>> about the associativity of the operators, how do you parse the two
>> following expressions:
>>
>> a || b ? d , e : f ? g : h
>> a ? b : c ? d , e : f = g
>>
>> Try to determine the correct parsings before reading any farther. The
>> correct parsings according to the C grammar cannot both be reproduced by
>> applying a single consistent precedence order to all of the relevant
>> operators. They are:
>>
>> (a || b) ? (d , e) : (f ? g : h)
>> (a ? b : (c ? (d , e) : f)) = g

>
> How do you get this second parse? It's a complex expression but it's
> only the top level of it that's bugging me.

I should have reviewed the entire discussion before posting that part of
it. I'd forgotten that you'd already corrected me on that issue the last
time I discussed it. The left operand of an assignment operator must be
a unary expression, so that's a syntax error, not a constraint
violation. That's not fatal to what I was trying to say, but it does
mean that this isn't the correct way to say it.
I need to modify the expression to make the point I was trying to make.
I don't have time to think about it right now, but I'll see what I can
put together later.
--
James Kuyper

Ben Bacarisse
Guest
Posts: n/a

 05-07-2012
James Kuyper <> writes:

> On 05/07/2012 08:18 AM, Ben Bacarisse wrote:
>> James Kuyper <> writes:

> ...
>>> about the associativity of the operators, how do you parse the two
>>> following expressions:
>>>
>>> a || b ? d , e : f ? g : h
>>> a ? b : c ? d , e : f = g
>>>
>>> Try to determine the correct parsings before reading any farther. The
>>> correct parsings according to the C grammar cannot both be reproduced by
>>> applying a single consistent precedence order to all of the relevant
>>> operators. They are:
>>>
>>> (a || b) ? (d , e) : (f ? g : h)
>>> (a ? b : (c ? (d , e) : f)) = g

>>
>> How do you get this second parse? It's a complex expression but it's
>> only the top level of it that's bugging me.

>
> I should have reviewed the entire discussion before posting that part of
> it. I'd forgotten that you'd already corrected me on that issue the last
> time I discussed it.

I don't recall that. In fact I seem to recall making a similar mistake
about what the syntax says because I took what gcc reports (that the LHS
of and assignment must be an lvalue) too literally. Anyway, this has
certainly come up before.

> The left operand of an assignment operator must be
> a unary expression, so that's a syntax error, not a constraint
> violation. That's not fatal to what I was trying to say, but it does
> mean that this isn't the correct way to say it.
> I need to modify the expression to make the point I was trying to make.
> I don't have time to think about it right now, but I'll see what I can
> put together later.

I think the fact that assignment does not follow the same pattern as the
other operators is all you need to make the point that a single
precedence for each operator can't capture the formal syntax of C.

The conditional operator is tricky, but you can fix the problem by
treating the "?<expression>:" part as the operator. Then it does behave
like a right-associative operator with a precedence between that of ||
and the assignment operators.

gcc's error reports suggest that it treats C expressions as an operator
precedence grammar and that this cases no problems because everything
that is formally a syntax error gets picked up later. As far as the
standard is concerned, a diagnostic is a diagnostic.

Putting these two together -- treating "?<exp>:" as an operator and
giving assignment the expected priority -- means that, as programmers,
we won't go wrong just as gcc does not go wrong. Problems will only
occur in newsgroups where the reason *why* an expression is incorrect
might matter.

I've not checked all the detail, but I don't recall every being misled
in practice by thinking of C expressions as having an operator
precedence grammar.

--
Ben.

BartC
Guest
Posts: n/a

 05-07-2012
"somenath" <> wrote in message
news:76630b90-04ab-4976-b1a0-...

> Then my question is how C compiler with out bothering about precedence
> produce the same result as 2+(3*5).
>
> I tried to explain myself the outcome of 2+3*5 the way Chris Torek
> has explained the expression -- - x but I am not able to construes
> how the precedence of * will be enforced by the C grammar with out
> using operator precedence.

It defines the syntax so that the "+" and "*" have to be processed in a
particular order. Then that has the same effect as using operator
priorities, parsing to: (+ (2 (* 3 5) instead of (* (+2 3) 5)

Apparently the C syntax is complicated that way (using well over a dozen
different levels of expressions) because of a few cases that need special
treatment. But that didn't really work because these cases are still
confusing even for the experts. And there are too many precedence levels
anyway...

--
Bartc

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Tim Clacy C++ 15 05-30-2005 02:14 AM Alex Vinokur C++ 3 03-20-2005 03:11 PM Alex Vinokur C++ 4 11-26-2004 11:46 PM John Smith C++ 2 10-06-2004 10:22 AM Jakob Bieling C++ 2 03-05-2004 04:27 PM

Advertisments