4
$\begingroup$

With LL grammars, there seems to be a very intuitive explanation, in terms of first and follow tables.( The first letter/s encountered in a particular state, can only mean a particular rule). With LR grammars however such an explanation seems to be difficult. Of course you could go through the entire construction of the DFA and so on. But is there a general principle or a few of them, that can give an intuitive understanding of LR grammars as a whole?? What is the intuition behind the item sets??

$\endgroup$
2
$\begingroup$

A language is $LR(k)$ if looking at the right side of a production, and looking $k$ symbols ahead, one can determine the left hand side of the production. This is quite incomplete, but intuitively easy (hah!) to grasp. In particular, it explains why $LR$ grammars are a much richer set than the $LL$ ones.

In practice, it is probably much more relevant to be able to understand the format in which your preferred LR parser generator spits out item sets when tickled the right way, and in particular how to track down the origin of conflicts and alternative ways to solve them (and their consecuences). I like the bison manual a lot in this regard.

$\endgroup$
  • 1
    $\begingroup$ Thank you. Could you provide an example to illustrate that intuition. $\endgroup$ – user2277550 Oct 23 '15 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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