Can the grammar of the concatenation of two lists with common elements be written as an LALR grammar without any collisions

46 views Asked by At

Can the following ABNF rules be written as a bison LALR grammar without any conflicts (shift/reduce or reduce/reduce)? Among them, lowercase letters are non-terminal symbols, and uppercase letters are terminal symbols.

s = [*(A / D) D] *(A / B)

The key constraints are: A can appear anywhere, but any D must appear before any B (if any)

I wrote the following bison code, but it reports shift/reduce conflict

%token A
%token B
%token D

%start s

%%
s : %empty
  | a_d_d
  | s A
  | s B;

a_d_d : D
    | A a_d_d
    | D a_d_d;

I would like to be able to write a conflict-free LALR grammar, is this possible?

0

There are 0 answers