Is every LL(1) grammar also an LR(0) grammar?

Question

I know that every LL(1) is also an LR(1). But what about the relationship between LL(1) and LR(0), can a LL(1) be a LR(0) as well?

Unplaced

This might be a better question for Computer Science SE (focused on theory) than StackOverflow (focused on practice). – Bronny

Answer 1

You ask two questions, one in the title and the other in the body of the post. Neither specify whether you are asking about languages or grammars, but the basic answers are the same:

1. Are all LL(1) languages LR(0)?

   No. A language which contains both a string and a proper prefix of that string cannot be LR(0). But many LL(1) languages have that form.

2. Are some LL(1) languages LR(0)?

   Sure.

3. (The unasked question) Are any LR(0) languages not LL(1).

   Yes. For example, the language {ambnc | m≥n≥0} is LR(0), but it has no LL(1) grammar.

Chappy

So by your answer I can say that .. if we do not get any duplicate entries in the LL(1) table for a grammar.. then that grammar.. although it is left factored.. can be a LR(0) (if and only if the grammar is conflict (shift/reduce) free on the LR(0) table).??? – Unplaced

@bopia: a grammar is LR(0) if the LR(0) table is free of conflicts. Nothing else is relevant. – Chappy

Could you give a LR(0) grammar for the {a^mb^n | m≥n≥0} language, please? – Straightlaced

@Chappy I guess you meant S -> T | a S; T -> | a T b. This is not LR(0) according to mdaines.github.io/grammophone Paste ` S -> T . S -> a S . T -> . T -> a T b .` – Straightlaced

A working example is {a^mb^nc | m≥n≥0} with this LR(0) grammar: S -> c . S -> a S . S -> X . X -> T c . T -> a T b . T -> a b . (dots denote end of rule) – Straightlaced

@qznc: You're right on both counts: I did mean S -> a S and that grammar is not LR(0), which I really should have known because it matches the empty string and grammars with λ rules cannot be LR(0). In your correction, X is unnecessary; you can replace S -> X . X -> T c . with S -> T c . I corrected the original post. Thanks. – Chappy