I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with the follow exception. I've provided the simplest case to illustrate the problem below.
S -> a b S | T
T -> a c T | d T | ϵ
This grammar rightly generate a FIRST(S) - FIRST(T) clash, as both S and T can generate a
as a first terminal.
One (clearly wrong) attempt to left-factor the a
terminal was to substitute T into the S production.
S -> a b S | a c S | d S | ϵ
This would allow for left factoring like so:
S -> a U | d S | ϵ
U -> b S | c S
However, this grammar is no longer equivalent, as it would accept the string acab
when the original grammar would not.
I'm hoping that there is some way to manipulate this grammar that I'm not aware of to eliminate the FIRST(S) and FIRST(T) clash. Is there a method to left-factor a terminal in recursive nested productions as is described above?
T
inS -> a b S | T
producesS -> a b S | a c T | d T | ϵ
, notS -> a b S | a c S | d S | ϵ
. $\endgroup$ – reinierpost Mar 29 '18 at 19:18