13
$\begingroup$

I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar.

We also know the facts that every LL grammar is LR that is LL grammar is a proper subset of LR grammar. First one is used in top-down parsing and the second one is used in bottom-up parsing.

But is there any way to so that we can say that a given grammar is LL or LR?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ How about using the canonical techniques to generate the $LL(k)$ and $LR(k)$ tables and checking whether they contain conflicts? $LL(1)$ and $LR(1)$ are usually treated in any standard textbook on parsing; the $LL(k)$ and $LR(k)$ techniques are a bit harder to find, but are also well-known. $\endgroup$
    – Alex ten Brink
    Commented Oct 5, 2012 at 16:39
  • $\begingroup$ @AlextenBrink This sounds as if you could give an answer! (Welcome back, you were missed!) $\endgroup$
    – Raphael
    Commented Oct 5, 2012 at 19:51
  • $\begingroup$ Using canonical technique to check whether a grammar is LL or LR is right but a lengthy way. I am trying for a small way of finding this which I found in the book of Compilers by Aho-Lam-Sethi-Ullman. $\endgroup$
    – Debabratta Jena
    Commented Oct 6, 2012 at 3:31

2 Answers 2

Reset to default
12
$\begingroup$

$LL(k)$ and $LR(k)$ grammars are nice not just because they can be parsed efficiently, but also because we can check if a grammar is $LL(k)$ or $LR(k)$, and because we can generate tables for them (parse tables are used to parse input strings). Note that for these two classes, having the parse table immediately allows you to check whether the grammars are in the classes, because this is so if and only if the tables contain no errors. Also, yes, there are classes of grammars which we can parse efficiently if we have a parse table, but for which we cannot generate the table if it exists.

Any textbook on parsing methods will teach you how to generate the tables for $LL(1)$ methods and possibly also for $LR(1)$ (though $SLR(1)$ is more common). Textbooks such as Parsing Theory by Sippu and Soisalon-Soininen also treat the parse table generation for $LL(k)$ and $LR(k)$ grammars.

Unfortunately, for really weird grammars, the parse tables for $LL(k)$ and $LR(k)$ (though not for $LL(1)$) can blow up and become huge; they will do this even for normal grammars if $k$ is high enough. There are tests available that can check whether a grammar is $LL(k)$ or $LR(k)$ or not that run in polynomial time (table generation is exponential). For details, read the textbook above. Note that in a lot of cases, the table is reasonably sized, so the test is not needed.

If you don't want to try values of $k$ to see if your program works, but instead want to have your computer figure out whether there exists a value of $k$ such that your grammar is $LL(k)$ or $LR(k)$, you are unfortunately out of luck, as this is undecidable. If your grammar is $LR(k)$ for some $k$ though, you can decide whether your grammar is $LL(c)$ for some $c$, possibly different from $k$ (see here for details).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Do you happen to know where I can find the details of the polynomial-time algorithm for testing if a language is LR(k) (aside from buying the textbook)? $\endgroup$
    – user541686
    Commented May 21, 2014 at 9:08
3
$\begingroup$

We have to check only that a grammar is LL or not because every LL grammar is LR that is LL is proper subset of LR. So if a grammar is LL then it must be LR but every LR is not LL.

A grammar G is in LL iff whenever A->C|D , the following condition should hold:

  1. First(C) and First(D) are disjoint sets.
  2. If empty is in First(D) the First(C) and Follow(A) are disjoint sets likewise empty is in First(C).
Improve this answer
$\endgroup$

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.