From: Michael J. Barillier
Subject: S-expression grammar?
Date: 
Message-ID: <87y8a97u34.fsf@shadizar.dyndns.org>
I'm trying to find a grammar (for feeding to lex/yacc to be used in a
C app) that will parse Lisp s-expressions.  Basically, I want to write
a chunk of code that will read from a stream and spit out a
box-and-pointers-like data structure representing the stuff read.
(I'd write it myself but I'm getting lazy in my old age ...)

Anyone know of such a beast?  Google was unresponsive.

thx -

-- 
Michael J. Barillier                   | ``When you have to shoot,
blackwolf(at)shadizar.dyndns.org       | shoot.  Don't talk.''
http://shadizar.dyndns.org/~blackwolf/ |               -- Tuco Ramirez
Public key 0x35E54973: EDB9 4FBC 4D0B 070C C0E3 2EE4 D822 78CE 35E5 4973
From: Wade Humeniuk
Subject: Re: S-expression grammar?
Date: 
Message-ID: <pKoje.8548$tt5.8137@edtnps90>
Michael J. Barillier wrote:
> I'm trying to find a grammar (for feeding to lex/yacc to be used in a
> C app) that will parse Lisp s-expressions.  Basically, I want to write
> a chunk of code that will read from a stream and spit out a
> box-and-pointers-like data structure representing the stuff read.
> (I'd write it myself but I'm getting lazy in my old age ...)
> 
> Anyone know of such a beast?  Google was unresponsive.
> 

You do not need lex/yacc.  There exists s-expression parsers
in abundance already, various Lisp implementations.  Instead
of using lex/yacc, read the s-expression into a Lisp and
write a Lisp program to ouput data to the C App.

Wade
From: GP lisper
Subject: Re: S-expression grammar?
Date: 
Message-ID: <1116630005.f56a51dfe11d5a3c30f6a017fa14be12@teranews>
On Fri, 20 May 2005 17:02:13 GMT, <··················@telus.net> wrote:
> Michael J. Barillier wrote:
>> I'm trying to find a grammar (for feeding to lex/yacc to be used in a
>> C app) that will parse Lisp s-expressions.  Basically, I want to write
>> a chunk of code that will read from a stream and spit out a
>> box-and-pointers-like data structure representing the stuff read.

> You do not need lex/yacc.  There exists s-expression parsers
> in abundance already, various Lisp implementations.  Instead
> of using lex/yacc, read the s-expression into a Lisp and
> write a Lisp program to ouput data to the C App.

An appropriate 'Lisp' is ECL, which you can insert into your C
application.


-- 
With sufficient thrust, pigs fly fine.
From: Marco Antoniotti
Subject: Re: S-expression grammar?
Date: 
Message-ID: <zNuje.49$mi7.69449@typhoon.nyu.edu>
You are better off asking these questions on the ecls mailing lists.

Cheers
--
Marco




Stefan Ram wrote:
> GP lisper <········@CloudDancer.com> writes:
> 
>>An appropriate 'Lisp' is ECL, which you can insert into your C
>>application.
> 
> 
>   Under Windows, 0.9c seems to have some problems with the
>   generation of C code 
> 
> http://groups.google.es/groups?selm=2uucolF2f0l1vU1%40uni-berlin.de&output=gplain
> 
>   and the download link provided now for 0.9d 
> 
> http://ecls.sourceforge.net/ecl-0.9d.exe
> 
>   does not work. 
> 
>   It should be possible to compile it under Windows with Mingw,
>   but this does not seem so easy to me, because it seem to need
>   several Mingw-tools (such as autoconfig) and one seem to have
>   to figure out, which tools are needed and so.
> 
From: Kent M Pitman
Subject: Re: S-expression grammar?
Date: 
Message-ID: <usm0hpzng.fsf@nhplace.com>
Michael J. Barillier <········@midsouth.rr.com> writes:

> I'm trying to find a grammar (for feeding to lex/yacc to be used in a
> C app) that will parse Lisp s-expressions.

An S-expression is just a Lisp expression.

Millions of years ago (ok, maybe just 40 or so), in Lisp 1.5 and
earlier, back in the 1960's, there were both M-expressions and
S-expressions.  M-expressions were the base language and S-expresions
were how you could represent the language as data.  Eventually, they
realized that S-expressions were adequate and dropped M-expressions.
The name had no useful meaning by the 1970's, but still hung on and
continues to confuse people today.

To parse a Lisp expression, call READ from in Lisp.

