From: ··········@gmail.com
Subject: writing a arithmetic parser?
Date: 
Message-ID: <1113706306.453690.86120@g14g2000cwa.googlegroups.com>
hi, anyone know of a simple working arithmetic parser that i can see
exactly how it's done? i wrote one in Java, but, i find it hard
translating to lisp.. mmm.. to clearify what i mean by arithmetic
parser, i want to be able to parse math equations such as (3+4)*5, by
doing them in the right order.. it sounds pretty simple, i want to see
how lisp compares to java.. thanks alot :D
From: Kenny Tilton
Subject: Re: writing a arithmetic parser?
Date: 
Message-ID: <a5l8e.7215$n93.5442@twister.nyc.rr.com>
··········@gmail.com wrote:

> hi, anyone know of a simple working arithmetic parser that i can see
> exactly how it's done? i wrote one in Java, but, i find it hard
> translating to lisp.. mmm.. to clearify what i mean by arithmetic
> parser, i want to be able to parse math equations such as (3+4)*5, by
> doing them in the right order.. it sounds pretty simple, i want to see
> how lisp compares to java.. thanks alot :D
> 

Yikes. You wrote one in Java but cannot write one in Lisp? I do not 
believe you. Lisp is a superset of Java, so your report is impossible. 
Instead of posting huge vague questions, just write the damn Lisp and 
whatever does not work, post it here and ask a sensible question.

This looks like a fancy way to get your homework done. Even if you did 
not have an imaginary Java version working, i would still wonder what 
the problem was, but the report would be plausible because you might 
just be a newbie to programming overall, or recursion or parsing. But 
you say "i wrote one in java....". pwuawhahahah.

Tell you what. Forget the arithmetic. You say "I find it hard 
translating to lisp". Got an example? (Answer: no.)

kenny

-- 
Cells? Cello? Cells-Gtk?: http://www.common-lisp.net/project/cells/
Why Lisp? http://lisp.tech.coop/RtL%20Highlight%20Film

"Doctor, I wrestled with reality for forty years, and I am happy to 
state that I finally won out over it." -- Elwood P. Dowd
From: ··········@gmail.com
Subject: Re: writing a arithmetic parser?
Date: 
Message-ID: <1113751773.429105.188250@g14g2000cwa.googlegroups.com>
well, no, i admit i don't know enough about lisp to write much stuff
that's useful.. since i did the parser for Java for my AP practice, i
thought i'd do it in lisp and see how they compare.. i do have the java
version working, i can send it via e-mail or post it somewhere if you
wish to see :D mmm.. now i found out my lisp skills is wayyy too bad..
so i'll dive into some more materials and post when i'm done (or have
questions :D)..

and oh yah, this is not an excuse to not do my homework, since i don't
learn lisp in school or anything, we learn java, that's why i wrote it
in  Java first, i got a AP exam coming up real soon :|

mmm.. what i did with my java version is that i wrote a
ExpressionTokenizer that takes in a String (expression).. and it has
two methods, peekToken() and nextToken(), it goes one character at a
time, if it meets a number next, it'll continue go on until it reaches
a sign..

second class is Evaluator.. i have getFactorValue(), getTermValue(),
getExpressionValue().. since this is a practice in mutual recursion..
we can divide a expression to several parts, if we meet a "()" in the
expression, it calles getExpressionValue again for the stuff inside
().. then the termvalue method handles the * / side of the expression
and + - is handled by factorvalue.. that's basically the gist of what
i'm doing. i'll post the .java file up (with a simple GUI based
calculator..) on my site later today :D
From: ··········@gmail.com
Subject: Re: writing a arithmetic parser?
Date: 
Message-ID: <1113753103.522855.5940@z14g2000cwz.googlegroups.com>
http://programer.name/calculator.zip

here is the .java files :D i'll figure out more on lisp later today :D
From: Pascal Bourguignon
Subject: Re: writing a arithmetic parser?
Date: 
Message-ID: <878y3h756a.fsf@thalassa.informatimago.com>
··········@gmail.com writes:

> http://programer.name/calculator.zip
> 
> here is the .java files :D i'll figure out more on lisp later today :D

Of course, you should see the infix package, but here is a quick-and-dirty
example:



;;; expr : term { [+|-] expr } .
;;; term : fact { [*|/] term } .
;;; fact : neg { ^ fact } .
;;; neg  : simp | - simp .
;;; simp : ident | number | ( expr ) .


(defun parse-simp (simp)
  "
DO:         Parses a simple expression:
            simp ::= number | symbol | ( expr ) .
RETURN:     A parse tree or :ERROR ; a cdr of simp.
"
  (cond
   ((numberp (car simp)) (values (car simp) (cdr simp)))
   ((symbolp (car simp)) (values (car simp) (cdr simp)))
   ((listp (car simp))
    (multiple-value-bind (expr rest) (parse-expr (car simp))
      (when rest (error "INVALID TOKENS IN SUB-EXPRESSION ~S." rest))
      (values expr (cdr simp))))
   (t (error "INVALID TOKEN IN EXPRESSION ~S." (car simp)))))


