5
$\begingroup$

when i was studying compilers i came across this in Wikipedia every DCFL has a corresponding unambiguous grammar and hence can be parsed by an LR(1) parser which is the most powerful parser then what is the significance of LR(k) parsers are they more powerful than LR(1) when every DCFL can be parsed by LR(1) why do we need LR(k)?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

Remember that the point of parsing (in almost all practical applications) is not simply to recognize whether or not a sentence is in a language, but rather to find the parse tree corresponding to the sentence in order to do further processing (such as compilation). Or, to put it another way, few people would purchase a "compiler" which took some input and whose output was limited to one of two sentences:

  • That input is a syntactically valid C program

  • That input is not a syntactically valid C program.

By a large, the desired product is an executable, not just an assurance that the program could be compiled if you had a compiler.

So, it is true that if there is an LR(k) grammar for a language, then there is also an LR(1) grammar. But it is not the same grammar (unless k is 1) and it will therefore not produce the same parse tree.

It is possible to mechanically transform the LR(k) grammar into an LR(1) grammar in a way that the original parse tree can be recovered, but it is not a procedure you want to try by hand. (Trust me on this.)

So if you have an LR(k) grammar and you want to build a parser, you could:

  • Find an LR(k) parser generator

  • Find a program which mechanically tranforms an LR(k) grammar into the corresponding LR(1) grammar and the code necessary to transform a parse tree produced by the LR(1) grammar into the corresponding parse tree which would have been produced by an LR(k) parse. Then feed the LR(1) grammar into an LR(1) parser generator and add the parse tree recovery code to the semantic actions.

These two tasks are not particularly different. The mechanical transformation of an LR(k) grammar into an LR(1) grammar blows up the size of the grammar much in the way that the LR(k) parse tables are much larger than the LR(1) parse tables. From a practical viewpoint, it is roughly equally difficult to find an LR(k) parser generator as it is to find an automatic LR(k)→LR(1) transformer.

Improve this answer
$\endgroup$
9
  • $\begingroup$ sir look at this link stackoverflow.com/questions/6379937/… .. sir in this image it shows LR(K) contains LR(1) in it but shouldnt they both be the same as if there is an LR(K) there will surely be an LR(1) grammer for the language right ? is this image wrong $\endgroup$
    – venkat
    Jan 11, 2018 at 5:25
  • $\begingroup$ @venkat: that chart is for grammars, not languages. An LR(1) grammar is LR(k) but an LR(k) grammar is not necessarily LR(1). The language is LR(1) because we know that there must be a different grammar for the language which is LR(1). $\endgroup$
    – rici
    Jan 11, 2018 at 6:16
  • 1
    $\begingroup$ You must try to understand the difference between a language and a grammar. A language is just a possibly-infinite set of sentences. A parser works on a grammar; the language it parses is the set of sentences recognised by that grammar. It s is undecidable (in general) whether two grammars produce the same set (language). $\endgroup$
    – rici
    Jan 11, 2018 at 14:11
  • 1
    $\begingroup$ @anir: "mechanically" means that there is an algorithm which can do it. No inspiration is necessary. The proof of the proposition is constructive; it shows that the algorithm works. You should be able to find the proof in a good text on formal language theory, probably with an example of the construction. The text I usually recommend is Parsing Theory by Sippu&Soisalon-Soininen, but it's not an easy read; there are probably other more accessible textbooks... $\endgroup$
    – rici
    Jun 29, 2019 at 14:58
  • 1
    $\begingroup$ As far as I know, there's no readily available software which implements the algorithm, for the same reason that LR(k) parser generators don't exist for values of $k>1$: the generated parsers are just too big. The LR(k)->LR(1) algorithm effectively starts with the LR(k) automaton; it does not in any way simplify it. It's really just a different presentation of the same algorithm. So in practical terms, it doesn't add much value. But understanding how it works is a great exercise in understanding the KR(k) algorithm in general. $\endgroup$
    – rici
    Jun 29, 2019 at 15:04

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.