🚀 go-pugleaf

In article <1992Nov10.170123.107@eng.cam.ac.uk> ptb@eng.cam.ac.uk (P.T.
Breuer) writes:


   Thanks to Debora Weber-Wulff for offering a test case.
   The language { a^n b^n | n>=0 } apparently definitely has no LL grammar
   (but does have a LR(0) one) and is specifiable in pre-cc. But not all
   LR(0) grammars are acceptable for precc, because LR(0) presentations can be
   left recursive. 

a^n b^n not LL ?  Here's a grammar:

S -> A -|   (endmarker)
A -> a A b
A -> e

You can tell which of the two productions for to use for A: if it's an "a",
you use the first, if it's "b" or the endmarker you use the second. (In other
words, the FIRST sets of the 2 A-productions are disjoint, as needed for
LL(1)-ness).  Am I missing something here?

   I think all LR(0) languages are expressible, though,
   if you choose the right grammar presentation.

There's a theorem that says that any deterministic context-free language (ie
acceptable by some deterministic PDA) is expressible by some LR(0) grammar.
However, the grammar may be pretty ugly.

--Mitch 
--
Mitchell Wand
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN, Boston, MA 02115     Phone: (617) 437 2072
Internet: wand@flora.ccs.northeastern.edu          Fax:   (617) 437 5121