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

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]
--

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