There is no grammar in the way you're meaning.  The definition is 
procedural, not syntactic, since it can be extended by user programs.

(You may be working with a subset that is more tractable than that to
a grammar, but since you didn't say, and only you would know, we have
to answer generally.)

> Basically, I want to write
> a chunk of code that will read from a stream and spit out a
> box-and-pointers-like data structure representing the stuff read.
> (I'd write it myself but I'm getting lazy in my old age ...)

As others have suggested, you're doing this from the wrong side.
Call up a Lisp, get it to call READ, and then use the Lisp printer
to re-format your data in a format your parser is happier with, 
such as XML.
 
> Anyone know of such a beast?  Google was unresponsive.

Google isn't (yet) a problem solver.  It doesn't find things that 
are not there. ;)  But there ARE some Lispers working there, so you
never know what the future may bring...
From: Michael J. Barillier
Subject: Re: S-expression grammar?
Date: 
Message-ID: <87wtpt671d.fsf@shadizar.dyndns.org>
>>>>> "kp" == Kent M Pitman <······@nhplace.com> writes:

    kp> To parse a Lisp expression, call READ from in Lisp.

    kp> There is no grammar in the way you're meaning.  The definition
    kp> is procedural, not syntactic, since it can be extended by user
    kp> programs.

The code I'm working on is a C app that interfaces to a running Lisp
via a pipe.  My implementation choices are a) have the C side
read/write Lisp-friendly data streams, b) have the Lisp side
read/write C-friendly data streams, or c) have the C side write
Lisp-friendly data streams (i.e., s-expressions) and the Lisp side
write C-friendly data streams (of unknown format).  Option c requires
that the interface implementation be split across two applications and
could become something of a maintenance headache.  My supposition was
that if there was a parser grammar available that option a would be a
cake-walk.  Option b is less desirable because I'd still have to write
some sort of parser on the C side to handle the data stream generated
by Lisp (this applies to option c as well).

Plus, I've had other instances where having a simple s-expression
parser in a C library would be handy.

    kp> (You may be working with a subset that is more tractable than
    kp> that to a grammar, but since you didn't say, and only you
    kp> would know, we have to answer generally.)

No read macros or anything, just simple ``(foo ("bar" . 123))''-like
stuff.

    kp> ... use the Lisp printer to re-format your data in a format
    kp> your parser is happier with, such as XML.
 
What's the quote?  ``XML is for people who are afraid of parentheses''
(or something like that). :)

    kp> Google isn't (yet) a problem solver.  It doesn't find things
    kp> that are not there. ;) But there ARE some Lispers working
    kp> there, so you never know what the future may bring...

Not a problem solver, but it sure makes those ``do my homework for
me'' problems easier.  Not that this is a homework assignment ... but
if the code was out there I had hoped Google would have indexed it.

And Microsoft's the future, not Google!  Steve told me so!!
<http://it.slashdot.org/article.pl?sid=05/05/19/1218253> (j/k, I
despise Microsoft.)

Thanks -

-- 
Michael J. Barillier                   | ``When you have to shoot,
blackwolf(at)shadizar.dyndns.org       | shoot.  Don't talk.''
http://shadizar.dyndns.org/~blackwolf/ |               -- Tuco Ramirez
Public key 0x35E54973: EDB9 4FBC 4D0B 070C C0E3 2EE4 D822 78CE 35E5 4973
From: Wade Humeniuk
Subject: Re: S-expression grammar?
Date: 
Message-ID: <uXuje.2932$HI.1968@edtnps84>
A quick Google search yielding a few C sexpr libraries

http://sexpr.sourceforge.net/
http://theory.lcs.mit.edu/~rivest/sexp.html

and..  a link to a sexpr doc with a BNF grammar

http://theory.lcs.mit.edu/~rivest/sexp.txt

Either use the C libraries or translate the BNF
into lex/yacc.

Wade
From: Wade Humeniuk
Subject: Re: S-expression grammar?
Date: 
Message-ID: <TOvje.6794$on1.1140@clgrps13>
Using the PARSERGEN package in LW (you can also use
cl-yacc for this purpose), here is a simple grammar
implemented in Lisp to parse sexprs.  Hopes it gives you
some insight for lex/yacc

CL-USER 29 > (with-input-from-string (s "(hello world () (12 \"ten\" 34))")
               (sexpr-parser (lambda () (sexpr-lexer s))))
((:SYMBOL "hello") (:SYMBOL "world") NIL ((:INT 12) (:STRING "ten") (:INT 34)))
NIL

Wade

(in-package :cl-user)

