Are there automatic transformation of grammar algorithms?

Question

From time to time you can write a grammar that creates shift/reduce conflict (for example) but after reading the grammar you notice that if you rewrite the productions the conflict will go away, despite the fact that the rewritten grammar is obviously equivalent and accepts exactly the same language.

Are there some automatic transformations of the grammar to avoid conflict? Something (just an analogy) as left recursion elimination in LL parsers?

For example, here is a trivial example of two grammars:

...
deco_symbol -> anon_symbol | named_symbol;
...

and

...
symbol -> anon_symbol | named_symbol;
deco_symbol -> symbol;
...

For LR(1) parser such indirection can be crucial and second form can introduce conflicts (it did in real life).

Since I asked this question I wrote automatic removal of identity production and it helped, so this would be the first type of transformation I know it is helpful. Now I am testing wrapper production removal and empty productions as well.

Answer 1

If you are willing to implement an lr(k) algorithm then yes, there are transformations that you should do in order to obtain a correct parser: first of all, you have to build an augmented grammar adding production S'->S, making S' the new axiom. This is actually not always necessary, but it allows you have a standardized procedure for all the productions so let's pretend it is for now. After that, you should also eliminate useless symbols from the grammar with the apposite algorithm.

If you execute lr(k) parsing under these hypothesis for the grammar, you should not have conflicts.

----- EDIT ----- I hope this will be of some help :)

An lr(k) parser builds a parsing table over a given grammar G. These parsers are able to recognize words generated from grammars which are deterministic context free and in lr(k) form. If a conflict occurs, then the language generated by the given grammar cannot be parsed using that table and the grammar is not a lr(k) grammar.

However, one can show that a language L is deterministic context free iff there exists k >= 1 such that L is generated by an lr(k) grammar.

I might be wrong but what I concluded from these notions is that if the grammar is lr(k) no conflicts should occur, and one of the definitions of a lr(k) grammar is:

The definition of lr(k) grammars states that the axiom must not occurr on the right hand side of any production, and should this is not be respected one needs contruct the augmented grammar first, using S' as new axiom and adding the only production S'->S. For further definitions of lr(k) grammars or a clarification of what I wrote, I advise to read The Theory of Parsing, Translation and Compiling (around page 370), since I fear I don't have the preparation to answer all questions.