using precedence and associativity to parse an expression

J

junky_fellow

Hi,

As I read in previous threads in this newsgroup, that there is no
precedence and associativity in C. Still, precedence and associativity
rules may be used to parse an expression.
Applying precedence/associativity is easier rather than applying
grammar rules.

My question is, if all expressions that can be parsed using ANSI C
grammar, can also be parsed using precedence and associativity
rules ?
Is there anything that cannot be parsed or will give different result
when parsed using precedence/associativity as compared to ANSI C
grammar.

thanks,
rahul
 
E

Eric Sosman

Hi,

As I read in previous threads in this newsgroup, that there is no
precedence and associativity in C. Still, precedence and associativity
rules may be used to parse an expression.

The grammar of C expressions is not *defined* in terms of
precedence and associativity, but that doesn't mean they don't
exist. They're a useful descriptive shorthand, and the fact
that they don't participate in the official definition in no
way detracts from their utility.

I'm not familiar with pre-metric Indian weights and measures,
but it's at least plausible that it might be useful to refer to
something as weighing so-and-so-many tola, even when the official
unit would be grams. Just so with P&A: Convenient, even if not
official.
Applying precedence/associativity is easier rather than applying
grammar rules.

Precedence and associativity rules *are* grammar rules.
There are many ways of expressing a grammar; some grammars can
be described (in whole or in part) by P&A.
My question is, if all expressions that can be parsed using ANSI C
grammar, can also be parsed using precedence and associativity
rules ?

The question drifts more toward general programming and/or
compiling, but I think the answer is Yes (although I have not
studied it carefully). There are difficulties, though, such as
properly identifying some operators. The `+' and `-' and `*'
tokens represent both unary and binary operators, and have
different precedences in the different roles.
Is there anything that cannot be parsed or will give different result
when parsed using precedence/associativity as compared to ANSI C
grammar.

The question is unclear to me. The act of parsing is the
determination of an expression's structure, usually represented
as a (possibly implicit) tree. In an unambiguous grammar, a
well-formed expression has exactly one parse tree. If you've
parsed it correctly, by whatever means, you have discovered that
unique tree -- and if you have not found the tree, you have not
parsed the expression. Therefore, it is not possible to arrive
at different results from different parsing strategies (still
assuming an unambiguous grammar): All will either find the unique
parse tree, or will find the expression ill-formed.
 
B

Ben Bacarisse

As I read in previous threads in this newsgroup, that there is no
precedence and associativity in C. Still, precedence and associativity
rules may be used to parse an expression.
Applying precedence/associativity is easier rather than applying
grammar rules.

First off, we have to dismiss a problem. C's grammar (as printed)
does not describe C's syntax (as parsed by compilers) because of the
ability to define a type alias. Let's just put such annoyances to one
side for the moment.
My question is, if all expressions that can be parsed using ANSI C
grammar, can also be parsed using precedence and associativity
rules ?

This is probably not the question you wanted to ask! Precedence and
associativity rules can be very general. Some (formal) systems allow
different left and right precedence and these are (probably) enough to
describe C's expression syntax.

A slightly different question is whether a given set of rules describe
C's expression accurately and that, of course, depends on the rules.
Is there anything that cannot be parsed or will give different result
when parsed using precedence/associativity as compared to ANSI C
grammar.

The usual listing of operators, grouped by precedence, with an
annotation describing the associativity[1] are not quite up to the job
but come so close that it rarely matters. Neither the ternary
operator (?:) nor the subscript operator ([]) can be fully described
in this way because they both permit a full expression as a sub-part
of the operator (inside the []s or between the ? and the :). It is
simple enough to describe these exceptions with, say, a footnote.

But even the plain unary operators are problematic. Most tables put
all prefix unary operators in the same precedence group, all with
right-to-left associativity. That means that:

op1 op2 op3 identifier

means

(op1 (op2 (op3 identifier)))

for all prefix unary operator opN. lets pick three: sizeof, !
(negation) and (char) (convert to char type). The tables therefore
suggest that