(defun parse-neg (neg)
  "
DO:         Parses a simple logical expression:
            neg ::= simp | - simp .
RETURN:     A parse tree or :ERROR ; a cdr of expr.
"
  (cond
   ((eq (car neg) '|-|)
    (multiple-value-bind (expr rest) (parse-simp (cdr neg))
      (if (eq :error expr)
        (values expr rest)
        (values (list '|-| expr) rest))))
   (t (parse-simp neg))))


(defmacro make-parse-level (name operators next)
  "
DO:         Generate a function named PARSE-{name} that parses the
            following rule:  name ::= name { operators next } .
            That functions will return a parse tree or :ERROR ; a cdr of expr.
"
  (let ((parse-level-name (intern (format nil "PARSE-~A" name)))
        (parse-next-name  (intern (format nil "PARSE-~A" next))))
    `(defun ,parse-level-name (expr)
       (let ((result))
         (multiple-value-bind (term rest) (,parse-next-name expr)
           (setq result term expr rest))
         (do () ((or (eq :error result)
                     (null expr)
                     (not (member (car expr) ',operators
                                  :test (function eq)))))
           (multiple-value-bind (term rest) (,parse-next-name (cdr expr))
             (if (eq :error term)
               (setq result :error)
               (setq result (list (car expr) result term)
                     expr   rest))))
         (values result expr)))))


(defmacro make-parse-unary (name operators next)
  "
DO:         Generate a function named PARSE-{name} that parses the
            following rule:  name ::= next | operators next .
            That functions will return a parse tree or :ERROR ; a cdr of expr.
"
  (let ((parse-level-name (intern (format nil "PARSE-~A" name)))
        (parse-next-name  (intern (format nil "PARSE-~A" next))))
    `(defun ,parse-level-name (expr)
       (let ((result))
         (if (member (car expr) ',operators :test (function eq))
           (multiple-value-bind (next rest) (,parse-next-name (cdr expr))
             (if (eq :error next)
               (values next rest)
               (values (list (car expr) next) rest)))
           (,parse-next-name  expr))))))


(make-parse-unary unary (sin cos atan -) simp)
(make-parse-level fact  (^)              unary)
(make-parse-level term  (* / mod)        fact)
(make-parse-level expr  (+ -)            term)
(make-parse-level comp  (< <= > >= = /=) expr)


(print (parse-comp '( a + 2 * ( - x ^ -(3 * pi / 2) - c + d / e ) < 0 )))
;; (< (+ A (* 2 (+ (- (^ (- X) (- (/ (* 3 PI) 2))) C) (/ D E)))) 0) 


(print (parse-comp '( sin x ^ 2 + cos x ^ 2 = 1)))
;; (= (+ (^ (SIN X) 2) (^ (COS X) 2)) 1)


(print (parse-comp '( sin(x) ^ 2 + cos(x) ^ 2 = 1)))
;; (= (+ (^ (SIN X) 2) (^ (COS X) 2)) 1) 



-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.
From: Karl A. Krueger
Subject: Re: writing a arithmetic parser?
Date: 
Message-ID: <d3soqj$5u2$1@baldur.whoi.edu>
··········@gmail.com wrote:
> hi, anyone know of a simple working arithmetic parser that i can see
> exactly how it's done? i wrote one in Java, but, i find it hard
> translating to lisp.. mmm.. to clearify what i mean by arithmetic
> parser, i want to be able to parse math equations such as (3+4)*5, by
> doing them in the right order.. it sounds pretty simple, i want to see
> how lisp compares to java.. thanks alot :D

There's a package called CL-INFIX which is just this -- a parser for
infix expressions.  It defines a reader-macro #I() that lets you use
infix code within a Lisp program:

#I(2 + 3 * 4)		-> 	14
'#I(2 + 3 * 4)		->	(+ 2 (* 3 4))

It is not limited to arithmetic, giving infix forms for array reference,
logic operations, and conditionals as well.

-- 
Karl A. Krueger <········@example.edu> { s/example/whoi/ }
From: William Bland
Subject: Re: writing a arithmetic parser?
Date: 
Message-ID: <pan.2005.04.17.17.17.20.559706@abstractnonsense.com>
On Sat, 16 Apr 2005 19:51:46 -0700, randomtalk wrote:

> hi, anyone know of a simple working arithmetic parser that i can see
> exactly how it's done? i wrote one in Java, but, i find it hard
> translating to lisp.. mmm.. to clearify what i mean by arithmetic
> parser, i want to be able to parse math equations such as (3+4)*5, by
> doing them in the right order.. it sounds pretty simple, i want to see
> how lisp compares to java.. thanks alot :D


http://abstractnonsense.com/convert.lisp.html

I wrote it a few months ago, when I needed an infix->RPN converter.  It
works by converting from infix to prefix, and then to RPN (so it does what
you want and then a little more).

It's just under 70 lines of code, so should be pretty easy to understand.

Hope that helps.
Cheers,
	Bill.
From: ··········@gmail.com
Subject: Re: writing a arithmetic parser?
Date: 
Message-ID: <1113779141.477810.270860@l41g2000cwc.googlegroups.com>
mmm.. apparently the cl-infix is not free (arguably not open source..)?
mmm.. since i did a google search, it says the infix package is under
non-free tree in debian :|.. i'll try the two pieces of code now :D
From: Karl A. Krueger
Subject: Re: writing a arithmetic parser?
Date: 
Message-ID: <d3vjh8$59q$1@baldur.whoi.edu>
··········@gmail.com wrote:
> mmm.. apparently the cl-infix is not free (arguably not open source..)?
> mmm.. since i did a google search, it says the infix package is under
> non-free tree in debian :|.. i'll try the two pieces of code now :D

CL-INFIX is distributed under a license that allows redistribution and
modification, but does not allow you to charge money for it:

;;; Copyright (c) 1993 by Mark Kantrowitz. All rights reserved.
;;;
;;; Use and copying of this software and preparation of derivative works
;;; based upon this software are permitted, so long as the following
;;; conditions are met:
;;;      o no fees or compensation are charged for use, copies, 
;;;        distribution or access to this software
;;;      o this copyright notice is included intact.
;;; This software is made available AS IS, and no warranty is made about
;;; the software or its performance.

Probably not a big deal for a casual or experimental project, but it
could be a pain for someone looking to make a collection of the world's
coolest Common Lisp packages ... or looking to use CL-INFIX in a project
with a goal of either proprietary *or* open source distribution.

For instance, these license terms would forbid someone from selling
CD-ROMs that contained CL-INFIX along with other software.  Even if the
presence of CL-INFIX were not the selling point of the CD-ROM, charging
money for the CD would still be a copyright infringement.

If Debian included CL-INFIX in their "main" distribution (which goes on
the install CD images) then nobody could sell Debian CDs without
violating the copyright on CL-INFIX.  Debian wants people to be able to
sell Debian CDs legally -- so they place packages such as this in
"non-free" which doesn't go on the CDs.

If you're concerned, you might be able to contact the author of CL-INFIX
and ask if it could be relicensed under a Free Software / Open source
license, such as the GPL, BSD, or LLGPL licenses.

-- 
Karl A. Krueger <········@example.edu> { s/example/whoi/ }
From: Mark Tarver
Subject: Re: writing a arithmetic parser?
Date: 
Message-ID: <1113983267.142833.160390@l41g2000cwc.googlegroups.com>
You may want to look at Qi which
generates good Lisp from pattern-directed
definitions.  It also has an inbuilt
compiler-compiler Qi YACC.  See
www.lambdassociates.org for
details and
www.lambdassociates.org/qilisp.htm
for the 15 minute introduction
for Lisp programmers.

There is also a large YACC for Lisp
- CL YACC available from
http://www.pps.jussieu.fr/~jch/software/cl-yacc/
for parsing work.

A lot depends here on what you
want to do with your arithmetic
reader and whether the input
is fully parenthesised or not.

Here is a simple recognisor in Qi.

(define arith?
   [X + Y] -> (and (arith? X) (arith? Y))
   [X * Y] -> (and (arith? X) (arith? Y))
   [X / Y] -> (and (arith? X) (arith? Y))
   [X - Y] -> (and (arith? X) (arith? Y))
   X -> (number? X))

or shorter.

(define arith?
   [X Op Y] -> (and (arith? X) (arith? Y))	where (element? Op [* / -
+])
   X -> (number? X))

Qi generates Lisp code from this code

(DEFUN arith? (V49)
 (COND
  ((AND (CONSP V49) (CONSP (CDR V49)) (CONSP (CDR (CDR V49)))
    (NULL (CDR (CDR (CDR V49))))
    (qi::wrapper
     (element? (CAR (CDR V49)) (CONS '* (CONS '/ (CONS '- (CONS '+
NIL)))))))
   (THE SYMBOL (and (arith? (CAR V49)) (arith? (CAR (CDR (CDR
V49)))))))
  (T (THE SYMBOL (number? V49)))))

More complex examples would use character
streams and deal with non-fully parenthesised
expressions.

See the online text Functional Programming in Qi
for a type checked version of this kind of program
(chapter 11).

hope this helps

Mark
comp.lang.lisp / 2005 / apr