Hi all,
I've been attempting to introduce myself to Common Lisp (thanks to
LispBox) for about three days now, and I'm floundering a wee bit, so
I'd like to seek your guidance.
First off, just so you know what skill level (if it's actually
applicable) I'm at, I've been programming for 2 years, 95% of the time
using Python, 3% using C and the other 2% trying and disliking Java, C#
etc.
Must say, Lisp is very much a culture shock, I found what I'd learnt in
Python was easily transferrable to most other Algol descendents, but it
has been of minimal usage so far with Lisp.
I learn best when I have a specific aim, so I thought I'd recode a
simple parser I wrote in Python into Lisp, just because Lisp feels like
it'd make an elegant parse.
The syntax is pretty straightforward, just looking to turn this
alliance = {
id = { type = 4716 id = 59728 }
type = dynasticalliance
startdate = { year = 1652 month = september day = 27 }
expirydate = { year = 1677 month = september day = 27 }
participant = { HOL FRA }
}
into
(alliance
((id ((type 4716) (id 59728))
(type dynasticalliance)
(startdate ((year 1652) (month september) (day 27)))
(expirydate ((year 1677) (month september) (day 27)))
(participant (HOL FRA))))
But to be honest, I'm not sure on what data structures to use.
In Python I'd simply used a list as a stack, and I'd append new lists
to it when new groups were opened and pop them when the group closed,
which if I understand my googled results correctly, is pretty much how
a context free grammar gets parsed... I know nothing about parsing
theory.
My first attempt at this used a vector created with
(make-array 0 :fill-pointer 0 :adjustable t)
as a stack and pushed/popped similar vectors on and off it. However, I
hamstrung myself with the fact that (last foo) doesn't work for
vectors, so I ended up using (elt foo (1- (length foo))) which isn't
overly elegant.
So, at this point, I gave up, as I realised that perhaps attempting to
reimplement Python in Lisp was missing the point; that it wasn't
working.
Oh, also, to clarify, a list in Lisp is what I'd call a linked list in
C, is that correct?
But yeah, I'd like to get the basics right and use the correct tool for
the job.
Is there a data structure traditionally used for stack operations? If
you were attempting to implement the above, what structure would you
use?
Also, if anyone knows of any simple parsers written in Lisp that I can
read, please let me know. I've found Franz's HTML parser, but it's a
bit too big for me to grok at the moment, given my minimal experience.
Thanks in advance,
Liam Clarke
--
Liam Clarke wrote:
> I learn best when I have a specific aim, so I thought I'd recode a
> simple parser I wrote in Python into Lisp, just because Lisp feels like
> it'd make an elegant parse.
You might learn from Henry Baker's "Pragmatic Parsing in Common Lisp"
http://home.pipeline.com/~hbaker1/Prag-Parse.html
On Sun, 01 Jan 2006 19:33:28 GMT, "Liam Clarke" <··········@gmail.com>
wrote:
>
>So, at this point, I gave up, as I realised that perhaps attempting to
>reimplement Python in Lisp was missing the point; that it wasn't
>working.
>
>Oh, also, to clarify, a list in Lisp is what I'd call a linked list in
>C, is that correct?
Pretty much.
>
>But yeah, I'd like to get the basics right and use the correct tool for
>the job.
You might consider a radically different approach than Python:
Investigate how to modify the Lisp Reader to treat '{' and '}' as '('
and ')'
Then read the whole toplevel thing in from a file as one big string,
prefix the string with '{', postfix the string with '}', call
READ-FROM-STRING on the string and you'll be 80% done without
having to do anything resembling parsing.
This would be considered an advanced technique but it would give
you a much better flavor of what is possible in Lisp that could be
difficult in Python; there's not a lot of sense in rewiriting your
Python code in Lisp virtually token for token.
JP Massar wrote:
> On Sun, 01 Jan 2006 19:33:28 GMT, "Liam Clarke" <··········@gmail.com>
> wrote:
>
> >
> > So, at this point, I gave up, as I realised that perhaps attempting
> > to reimplement Python in Lisp was missing the point; that it wasn't
> > working.
> >
> > Oh, also, to clarify, a list in Lisp is what I'd call a linked list
> > in C, is that correct?
>
> Pretty much.
>
> >
> > But yeah, I'd like to get the basics right and use the correct tool
> > for the job.
>
> You might consider a radically different approach than Python:
>
> Investigate how to modify the Lisp Reader to treat '{' and '}' as '('
> and ')'
>
> Then read the whole toplevel thing in from a file as one big string,
> prefix the string with '{', postfix the string with '}', call
> READ-FROM-STRING on the string and you'll be 80% done without
> having to do anything resembling parsing.
>
> This would be considered an advanced technique but it would give
> you a much better flavor of what is possible in Lisp that could be
> difficult in Python; there's not a lot of sense in rewiriting your
> Python code in Lisp virtually token for token.
Hmm... well, modifying the read-table seemed simple, but using
(set-syntax-from-char #\{ #\() is explicitly mentioned in the Hyperspec
as only giving you the ability to do - {list 1 2 3) as the reader macro
for the left parentheses is hardwired to look for a right parentheses.
No worries, thinks I, I'll just use get-macro-character and have a look
at the reader macro for left paren, and try and tweak that, it'll be
fun.
Oerrr. Okay, so for a function -
(foo()
(print 'bob))
using (pprint #'foo) gives
#<CLOSURE FOO NIL (DECLARE (SYSTEM::IN-DEFUN FOO)) (BLOCK FOO (PRINT
'BOB))>
but using (pprint #'(get-macro-character #\()) gives -
#<SYSTEM-FUNCTION SYSTEM::LPAR-READER>
So, from this, I assume that LPAR-READER is compiled and hence not
human readable.
Which leads me to now- I'm having real issues trying to find the source
code for LPAR-READER; I'm using CLISP, and I've gone to the CVS
directory, but I can't seem to find anything resembling a system.lisp
or similar.
I can achieve a similar effect with -
(setq w (substitute #\( #\{ (substitute #\) #\} sample-text)))
on the given text, but the idea of temporarily changing the parser
sounds more fun than a string sub.
However, must say that I'm quite impressed with how simple it is to
change the readtable on the fly, but I can foresee myself doing
something very stupid with that power at some point.
Any assistance in locating the source for LPAR-READER would be
greatfully appreciated.
Regards,
Liam Clarke
--
Liam Clarke <··········@gmail.com> wrote:
+---------------
| #<SYSTEM-FUNCTION SYSTEM::LPAR-READER>
|
| So, from this, I assume that LPAR-READER is compiled and hence not
| human readable.
|
| Which leads me to now- I'm having real issues trying to find the source
| code for LPAR-READER; I'm using CLISP, and I've gone to the CVS
| directory, but I can't seem to find anything resembling a system.lisp
| or similar.
...
| Any assistance in locating the source for LPAR-READER would be
| greatfully appreciated.
+---------------
The source for LPAR-READER is not in Lisp, it's in C [as are a lot
of the speed-critical I/O routines in CLISP]. Look in the following
source files [the CLISP build preprocesses ".d" into ".c" files]:
src/constsym.d [line 359 or so]
src/io.d [line 2519 or so]
But you might be able to use READ-DELIMITED-LIST (q.v.) to solve
your problem...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
In article <······················@news.xtra.co.nz>,
Liam Clarke <··········@gmail.com> wrote:
> The syntax is pretty straightforward, just looking to turn this
>
> alliance = {
> id = { type = 4716 id = 59728 }
> type = dynasticalliance
> startdate = { year = 1652 month = september day = 27 }
> expirydate = { year = 1677 month = september day = 27 }
> participant = { HOL FRA }
> }
>
> into
>
> (alliance
> ((id ((type 4716) (id 59728))
> (type dynasticalliance)
> (startdate ((year 1652) (month september) (day 27)))
> (expirydate ((year 1677) (month september) (day 27)))
> (participant (HOL FRA))))
This would be really easy to write as a recursive-descent parser, in
which case you don't need to worry about manually keeping track of the
parse state on a stack. Google for "recursive-descent parser" for
examples.
That being said, allow me to present the "cheating" solution:
(asdf:operate 'asdf:load-op :yacc) ; see http://www.cliki.net/CL-Yacc
(use-package :yacc)
(defun simple-lexer (stream)
#'(lambda ()
(let ((*read-eval* nil))
(handler-case
(let* ((token (read stream t)))
;; KLUDGE - this will break under a different *package*
(if (member token '({ = }))
(values token token)
(values 'NAME token)))
(end-of-file () (values nil nil))))))
(define-parser *simple-parser*
(:start-symbol expression-list)
(:terminals (NAME { = }))
(expression
NAME
(NAME = expression (lambda (a b c) (list a c)))
(NAME = { expression-list } (lambda (a b c d e) (list a d))))
(expression-list
(expression)
(expression-list expression (lambda (a b) (append a (list b))))))
CL-USER> (with-input-from-string (s "alliance = {
id = { type = 4716 id = 59728 }
type = dynasticalliance
startdate = { year = 1652 month = september day = 27 }
expirydate = { year = 1677 month = september day = 27 }
participant = { HOL FRA }
} ")
(parse-with-lexer (simple-lexer s) *simple-parser*))
((ALLIANCE
((ID ((TYPE 4716) (ID 59728)))
(TYPE DYNASTICALLIANCE)
(STARTDATE ((YEAR 1652) (MONTH SEPTEMBER) (DAY 27)))
(EXPIRYDATE ((YEAR 1677) (MONTH SEPTEMBER) (DAY 27)))
(PARTICIPANT (HOL FRA)))))
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Wow, thanks for that everyone.
I had a read of that pragmatic parsing, and I think I'll bookmark it
and come back to it when I'm more able to understand it, but I gleaned
from it that the gentleman used macros to create a sort of mini-parsing
language, the kind of stuff Paul Graham keeps mentioning as an
illustration of why he likes Lisp so much.
I may actually code the parser 3 times, to try all three mentioned
approaches. And, when I actually approach something resembling
competent, I'll see what approaches I glean from the parsing article.
Thanks so much!
Liam Clarke
--
From: Russell McManus
Subject: Re: Lisp newbie, data structures, parsing.
Date:
Message-ID: <87aceepv33.fsf@cl-user.org>
"Liam Clarke" <··········@gmail.com> writes:
> Wow, thanks for that everyone.
>
> I had a read of that pragmatic parsing, and I think I'll bookmark it
> and come back to it when I'm more able to understand it, but I gleaned
> from it that the gentleman used macros to create a sort of mini-parsing
> language, the kind of stuff Paul Graham keeps mentioning as an
> illustration of why he likes Lisp so much.
>
> I may actually code the parser 3 times, to try all three mentioned
> approaches. And, when I actually approach something resembling
> competent, I'll see what approaches I glean from the parsing article.
> Thanks so much!
From my home-grown parser generator:
(defpackage "LIAM"
(:use :common-lisp))
(in-package "LIAM")
(org.cl-user.parser-gen:def-lexer liam-lexer ()
(("[a-zA-Z]+" :alpha)
("[0-9]+" :digit)
("[{}=]" :punctuation)))
(org.cl-user.parser-gen:defparser liam-parser (:lexer liam-lexer
:start-state key-equals-value)
(key-equals-value := (and key "=" rvalue))
(key := (:token :alpha))
(rvalue := (or sub-key-equals-value simple-value list-value))
(simple-value := (or (:token :digit) (:token :alpha)))
(sub-key-equals-value := (and "{" (* key-equals-value) "}"))
(list-value := (and "{" (* simple-value) "}")))
(let ((s
" alliance = {
id = { type = 4716 id = 59728 }
type = dynasticalliance
startdate = { year = 1652 month = september day = 27 }
expirydate = { year = 1677 month = september day = 27 }
participant = { HOL FRA }
}"))
(org.cl-user.parser-gen::->list
(liam-parser s)))
=> (KEY-EQUALS-VALUE
((KEY "alliance")
(SUB-KEY-EQUALS-VALUE
(((KEY-EQUALS-VALUE
((KEY "id")
(SUB-KEY-EQUALS-VALUE
(((KEY-EQUALS-VALUE ((KEY "type") (SIMPLE-VALUE "4716")))
(KEY-EQUALS-VALUE ((KEY "id") (SIMPLE-VALUE "59728"))))))))
(KEY-EQUALS-VALUE ((KEY "type") (SIMPLE-VALUE "dynasticalliance")))
(KEY-EQUALS-VALUE
((KEY "startdate")
(SUB-KEY-EQUALS-VALUE
(((KEY-EQUALS-VALUE ((KEY "year") (SIMPLE-VALUE "1652")))
(KEY-EQUALS-VALUE ((KEY "month") (SIMPLE-VALUE "september")))
(KEY-EQUALS-VALUE ((KEY "day") (SIMPLE-VALUE "27"))))))))
(KEY-EQUALS-VALUE
((KEY "expirydate")
(SUB-KEY-EQUALS-VALUE
(((KEY-EQUALS-VALUE ((KEY "year") (SIMPLE-VALUE "1677")))
(KEY-EQUALS-VALUE ((KEY "month") (SIMPLE-VALUE "september")))
(KEY-EQUALS-VALUE ((KEY "day") (SIMPLE-VALUE "27"))))))))
(KEY-EQUALS-VALUE
((KEY "participant")
(LIST-VALUE (((SIMPLE-VALUE "HOL") (SIMPLE-VALUE "FRA")))))))))))
By default the result of my generated parsers is not list structure
but CLOS objects, thus the call to ->list.
-russ
"Liam Clarke" <··········@gmail.com> writes:
> Hi all,
>
>
> I've been attempting to introduce myself to Common Lisp (thanks to
> LispBox) for about three days now, and I'm floundering a wee bit, so
> I'd like to seek your guidance.
>
> First off, just so you know what skill level (if it's actually
> applicable) I'm at, I've been programming for 2 years, 95% of the time
> using Python, 3% using C and the other 2% trying and disliking Java, C#
> etc.
>
> Must say, Lisp is very much a culture shock, I found what I'd learnt in
> Python was easily transferrable to most other Algol descendents, but it
> has been of minimal usage so far with Lisp.
>
> I learn best when I have a specific aim, so I thought I'd recode a
> simple parser I wrote in Python into Lisp, just because Lisp feels like
> it'd make an elegant parse.
>
> The syntax is pretty straightforward, just looking to turn this
>
> alliance = {
> id = { type = 4716 id = 59728 }
> type = dynasticalliance
> startdate = { year = 1652 month = september day = 27 }
> expirydate = { year = 1677 month = september day = 27 }
> participant = { HOL FRA }
> }
>
> into
>
> (alliance
> ((id ((type 4716) (id 59728))
> (type dynasticalliance)
> (startdate ((year 1652) (month september) (day 27)))
> (expirydate ((year 1677) (month september) (day 27)))
> (participant (HOL FRA))))
> But to be honest, I'm not sure on what data structures to use.
Lists. That is, it comes without thinking about it.
;; First, let's read {...} as lists:
[1]> (set-macro-character #\{
(lambda (stream char) (read-delimited-list #\} stream t)))
T
[2]> '{a b c}
}
(A B C})
;; Ok, we've got a problem sincce } is still considered to be part of symbols.
[3]> (set-syntax-from-char #\} #\))
T
[4]> '{a b c}
(A B C)
;; Good. Let's try it:
[5]> (defparameter src '( alliance = {
id = { type = 4716 id = 59728 }
type = dynasticalliance
startdate = { year = 1652 month = september day = 27 }
expirydate = { year = 1677 month = september day = 27 }
participant = { HOL FRA }
}))
SRC
[6]> src
(ALLIANCE =
(ID = (TYPE = 4716 ID = 59728) TYPE = DYNASTICALLIANCE STARTDATE =
(YEAR = 1652 MONTH = SEPTEMBER DAY = 27) EXPIRYDATE =
(YEAR = 1677 MONTH = SEPTEMBER DAY = 27) PARTICIPANT = (HOL FRA)))
;; How about it: we've got a sexpr (lists) and didn't do any parsing!
;; Now, let's transform this sexpr:
[7]> (defun equal-to-lists (src)
(if (atom src)
src
(loop :for (left equal right) :on src
:collect (list left (equal-to-lists right)))))
EQUAL-TO-LISTS
[8]> (equal-to-lists src)
((ALLIANCE
((ID ((TYPE 4716) (= ID) (4716 =) (ID 59728) (= NIL) (59728 NIL))) (= TYPE)
((TYPE = 4716 ID = 59728) =) (TYPE DYNASTICALLIANCE) (= STARTDATE)
(DYNASTICALLIANCE =)
(STARTDATE
((YEAR 1652) (= MONTH) (1652 =) (MONTH SEPTEMBER) (= DAY) (SEPTEMBER =)
(DAY 27) (= NIL) (27 NIL)))
(= EXPIRYDATE) ((YEAR = 1652 MONTH = SEPTEMBER DAY = 27) =)
(EXPIRYDATE
((YEAR 1677) (= MONTH) (1677 =) (MONTH SEPTEMBER) (= DAY) (SEPTEMBER =)
(DAY 27) (= NIL) (27 NIL)))
(= PARTICIPANT) ((YEAR = 1677 MONTH = SEPTEMBER DAY = 27) =)
(PARTICIPANT ((HOL NIL) (FRA NIL))) (= NIL) ((HOL FRA) NIL)))
(= NIL)
((ID = (TYPE = 4716 ID = 59728) TYPE = DYNASTICALLIANCE STARTDATE =
(YEAR = 1652 MONTH = SEPTEMBER DAY = 27) EXPIRYDATE =
(YEAR = 1677 MONTH = SEPTEMBER DAY = 27) PARTICIPANT = (HOL FRA))
NIL))
;; Oops, forgot to skip the processed items:
[9]> (defun equal-to-lists (src)
(if (atom src)
src
(loop :for (left equal right) :on src :by (function cdddr)
:collect (list left (equal-to-lists right)))))
EQUAL-TO-LISTS
[10]> (equal-to-lists src)
((ALLIANCE
((ID ((TYPE 4716) (ID 59728))) (TYPE DYNASTICALLIANCE)
(STARTDATE ((YEAR 1652) (MONTH SEPTEMBER) (DAY 27)))
(EXPIRYDATE ((YEAR 1677) (MONTH SEPTEMBER) (DAY 27)))
(PARTICIPANT ((HOL NIL))))))
;; Good enough, but there's a special case not treated, for the list
;; of participants where there's no =.
;; We'll have to be more explicit in listing the cases:
;; [... after several tries and typoes ...]:
[19]> (defun equal-to-lists (src)
(if (atom src)
src
(loop
:with result = '()
:while src
:do (cond
((consp (first src))
(push (equal-to-lists (first src)) result)
(setf src (cdr src)))
((eq '= (second src))
(push (list (first src) (equal-to-lists (third src))) result)
(setf src (cdddr src)))
(t
(setf result (nconc (reverse src) result)
src nil)))
:finally (return (nreverse result)))))
EQUAL-TO-LISTS
[20]> (equal-to-lists src)
((ALLIANCE
((ID ((TYPE 4716) (ID 59728))) (TYPE DYNASTICALLIANCE)
(STARTDATE ((YEAR 1652) (MONTH SEPTEMBER) (DAY 27)))
(EXPIRYDATE ((YEAR 1677) (MONTH SEPTEMBER) (DAY 27)))
(PARTICIPANT (HOL FRA)))))
[21]>
There's an additionnal enclosing list, since I started by putting
aliance = ... inside a list:
(defparameter src '( alliance = { ... } ))
You can remove it easily with: (first (equal-to-lists src))
--> (ALLIANCE
((ID ((TYPE 4716) (ID 59728))) (TYPE DYNASTICALLIANCE)
(STARTDATE ((YEAR 1652) (MONTH SEPTEMBER) (DAY 27)))
(EXPIRYDATE ((YEAR 1677) (MONTH SEPTEMBER) (DAY 27)))
(PARTICIPANT (HOL FRA))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.
Hi,
funny that this discussion comes up right now. Just last week I was
thinking about the processing of such a list compared to XSL(T)
(Please excuse my mentioning that other hype ;-)
Is there any idiomatic way to acces -say- ALLIANCE/STARTDATE/MONTH
easily?
Not that I really liked fiddling with XPATH but at least it kinda works
for addressing elements in a tree.
This sound pretty much like a DOM-parser to me, but please correct me
if I'm wrong (or otherwise just stupid).
Of course I'd expect a little more from CL ;-)
Regards
Stefan
"Stefan Kamphausen" <······@gmx.de> writes:
> funny that this discussion comes up right now. Just last week I was
> thinking about the processing of such a list compared to XSL(T)
> (Please excuse my mentioning that other hype ;-)
>
> Is there any idiomatic way to acces -say- ALLIANCE/STARTDATE/MONTH
> easily?
It's rather trivial to walk a tree given a path.
[57]> (defun walk (tree path)
(cond
((null path) (values tree t))
((atom tree) (values nil nil))
(t (let ((child (find-if (lambda (child) (eql (car child) (car path)))
tree)))
(if child
(walk (second child) (cdr path))
(values nil nil))))))
WALK
[58]> (equal-to-lists src)
((ALLIANCE
((ID ((TYPE 4716) (ID 59728))) (TYPE DYNASTICALLIANCE)
(STARTDATE ((YEAR 1652) (MONTH SEPTEMBER) (DAY 27)))
(EXPIRYDATE ((YEAR 1677) (MONTH SEPTEMBER) (DAY 27)))
(PARTICIPANT (HOL FRA)))))
[59]> (walk (equal-to-lists src) '(alliance startdate month ))
SEPTEMBER ;
T
[60]>
--
__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.
Pascal Bourguignon <····@mouse-potato.com> wrote:
+---------------
| "Stefan Kamphausen" <······@gmx.de> writes:
| > Is there any idiomatic way to acces -say- ALLIANCE/STARTDATE/MONTH
| > easily?
|
| It's rather trivial to walk a tree given a path.
|
| (defun walk (tree path) ... )
+---------------
Pascal,
Quite coincidentally, today I needed to do a bit of data extraction
from some hardware-design EDIF format files -- which are just single
huge s-exprs of the form (ELEMENT-NAME [OPTIONAL-LABEL] ELEMENTS...) --
and the notion of a PATH argument was just the hint I needed!
Thanks!!
-Rob
p.s. I extended my PATHs to allow both element-names and
lists of (ELEMENT-NAME LABEL), but it was equally trivial to
walk, once the notion of a "path" in the API was suggested.]
p.p.s. Hint: For best results working with EDIFs, do
a (setf (readtable-case *readtable*) :invert) first. ;-}
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Liam Clarke wrote:
>
> Hi all,
>
>
> I've been attempting to introduce myself to Common Lisp (thanks to
> LispBox) for about three days now, and I'm floundering a wee bit, so
> I'd like to seek your guidance.
>
> First off, just so you know what skill level (if it's actually
> applicable) I'm at, I've been programming for 2 years, 95% of the time
> using Python, 3% using C and the other 2% trying and disliking Java, C#
> etc.
>
> Must say, Lisp is very much a culture shock, I found what I'd learnt in
> Python was easily transferrable to most other Algol descendents, but it
> has been of minimal usage so far with Lisp.
>
> I learn best when I have a specific aim, so I thought I'd recode a
> simple parser I wrote in Python into Lisp, just because Lisp feels like
> it'd make an elegant parse.
>
> The syntax is pretty straightforward, just looking to turn this
>
> alliance = {
> id = { type = 4716 id = 59728 }
> type = dynasticalliance
> startdate = { year = 1652 month = september day = 27 }
> expirydate = { year = 1677 month = september day = 27 }
> participant = { HOL FRA }
> }
>
> into
>
> (alliance
> ((id ((type 4716) (id 59728))
> (type dynasticalliance)
> (startdate ((year 1652) (month september) (day 27)))
> (expirydate ((year 1677) (month september) (day 27)))
> (participant (HOL FRA))))
>
>
> But to be honest, I'm not sure on what data structures to use.
>
> In Python I'd simply used a list as a stack, and I'd append new lists
> to it when new groups were opened and pop them when the group closed,
> which if I understand my googled results correctly, is pretty much how
> a context free grammar gets parsed... I know nothing about parsing
> theory.
>
> My first attempt at this used a vector created with
> (make-array 0 :fill-pointer 0 :adjustable t)
>
> as a stack and pushed/popped similar vectors on and off it. However, I
> hamstrung myself with the fact that (last foo) doesn't work for
> vectors, so I ended up using (elt foo (1- (length foo))) which isn't
> overly elegant.
>
> So, at this point, I gave up, as I realised that perhaps attempting to
> reimplement Python in Lisp was missing the point; that it wasn't
> working.
>
> Oh, also, to clarify, a list in Lisp is what I'd call a linked list in
> C, is that correct?
I think so, yes, where every node is a pair.
>
> But yeah, I'd like to get the basics right and use the correct tool for
> the job.
>
> Is there a data structure traditionally used for stack operations? If
> you were attempting to implement the above, what structure would you
> use?
>
> Also, if anyone knows of any simple parsers written in Lisp that I can
> read, please let me know. I've found Franz's HTML parser, but it's a
> bit too big for me to grok at the moment, given my minimal experience.
>
> Thanks in advance,
>
> Liam Clarke
>
> --
Here is a recursive-descent (newbie attempt) version using symbols for input
and output. I have substituted "()" with "[]" in the output since it will
allow me to output a one-level list. It may still have some bugs.
;; Grammar
;;
;; progr -> expr
;; expr -> token '=' token | token '=' group
;; group -> '{' token+ | expr+ '}'
;; token -> TERMINAL
(defconstant +input+
'(alliance = { id = { type = 4716 id = 59728 }
type = dynasticalliance
startdate = { year = 1652 month = september day = 27 }
expirydate = { year = 1677 month = september day = 27 }
participant = { HOL FRA } }))
(defconstant +LPAREN+ '[)
(defconstant +RPAREN+ '])
(defconstant +EQUAL+ '=)
(defconstant +LBRACE+ '{)
(defconstant +RBRACE+ '})
(defparameter *buf* +input+)
(defparameter *out* nil)
(defun read-token () (pop *buf*))
(defun look-ahead () (car *buf*))
(defun push-token (token) (push token *out*))
(defun group ()
(push-token +LPAREN+)
(do ((token (read-token) (read-token)))
((eql token +RBRACE+) nil)
(if (eql (look-ahead) +EQUAL+)
(expr token)
(push-token token))))
(defun expr (token)
(push-token +LPAREN+)
(push-token token)
(let ((token (read-token)))
(if (eql token +EQUAL+)
(let ((token (read-token)))
(if (eql token +LBRACE+)
(group)
(push-token token)))
(error "expected =")))
(push-token +RPAREN+))
(defun progr ()
(setf *buf* +input+)
(expr (read-token))
(pprint (nreverse *out*)))
(progr)
Regards,
John
John wrote:
> Liam Clarke wrote:
[...]
> ... It may still have some bugs.
Yes indeed. For starters,
(push-token +RPAREN+) at end of group.
(defun group ()
(push-token +LPAREN+)
(do ((token (read-token) (read-token)))
((eql token +RBRACE+) (push-token +RPAREN+))
(if (eql (look-ahead) +EQUAL+)
(expr token)
(push-token token))))
Also, the output is not exactly correct.
Could be my grammar is wrong.
[ ALLIANCE
[[ ID [ [ TYPE 4716 ] [ ID 59728 ] ] ]
[ TYPE DYNASTICALLIANCE ]
[ STARTDATE [ [ YEAR 1652 ] [ MONTH SEPTEMBER ] [ DAY 27 ] ] ]
[ EXPIRYDATE [ [ YEAR 1677 ] [ MONTH SEPTEMBER ] [ DAY 27 ] ] ]
[PARTICIPANT [ HOL FRA ] ] ] ]
John wrote:
>
> (defun group ()
> (push-token +LPAREN+)
> (do ((token (read-token) (read-token)))
> ((eql token +RBRACE+) nil)
> (if (eql (look-ahead) +EQUAL+)
> (expr token)
> (push-token token))))
>
--
Hi John,
Thanks for that. Just a question, I'm confused as to what
(token (read-token) (read-token)) does in the above, and where token
comes from. Does it come from expr? What sort of scoping does Lisp use?
Regards,
Liam Clarke
Liam Clarke wrote:
> John wrote:
>
>
> >
> > (defun group ()
> > (push-token +LPAREN+)
> > (do ((token (read-token) (read-token)))
> > ((eql token +RBRACE+) nil)
> > (if (eql (look-ahead) +EQUAL+)
> > (expr token)
> > (push-token token))))
> >
Please disregard my earlier message; 'twas a bit of a dumb question.
I've decided to go back to learning the fundamentals of Lisp before
launching into recursive descent parsers (!). I now know what (token
(read-token) (read-token)) means, (variable initial-value
incr-by-value).
Incidentally, I've found Peter Seibel's Practical Common Lisp to be
invaluable for this.
Liam Clarke <··········@gmail.com> wrote:
+---------------
| I now know what (token (read-token) (read-token)) means,
| (variable initial-value incr-by-value).
+---------------
Small quibble: It's actually (variable initial-value subsequent-values),
since there may be no notion of "incrementing" going on. Or as the CLHS
says it:
(var [init-form [step-form]])
Notice that for DO and DO* a missing step-form simply leaves the
variable unmodified the next time through, as if the "step-form"
were simply "var". [Though it might be modified by explicit assignments
the programmer does in the body.]
[You're probably not ready for this yet, but when you are...]
This should be contrasted with the behaviour of the LOOP macro's
"for-as-equals-then" variant:
(LOOP FOR var = [form1 [THEN form2] ...)
where if "form2" is omitted then the variable "var" still *is* updated
every time through the loop, but by the value of "form1", which is
re-evaluated every time though the loop. That's why the common idiom
for stepping through the lines of a file is this:
(with-open-file (s "filename")
(loop for line = (read-line s nil nil)
while line
do (process-one-line line)))
instead of this:
(with-open-file (s "filename")
(loop for line = (read-line s nil nil) then (read-line s nil nil)
while line
do (process-one-line line)))
whereas using DO would require repeating the call to READ-LINE:
(with-open-file (s "filename")
(do ((line (read-line s nil nil) (read-line s nil nil)))
((null line))
(process-one-line line)))
However, there's even an idiom which shortens that a little, too: ;-}
(with-open-file (s "filename")
(do ((line #1=(read-line s nil nil) #1#))
((null line))
(process-one-line line)))
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607