CFG - Left factoring in recursive nested productions

Question

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?

Answer 1

You can solve this with regular expressions:

S -> a b S | T

is equivalent to

S -> (a b)* T

and

T -> a c T | d T | ϵ

is equivalent to

T -> (a c | d)*

Subtitute T into the rule for S:

S -> (a b)* (a c | d)*

Now, you can use a standard method to derive a right regular grammar.

Answer 2

I'm nearly certain that I've discovered the following equivalent left-factored grammar.

S -> a X | W
T -> b S

U -> c Y
V -> a U

W -> d Y | ϵ

X -> T | U
Y -> V | W

This was obtained by enumerating the following list of test cases and manually checking them.

Test strings that the grammar should accept:

• ϵ
• ab
• abab
• abac
• abacac
• abacd
• ac
• acac
• abd
• acd
• dac
• d
• dd

Test strings that the grammar should reject:

• dab
• acab
• abdab
• abacab