1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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, 2017 at 18:38

2 Answers 2

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\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, 2017 at 16:40
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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, 2017 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, 2017 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, 2017 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, 2017 at 19:52

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.