Hello
Did anyone have a program to translate mathematics-expressions in INFIX
expressions (like LISP expressions)
for example:
(2*x+5-6) ----> (- (+ (* 2 x) 5) 6)
Thank you
"Runser Jean-Claude" <··················@wanadoo.fr> writes:
> Did anyone have a program to translate mathematics-expressions in INFIX
> expressions (like LISP expressions)
>
> for example:
>
> (2*x+5-6) ----> (- (+ (* 2 x) 5) 6)
Math expressions ARE in "infix" notation. Lisp notation is sometimes,
by slight abuse of terminology, called "prefix" because the operator
precedes rather than intermingles. (For various nitpicky reasons, I
think this classification isn't "scientific", though it is often
practical and I don't usually fight it.)
For those who are not familiar, the following are some examples of
various operator relationships:
sine x prefix notation for "sine"
a+b infix notation (may or may not permit `nary')
x! postfix notation for "!" (factorial)
|x| matchfix notation for "|"..."|" (absolute value)
temperature nofix notation for "temperature"
(a function call masquerades as variable;
often, a variable that REALLY varies)
The above "operator" uses contrast with conventional function calling
such as f(a,b,c,...). Lisp, I would argue, is just a variation of
function calling notation, as (f a b c...) and is not rightly an operator
notation at all becuase it never gets into issues of operator precedence
as a prefix notation like prefix
sin cos x y
would. In Lisp, since one always says
(sin (cos (* x y)))
or
(sin (* (cos x) y))
just as in functional notation one would always say
sin(cos(times(x,y)))
or
sin(times(cos(x),y))
there wouldn't ever be an ambiguity.
Not that any of this has to do with the translation process. I just
wanted to throw out some terminology I like since it's consistent with
parsers I grew up with, and since it nofix and matchfix seem to be terms
people haven't ever seen even though they commonly use these operators.
The above is stuff I recall having come from parsers I call "Pratt"
Parsers (for Vaughan Pratt). My recollection is that they are described
in the following paper:
"A formalization and correctness proof of the CGOL Language System",
Van de Vanter, M.L., MIT/LCS/TR-147, 1975. (99 pages)
I think you might be able to order this paper from
http://reading-room-www.lcs.mit.edu/rr/catalog/catalog.html.
Here's its abstract:
In many important ways the design and implementation of
programming languages are hindered rather than helped by BNF.
We present an alternative meta-language based on the work of
Pratt which retains much of the effective power of BNF but is
more convenient for the designer, implementor and user alike.
Its amenability to formal treatment is demonstrated by a
rigorous correctness proof of a simple implementation.
I don't know of a public implementation of this althought I've
seen many private implementations and find them dreadfully
convenient to use.
I'm sure someone will tell you about YACC-like things and why they
are superior. But I think YACC is one of the yuckiest things to
hit parserland ever. Not because it doesn't work--but because of
the awful way it constrains the way people think about parsers.
Just my opinion.
Kent M Pitman <······@world.std.com> writes:
>The above is stuff I recall having come from parsers I call "Pratt"
>Parsers (for Vaughan Pratt). My recollection is that they are described
>in the following paper:
> "A formalization and correctness proof of the CGOL Language System",
> Van de Vanter, M.L., MIT/LCS/TR-147, 1975. (99 pages)
>I think you might be able to order this paper from
> http://reading-room-www.lcs.mit.edu/rr/catalog/catalog.html.
>Here's its abstract:
> In many important ways the design and implementation of
> programming languages are hindered rather than helped by BNF.
> We present an alternative meta-language based on the work of
> Pratt which retains much of the effective power of BNF but is
> more convenient for the designer, implementor and user alike.
> Its amenability to formal treatment is demonstrated by a
> rigorous correctness proof of a simple implementation.
>I don't know of a public implementation of this althought I've
>seen many private implementations and find them dreadfully
>convenient to use.
I think that SIOD, and perhaps SLIB have some kind of Pratt parser
support, but I may be mistaken.
*pause*
Yup, here's something out of SLIB: (I snipped out the license text)
; "prec.scm", dynamically extensible parser/tokenizer -*-scheme-*-
; Copyright 1989, 1990, 1991, 1992, 1993, 1995, 1997 Aubrey Jaffer.
;
; This file implements:
; * a Pratt style parser.
; * a tokenizer which congeals tokens according to assigned classes of
; constituent characters.
;
; This module is a significant improvement because grammar can be
; changed dynamically from rulesets which don't need compilation.
; Theoretically, all possibilities of bad input are handled and return
; as much structure as was parsed when the error occured; The symbol
; `?' is substituted for missing input.
and SIOD has a parser_pratt.scm bundled with it.
Hope this helps.
--
Will Hartung - Rancho Santa Margarita. It's a dry heat. ······@netcom.com
1990 VFR750 - VFR=Very Red "Ho, HaHa, Dodge, Parry, Spin, HA! THRUST!"
1993 Explorer - Cage? Hell, it's a prison. -D. Duck
In article <··························@pentium-133>, "Runser Jean-Claude"
<··················@wanadoo.fr> wrote:
>Hello
>
>Did anyone have a program to translate mathematics-expressions in INFIX
>expressions (like LISP expressions)
>
>for example:
>
>(2*x+5-6) ----> (- (+ (* 2 x) 5) 6)
Nope. But I can tell you how to do it.
Read the expression into a string.
Scan the string for the operator of lowest precidence.
Note: As someone else mentioned, there are prefix, infox, postfix,
infix, and nofix operators to contend with. Parenthesis would be an
example of a matchfix expression which you would commonly encounter.
Start building a tree in which a nore is an operator and its branches
are its operands. Place the substrings which represent the operator's
arguments at the branches of the node.
Call the parser on each of the substrings.
Your parser will then return the tree which it has built.
So, the following expression: (2*x+5-6)
Would translate into
( )
|
-
/ \
| 6
+
/ \
| 5
*
/ \
2 VAR
|
x
Does this help? If not, I could babble more. (;
>Thank you
B.B. --I am not a goat!
Runser Jean-Claude wrote:
> Hello
>
> Did anyone have a program to translate mathematics-expressions in INFIX
> expressions (like LISP expressions)
>
> for example:
>
> (2*x+5-6) ----> (- (+ (* 2 x) 5) 6)
>
> Thank you
A keyword search on "infix" at the CMU AI archive yielded the following:
Keywords: infix
> Infix Notation for Lisp
lang/lisp/code/syntax/infix/
INFIX: Infix reader macro for Common Lisp.
75 KB; Version: 14-OCT-93
The URL for the CMU archive search page is:
http://www-cgi.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/html/keys/keysform.html
Runser Jean-Claude <··················@wanadoo.fr> wrote in article
<··························@pentium-133>...
> Did anyone have a program to translate mathematics-expressions in INFIX
You might find the pratt parser in
http://people.delphi.com/gjc/siod.html
to be of practical use.
For speed I wrote the tokenizer pass in C, so that it would
be competitive in speed with other techniques.
"Runser Jean-Claude" <··················@wanadoo.fr> writes:
>
> Did anyone have a program to translate mathematics-expressions in INFIX
> expressions (like LISP expressions)
>
> for example:
>
> (2*x+5-6) ----> (- (+ (* 2 x) 5) 6)
Below is the relevant entry from the FAQ. See especially the paragraph
on CGOL (a CGOL-like Pratt parser is employed in Macsyma).
-Bill Dubuque
Languages and Alternate Syntaxes:
Generalized Lisp (or Glisp for short) is a coordinated set of high
level syntaxes for Common Lisp. Initially GLisp consists of three
dialects: Mlisp, Plisp and ordinary Lisp, together with an extensible
framework for adding others. Mlisp (Meta-Lisp) is an Algol-like
syntax for people who don't like writing parentheses. For example,
one can write print("abc", stream) instead of (print "abc" stream).
Plisp (Pattern Lisp) is a pattern matching rewrite-rule language.
Plisp is a compiler-compiler; its rules are optimized for writing
language translators. All dialects may be freely intermixed in a
file. The translators for all dialects are written in Plisp, as is
the Glisp translator framework itself. Support routines for the
translators are written in Mlisp and/or Lisp. All dialects are
translated to Common Lisp and execute in the standard Common Lisp
environment. Glisp is available by anonymous ftp from apple.com or
ftp.apple.com:/dts/mac/lisp/glisp.tar.Z
GLISP runs in MCL and has to be modified for other Common Lisp
implementations.
CGOL is algol-like language that is translated into Lisp before
execution. It was developed originally by Vaughn Pratt. A Common Lisp
implementation of CGOL is available by anonymous ftp from
peoplesparc.berkeley.edu:/pub/cgol.1.tar.Z [128.32.131.14]
(The number "1" may increase if newer versions are posted.) It was
written by a UC Berkeley graduate student, Tom Phelps, as a term
project, so there may still be some rough edges. There is a lot of
documentation in the distribution, including the "original" CGOL memo
(pratt.memo). For more information, contact Richard Fateman
<·······@peoplesparc.berkeley.edu>.
StarLisp Simulator. The StarLisp Simulator simulates *Lisp, one of
the programming langauges used to program the Connection Machine.
StarLisp runs under Symbolics, Lucid, Allegro, and Franz, and is
available by anonymous ftp from
think.com:/cm/starlisp/starsim-f19-sharfile
The "CM5 *Lisp Tutorial" is available by anonymous ftp from
arp.anu.edu.au:/ARP/papers/starlisp/ [150.203.20.2]
in Andrew "ez" and postscript formats. Write to Zdzislaw Meglicki
<·················@cisr.anu.edu.au> for more information about the tutorial.
InterLisp->Common-Lisp Translator -- ftp.ai.sri.com:/pub/pkarp/lisp/ilisp/
Other InterLisp to Common Lisp translators may be found in the LispUsers
archive listed above.
The Yale Haskell system runs in CMU Common Lisp, Lucid CL, and AKCL.
It is available by anonymous ftp from
Chalmers animal.cs.chalmers.se:/pub/haskell/yale/ [129.16.225.66]
Glasgow ftp.dcs.glasgow.ac.uk:/pub/haskell/yale/ [130.209.240.50]
Yale nebula.cs.yale.edu:/pub/haskell/yale/ [128.36.13.1]
as the files
haskell-beta-2-source.tar.Z -- full sources
haskell-beta-2-sparc.tar.Z -- sparc executable