(require "parsergen")
(use-package :parsergen)

(defparser sexpr-parser
            ((s-expression sexpr))
            ((atom int) (list :int $1))
            ((atom symbol) (list :symbol $1))
            ((atom string) (list :string $1))
            ((sexpr atom) $1)
            ((sexpr list) $1)
            ((list |(| |)|) nil)
            ((list |(| contents |)|) $2)
            ((contents sexpr) (list $1))
            ((contents sexpr contents) (cons $1 $2)))

(defun sexpr-lexer (stream)
   (let ((c (read-char stream nil)))
     (cond
      ((null c) (values nil nil))
      ((member c '(#\space #\tab #\newline)) (sexpr-lexer stream))
      ((char= c #\() (values '|(| c))
      ((char= c #\)) (values '|)|))
      ((char= c #\")
       (let ((buffer (make-array 16 :element-type 'base-char
                                 :fill-pointer 0 :adjustable t)))
         (do ((c (read-char stream nil) (read-char stream nil)))
             ((cond
               ((null c) (error "sexpr-lexer error, unexpected eof in string"))
               ((char= c #\") t)
               (t nil))
              (values 'string buffer))
           (vector-push-extend c buffer))))
      ((alpha-char-p c)
       (let ((buffer (make-array 16 :element-type 'base-char
                                 :fill-pointer 0
                                 :adjustable t)))
         (vector-push-extend c buffer)
         (do ((c (read-char stream nil) (read-char stream nil)))
             ((or (null c) (not (alphanumericp c)))
              (unread-char c stream)
              (values 'symbol buffer))
           (vector-push-extend c buffer))))
      ((digit-char-p c)
       (let ((buffer (make-array 16 :element-type 'base-char
                                 :fill-pointer 0
                                 :adjustable t)))
         (vector-push-extend c buffer)
         (do ((c (read-char stream nil) (read-char stream nil)))
             ((cond
               ((null c) t)
               ((member c '(#\space #\tab #\newline #\"))
                (unread-char c stream) t)
               ((alpha-char-p c)
                (error "sexpr-lexer error, unexpected alpha in int"))
               ((member c '(#\( #\)))
                (unread-char c stream) t)
               (t nil))
              (values 'int (parse-integer buffer)))
           (vector-push-extend c buffer))))
      (t
       (error "sexpr-lexer error, invalid character ~S" c)))))
From: Paolo Amoroso
Subject: Re: S-expression grammar?
Date: 
Message-ID: <87hdgvehj3.fsf@plato.moon.paoloamoroso.it>
Kent M Pitman <······@nhplace.com> writes:

> Millions of years ago (ok, maybe just 40 or so), in Lisp 1.5 and
> earlier, back in the 1960's, there were both M-expressions and
> S-expressions.  M-expressions were the base language and S-expresions

Were there any actual implementations of M-expressions back then?


Paolo
-- 
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film
Recommended Common Lisp libraries/tools (see also http://clrfi.alu.org):
- ASDF/ASDF-INSTALL: system building/installation
- CL-PPCRE: regular expressions
- UFFI: Foreign Function Interface
From: GP lisper
Subject: Re: S-expression grammar?
Date: 
Message-ID: <1116759609.7d4d728d871290f9fefbc8c38ac153df@teranews>
On Sun, 22 May 2005 11:28:32 +0200, <·······@mclink.it> wrote:
> Kent M Pitman <······@nhplace.com> writes:
>> S-expressions.  M-expressions were the base language and S-expresions
>
> Were there any actual implementations of M-expressions back then?

You can find them in the Lisp 1.5 manual.


-- 
With sufficient thrust, pigs fly fine.
From: Christopher C. Stacy
Subject: Re: S-expression grammar?
Date: 
Message-ID: <usm0f70a5.fsf@news.dtpq.com>
GP lisper <········@CloudDancer.com> writes:

> On Sun, 22 May 2005 11:28:32 +0200, <·······@mclink.it> wrote:
> > Kent M Pitman <······@nhplace.com> writes:
> >> S-expressions.  M-expressions were the base language and S-expresions
> >
> > Were there any actual implementations of M-expressions back then?
> 
> You can find them in the Lisp 1.5 manual.

I don't think there was an implementation of M-expressions.
That's why S-expressions were invented.
From: GP lisper
Subject: Re: S-expression grammar?
Date: 
Message-ID: <1116798304.00208e1dd1f7ae393de68ad17078d567@teranews>
On Sun, 22 May 2005 15:22:58 GMT, <······@news.dtpq.com> wrote:
> GP lisper <········@CloudDancer.com> writes:
>
>> On Sun, 22 May 2005 11:28:32 +0200, <·······@mclink.it> wrote:
>> > Kent M Pitman <······@nhplace.com> writes:
>> >> S-expressions.  M-expressions were the base language and S-expresions
>> >
>> > Were there any actual implementations of M-expressions back then?
>> 
>> You can find them in the Lisp 1.5 manual.
>
> I don't think there was an implementation of M-expressions.
> That's why S-expressions were invented.

Well, I don't know for sure, but it does seem that the "M" involved
here used them and I cannot imagine that he didn't have a lisp
available to utilize his code.  Perhaps it was an early and private
lisp for McCathy alone, but their presence the published 1.5 manual (a
large group effort) tends to make me guess otherwise.


-- 
With sufficient thrust, pigs fly fine.
From: Christopher C. Stacy
Subject: Re: S-expression grammar?
Date: 
Message-ID: <uoeb27e9a.fsf@news.dtpq.com>
GP lisper <········@CloudDancer.com> writes:

> On Sun, 22 May 2005 15:22:58 GMT, <······@news.dtpq.com> wrote:
> > GP lisper <········@CloudDancer.com> writes:
> >
> >> On Sun, 22 May 2005 11:28:32 +0200, <·······@mclink.it> wrote:
> >> > Kent M Pitman <······@nhplace.com> writes:
> >> >> S-expressions.  M-expressions were the base language and S-expresions
> >> >
> >> > Were there any actual implementations of M-expressions back then?
> >> 
> >> You can find them in the Lisp 1.5 manual.
> >
> > I don't think there was an implementation of M-expressions.
> > That's why S-expressions were invented.
> 
> Well, I don't know for sure, but it does seem that the "M" involved
> here used them and I cannot imagine that he didn't have a lisp
> available to utilize his code.  Perhaps it was an early and private
> lisp for McCathy alone, but their presence the published 1.5 manual (a
> large group effort) tends to make me guess otherwise.

Everything I've read by McCarthy says that the M-expression language
was an early notation for describing the semantics of the language,
and that S-expressions were the only thing that was implemented.
What do you mean by "the 'M' involved here"?
What in the Lisp 1.5 manual leads you to believe that 
there is any implementation that accepts M-expressions?
From: Hartmann Schaffer
Subject: Re: S-expression grammar?
Date: 
Message-ID: <spwke.3942$pi1.20898@newscontent-01.sprint.ca>
Christopher C. Stacy wrote:
> ...
> Everything I've read by McCarthy says that the M-expression language
> was an early notation for describing the semantics of the language,
> and that S-expressions were the only thing that was implemented.
> What do you mean by "the 'M' involved here"?
> What in the Lisp 1.5 manual leads you to believe that 
> there is any implementation that accepts M-expressions?

slightly off-topic:  i remember having read (a long time ago, iirc in J. 
Sammets programming languages book) about some project called lisp-2, 
that implemented an algol or m-expr type syntax for lisp.  from what i 
remember, it was at stanford under an l. abrahams.  does anybody 
remember anything about this project?  i did try a few web searches, but 
came up empty

hs
From: David Steuber
Subject: Re: S-expression grammar?
Date: 
Message-ID: <87ekc1tbxp.fsf@david-steuber.com>
···@zedat.fu-berlin.de (Stefan Ram) writes:

>   When I wrote a comparison of Unotal with S-expressions,
>   I became aware of the problem that there is not a single
>   widely-accepted Lisp-implementation-independent formal
>   specification of S-expressions.
> 
> http://www.purl.org/stefan_ram/pub/s-expressions-compared-to-unotal

I don't see how s-exps are different from one lisp to another.  Your
web page doesn't clear it up for me.  Could you explain differently?

-- 
An ideal world is left as an excercise to the reader.
   --- Paul Graham, On Lisp 8.1
No excuses.  No apologies.  Just do it.
   --- Erik Naggum
From: Wade Humeniuk
Subject: Re: S-expression grammar?
Date: 
Message-ID: <UyIje.4658$HI.1721@edtnps84>
Stefan Ram wrote:

> 
>   draft-rivest-sexp-00.txt introduces Base64-atom-literals, like
>   |YWJj|, which are not part of most Lisp-implementations,
>   AFAIK, and on the other hand, does not seem to include dotted
>   pairs.
> 

Speaking of which, here is a possible parser for Rivest's Canonical/Transport
sexprs (For LispWorks),

CL-USER 8 > (parse-rivest-sexp "(4:icon[12:image/bitmap]9:xxxxxxxxx)")
("icon" (:DISPLAY-ENCODED "image/bitmap" #(120 120 120 120 120 120 120 120 120)))
NIL

CL-USER 9 > (parse-rivest-sexp "(7:subject(3:ref5:alice6:mother))")
("subject" ("ref" "alice" "mother"))
NIL

Wade


(in-package :cl-user)

(eval-when (:compile-toplevel :load-toplevel :execute)
   (require "parsergen")
   (use-package :parsergen))

(defparser rivest-canonical-sexp-parser
            ((s-expression sexpr))
            ((sexpr string) $1)
            ((sexpr list) $1)
            ((string display simple-string)
             (list :display-encoded $1
                   (map '(simple-array (unsigned-byte 8) (*)) #'char-int $2)))
            ((string simple-string) $1)
            ((display \[ simple-string \]) $2)
            ((simple-string raw) $1)
            ((elements sexpr) (list $1))
            ((elements sexpr elements) (cons $1 $2))
            ((list \( elements \)) $2))

(defun rivest-canonical-sexp-lexer (stream)
   (let ((c (read-char stream nil)))
     (cond
      ((null c) (values nil nil))
      ((member c '(#\space #\tab #\newline)) (error "No Whitespace Allowed in Rivest 
Canonical Form"))
      ((char= c #\() (values '\( c))
      ((char= c #\)) (values '\) c))
      ((char= c #\[) (values '\[ c))
      ((char= c #\]) (values '\] c))
      ((digit-char-p c)
       (let ((length (digit-char-p c)))
         (loop for c = (read-char stream) do
               (cond
                ((digit-char-p c) (setf length (+ (* 10 length) (digit-char-p c))))
                ((char= #\: c) (loop with string = (make-array length :element-type 
'character)
                                     for i from 0 below length
                                     do (setf (aref string  i) (read-char stream))
                                     finally (return-from rivest-canonical-sexp-lexer
                                               (values 'raw string))))
                (t (error "Invalid Rivest Simple String")))))))))

(defun parse-rivest-sexp (string)
   (with-input-from-string (s string)
     (rivest-canonical-sexp-parser (lambda () (rivest-canonical-sexp-lexer s)))))
From: alex goldman
Subject: Re: S-expression grammar?
Date: 
Message-ID: <2200589.sdtVNZZ3I3@yahoo.com>
Michael J. Barillier wrote:

> I'm trying to find a grammar (for feeding to lex/yacc to be used in a
> C app) that will parse Lisp s-expressions. 

I don't think it's possible, because of the reader macros. Lisp is
ungrammatical :-)
From: Matthias Buelow
Subject: Re: S-expression grammar?
Date: 
Message-ID: <3fl0mpF8chiuU1@news.dfncis.de>
alex goldman wrote:

> I don't think it's possible, because of the reader macros. Lisp is
> ungrammatical :-)

Surely not ungrammatical, since then you wouldn't be able to write a 
Lisp interpreter or compiler (at least not on our current types of 
computers).  It's simply not context-free anymore (and probably not 
context-sensitive either).

mkb.
From: Eivind Midtg�rd
Subject: Re: S-expression grammar?
Date: 
Message-ID: <3fgjavF7cmoiU1@individual.net>
"Michael J. Barillier" <········@midsouth.rr.com> wrote in message
···················@shadizar.dyndns.org...
> Basically, I want to write
> a chunk of code that will read from a stream and spit out a
> box-and-pointers-like data structure representing the stuff read.
> (I'd write it myself but I'm getting lazy in my old age ...)

http://www.complang.tuwien.ac.at/~schani/lispreader ?

-- 
Eivind
From: Michael J. Barillier
Subject: Re: S-expression grammar?
Date: 
Message-ID: <87vf58wumh.fsf@shadizar.dyndns.org>
>>>>> "EM" == Eivind Midtg�rd <········@frisurf.no> writes:

    em> http://www.complang.tuwien.ac.at/~schani/lispreader ?

That's what I was looking for - thanks!!

-- 
Michael J. Barillier                   | ``When you have to shoot,
blackwolf(at)shadizar.dyndns.org       | shoot.  Don't talk.''
http://shadizar.dyndns.org/~blackwolf/ |               -- Tuco Ramirez
Public key 0x35E54973: EDB9 4FBC 4D0B 070C C0E3 2EE4 D822 78CE 35E5 4973
comp.lang.lisp / 2005 / may