# Are regular grammars always LR(1)

The question is fairly straight forward. I just found a question on the internet that asks whether all regular grammars are

1. LL(1)

2. LR(1)

I guess they can't be LL(1) because of left recursion, but how do we prove that they are LR(1) if so.

• First provide a definition of regular grammar. E.g. according to cs.odu.edu/~toida/nerzic/390teched/regular/grammar/… they cannot be left recursive. – reinierpost Jan 30 '15 at 10:41
• I took it to mean the wikipedia definition for regular grammar, which could be both left recursive and right recursive. en.wikipedia.org/wiki/Regular_grammar – anirudh Jan 30 '15 at 11:48
• I notice Wikipedia unexplainably lacks a definition of a LR(k) grammar. So you'll need to get that from a textbook and apply it. – reinierpost Jan 30 '15 at 13:34
• @reinierpost That's far from unexplainable. The article has probably been mostly written by programmer-types. (There's a notable decline of rigor all over Wikipedia the farther along the road from mathematics to programming -- or even mathematical/formal topics programmers find relevant.) – Raphael Jan 30 '15 at 14:00
• There are plenty of people of people here who could fix it ... – reinierpost Jan 30 '15 at 15:53

No.

LR(k) grammars have to be unambiguous, that is there can be only one possible parse tree for every (valid) input. There are left- and right-regular grammars violating that, for example

$\displaystyle\qquad S \to aS \mid aaS \mid a$

or, if that one does not match your definition of right-regular,

\qquad\displaystyle\begin{align} S &\to aS, S \to aA, \\ A &\to aA, A \to a \end{align}

as reinierpost mentions in a comment.

Of course, every regular language does have an unambiguous (right-)regular grammar; get one from its minimal DFA using the standard construction.

• Yes. Such grammars can still be ambiguous, e.g. $S \rightarrow aS, S \rightarrow aA, A \rightarrow aA, A \rightarrow a$. They can't when they're simple (which is defined incorrectly in Wikipedia, I'll fix it). – reinierpost Jan 30 '15 at 16:49
• @reinierpost Thanks, edited. I don't know what you mean by "simple" but one can certainly give a name to the class of all unambiguous regular grammars. – Raphael Jan 30 '15 at 17:13
• Simple = in Greibach Normal Form with all right hand sides for the same nonterminal starting with a different terminal. So it's very close to $\epsilon$-less LL(1). – reinierpost Jan 30 '15 at 17:23