0
$\begingroup$

Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind:

  • total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating action table),
  • the size of action/goto table (in total)
  • is there any "side-effect" of removing some of shift-reduce conflicts

?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The point of generating a parser (usually) is to parse: "Analyse (a string or text) into logical syntactic components" (some online dictionary). That's different from simply recognizing that a text is a member of a language. A given language has a variety of grammars which will recognize its sentences, but typically there is a specific grammar which defines the "logical syntactic components" and their relationship to each other, as in the above definition. In real-world applications -- compilers, for example -- one expects an output which is more interesting than simply "the input is/is not a valid program".

In some cases, it is possible to recover the original parse tree from the parse tree generated by parsing a transformed grammar. (This is true for CNF, with the usual transformation strategy.) In other cases (such as GNF, as far as I know), it is annoyingly difficult, making such a transformation of limited use for parsing (as opposed to recognition).

Also, not all grammar transformations preserve LR(k)-ness. In particular, the usual CNF transformation involves refactoring of every production into a series of rules with precisely two non-terminals. This often has the effect of converting an LR(1) grammar into a grammar which is not LR(k) for any k. So that's not much help, either.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you very much for your insight, it is actually helpful. In practice you don't deal with pure LR(k) grammar, because you add some precedence rules, and with them you have LR(k) grammar. And the observation you give about conversion to CNF could be reversed -- expand the rules (to obtain anti-CNF form) in order to get LR(k) grammar (from non-LR, because of the conflicts). I am actually pursue this notion as we speak, by eliminating alias productions (which should be easy and cheap to do). $\endgroup$
    – greenoldman
    Commented Aug 18, 2015 at 20:47
  • $\begingroup$ @greenoldman: There's a standard transformation which can produce an LR(1) grammar corresponding to any LR(k) grammar, and which also preserves the parse tree. The standard precedence hack is also a parse-tree-preserving transform, as you say. But all of that is going in the "other direction" from your original question, to which I think the answer is basically "No benefits". $\endgroup$
    – rici
    Commented Aug 18, 2015 at 22:42
  • $\begingroup$ once again, thank you. Actually the direction is OK, only with minus sign, so it is very valuable for me, which form I should seek. Did I read you correctly that you can transform any LR(k) gramar to LR(1)? I was not aware of this. Time for google :-). $\endgroup$
    – greenoldman
    Commented Aug 18, 2015 at 23:01
  • 1
    $\begingroup$ @greenoldman: Yes, it's fairly simple. But you need to know k in advance, which takes away a lot of the fun. $\endgroup$
    – rici
    Commented Aug 18, 2015 at 23:55
  • $\begingroup$ @greenoldman: There's a rough explanation of the algo in the comments in this answer on SO: stackoverflow.com/questions/20207339/real-world-lrk-1-grammars/… $\endgroup$
    – rici
    Commented Aug 18, 2015 at 23:59

Your Answer

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

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