How to resolve shift/reduce conflict - pattern detection in a sequence?

Question

I can not eliminate shift/reduce conflict from the gramma in yacc like parser (GPPG for C# v. 1.5.2).

The challenge is typical, we have a comma-separated sequence of elements: a, b, c, d, ..., k.

I would like to detect particular patterns in the sequences as separate literals, e.g. "a,b,c " or "a,b", in addition to individual elements like "a", "b", "c". The grama is as followes:

main   : list { Console.WriteLine("Rule -> main"); }    
       ;

list       : element | list separator element
       ;

element :
        | number
        | element_multiple %prec list
        | element_single
        ;



element_single :        a       | b     | c     | d     | e     | f     | g     | h     | i     | j     | k
        ;

element_multiple : abc | ab
        ;

ab      : a separator b  { Console.WriteLine("Rule -> literal: ab"); }  
        ;
abc     : a separator b separator c { Console.WriteLine("Rule -> literal: abc"); }  
        ;

separator : SEPARATOR                   { Console.WriteLine("Rule -> separator"); } 
        ;

a       : A                             { Console.WriteLine("Rule -> literal: {0}", $1.s); }    
        ;
b       : B                             { Console.WriteLine("Rule -> literal: {0}", $1.s); }    
        ;
c       : C                             { Console.WriteLine("Rule -> literal: {0}", $1.s); }    
        ;
d       : D                             { Console.WriteLine("Rule -> literal: {0}", $1.s); }    
        ;

The grama is generating two shift/reduce conflicts (no supprise):

1> Shift/Reduce conflict, state 10 on SEPARATOR
1> Shift/Reduce conflict, state 12 on SEPARATOR

but more over parsers fails when it faces the sequence like "a,f".

Syntax error, unexpected F, expecting B

rici rici · Accepted Answer · 2020-07-13T22:46:34

This can be done but it's ugly.

If you were using bison, then you could just use a GLR parser, which would let you handle the ambiguity. (Although you still have to do something to handle the ambiguity, since the naïve grammar is ambiguous.) Otherwise, you will need to jump through some hoops in order to disambiguate the grammar.

As presented, your grammar is parseable with a fixed lookahead (4 tokens), which means that there is an LALR(1) grammar. That grammar can even be created mechanically, since we know what the required lookahead is, but the automatically-produced grammar will be pretty bloated. Doing it by hand is tedious but the results are a bit more manageable (but still bloated).

The essence of the lookahead elimination algorithm is to delay reductions by k tokens (where k is the amount of lookahead to eliminate). That's done by keeping the latest k semantic values with each non-terminal, so that the delayed reduction has the semantic values it needs to produce its (delayed) semantic value. Fortunately, we only have to do that for productions which require extra lookahead, if we can identify which productions those are. (There's no efficient algorithm for doing that in general, and worse if k isn't known, but it's often more or less obvious.)

In this case, what we mostly want to avoid is that list, a gets reduced to list, element and then to list before the a has a chance to be combined with a following , b. (We'll also need to avoid reducing list, a, b to list, element_multiple, but we'll get to that later.)

We do that by creating a non-terminal list plus a which holds on to the list and the a. If that non-terminal gets followed by , b, then we'll still need to hold on to that b as well, which we do with a list plus a plus b non-terminal.

On the other hand, if list plus a is followed by (say) , c, then we'll have to do the equivalent of retroactively reducing the original list, a to list, and then reduce that list, c to list.

And there is one more possibility, which is that list plus a is followed by another a. In that case, we first retroactively reduce the original list and the a, and then create a new list plus a.

So here's the implementation.

Since I've never used GPPG nor C#, I've written this in vanilla C, using bison. I hope it's all sufficiently basic that you can translate it into your target language.

First, the (simple) data structures:

struct List {
  List*   prev;
  Element elt;
};

struct OneHold {
  List*   prev;
  char    held;
};

struct TwoHold {
  List*   prev;
  char    held1;
  char    held2;
};

}

OneHold and TwoHold are used to hold onto semantic values until they are actually needed.

So, with that, the semantic type declaration and the grammar:

%union {  
  char    token;
  OneHold one_hold;
  TwoHold two_hold;
  List*   list;
}

%token <token> 'a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' ...
%%

start   : expr              { print_list($1); putchar('\n'); free_list($1); }

%type <list> expr;
expr    : list
        | lista             { $$ = push_single($1.prev, $1.held); }
        | listab            { $$ = push_seqab($1.prev, $1.held1, $1.held2); }
%type <list> list;
list    : nota              { $$ = push_single(NULL, $1); }
        | list ',' nota     { $$ = push_single($1, $3); }
        | lista ',' notab   { $$ = push_single(push_single($1.prev, $1.held), $3); }
        | listab ',' notac  { $$ = push_single(push_seqab($1.prev, $1.held1, $1.held2), 
                                               $3);
                            }
        | listab ',' 'c'    { $$ = push_seqabc($1.prev, $1.held1, $1.held2, $3); }
%type <one_hold> lista;
lista   : 'a'               { $$ = (OneHold){ .prev = NULL, .held = $1}; }
        | list ',' 'a'      { $$ = (OneHold){ .prev = $1,   .held = $3}; }
        | lista ',' 'a'     { $$ = (OneHold){ .prev = push_single($1.prev,
                                                                  $1.held),
                                              .held = $3};
                            }
        | listab ',' 'a'    { $$ = (OneHold){ .prev = push_seqab($1.prev,
                                                                 $1.held1,
                                                                 $1.held2),
                                              .held = $3};
                            }
%type <two_hold> listab;
listab  : lista ',' 'b'     { $$ = (TwoHold){ .prev = $1.prev,
                                              .held1 = $1.held,
                                              .held2 = $3};
                            }
%type <token> letter nota notab notac;
letter  : 'd' | 'e' | 'f' | 'g' | 'h' ...
nota    : 'b' | 'c' | letter
notab   : 'c' | letter
notac   : 'b' | letter

How to resolve shift/reduce conflict - pattern detection in a sequence?

1 Answers