NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/lang/function/1347

Internet Message Format | 1992-11-10 | 2.0 KB

Path: sparky!uunet!pipex!warwick!mrccrc!doc.ic.ac.uk!agate!ames!saimiri.primate.wisc.edu!zaphod.mps.ohio-state.edu!darwin.sura.net!spool.mu.edu!hri.com!noc.near.net!lynx!random.ccs.northeastern.edu!news
From: [e-mail] (Mitchell Wand)
Newsgroups: comp.lang.functional
Subject: Re: Functional Parsers
Message-ID: <[e-mail]>
Date: 10 Nov 92 18:52:23 GMT
References: <[e-mail]> <[e-mail]>
    <[e-mail]>
    <[e-mail]>
Sender: [e-mail]
Organization: College of Computer Science, Northeastern University
Lines: 34
In-Reply-To: [e-mail]'s message of 10 Nov 92 17: 01:23 GMT
Nntp-Posting-Host: dec5120z.ccs.northeastern.edu

In article <[e-mail]> [e-mail] (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: [phone]
Internet: [e-mail]          Fax:   [phone]