From: Chris F Clark
Subject: Is there a parser combinator library (or lisp macro solution) for LR parsing?
Date:
Message-ID: <sddwsvz6upz.fsf@shell01.TheWorld.com>
I've been following the various threads in the lisp v. stfp debate
with some interest, especially the macro related parts. After much
reading I wonder if there exists a combinator library or a set of
macros that implement LR parsing.
In particular, I would like a set of macros or combinators, that allow
me to express a grammar and have it checked for well-formed LR-ness,
i.e. that said grammar expressed as macro/function calls is
unambiguous and can be parsed using the left-to-right 1 token
lookahead reduction method with no backtracking, and if the grammar
meets those conditions to produce, create, instantiate, write,
implement, become, whatever the corresponding code that implements
said parser, so that calling those functions results in parsing using
an LR parser. If not, I want the library to indicate an error
(perferrably as readable as possible) at "compile time",
i.e. statically before my program is running and data is coming in.
I ask this question because it gets at one particular point in the
argument, whether one or the other system allows effective arbitrary
rewriting of said code. (It will not settle the debate once and for
all, but it may settle one point at least in my mind.) If one of the
systems (macros or combinator libraries) can express this (and the
other cannot), then that system is better suited to the kind of
self-checking I would want to use.
Note that the question was asked the specific way to get at those issues:
1) Can the system produce rewrites where one needs "to loop" over some
space before establishing how much code is written?
2) Can the system detect and report error and incosnsitencies in the
input patterns (i.e. I want to see "shift/reduce errors" in the
places they belong)?
A system that can do both of those things clearly is sufficiently
powerful (item 1) and sufficiently self-checking (item 2) to write
complex DSLs in (and have uses of those DSL be reliable).
I know we can do the above in stand-alone tools. I know also that we
can do part of the above (e.g. unchecked LL parser combinator
libraries). I don't know if the combination (doing all of the above
without using an outside tool) is possible, especially not if one
wants safety.
From: Neelakantan Krishnaswami
Subject: Re: Is there a parser combinator library (or lisp macro solution) for LR parsing?
Date:
Message-ID: <slrnfc1icv.vvl.neelk@gs3106.sp.cs.cmu.edu>
In article <<···············@shell01.TheWorld.com>>,
Chris F Clark <···@shell01.TheWorld.com> wrote:
> I've been following the various threads in the lisp v. stfp debate
> with some interest, especially the macro related parts. After much
> reading I wonder if there exists a combinator library or a set of
> macros that implement LR parsing.
Yeah, you can do LR parsing combinator style, though for some reason
it's much less common. Google for "recursive ascent" parsing. The
obvious implementation isn't checked, either, though -- the same
problem as recursive descent parser combinators.
--
Neel R. Krishnaswami
·····@cs.cmu.edu
From: Pascal Bourguignon
Subject: Re: Is there a parser combinator library (or lisp macro solution) for LR parsing?
Date:
Message-ID: <87643jdu25.fsf@informatimago.com>
Chris F Clark <···@shell01.TheWorld.com> writes:
> In particular, I would like a set of macros or combinators, that allow
> me to express a grammar and have it checked for well-formed LR-ness,
Yes. Use cliki.net.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
From: Chris F Clark
Subject: Re: Is there a parser combinator library (or lisp macro solution) for LR parsing?
Date:
Message-ID: <sddmywu6o2z.fsf@shell01.TheWorld.com>
Pascal Bourguignon <···@informatimago.com> writes:
> Chris F Clark <···@shell01.TheWorld.com> writes:
>> In particular, I would like a set of macros or combinators, that allow
>> me to express a grammar and have it checked for well-formed LR-ness,
> Yes. Use cliki.net.
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> NOTE: The most fundamental particles in this product are held
> together by a "gluing" force about which little is currently known
> and whose adhesive power can therefore not be permanently
> guaranteed.
Thank you, there appear to be 3 possiblities there, Zebu, LALR, and
CL-Yacc. I'm not sure any of them is a "macro" package (nor is it
clear to me yet that any of them is *not* a macro package either), but
I will investigate further.
On Aug 14, 1:08 pm, Chris F Clark <····@shell01.TheWorld.com> wrote:
> Pascal Bourguignon <····@informatimago.com> writes:
> > Chris F Clark <····@shell01.TheWorld.com> writes:
> >> In particular, I would like a set of macros or combinators, that allow
> >> me to express a grammar and have it checked for well-formed LR-ness,
> > Yes. Use cliki.net.
>
> > --
> > __Pascal Bourguignon__ http://www.informatimago.com/
>
> > NOTE: The most fundamental particles in this product are held
> > together by a "gluing" force about which little is currently known
> > and whose adhesive power can therefore not be permanently
> > guaranteed.
>
> Thank you, there appear to be 3 possiblities there, Zebu, LALR, and
> CL-Yacc. I'm not sure any of them is a "macro" package (nor is it
> clear to me yet that any of them is *not* a macro package either), but
> I will investigate further.
You might want to add this one to your list: FU Compiler Compiler
http://common-lisp.net/project/fucc/
From: David Golden
Subject: Re: Is there a parser combinator library (or lisp macro solution) for LR parsing?
Date:
Message-ID: <Wo6wi.21499$j7.396098@news.indigo.ie>
Chris F Clark wrote:
> a set of macros that implement LR parsing.
Just in case: Remember lisp macros are written in lisp. And of course
one can write parser generators in lisp, so therefore a lisp macro can
output a parser. See cl-yacc for a LALR(1) implementation (though
technically its out-of-box macros output representations of "parser"
objects for later passing to a general function, you could
just write macros to make specialised parser functions if you wanted)
http://www.pps.jussieu.fr/~jch/software/cl-yacc/cl-yacc.html#Macro-interface