ok it is LL(1)

But how can u say it is not LR(1) or LALR(1)?

means it can be satisfied by some other language too. plz explain

The Gateway to Computer Science Excellence

+49 votes

Best answer

ans is **A**

$First(S)=First(C)=\{c,d\}$

There are no multiple entries in single row of parsing table hence grammar is LL1

Note : If we have $A \rightarrow B\mid C,$ for grammar to be LL(1) first(B) intersection First(C) should be null otherwise grammar is not LL1. If First(B) contains $\epsilon$ then Follow(A) intersection First(C) should be null. Using this we can say grammar is LL(1) or not without constructing parsing table.

An $\epsilon$ free LL(1) grammar is also SLR(1) and hence LALR(1) and LR(1) too.

+2

ok it is LL(1)

But how can u say it is not LR(1) or LALR(1)?

means it can be satisfied by some other language too. plz explain

0

You need to check it for slr(1) also. If it's going to be slr(1) then it will be LALR(1) and CLR(1) also.

PS: if you check given grammar is LR(0) also

PS: if you check given grammar is LR(0) also

–2

Grammar is LL(1) is correct.. Every LL(1) grammar is LALR(1) so it is LALR also. but when it is not SLR(1) as it contain S-R conflict... so ans should be c!!!!!!!!!!?

0

LALR(1) generate DCFL and LL(1) generate regular language.

Regular Language is subset of DCFL so If grammar is LL(1), it should be LALR(1)!

+22

That's wrong except the conclusion. If a grammar is LL(1) and not containing $\epsilon$, then it is SLR(1) and so LALR(1) and LR(1).

LL(1) generate a superset of regular and subset of DCFL. LL(k) strictly generate a subset than LL(k+1) for k >=0.

SLR(1) generate DCFL. LALR(1) and LR(1) also generate DCFL. LR(k) generate the same language as LR(k+1) for k > 0. LR(0) generate the DCFL with prefix property (DPDA with empty stack).

For parser we tell power not in terms of the language their grammar can generate, but the grammars they can parse. SLR(1) < LALR(1) < LR(1), because they can parse more and more grammars in that order though all those grammars can generate the same set- DCFL. i.e., for any LR(1) grammar there is an equivalent SLR(1) grammar which can be parsed by a SLR(1) parser.

LL(1) generate a superset of regular and subset of DCFL. LL(k) strictly generate a subset than LL(k+1) for k >=0.

SLR(1) generate DCFL. LALR(1) and LR(1) also generate DCFL. LR(k) generate the same language as LR(k+1) for k > 0. LR(0) generate the DCFL with prefix property (DPDA with empty stack).

For parser we tell power not in terms of the language their grammar can generate, but the grammars they can parse. SLR(1) < LALR(1) < LR(1), because they can parse more and more grammars in that order though all those grammars can generate the same set- DCFL. i.e., for any LR(1) grammar there is an equivalent SLR(1) grammar which can be parsed by a SLR(1) parser.

+2

@Arjun sir, I know that $LR(1)=LR(k)=DCFL\; \;(k\geq0)$.

I mean: For every k≥1, "a language can be generated by an LR(k) grammar if and only if it is deterministic [and context-free], if and only if it can be generated by an LR(1) grammar.

and wiki says this too.

But your last line of comment is saying,

"for any LR(1) grammar there is an equivalent SLR(1) grammar which can be parsed by a SLR(1) parser." i.e. $LR(1)=LR(k)=SLR=DCFL$. Can i get any refrence for it ?

+2

Thank you sir for link. It makes a statement, that is

"every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar", I am not sure how much it is true, as this is also "discussion" not a source to be trusted. I will try if i find any better source.

Thank you sir :)

"every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar", I am not sure how much it is true, as this is also "discussion" not a source to be trusted. I will try if i find any better source.

Thank you sir :)

+3

@Arjun sir, I asked this question here and got an awesome reply :)

He also proved this statement.

0

@Sachin Mittal 1

I have a small doubt ::

Statement 1 : For every DCFL there exits a LR(0) or a LR(1) grammer.

Statement 2 : For every DCFL there exits a LR(1) grammer.

Which is true??

According to me first one.But the discussion and other links, points that second one is true.

I am confused a bit.Can you provide some reference on this.

I have a small doubt ::

Statement 1 : For every DCFL there exits a LR(0) or a LR(1) grammer.

Statement 2 : For every DCFL there exits a LR(1) grammer.

Which is true??

According to me first one.But the discussion and other links, points that second one is true.

I am confused a bit.Can you provide some reference on this.

0

@Arjun sir:-

IS the following statement true?

If a grammar is LL(1) and not containing ϵϵ, then it is SLR(1) and so LALR(1) and LR(1).

0

wikki says-

A *ε*-free LL(1) grammar is also a SLR(1) grammar. A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar. A LL(1) grammar with symbols that have only the empty derivation may or may not be LALR(1).^{[5]}

0

According to wiki - https://en.wikipedia.org/wiki/LL_grammar

A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar.

is it true?

0

@Arjun sir @Pooja Palod mam.. please validate these statement

"A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar."

"An ϵ free LL(1) grammar is also SLR(1) and hence LALR(1) and LR(1) too."

0

@Arjun LR(k) generate the same language as LR(k+1) for k > 0

But the above Venn diagram doesn't support this,right? LR(1) is shown as a subset of LR(k).

0

If a grammar is LL(1) and not containing

ϵ, then it is SLR(1) and so LALR(1) and LR(1).

@Arjun Sir,

So does it means that, **if a grammar is LL(1) and not containing epsilon** then it will not be LR(0) ? *because I am not able to get any such grammar !*

+2 votes

0

Hi @Sachin Mittal 1, is this statement really true "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar". Check this wiki link out https://en.wikipedia.org/wiki/LALR_parser, it says here "It was also proven that there exist LR(1) languages that are not LALR".

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,379 answers

198,524 comments

105,318 users