Parsing strings into LISP syntax
Pascal Saremsky
I have an input string (from a file or whatever) of the form
"fn(x)"
which I would like to assign to a variable as
'(fn x)
Something like:
(setf hello (translate "f(x)"))
1> hello
(F X)
I'm confused by creating symbols from strings, parsing parenthesis that are
in non-lisp syntax using the read or read-line functions, etc.
I have recently bought both Graham Lisp books and Norvig's AI book.
Can anyone point me in the right direction?
Tom Breton
> Hi all,
>
> I have an input string (from a file or whatever) of the form
>
> "fn(x)"
>
> which I would like to assign to a variable as
>
> '(fn x)
>
> Something like:
>
> (setf hello (translate "f(x)"))
>
> 1> hello
> (F X)
I can't give you anything nearly sufficient, but I can tell you what's
going on and why you're having trouble. What you're trying to do is
called "parsing", and there are whole mini-languages devoted to it.
Lisp, for all its virtue, is not very strong in general parsing.
That's because it's so easy to just read Lisp in that one rarely needs
to do general-purpose parsing. Of course it *can* be done in Lisp,
but generally for parsing, one thinks of PCCTS, or lex and yacc, or
flex and bison, none of which are in Lisp.
Of course, you could hack a quick and dirty solution in Lisp. It will
be hard to maintain, but if you're just looking for a one-time, short
term thing, that's one way to go.
--
Tom Breton, http://world.std.com/~tob
Not using "gh" since 1997. http://world.std.com/~tob/ugh-free.html
Rainer Joswig
> Lisp, for all its virtue, is not very strong in general parsing.
This is FUD. Lisp has been used in parsing problems for decades.
Half of the natural language systems have been written in Lisp.
On my Lisp machine I'd just use the parser substrate that
is available and has been used with the C, Pascal and Fortran
compiler from Symbolics. This stuff available since 15 years.
I guess companies and universities have lot's of parsers
written in CL.
Pascal Saremsky
I already have a function defined in lisp, for example:
(defun fn (x)
(* x 3))
Now I want to evaluate a string that was entered at run-time (via file, or
whatever). E.g:
1> (evaluate "fn(5)")
15
Presumably I would have called a function as in the original posting called
(translate "fn (5)") which would have returned (fn 5). It could then use
funcall on the cdr, etc.
So the question is, how do I create dynamically a symbol 'fn which stands
for the function (fn) from the input string "fn"? And, how do I create
dynamically a variable x which evaluates to itself from the input string
"x"?
I've played with intern, gensym, make-symbol, etc. but to no avail, and the
Graham book does not go into great detail about them.
Thanx
Pascal Saremsky wrote in message <80027o$v1$1...@newsmaster.cc.columbia.edu>...
>Hi all,
>
>I have an input string (from a file or whatever) of the form
>
> "fn(x)"
>
>which I would like to assign to a variable as
>
> '(fn x)
>
>Something like:
>
> (setf hello (translate "f(x)"))
>
>1> hello
>(F X)
>
Erik Naggum
| So the question is, how do I create dynamically a symbol 'fn which stands
| for the function (fn) from the input string "fn"?
the function FIND-SYMBOL takes a string a returns a symbol with that name
if it exists and a status keyword that says how the symbols is available
in that package. you can use this to control access only to external
functions in your user-accessible package.
| And, how do I create dynamically a variable x which evaluates to itself
| from the input string "x"?
you use special variables for this, and the symbol lookup is just like
FIND-SYMBOL. if the user shall be able to use new symbols, use INTERN
instead of FIND-SYMBOL.
| I've played with intern, gensym, make-symbol, etc. but to no avail, and
| the Graham book does not go into great detail about them.
INTERN should have given you a valuable lead. perhaps you have been
using a different package inadvertently? if you post your code, however,
helping you becomes significantly easier.
#:Erik
--
Attention Microsoft Shoppers! MS Monopoly Money 6.0 are now worthless.
Tom Breton
> In article <m34sf0q...@world.std.com>, Tom Breton <t...@world.std.com> wrote:
>
> > Lisp, for all its virtue, is not very strong in general parsing.
>
> This is FUD.
Knee-jerk defenders like you give Lisp a bad name. It's a nice
language, not a religion.
I gave him the answer he needed, and if it wasn't as flattering to
Lisp as you would like, too bad.
> Half of the natural language systems have been written in Lisp.
Boy, did you pick the wrong guy to try this particular trick on. I do
NLP, and its focus is almost entirely different than parsing computer
language. No bearing. I've caut you trying to pull the wool over my
eyes.
> On my Lisp machine
I really don't care.
Rainer Joswig
> jos...@lavielle.com (Rainer Joswig) writes:
>
> > In article <m34sf0q...@world.std.com>, Tom Breton <t...@world.std.com> wrote:
Another one for my killfile.
--
Rainer Joswig, ISION Internet AG, Harburger Schlossstrasse 1,
21079 Hamburg, Germany, Tel: +49 40 77175 226
Email: rainer...@ision.de , WWW: http://www.ision.de/
Pascal Saremsky
This is the example:
Let's say I wanted to 'compile' the following string into lisp:
(compile-from-c "int times3(x) { return x*3; }")
so that I can now use
1> (times3 5)
15
Clearly I need something to take the string "times3" and generate the symbol
TIMES3 from it. Intern or find-symbol alone doesn't seem to help me; the
following example doesn't work:
(defun (intern "TIMES3") (x) ;; Wrong!
(* x 3))
Perhaps I should use macros?
I'm doing everything in the same package.
I get the feeling I'm missing the essence of lisp here!
-Pascal
Erik Naggum wrote in message <31509030...@naggum.no>...
Rainer Joswig
> Clearly I need something to take the string "times3" and generate the symbol
> TIMES3 from it.
(intern "TIMES3") works.
>Intern or find-symbol alone doesn't seem to help me; the
> following example doesn't work:
>
> (defun (intern "TIMES3") (x) ;; Wrong!
> (* x 3))
DEFUN doesn't evaluate the function name part.
Something like this will work:
(setf (symbol-function (intern "TIMES3"))
(lambda (x) (* x 3)))
Pascal Saremsky
itself, then I could use symbol-value instead:
(setf (symbol-value (intern "F")) (intern "F"))
1> F
F
Because the second intern returns an instance of the same symbol. Please
correct me if I'm wrong, otherwise this works fine for me!
I'll figure out the package complications later on...
Thanks Erik and Rainer.
-Pascal
Rainer Joswig wrote in message ...
Erik Naggum
| I get the feeling I'm missing the essence of lisp here!
well, just that INTERN is called by the Lisp reader when it sees a string
of characters that doesn't match anything else. so when you write
(defun times3 (x) (* x 3))
the Lisp reader has already interned the symbol for you, and (find-symbol
"TIMES3") will return the symbol.
at this point, we're getting too close for comfort to the Lisp reader's
character case conversion algorithm, and you are well advised not to try
to out-do it. for legacy reasons (a.k.a. "hysterical raisins"), the Lisp
reader upcases; it could have downcased, it could have retained case; it
upcases, but you don't have to do that. when you read that symbol as a
string of characters, just call FIND-SYMBOL (or INTERN) on it directly,
and the right symbol is returned.
however, to get a symbol in Lisp with the same name, you must cause the
Lisp reader to see the exact name, too. this essentially means that you
have to cause INTERN not to do case conversion. using a very powerful
Lisp reader mechanism, the read-time evaluator, you could do
(defun #.(intern "times3") (x) (* x 3))
but we have special syntax for this common phenomenon:
(defun |times3| (x) (* x 3))
you can actually cause the Lisp reader not to do case conversion, and
this may be preferable in your own code. see the function READTABLE-CASE
for the whole story. however, if you set up a case sensitive readtable
for your Lisp code, remember that Common Lisp upcases, and you need to
type in uppercase, too:
(DEFUN times3 (x) (* x 3))
the aesthetics of this approach is, however, generally disputed.
Erik Naggum
| Because the second intern returns an instance of the same symbol. Please
| correct me if I'm wrong, otherwise this works fine for me!
almost correct: INTERN returns the exact same value every timeน. the
whole point with INTERN is precisely that: to return _the_ symbol that
has the name given by the argument, so if the two strings are EQUAL (that
is, STRING=), then the symbols returned will be EQ. you may have gotten
this point, already, but your wording left an ambiguity -- symbols don't
have instances, they _are_ instances.
#:Erik, persnicketeer
-------
น barring intervening UNINTERN calls or changes to *PACKAGE*.
Alex Henderson
>
> "fn(x)"
>
> which I would like to assign to a variable as
>
> '(fn x)
Since the f(g(x)) form of syntax merely puts the function name just
outside a set of parentheses (as opposed to just inside) I think this
simple case can be coped with in the following naive manner, by pushing
such atoms inside any following lists:
----
(defun read-as-list (string)
(do* ((stream (make-string-input-stream string))
(list (list #1=(read stream nil)) (push #1# list)))
((not (listen stream)) (reverse list))))
(defun functionise (list)
(let ((copy (copy-tree list)))
(rfunctionise copy)))
(defun rfunctionise (list)
(do ((sublist list (cdr sublist)))
((endp sublist) list)
(when (consp (cadr sublist))
(rfunctionise (cadr sublist))
(when (atom (car sublist))
(setf (car sublist) (push (car sublist) (cadr sublist))
(cdr sublist) (cddr sublist))))))
(defun read-function-form (string)
(rfunctionise (read-as-list string)))
----
'read-function-form' produces a list of the function forms in the string
given (and will include a final NIL if the string terminates with whitespace).
However, I suspect this is possibly a little more elementary than what
you're looking for. If what you really want is to build your own parser
for algebraic functions expressed as text, then there are, it seems to
me, two main options: 1) write your own parsing functions, or 2) use
common lisp's inbuilt reading framework, writing your own readtable and
shadowing *readtable* while reading.
The former can be less messy for simpler syntaxes, the latter much more
powerful, and undoubtedly the Right Way. The first third or thereabouts
of chapter 22 of Steele give some indication of the mess you are likely
to enounter with option 2...
HTH, HAND.
A
PS: Actually, option 3 is to look for someone else who's already done it
- it's likely to be out there somewhere, since it'd be useful enough.
--====----====----====----====----====----====----====----====--
K(-B-E-A)K8,1:C//cc/DE/F24,'GfGAB^/b'b(EG)b(FA)b(EG)=b(DF)c(E)/^
Rainer Joswig
> I see. And so if I also wanted to create a symbol which evaluates to
> itself, then I could use symbol-value instead:
>
> (setf (symbol-value (intern "F")) (intern "F"))
See also the function SET .
This is btw. a property of keywords (symbols in the keyword package):
they are symbols that evaluate to themselves.
>
> 1> F
> F
>
> Because the second intern returns an instance of the same symbol.
The difference between strings and interned symbols is that you get
the *same* object with symbols. So there is only one
instance of a symbol with a certain name - once they are interned.
(eq 'f 'f) -> T
(eq "f" "f") -> NIL
To puzzle you a bit more:
if you don't intern symbols (put them in a package) they
won't be eq, too.
(eq (make-symbol "F") (make-symbol "F")) -> NIL
(eq '#:F '#:F) -> NIL
Andrew Cooke
"Pascal Saremsky" <ps...@columbia.edu> wrote:
> I have an input string (from a file or whatever) of the form
>
> "fn(x)"
>
> which I would like to assign to a variable as
If you do want to use a parser, then email me for details about Zebu (a
yacc kind of thing written in Lisp) - I'm not connected with the package
in any way, but have version 3.5.5 which is the latest version I could
find (and a lot more up-to-date than the CMU archive). It's quite cute
and easy to use (if you've used this kind of thing before - if not, then
there would be a pretty steep learning curve).
Andrew
http://www.andrewcooke.free-online.co.uk
PS Incidentally, Zebu no onger seems to be supported. If anyone knows
otherwse, or would like to support it, please contact me - otherwise I
may stick a version with my mods on my web site early next year and act
as some kind of interim source/maintainer (I would really recommend
someone else doing this as I know very little about Lisp! :-).
Sent via Deja.com http://www.deja.com/
Before you buy.
see.signature
<and...@andrewcooke.free-online.co.uk> wrote:
>If you do want to use a parser, then email me for details about Zebu (a
>yacc kind of thing written in Lisp) - I'm not connected with the package
>in any way, but have version 3.5.5 which is the latest version I could
>find (and a lot more up-to-date than the CMU archive). It's quite cute
>and easy to use (if you've used this kind of thing before - if not, then
>there would be a pretty steep learning curve).
>
zebu 3.5.5 is availiable at cmu, but its quite difficult to find:
ftp://ftp.cs.cmu.edu/user/ai/new/zebu-3.5.5.tgz
Marc
--
------------------------------------------------------------------------------
email: marc dot hoffmann at users dot whh dot wau dot nl
------------------------------------------------------------------------------
Tim Bradshaw
> Lisp, for all its virtue, is not very strong in general parsing.
> That's because it's so easy to just read Lisp in that one rarely needs
> to do general-purpose parsing. Of course it *can* be done in Lisp,
> but generally for parsing, one thinks of PCCTS, or lex and yacc, or
> flex and bison, none of which are in Lisp.
> Of course, you could hack a quick and dirty solution in Lisp. It will
> be hard to maintain, but if you're just looking for a one-time, short
> term thing, that's one way to go.
Alternatively, for the purpose of the original poster, just use one of
the several `infix readers' for Lisp, which generally do this kind of
thing pretty painlessly.
--tim
Gavin E. Gleason
> Boy, did you pick the wrong guy to try this particular trick on. I do
> NLP, and its focus is almost entirely different than parsing computer
> language. No bearing. I've caut you trying to pull the wool over my
> eyes.
You would have to be a severe moron not to be able to parse natural
language, its SPACE delimited!!!!
As for organizing the words into meaningful structures I cant imagine
what possible structure you are using that lisp would not allow you to
make...
Only an idiot would try to do NLP with regexp. So what is it that is
lacking in CL? I have a strange feeling that you cant code lisp well
enough to make any kind of meaningful statement.
Gavin E. Mendel-Gleason
--
"Syntactic sugar causes cancer of the semicolon."
-Alan Perlis
edward konig
Viewing the contents of the unzipped items, they seem to be garbage..
Thanks,
Ed K
see.signature <any...@No-Such-Domain.anywhere> wrote in message
news:slrn82av6f...@Flex111.dNWL.WAU.NL...
see.signature
<kon...@worldnet.att.net> wrote:
[about unpacking zebu]
>Any guidance on obtaining/installing this under Win98?
>
>Viewing the contents of the unzipped items, they seem to be garbage..
>
use gzip at first:
gzip -d zebu....tgz => zebu...tar
then use tar xf zebu...tar > gives you the installation in ./zebu-3.5.5
Marc
--
------------------------------------------------------------------------------
Sam Steingold
>>>> On the subject of "Parsing strings into LISP syntax"
>>>> Sent on Fri, 5 Nov 1999 19:33:14 -0500
>>>> Honorable "Pascal Saremsky" <ps...@columbia.edu> writes:
>>
>> Something like:
>>
>> (setf hello (translate "f(x)"))
>>
>> 1> hello
>> (F X)
I hope this is not homework.
(defun translate (string)
(multiple-value-bind (symbol pos) (read-from-string string)
(cons symbol
(read-from-string (substitute #\Space #\, string) nil nil
:start pos))))
--
Sam Steingold (http://www.podval.org/~sds/)
Micros**t is not the answer. Micros**t is a question, and the answer is Linux,
(http://www.linux.org) the choice of the GNU (http://www.gnu.org) generation.
Never underestimate the power of stupid people in large groups.
Roger Corman
>"Pascal Saremsky" <ps...@columbia.edu> writes:
>
>> Hi all,
>>
>> I have an input string (from a file or whatever) of the form
>>
>> "fn(x)"
>>
>> which I would like to assign to a variable as
>>
>> '(fn x)
>>
>> Something like:
>>
>> (setf hello (translate "f(x)"))
>>
>> 1> hello
>> (F X)
>
>I can't give you anything nearly sufficient, but I can tell you what's
>going on and why you're having trouble. What you're trying to do is
>called "parsing", and there are whole mini-languages devoted to it.
>
>Lisp, for all its virtue, is not very strong in general parsing.
I have written many parsers in several different languages, including
C, C++, Java and Common Lisp. Given a choice, I would choose Common
Lisp any day over the other three languages I mentioned. It is very
easy to write a parser which is easy to modify and maintain. I think
the reason lisp wins big here is that you generally want the output of
a parser to be a parse tree of heterogenous data types. Lisp supports
this structure implicitly, and so manipulating the resulting parse
tree is simple and elegant. If you use Bison or something like that
you have to build your own output data types, and they aren't as
likely to be as easy to work with.
I won't try to say lisp is better than any special purpose parser
language, but I don't think it is fair to give the impression that
lisp is weak in this area.
Roger Corman
Arseny Slobodjuck
<ps...@columbia.edu> wrote:
>I have an input string (from a file or whatever) of the form
>
> "fn(x)"
>
>which I would like to assign to a variable as
>
> '(fn x)
>
>Something like:
>
> (setf hello (translate "f(x)"))
>
>1> hello
>(F X)
>
>I'm confused by creating symbols from strings, parsing parenthesis that are
>in non-lisp syntax using the read or read-line functions, etc.
judje me, people :
-------------------- 8< ------ cut here --------------
; 11.11.99
;pascal expression to lisp convertor
;originally wroten by Arseny Slobodjuck
;syntax based on Lewis book
;"Theoretical base of compilator creating"
;(something like this, i don't remember precizely
;and besides read in translation)
;principle of algorithm :
;First, define some of lex analyzer functions
;which can read base set of lexems or
;query input stream about type of current lexem
;Then can be defined rules-functions
;each of this must read input stream for one rule
;of language and perform according tasks
;(for this example it is output lisp code).
;In that example functions usually
;return simply string, containing translation
;of those part of input stream which belongs
;to current rule. Not so with get-pc and get-tc.
;For better output they accumulate translation
;of additional arguments for base arithmetic
;operators each in two lists - get-pc in
;(cons list-of-multipliers list-of-dividers)
;and get-tc does analogically with
;args for + and -. If get-pc or get-tc
;expands to none, it returns (cons nil nil).
;Absolutely all of get-?? functions return nil
;if input stream does not correspond the
;grammatic.
;below is the grammatic
;<E> :== <T><Tc>
;<Tc> :== +<T><Tc>
;<Tc> :== <nil>
;<T> :== <P><Pc>
;<Pc> :== *<P><Pc>
;<Pc> :== <nil>
;<P> :== (<E>)
;<P> :== v<F>
;<F> :== (L)
;<F> :== <nil>
;<L> :== <E><Lc>
;<L> :== <nil>
;<Lc> :== ,<E><Lc>
;<Lc> :== <nil>
;function itself
(defun p2l(p)
(let ((cp 0) (lp "(") (rp ")"))
(labels
(
(see-char () (and (>= cp 0) (< cp (length p)) (char p cp)))
(nxt-char () (let ((c (see-char))) (when c (setq cp (+ cp 1)))
c))
(nxt-smart () (let ((c (nxt-char))) (skip-white) c))
(skip-white () (loop
(when (not (eql (see-char) #\Space)) (return-from skip-white
(see-char)))
(nxt-char)))
(smartcat (sl) (unless (some #'(lambda (x) (not x)) sl) (apply
(function concatenate) (quote string) sl)))
(spacecat (sl) (if sl (concatenate 'string (car sl) (if (cdr sl) "
" "") (spacecat (rest sl))) ""))
(somecharp (ch) (when (eq (see-char) ch) t))
(plusminusp () (or (somecharp #\+) (somecharp #\-)))
(muldivp () (or (somecharp #\/) (somecharp #\*)))
(openbrp () (somecharp #\())
(closebrp () (somecharp #\)))
(commap () (somecharp #\,))
(zsymbolp () (when (and (see-char) (char<= #\a (see-char) #\z))
t))
(get-v () (let (vo)
(loop while (zsymbolp) do
(setq vo (if vo (concatenate 'string vo (string (nxt-char)))
(string (nxt-char))))) (skip-white) vo))
(get-t () (let (po pco rv)
(and
(setq po (get-p))
(setq pco (get-pc)) ;pc returns (cons l* l/)
;if expression continues with
;*/<p>
;l* contains list of *terms
;l/ accordingly /terms
;or (cons nil nil)
;if <pc>:==-| (empty)
;or nil on parse error
(setq rv
(if (car pco)
(smartcat (list lp "* " po " " (spacecat (car
pco)) rp ))
po))
(if (cdr pco)
(smartcat (list lp "/ " rv " "
(spacecat (cdr pco))
rp))
rv))))
(get-tc () (let (to tco zsign)
(if (plusminusp)
(and
(setq zsign (nxt-smart))
(setq to (get-t))
(setq tco (get-tc))
(if (eql zsign #\+)
(cons (concatenate 'list (list to) (car tco)) (cdr tco))
(cons (car tco) (concatenate 'list (list to) (cdr
tco))))
)
(cons nil nil))))
(get-p () (let (eo vo fo)
(cond
((openbrp) (and (nxt-smart) (setq eo (get-e)) (closebrp)
(nxt-smart) eo))
((zsymbolp) (and (setq vo (get-v)) (setq fo (get-f))
(if (car fo);fo is a paramlist
(smartcat (list lp vo " " (cdr fo) rp))
vo)))
(t nil))));p have no right to be empty
(get-pc () (let (zsign po pco)
(cond
((muldivp) (and (setq zsign (nxt-smart))
(setq po (get-p))
(setq pco (get-pc))
(if (eql zsign #\*)
(cons (concatenate 'list (list po) (car pco))
(cdr pco))
(cons (car pco) (concatenate 'list (list po) (cdr
pco))))))
(t (cons nil nil)))))
(get-f () (let (lo)
(cond ((openbrp);f is a paramlist
(and (nxt-smart) (setq lo (get-l)) (closebrp) (nxt-smart)
(cons t lo)))
(t (cons nil "")))))
(get-l () (let (eo lco)
(cond ((closebrp) "")
(t (and (setq eo (get-e)) (setq lco (get-lc))
(smartcat (list eo lco)))))))
(get-lc () (let (eo lco)
(cond ((commap) (and (nxt-smart) (setq eo (get-e)) (setq
lco (get-lc))
(smartcat (list " " eo lco))))
((closebrp) "")
(t nil))))
(get-e () (let (to tco rv)
(and (setq to (get-t)) (setq tco (get-tc))
(setq rv
(if (car tco)
(smartcat (list lp "+ " to " " (spacecat (car tco)) rp
))
to))
(if (cdr tco)
(smartcat (list lp "- " rv " "
(spacecat (cdr tco))
rp))
rv))))
);labels def
(skip-white)
(get-e)
);labels
);let
);p2l
;out formatter
(defun show-p2l (s)
(format t "~S ==>~%~S~%" s (p2l s)))
;test
(show-p2l "b+a-c(x,y,z*y)*d(y)")
-------------------- 8< ------ cut here --------------
Christopher Browne
wrote:
>I have written many parsers in several different languages, including
>C, C++, Java and Common Lisp. Given a choice, I would choose Common
>Lisp any day over the other three languages I mentioned. It is very
>easy to write a parser which is easy to modify and maintain. I think
>the reason lisp wins big here is that you generally want the output of
>a parser to be a parse tree of heterogenous data types. Lisp supports
>this structure implicitly, and so manipulating the resulting parse
>tree is simple and elegant. If you use Bison or something like that
>you have to build your own output data types, and they aren't as
>likely to be as easy to work with.
>
>I won't try to say lisp is better than any special purpose parser
>language, but I don't think it is fair to give the impression that
>lisp is weak in this area.
Common Lisp has considerable power in parsing; the problem is that
when people start thinking about parsing, they tend to consider a
LEX/YACC-based parsing "architecture," with EBNF and the like.
Lisp-based parsing systems tend to Not Work That Way, and so a giant
disconnect immediately takes place.
--
Rules of the Evil Overlord #68. "I will not strike a bargain with a
demonic being then attempt to double-cross it simply because I feel
like being contrary."
<http://www.eviloverlord.com/lists/overlord.html>
cbbr...@hex.net- <http://www.hex.net/~cbbrowne/langlisp.html>