1
$\begingroup$

I know that languages that have LL(1) grammar also will have LR(1) grammar as LL(1) grammar can be written only for a subset of DCFL whereas LR(1) grammar can be written for all DCFL, but I wanted to know where LL(1) will fall if I had it put it along with LR parsers.

L1 is defined as languages for which LL(1) grammar exists and L2 is defined as languages for which LALR(1) grammar exists, is L1 a subset of L2? so I was looking for a language that has LL(1) grammar but doesn't have LALR(1) grammar as a counter-example.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Every language which has an $LR(k)$ grammar for some $k$ has an $SLR(1)$ grammar (which is necessarily also $LALR(1)$ and $LR(1)$).

The proof is constructive: from the $LR(k)$ grammar, you can mechanically derive the $SLR(1)$ grammar.

So $LR(1)$ languages and $LALR(1)$ languages are the same set (which is the set of deterministic languages), and as you note $LL(1)$ languages are a proper subset.

Improve this answer
$\endgroup$
2
  • $\begingroup$ as for any LR(k) grammar we can derive SLR(1) grammar so SLR(1) = LALR(1) = LR(1) = DCFL...would this be right? also I know LL(1) is subset of LL(k) but is it possible that LR(1) is a subset of LL(k) for some k?(with respect to their language sets) $\endgroup$
    – Arun Madhav
    Commented Dec 9, 2022 at 5:11
  • $\begingroup$ @arun: $LL(k) \subset LR(k)=LR(1)$. So $LL(k) \subset LR(1)$. So, no. $\endgroup$
    – rici
    Commented Dec 9, 2022 at 5:25

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.