Re: Shift/reduce conflict?

[Tim Van Holder]

> For an input where "xxxyxz", "xyxz", "xxxz" and "xz" are all valid,
> I tried the following (flex not used):
> 
> start: xx xy xz
> xx: |'x''x'
> xy: |'x''y'
> xz: 'x''z'
> 
> Unfortunately, it doesn't seem to work. Once the first 'x' is read,
> only 'x' is expected, 'y' and 'z' becomes illegal. Any suggestions?

In such cases, refactoring the parent tends to help:

start
: xx xy xz
| xy xz
| xx xz
| xz
;

xx
: 'x' 'x'
;

xy
: 'x' 'y'
;

xz
: 'x' 'z'
;

In this case (because the non-optional portion is the last one), it
results in writing all valid cases in full.
If 'xy' was the fixed part (i.e. xxxyxz, xxxy, xyxz, xy as valid),
it would be slightly shorter:

start
: xx xy opt_xz
| xy opt_xz
;

xx
: 'x' 'x'
;

xy
: 'x' 'y'
;

opt_xz
: /* empty */
| 'x' 'z'
;

In general the solution is to avoid a grammar where such ambiguity
exists.  I am assuming yours is a simplified example, and 'x' represents
a token other than a single char - otherwise yylex() should be combining
xx, xy and xz into a token, removing the entire problem.  In fact, in
such a case, (f)lex could be used to do this matching all by itself
[pattern: (("xx")?("xy")?"xz")].