340 views
0 votes
0 votes
"Every Regular Grammar has a Right linear grammar and this is LL(1)"

What is meaning of this statement exactly and does it hold always?

My Assumptions:

If a grammar is right linear grammar then it can be parser by LL(1)

 ->I am sure they are not left recursive.
-->There definitely exist one unambiguous grammar for that right linear grammar.
But this is not suffice to make grammar LL(1).

Correct if I assumed anything wrong with some intutive answer.

1 Answer

0 votes
0 votes

"Every Regular Grammar has a Right linear grammar and this is LL(1)"

Conditions for LL(1) :

1) unambiguous CFG .

2) left factored.

3) not left recursive.

If a grammar is Right linear then it is Not left recursive for sure.

But if the Right linear grammar is like this,

$S$ $→$ $aA$|$a$                                                                                                                                                               

$A$ $→$ $c$

Then this is not left factored grammar, hence Not LL(1), but there are some which can satisfy all the conditions and can be LL(1).

 

Related questions

0 votes
0 votes
1 answer
1
Hirak asked Jun 1, 2019
2,030 views
S → aSbS /bSaS / ϵS → aABb A→ c/ ϵ B → d/ ϵWhich of the following is LL1. Explain in details.
0 votes
0 votes
0 answers
2
2 votes
2 votes
0 answers
3
admin asked Aug 20, 2019
365 views
Show that the following grammar:$S\rightarrow AaAb\mid BbBa$$A\rightarrow \epsilon$$A\rightarrow\epsilon$is LL(1) but not SLR(1).