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;
	$self;
}

#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;
	$self->{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") ;
	while(<FILE>){
		push @results, ($self->process_line($_));
	}
	@results;
}

#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;
	$operandStack[0];
}

1;

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

4 Comments

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.