home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!mcsun!uknet!cam-eng!ptb
- From: ptb@eng.cam.ac.uk (P.T. Breuer)
- Newsgroups: comp.lang.functional
- Subject: Re: Functional Parsers
- Keywords: parsers
- Message-ID: <1992Nov10.170123.107@eng.cam.ac.uk>
- Date: 10 Nov 92 17:01:23 GMT
- References: <1992Nov3.145117.21227@eng.cam.ac.uk> <1992Nov3.160104.5305@odin.diku.dk> <1992Nov4.153220.8174@eng.cam.ac.uk>
- Sender: ptb@uk.ac.cam.eng
- Organization: Cambridge University Engineering Department, England
- Lines: 61
- Nntp-Posting-Host: tw308.eng.cam.ac.uk
-
- >In article <1992Nov3.160104.5305@odin.diku.dk> torbenm@diku.dk
- >(Torben AEgidius Mogensen) writes:
- >>ptb@prg.ox.ac.uk (Peter Breuer) writes:
- >>
- >>>There is also a paper by Jonathan Bowen and myself (which I think has
- >>>[...]
- >>
- >>Does this parser generator handle non-LL languages?
- >
- >I don't mind admitting that I don't know what a non-LL language looks like.
-
-
- 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. I think all LR(0) languages are expressible, though,
- if you choose the right grammar presentation.
-
- two specifications:
-
- (1) not using attributes
-
- @ S = AB $
-
- @ AB = a AB b
- @ | a b
-
- (2) using attributes
-
- @ S = as\n b*n $
-
- @ as = a as\n @n+1
- | a @1
-
- The latter is the more powerful technique, since it is computationally
- complete, as I showed by specifying an interpreter for occam object
- code. Admittedly, that was the worst possible example to choose! But
- it's the basis of my claim that LR(0) languages are expressible.
-
- If you want the functional programming interpretations, then (using the
- operator notation from graham hutton's soon-to-be JFP paper - see this
- thread)
-
- (1) S = AB $then EOL
-
- AB = (a $then AB $then b) $alt (a $then b)
-
- (2) S = as $into (n -> bs(n) $then EOL)
-
- as = (a $then as $into (n -> success(n+1))) $alt (a $then success 1)
-
- bs(n) = b $then bs(n-1) , n>1
- = b , otherwise
-
- Has anyone done a speed comparison of the pure combinator approach (aka
- Wadler (1985), Fairbairn (1987), etc.) versus combinators which build new
- state machines from old, Using cross products of the state spaces, and
- so on?
-
- Peter
-