Till now I have believed that a LL language is a language generated by a LL grammar. Same goes for LR.

Now I know some of the hierarchies such as $LL(1)\subset LR(1)$. I used to think that the hierarchy is valid for language as well as grammar i,e if a grammar is LL1 then it must be LR(1); If a language is LL(1) then it must be LR(1).

Language theoretic comparison of LL and LR grammars

In the above link there is mention about two type of hierarchy. One for grammar, another for language. The two hierarchies are different at some points.

For e,g for grammar hierarchy $LALR(1)\subset LR(1)$ but for language hierarchy $LALR(1)=LR(1)$. I accept the grammar hierarchy. But the language hierarchy confuses me. Basically this hierarchy says that LALR(1) language set is equal to LR(1) language set.

How could this be true?

There are some grammars which are LR(1) but not LALR(1). So the language produced by these grammars should be LR(1) but not LALR(1) thus violating the language hierarchy.

I must be making some kind of mistake. please someone point that out?

  • $\begingroup$ Where are you getting the equality $LALR(1) = LR(1)$ from? I don't see that mentioned anywhere in the answer at that link, either. $\endgroup$ – D.W. Dec 28 '17 at 18:38

A language is in a class if there exist a grammar of that class which generates the language. Stating that for languages $LALR(1)=LR(1)$, means that when you have a $LR(1)$ grammar you can build a $LALR(1)$ grammar for the same language. The grammar may be more complex than the $LR(1)$ grammar (for instance, it may use equivalent but different non-terminals to provide the finer distinction of contexts that $LR(1)$ gives for free).

  • $\begingroup$ Your answer makes sense. Every LALR(1) grammar is LR(1) grammar. But there are some LR(1) grammars which are not LALR(1) grammar. Let x be one such grammar. Then it may be possible to build a grammar which is LALR(1) and generate the same language as x. In this way the LALR(1) language set would be equal to LR(1) language set. $\endgroup$ – Kishan Kumar Dec 29 '17 at 16:40

The notation $LR(1)$ denotes the set of languages that can be accepted by a LR(1) parser. So when you see something like $LALR(1)=LR(1)$, that is fundamentally about languages. It is incorrect to write "$LALR(1) \subset LR(1)$ for the grammar hierarchy"; that is meaningless. You haven't defined what you mean by a "grammar hierarchy", so we're forced to guess what that might mean. That's a non-standard concept -- we usually focus on the language hierarchy.

I don't know what the correct relationship between $LALR(1)$ and $LR(1)$ is, but here's how it could be true (if it is true): every LALR(1) grammar is a LR(1) grammar, but not every LR(1) grammar is a LALR(1) grammar; yet perhaps every LR(1) grammar can be rewritten into an equivalent LALR(1) grammar (one that accepts the same language). That would be consistent with (a natural interpretation) of what you wrote.

Keep in mind that there might be multiple grammars that accept the same language.

  • $\begingroup$ " It is incorrect to write "LALR(1)⊂LR(1)LALR(1)⊂LR(1) for the grammar hierarchy"; that is meaningless. " I don't agree with this. When we say $LALR(1) \subset LR(1)$ then for grammar it would mean that every LALR (1) grammar is also LR(1) grammar. I don't see any problem with that. $\endgroup$ – Kishan Kumar Dec 29 '17 at 16:33
  • $\begingroup$ @KishanKumar, It's all in how you define $LR(1)$. You might not see a problem with it, but the problem is that $LR(1)$ is defined (at least in the post you linked to) to mean the set of languages that can be accepted by a LR(1) parser -- see the second paragraph of the question you linked to. That is the standard definition of $LR(1)$, and with that definition, the statement is meaningless. If you want to define $LR(1)$ differently, you can, but you need to state your definitions explicitly (and it might not be a great idea to use notation differently from what's standard in the field). $\endgroup$ – D.W. Dec 29 '17 at 17:57
  • $\begingroup$ I get what u are trying to say. My point is that it makes perfect sense to talk about grammar hierarchy. Your earlier comment led me to believe that u are saying that no hierarchy exists for grammars. But what u really want to say is that hierarchy exists but the notation $LALR(1)\subset LR(1)$ is used for language. $\endgroup$ – Kishan Kumar Dec 29 '17 at 18:57
  • $\begingroup$ @KishanKumar, yes, exactly. Well said. (Perhaps the first two sentences of my answer will make more sense in light of that?) $\endgroup$ – D.W. Dec 29 '17 at 19:52

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.