sizeof (char) ! x

parses in the same way as

sizeof ! (char) x

but it does not. In fact the first is a syntax error. I don't think
(but I am not sure) that any simple table can capture the syntax of
these sorts of expressions.

[1] For example: http://www.difranco.net/cop2220/op-prec.htm
 
G

Gene

Hi,

  As I read in previous threads in this newsgroup, that there is no
precedence and associativity in C. Still, precedence and associativity
rules may be used to parse an expression.
Applying precedence/associativity is easier rather than applying
grammar rules.

My question is, if all expressions that can be parsed using ANSI C
grammar, can also be parsed using precedence and associativity
rules ?
Is there anything that cannot be parsed or will give different result
when parsed using precedence/associativity as compared to ANSI C
grammar.

Legal C expressions can be parsed by a more-or-less standard operator
precedence parser, which associates an integer indicator of precedence
and a boolean tag for associativity with each operator. The usual
hack for unary operators is needed. Implementation is pretty easy.

Whether such a parser accurately identifies all syntax errors (i.e.
detects all inputs that are not syntactically correct expressions) is
a harder question.
 
S

spinoza1111

Hi,

  As I read in previous threads in this newsgroup, that there is no
precedence and associativity in C. Still, precedence and associativity

Nice job, Seebach, nice job:
Destroy knowledge rather than create it:
Your conduct has created fear, uncertainty, and doubt:
That was your goal, destruction: it was to destroy you set out.
 
S

spinoza1111

First off, we have to dismiss a problem.  C's grammar (as printed)
does not describe C's syntax (as parsed by compilers) because of the
ability to define a type alias.  Let's just put such annoyances to one
side for the moment.

....and make things even more unclear to newbies in order to maintain
"expertise". Ben, it's sad to see a great programmer like you
corrupted. You've made a statement on an area (compiler development)
in which you have no standing and which is false.
My question is, if all expressions that can be parsed using ANSI C
grammar, can also be parsed using precedence and associativity
rules ?

This is probably not the question you wanted to ask!  Precedence and
associativity rules can be very general.  Some (formal) systems allow
different left and right precedence and these are (probably) enough to
describe C's expression syntax.

A slightly different question is whether a given set of rules describe
C's expression accurately and that, of course, depends on the rules.
Is there anything that cannot be parsed or will give different result
when parsed using precedence/associativity as compared to ANSI C
grammar.

The usual listing of operators, grouped by precedence, with an
annotation describing the associativity[1] are not quite up to the job
but come so close that it rarely matters.  Neither the ternary
operator (?:) nor the subscript operator ([]) can be fully described
in this way because they both permit a full expression as a sub-part
of the operator (inside the []s or between the ? and the :).  It is
simple enough to describe these exceptions with, say, a footnote.

But even the plain unary operators are problematic.  Most tables put
all prefix unary operators in the same precedence group, all with
right-to-left associativity.  That means that:

  op1 op2 op3 identifier

means

  (op1 (op2 (op3 identifier)))

for all prefix unary operator opN.  lets pick three: sizeof, !
(negation) and (char) (convert to char type).  The tables therefore
suggest that

  sizeof (char) ! x

parses in the same way as

  sizeof ! (char) x

but it does not.  In fact the first is a syntax error.  I don't think
(but I am not sure) that any simple table can capture the syntax of
these sorts of expressions.

[1] For example:http://www.difranco.net/cop2220/op-prec.htm
 
N

Nick Keighley

...and make things even more unclear to newbies in order to maintain
"expertise".

I don't consider pointing out a potential problem to be making things
unclear.
Ben, it's sad to see a great programmer like you
corrupted. You've made a statement on an area (compiler development)
in which you have no standing and which is false.

I suspect he knows a lot more about the subject than you (yes, I know
you wrote a book). If you consider he has said something that is
untrue it would make things much cleaer if you explained which bit
what he had said was incorrect.

<snip>
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top