Re: optional nonterminal symbols

[Hans Aberg]

On 21 Nov 2005, at 12:49, Arkadius Nowakowski wrote:

> Hi,
>
> I've got a gramar like this:
>
> %{
> %}
>
> %start start
>
> %token START END TAG1_1 TAG1_2 TAG2
>
> %%
>
> start: START tag1 END
>         | START tag1 tag2 END
> ;
>
> tag1: tag1_1 {}
>         | tag1_1 tag1_2 {}
> ;
>
> tag1_1: TAG1_1 {}
> ;
>
> tag1_2: /*empty*/ {}
>         | TAG1_2 {}
> ;
>
> tag2: TAG2 {}
> ;
>
> %%
>
> As you can see, the nonterminal symbols "tag2" and the sub symbol
> "tag1_2" are optional. Of course bison tells me, that there is a
> reduce/reduce conflict. Is there a way to change the bison source
> achieving the same goal?

You need to somehow merge together the two empties, if you want to  
avoid the conflict. Strictly speaking, this is not a grammar problem,  
but an action problem (of the parse tree). Think of a product that  
you expand: (A | epsilon)(B | epsilon) = A B | A | B | epsilon. Here,  
on the RHS, there is only one empty (= epsilon) grammar symbol.

  Hans Aberg