Yacc: reduce/reduce-conflict

Yacc: reduce/reduce-conflict

Post by Markus Wagne » Mon, 12 May 1997 04:00:00



Hello, I am using GNU Bison for creating a parser for resource scripts.
These scripts should contain definitions for MENUs, BITMAPs, and so on.
There are constructors like in C++ for defining certain objects.
For defining rectangles it would be fine to have some kind of
overloading:

COOR (INT,INT)
RECT (INT,INT,INT,INT)
RECT (COOR,COOR)

I would like to to parse constructs like this:

RECT r1 = RECT (0,0,1023,767);

// or:

COOR c0 = COOR (0,0);
COOR c1 = COOR (1023,767);
RECT r1 = RECT (c0,c1);

For this I use the following grammar rules:

exp_int   -> NUM
           | ID

exp_coor -> COOR '(' exp_int ',' exp_int ')'
          | ID

exp_rect -> RECT '(' exp_int ',' exp_int ',' exp_int ',' exp_int ')'
            RECT '(' exp_coor ',' exp_coor ')'
          | ID

The problem is that exp_rect produces a reduce/reduce-conflict:

    exp_rect  ->  RECT '(' . exp_int ',' exp_int ',' exp_int ',' exp_int
')'
    exp_rect  ->  RECT '(' . exp_coor ',' exp_coor ')'

This is because exp_int and exp_coor both may result as an ID:

    exp_int   ->  TOK_ID .
    exp_coor  ->  TOK_ID .

I know the reason for this conflict, but how could one rewrite this
piece
of grammar without conflicts in a natural way?

 
 
 

Yacc: reduce/reduce-conflict

Post by Herve Couppe de Lahongrais - CD » Tue, 13 May 1997 04:00:00


I assume that the ID token means "IDentifier", so I think it can't be
reduced to exp_int which means "expression of type integer".
Rewritting the grammar like the following, it has no reduce/reduce
conflict :

%token  NUM
%token  ID
%token  COOR
%token  RECT

%start  exp_rect

%%
exp_int  : NUM

exp_coor : COOR '(' exp_int ',' exp_int ')'
         | ID

exp_rect : RECT '(' exp_int ',' exp_int ',' exp_int ',' exp_int ')'
         | RECT '(' exp_coor ',' exp_coor ')'
         | ID

--
Herve Couppe de Lahongrais (SEU)       | Eurocontrol Experimental Centre


 
 
 

1. yacc: shift/reduce conflict

Hello

According to the YACC specifications, in case of a shift/reduce
conflict, YACC is supposed to SHIFT. In my little sample-program,
it seems to do the reducing though. Or is there anything I missed ?
Here are the programs :

------------------------ x.l -----------------------

digit           [0-9]
year            1(8|9){digit}{2}
day             (0|1|2){digit}|3(0|1)

%%

{year}          return YEAR;
{day}           return DAY;

%%

------------------------ x.y -----------------------

%token    YEAR DAY

%%

a :        | a c

c :       YEAR  { printf("YEAR\n"); }
        | DAY   { printf("DAY\n");  }
%%

----------------- execution example : ---------------

22
DAY

11
DAY

1922
DAY
DAY

Why doesn't it continue shifting and find the YEAR-token ??
I didn't get any compiling errors either, like "1 rule never reduced"
or something. (I use AT&T lex)

Thanks for your help.
Cornelia

2. Xfree86 on STB AGP card q.

3. Reduce gif without reducing resolution?

4. problems with Counter for Webaccess

5. reduce in yacc

6. netgear ga621 / ns83820

7. Subject: Shift/reduce conflicts and precedence

8. SGI Indigo 2 and Linux

9. shift/reduce conflict with BISON

10. YACC + YACC = YACC

11. Reduce a SCO partition

12. How to reduce size of Windows Partition?

13. reduce stack size: elf_core_dump()