I came across following:
Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.
I tried to get that.
Definition: Right linear grammar (RLG)
In right linear grammar, all productions are of one of the following forms: $A\rightarrow t^*V$ or $A\rightarrow t^*$, where $A$ and $V$ are non terminals and $t$ is terminal.
Definition: LL(1) grammar
A grammar $G$ is $LL(1)$ grammar if and only if whenever $A→α|β$ are two distinct productions of $G$, the following conditions hold:
- For no terminal $a$ do both $α$ and $β$ derive strings beginning with $a$.
- At most one of $α$ and $β$ can derive the empty string.
- If $β⇒^*ϵ$, then $α$ does not derive any string beginning with a terminal FOLLOW(A). Likewise, if $α⇒^*ϵ$, then $β$ does not derive any string beginning with a terminal in FOLLOW(A). ($β⇒^*ϵ$ means $B$ derives $\epsilon$)
(Q1.) How definition of RLG ensures condition 1 in the definition of LL(1) grammar.
This answer says:
All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or one produces ε and has $ as a lookahead token.
(Q2.) I read somewhere "eliminating left recursion from given grammar does not necessarily make it LL(1)". Then how turning grammar to right recursive will ensure its LL(1) (as stated in above quoted answer)?
(Q3). I didnt get the significance of "one produces ε and has $ as a lookahead token" in above quoted answer.
(Q4.) First quote in this question says right linear grammar is LL(1). How is it so?
(Q5.) This answer says "all regular languages have a LR(0) grammar", I guess its incorrect as LR(0) are DCFLs with prefix property which are not superset of regular languages. Am I right with this?