Re: problem with C grammar

<the.malfunction@googlemail.com> wrote in message


> Is there any way to change the grammar such that I can use
> IDENTIFIER instead of TYPE_NAME here without having all those
> conflicts?


As Ivan Kosarev said, the short answer is "no", particularly not with
Bison (or Yacc) or any other non-predicated parser. If you use a
predicated parser, e.g. PCCTS, you can move the symbol table query
into the parser. You can do the same thing with "adaptive" parsers
like Meta-S.


However, if you are using a plain LL or LR parser, you can't query the
symbol table as part of the grammar. There is no BNF construct that
does a symbol table query. And, this is the point of the TYPE_NAME
token, to represent an IDENTIFIER that hase been declared to represent
a typedef (or is a built-in type name). Discerning that requires one
to inspect the symbol table (or whereever you store which names are
declared what).


It is worth noting that this problem is not new. If I recall
correctly, Frank Deremer wrote describing the canonical solution back
in the 70's (or perhaps 60's). He said that parsing was a 3 step
process. He broke the lexer part into two steps: the scanner and the
screener. The scanner is what one typically writes in regular
expressions (e.g. LEX). The screener then takes those tokens and
matches them against a symbol table to distinguish keywords (and type
name) from normal identifiers. The screener does not have to be part
of the lexer per se, but unless your parser can execute code that does
symbol table queries, it can't be part of the parser (because it can't
be expressed in BNF). Technically, the C language is not LR (and thus
not LL either).


Thus, you cannot replace the TYPE_NAME references in a yacc grammar
with IDENTIFIER references without getting conflicts. The grammar is
depending on some other phase (the screener) to assist it and make the
language acceptable, by changing the language into something that is
LR.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

Return to the comp.compilers page.
Search the comp.compilers archives again.