using precedence and associativity to parse an expression
junky_...@yahoo.co.in
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
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.
--
Eric Sosman
eso...@ieee-dot-org.invalid
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
--
Ben.
Gene
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.
spinoza1111
<junky_fel...@yahoo.co.in> wrote:
> 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.
spinoza1111
> "junky_fel...@yahoo.co.in" <junky_fel...@yahoo.co.in> writes:
> > 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.
...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.
Nick Keighley
> On Feb 15, 10:37 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> > "junky_fel...@yahoo.co.in" <junky_fel...@yahoo.co.in> writes:
> > > 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.
>
> ...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>