Re: When is a typedef name not a typedef name?

mengel@fnal.fnal.gov (Marc W. Mengel)
31 Jul 91 16:39:57 GMT

          From comp.compilers

Related articles
When is a typedef name not a typedef name? jwl@sag4.ssl.berkeley.edu (1991-07-09)
Re: When is a typedef name not a typedef name? henry@zoo.toronto.edu (1991-07-20)
Re: When is a typedef name not a typedef name? mengel@fnal.fnal.gov (1991-07-31)
Parsing C jar@florida.HQ.Ileaf.COM (1991-08-07)
| List of all articles for this month |

Newsgroups: comp.lang.c,comp.compilers
From: mengel@fnal.fnal.gov (Marc W. Mengel)
Followup-To: comp.lang.c
Summary: reduce/reduce errors *can* be okay...
Keywords: C, parse
Organization: Compilers Central
References: 91-07-032
Date: 31 Jul 91 16:39:57 GMT

jwl@sag4.ssl.berkeley.edu (Jim Lewis) writes:


> ...the following code is legal:


>typedef int foo;


>struct bar { foo foo; };
...
>Rewriting the grammar seems hopeless -- every variation I've come up
>with resulted in reduce/reduce conflicts.


True, but if you look at the conflict, (i.e. in a simpler grammar
like


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%token typename identifier struct


%%
declar_list
: declar
| declar_list declar
;


declar : type decl_list ';'
| type declar '{' '}'
;


type : typename
| struct '{' declar_list '}'
| /*empty*/
;


decl_list
: decl
| decl_list ',' declar
;


decl : typename
| identifier
| '*' decl
| '(' decl ')'
| decl '(' ')'
| decl '[' ']'
;
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


which brings out the problem) the reduce/reduce conflict
you get is:




10: reduce/reduce conflict (red'ns 5 and 10 ) on (
state 10
type : typename_ (5)
decl : typename_ (10)


; reduce 10
, reduce 10
[ reduce 10
. reduce 5




which of course breaks code like


fred() {}


i.e. it tries to treat fred as a type, and chokes later. However
since yacc is mindless, if we move the 'decl' rule higher up
in the grammar than the 'type' rule, like


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%token typename identifier struct


%%
declar_list
: declar
| declar_list declar
;


decl : typename
| identifier
| '*' decl
| '(' decl ')'
| decl '(' ')'
| decl '[' ']'
;


declar : type decl_list ';'
| type declar '{' '}'
;


type : typename
| struct '{' declar_list '}'
| /*empty*/
;


decl_list
: decl
| decl_list ',' declar
;


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -




We get the opposite behavior, i.e.


10: reduce/reduce conflict (red'ns 3 and 11 ) on (
state 10
decl : typename_ (3)
type : typename_ (11)


( reduce 3
[ reduce 3
; reduce 3
, reduce 3
. reduce 11


we reduce to a declarator with a '(' in the lookahead, which
is what we really want. So the point is, even if you have
reduce/reduce errors, you can force yacc to pick one resolution
over the other by the order of your rules, and keep on rolling
along...
-------
Marc Mengel
mengel@fnal.fnal.gov
[Lest it not be obvious, this is a part of C syntax which is painfully
context dependent, which means that yacc cannot handle it without some sort
of kludge, be it a reduce/reduce conflict or more typically some sort of
ad-hoc code in the lexer. -John]
--


Post a followup to this message

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