0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ First provide a definition of regular grammar. E.g. according to cs.odu.edu/~toida/nerzic/390teched/regular/grammar/… they cannot be left recursive. $\endgroup$ – reinierpost Jan 30 '15 at 10:41
  • $\begingroup$ 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 $\endgroup$ – anirudh Jan 30 '15 at 11:48
  • 2
    $\begingroup$ 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. $\endgroup$ – reinierpost Jan 30 '15 at 13:34
  • $\begingroup$ @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.) $\endgroup$ – Raphael Jan 30 '15 at 14:00
  • $\begingroup$ There are plenty of people of people here who could fix it ... $\endgroup$ – reinierpost Jan 30 '15 at 15:53
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – reinierpost Jan 30 '15 at 16:49
  • $\begingroup$ @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. $\endgroup$ – Raphael Jan 30 '15 at 17:13
  • $\begingroup$ 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). $\endgroup$ – reinierpost Jan 30 '15 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.