628 views
0 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 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).

 

Position:
Show:

Related questions

0 0 votes
1 answers 1 answer
3.0k
3.0k views
Hirak asked Jun 1, 2019
3,042 views
S → aSbS /bSaS / ϵS → aABb A→ c/ ϵ B → d/ ϵWhich of the following is LL1. Explain in details.
0 0 votes
2 2 answers
1.1k
1.1k views
Ebrahim asked Jan 12, 2024
1,114 views
Q1. For the following grammar N - AB | BA A - a | CAC B - b | CBC C - a | b Find the FIRST and FOLLOW
0 0 votes
0 0 answers
720
720 views
admin asked Aug 20, 2019
720 views
Show that the following grammar:$S\rightarrow SA\mid A$$A\rightarrow a$is SLR(1) but not LL(1).
2 2 votes
0 0 answers
638
638 views
admin asked Aug 20, 2019
638 views
Show that the following grammar:$S\rightarrow AaAb\mid BbBa$$A\rightarrow \epsilon$$A\rightarrow\epsilon$is LL(1) but not SLR(1).