4
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

-2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is not what OP is asking. $\endgroup$
    – vonbrand
    Aug 30, 2015 at 19:47
  • $\begingroup$ I thought it was because OP used the tag lr(k) $\endgroup$ Aug 30, 2015 at 19:48
  • 2
    $\begingroup$ Can you edit your answer to clarify how it answers the question? The question asks if there's a way to eliminate conflicts. You recommend some transformations but they don't seem to have anything to do with conflicts. Are you claiming those transformations (adding S'->S, removing useless symbols) eliminate conflicts? If yes, can you justify that claim? If no, how does this answer the question? $\endgroup$
    – D.W.
    Aug 30, 2015 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.