syntax/notation used in describing c's grammar

[ben]

getting a bit confused with the details of how c's grammar is
specified, especially when you get self-reference like in this:

postfix-expression:
primary-expression
postfix-expression [ expression ]
postfix-expression ( argument-expression-listopt )
postfix-expression . identifier
postfix-expression -> identifier
postfix-expression ++
postfix-expression --
( type-name ) { initializer-list }
( type-name ) { initializer-list , }

(copied and pasted from a ISO/IEC 9899 (that's "C99" i think)
specification pdf)

when a module (i'm thinking of the above whole thing as a module) is
referred to from within itself like in the above one, at the start of
one or several of its possibilities, that means that one of the other
variations/possibilities of the postfix-expression module must occur
immediately before one of the possibilities that start with
'postfix-expression' can occur right? so you can have a '++' only after
one of the three lines which do not begin with 'postfix-expression'
have occured? or another way of getting at the same point: if you had a
module, say called 'xyz', whose possibilities all started with 'xyz',
then that module would be a waste of time and impossible and useless
because none of it could ever occur? at least one of the possibilities
should *not* start with 'xyz' -- then it would be possible for it to
occur? is that right?

also, does that give potentially endless looping like behaviour -- not
just one possibility that starts with 'postfix-expression' but
several/many even possibly? eg, a primary-expression occurs, so then
that primary-expression stands for a postfix-expression. then say [
expression ] occurs after the primary expression. (so what's occured so
far is: primary-expression [ expression ] ). what's occured so far is a
postfix-expression, so can another [ expression ] follow on, or even
anything else that has 'postfix-expression' before it in the above
list? and then again possibly, and again etc?

so, just to clarify, you could have these occurances, for example,
within the code and it'd be fine? (at least according to the grammar
that is, it'd be fine?) (one line per part):

( type-name ) { initializer-list }
++
( argument-expression-listopt )
-> identifier
-> identifier

(i guess that couldn't actually happen in code (according to further
checks by compiler/parser or whatever), but so far as what the above
postfix-expression grammar specification goes, that's ok?)

so the logic of implementing that in code, you'd need to look back to
the previous occurance when a module name is encountered? -- but that's
only applicable to modules self-referencing themselves isn't it? that's
what i can't quite understand. when you come accross a module name that
isn't self referencing, there's no need to look back -- it's just a
straight, 'does it occur here' question, but when it's a self reference
it seems to be a 'did it occur last time' question. i feel there
shouldn't be any logical difference between a module using it's own
module name, and a module using another module's name, but it does seem
a different logic -- am i just getting confused or is a slightly
different logic required for modules references to themselves?

btw, i'm attempting to do a c, also objective-c, (semi) parser --
that's why i'm trying to get on top of the grammar syntax.

one last quickie: this line:
( type-name ) { initializer-list , }
it looks like a ',' can occur followd by a '}' ? surely i'm reading
that wrong as that isn't possible? feels like there should be something
inbetween the , and }?

thanks-a-lot, ben

 

[Ben Pfaff]

postfix-expression:
primary-expression
postfix-expression [ expression ]
postfix-expression ( argument-expression-listopt )
postfix-expression . identifier
postfix-expression -> identifier
postfix-expression ++
postfix-expression --
( type-name ) { initializer-list }
( type-name ) { initializer-list , }

(copied and pasted from a ISO/IEC 9899 (that's "C99" i think)
specification pdf)

when a module (i'm thinking of the above whole thing as a module)

The proper term is "nonterminal".

is referred to from within itself like in the above one, at the
start of one or several of its possibilities, that means that
one of the other variations/possibilities of the
postfix-expression module must occur immediately before one of
the possibilities that start with 'postfix-expression' can
occur right?

No. There is no such requirement.

so you can have a '++' only after one of the three lines which
do not begin with 'postfix-expression' have occured?

Nope. something like a->b++ is potentially valid syntax.

or another way of getting at the same point: if you had a
module, say called 'xyz', whose possibilities all started with
'xyz', then that module would be a waste of time and impossible
and useless because none of it could ever occur? at least one
of the possibilities should *not* start with 'xyz' -- then it
would be possible for it to occur? is that right?

Yes: to be a sensible grammar, at least one of the productions
for a nonterminal mentioned in a grammar must not contain itself
on the right-hand side.

also, does that give potentially endless looping like behaviour -- not
just one possibility that starts with 'postfix-expression' but
several/many even possibly? eg, a primary-expression occurs, so then
that primary-expression stands for a postfix-expression. then say [
expression ] occurs after the primary expression. (so what's occured so
far is: primary-expression [ expression ] ). what's occured so far is a
postfix-expression, so can another [ expression ] follow on, or even
anything else that has 'postfix-expression' before it in the above
list? and then again possibly, and again etc?

Yes, you can loop for a long time. But a real program is not
infinite in length, and every real C implementation has limits on
how big or complex a program it can accept.

so, just to clarify, you could have these occurances, for example,
within the code and it'd be fine? (at least according to the grammar
that is, it'd be fine?) (one line per part):

( type-name ) { initializer-list }
++
( argument-expression-listopt )
-> identifier
-> identifier

(i guess that couldn't actually happen in code (according to further
checks by compiler/parser or whatever), but so far as what the above
postfix-expression grammar specification goes, that's ok?)

Right. The above is syntactically valid but semantically
unlikely to be valid.

so the logic of implementing that in code, you'd need to look back to
the previous occurance when a module name is encountered? -- but that's
only applicable to modules self-referencing themselves isn't it? that's
what i can't quite understand. when you come accross a module name that
isn't self referencing, there's no need to look back -- it's just a
straight, 'does it occur here' question, but when it's a self reference
it seems to be a 'did it occur last time' question. i feel there
shouldn't be any logical difference between a module using it's own
module name, and a module using another module's name, but it does seem
a different logic -- am i just getting confused or is a slightly
different logic required for modules references to themselves?

Parsers are somewhat complex beasts. It's not always easy to get
them to be correct. It's far more difficult to get them correct
if you don't have the right knowledge to write them. The best
place to get that knowledge is probably a compilers textbook.
Have you tried reading one?

Alternatively, you could use a "parser generator" such as Bison
or yacc.

btw, i'm attempting to do a c, also objective-c, (semi) parser --
that's why i'm trying to get on top of the grammar syntax.

one last quickie: this line:
( type-name ) { initializer-list , }
it looks like a ',' can occur followd by a '}' ? surely i'm reading
that wrong as that isn't possible? feels like there should be something
inbetween the , and }?

No, in many places in C a trailing comma is allowed in a list of
comma-separated items. It makes it easier to rearrange things in
the list (when they're one per line) if you don't have to deal
with an exceptional comma after the last item. It can also
simplify programs that generate C.

 

[Ben Pfaff]

postfix-expression:
primary-expression
postfix-expression [ expression ]
postfix-expression ( argument-expression-listopt )
postfix-expression . identifier
postfix-expression -> identifier
postfix-expression ++
postfix-expression --
( type-name ) { initializer-list }
( type-name ) { initializer-list , }
when a "nonterminal"
is referred to from within itself like in the above one, at the
start of one or several of its possibilities, that means that
one of the other variations/possibilities of the
postfix-expression module must occur immediately before one of
the possibilities that start with 'postfix-expression' can
occur right?

No. There is no such requirement.

are you sure? i think i might have just worded that wrongly because
what's said later, and you agree to, contradics your above answer -- i
think i might have just worded the above part badly/misleadingly.

Well, let's see.

basically what i'm saying (checking on that i've understood the
"postfix-expression:" grammer specification) is this:

on the first reading/occurance of a postfix-expression part, only one
of these three possibilities are possible:
primary-expression
( type-name ) { initializer-list }
( type-name ) { initializer-list , }

The first token (terminal) in a postfix-expression has to come
from one of those productions, yes.

then, once one of those three has occured, one of these things can
occur and follow on possibly :
[ expression ]
( argument-expression-listopt )
. identifier
-> identifier
++
--
(and none of those would be possible if one of the three things in the
first list hadn't happend).
and then that second list above can be repeated over and over possibly,
until something else happens.

Yes, that's one way to look at it.

shouldn't that be left-hand side?

Each production has the form L -> R, where L is a single
nonterminal and R is a string of terminals and nonterminals.
Here everything in R is on the right-hand side.

generally, so far my parser is going ok. i think i'm ok doing it the
way i am (so far that is). i think learning yacc or bison would take
longer and be harder than the way i'm going. just needed to check on
the grammar of the grammar as it were. i don't think i need a fully
fledged parser, although saying that, i'm not even sure if a
semi-parser is possible or easier -- it may turn out that you either
parse, or you don't, or that letting somethings go, being flexible
won't be easier. i'm not sure at the moment. anyway i'm rambling. if it
is possible and easier to do a semi-parser than a full parser, that's
what i'm going to do.

Well, good luck. I still think you'd be better off getting a
good book on grammars and parsers, whether you decide to write
your own parser or use someone else's parser generator.

 

[ben]

hiyer Ben,

thanks very much for the reply.

postfix-expression:
primary-expression
postfix-expression [ expression ]
postfix-expression ( argument-expression-listopt )
postfix-expression . identifier
postfix-expression -> identifier
postfix-expression ++
postfix-expression --
( type-name ) { initializer-list }
( type-name ) { initializer-list , }
when a "nonterminal"
is referred to from within itself like in the above one, at the
start of one or several of its possibilities, that means that
one of the other variations/possibilities of the
postfix-expression module must occur immediately before one of
the possibilities that start with 'postfix-expression' can
occur right?

No. There is no such requirement.

are you sure? i think i might have just worded that wrongly because
what's said later, and you agree to, contradics your above answer -- i
think i might have just worded the above part badly/misleadingly.

Nope. something like a->b++ is potentially valid syntax.

basically what i'm saying (checking on that i've understood the
"postfix-expression:" grammer specification) is this:

on the first reading/occurance of a postfix-expression part, only one
of these three possibilities are possible:
primary-expression
( type-name ) { initializer-list }
( type-name ) { initializer-list , }

then, once one of those three has occured, one of these things can
occur and follow on possibly :
[ expression ]
( argument-expression-listopt )
. identifier
-> identifier
++
--
(and none of those would be possible if one of the three things in the
first list hadn't happend).
and then that second list above can be repeated over and over possibly,
until something else happens.

Yes: to be a sensible grammar, at least one of the productions
for a nonterminal mentioned in a grammar must not contain itself
on the right-hand side.

shouldn't that be left-hand side?

Parsers are somewhat complex beasts. It's not always easy to get
them to be correct. It's far more difficult to get them correct
if you don't have the right knowledge to write them. The best
place to get that knowledge is probably a compilers textbook.
Have you tried reading one?

Alternatively, you could use a "parser generator" such as Bison
or yacc.

generally, so far my parser is going ok. i think i'm ok doing it the
way i am (so far that is). i think learning yacc or bison would take
longer and be harder than the way i'm going. just needed to check on
the grammar of the grammar as it were. i don't think i need a fully
fledged parser, although saying that, i'm not even sure if a
semi-parser is possible or easier -- it may turn out that you either
parse, or you don't, or that letting somethings go, being flexible
won't be easier. i'm not sure at the moment. anyway i'm rambling. if it
is possible and easier to do a semi-parser than a full parser, that's
what i'm going to do.

and it does look like the logic of a nonterminal reference to the
nonterminal that that reference is in, is a slightly different logic to
a nonterminal reference to another nonterminal -- in that the self
reference needs to look back at the last thing that occured rather than
the thing that's occuring now. not completely sure on that, but
anyway...

No, in many places in C a trailing comma is allowed in a list of
comma-separated items. It makes it easier to rearrange things in
the list (when they're one per line) if you don't have to deal
with an exceptional comma after the last item. It can also
simplify programs that generate C.

great. well i never knew that.

thans very much for the info -- most useful.

ben.

 

[ben]

Yes, that's one way to look at it.

cool. thanks for the info.

ben.