Wed, 19 Oct 1994 04:08:11 GMT

Related articles |
---|

A simple pattern matching tool for C++ aleung@netcom.com (1994-10-19) |

Re: A simple pattern matching tool for C++ leun7056@cs.nyu.edu (1994-10-23) |

Newsgroups: | comp.compilers,comp.lang.c++ |

From: | aleung@netcom.com (Allen Leung) |

Keywords: | C++, tools |

Organization: | None |

Date: | Wed, 19 Oct 1994 04:08:11 GMT |

Fellow C++ programmers,

I am building a simple extension of C++ called Prop to be used in

tasks such as compiler construction and program transformation. While much

of the research and development is still incomplete, one small extension on

(Standard ML-like) algebraic datatypes and pattern matching is quite robust,

and can be used independently of other features.

I invite everyone to try it (source available via anonymous

ftp://ftp.netcom.netcom:/pub/aleung/Prop), and perhaps give me some

feedback in return. All the source code is in the public domain; and if you

can actually use it to do useful work, so much the better. Documentation

is available in texinfo and dvi format.

Currently, the system has been tested on gcc 2.5.7 and 2.5.8, under

Unix and DOS. It comes with a home-grown C++ library, and Bison and flex

are needed. Please email me for more details.

best,

allen. (aleung@netcom.com, leun7056@cs.nyu.edu)

-------------------------- A brief demo -------------------------------------

Algebraic datatypes declarations in Prop can used to specify typed,

attributed, graph structures that are used extensively in compiler front-ends,

i.e. structures such as abstract syntax trees.

For example, a (very simple) expression tree type EXP can be specified in

Prop with the following two type equations:

datatype EXP = integer (int) // integer literals

| ident (char) // identifiers

| binop (BINOP, EXP, EXP) // binary operator node

and BINOP = add | sub | mul | div // arithmetic operators

;

Now, expressions such as `1 + 2' can be represented as the labeled-tree:

binop(add, integer(1), integer(2));

Since EXP (and BINOP) are valid C++ types(i.e. there is no data impedence

mismatch between C++ and Prop), we may actual say things like the following

in our C++ programs:

EXP e1 = binop(add, ident('A'), integer(1));

EXP e2 = binop(mul, e1, e1);

Variable `e2' now contains the dag representing the expression:

(A + 1) * (A + 1)

Testing and decomposing an alg-type value is accomplished using pattern

matching thru the `match' statement. The match statement can be seen as

a generalisation of `switch' and `if'. For example, an expression

evaluator can be written as a topdown tree traversal, but without having to

mess around with pointers or variant tags:

int eval(EXP e, int env[])

{ match (e) {

case integer i: return i;

case ident v: return env[v];

case binop(add,a,b): return eval(a,env) + eval(b,env);

case binop(sub,a,b): return eval(a,env) - eval(b,env);

case binop(mul,a,b): return eval(a,env) * eval(b,env);

case binop(div,a,b): return eval(a,env) / eval(b,env);

}

}

In general, datatype declarations can be mutually recursive

and patterns can be nested arbitrarily deep. The Prop preprocesser

will translate all algebraic datatype specifications into C++ class hierarchies

[before compilation] and all pattern matching into efficient tree traversal

code.

The preprocessor is written in itself; the core algorithms(

Milner-style type inference, Wadler's pattern matching compilation, and AST

traversal) involving trees and dags are written using pattern matching.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.