A very basic LISP style expression parser

I had always been interested in writing a simple LISP interpreter. Well, had some free time today, and thought, why not create a parser that can return the results of mathematical expressions that are entered as LISP expressions. Nothing fancy, but here is a class that can take in a file containing math expressions and return the results of each line as an array.

package Processor;

use strict;
use warnings;

#Creates the object, nothing else
sub new {
	my $class=shift;
	my $self={};
	bless $self, $class;

#Set the file to be processed, or return the currently
#selected file
sub file{
	my $self=shift;
	my $filename=shift;
	$self->{filename}=$filename if defined $filename;

#Process each line of the file as an expression, and load
#an array with the results
sub process_file{
	my $self=shift;
	return unless defined $self->{filename};
	my @results=();
	open FILE, $self->{filename} or die ("Could not open file") ;
		push @results, ($self->process_line($_));

#Processes LISP style expressions that are valid
sub process_line{
	my $self=shift;
	my $line=shift;
	my @opstack=();
	my @operandStack=();
	for(split(" ",$line)){
		push @opstack,$_ if $_ eq "(" or 
				    $_ eq "+" or 
				    $_ eq "-" or 
				    $_ eq "*" or
				    $_ eq "/";
		push @operandStack,$_ if /^\d+$/;
		if($_ eq ")"){
			my $op1=pop @operandStack;
			my $op2=pop @operandStack;
			my $op=pop @opstack;
			pop @opstack;
			if ($op eq "+"){
				push @operandStack,($op1+$op2);
			}elsif ($op eq "-"){
				push @operandStack,($op2-$op1);
			}elsif ($op eq "*"){
				push @operandStack,($op1*$op2);
			}elsif ($op eq "/"){
				push @operandStack,($op2/$op1);
	return "Invalid expression" unless @operandStack==1;


I sure do hope to add variables to this, so that results can be used from one line of the file to another.


Ah, coolness. For an alternate approach, check out my AI::Prolog preprocessor for math. It would take Prolog math expressions like this:

X \= 9 / (3 + (4+7) % ModValue) + 2 / (3+7).

And rewrite them in a form which my parser could understand:

ne(X, plus(div(9, mod(plus(3, plus(4, 7)), ModValue)), div(2, plus(3, 7)))).

I leverage the regex engine to make this work and it was fairly straightforward.

I have a rather-much larger and more complete Scheme interpreter, written as a small Perl module. Currently it handles most of the basic types (booleans, integers, strings, pairs, lists), lambda expressions, variables in environments. About the only thing it's missing is a full macro translator.

It's not on CPAN (yet?), but it's based on my parser module, Parser::MGC, which is.

Leave a comment

About Hathibelagal

user-pic I am a web applications, and enterprise systems developer who is always on the lookout for better programming paradigms and coding styles.