An RPN Interpreter in Go (Golang)

I built a non-Turing-complete interpreter in Go whose current incarnation is simply named “rpnrepl”.  rpnrepl is a very tiny stack-based, postfix language whose syntax is similar to that of the Forth programming language.

rpnrepl can only perform four mathematical operations, display the topmost item on the stack, display a newline, and exit the running program.

Unlike Forth whose grammar can change dynamically, rpnrepl does have a simple grammar.  Words are separated by spaces unless bound by single quotation-marks or double quotation-marks.  If a word looks like an integer, it is treated as an integer.  Otherwise a word is assumed to represent a function.  rpnrepl tries to execute these functions immediately as it finds them.

The seven functions supported are +,-,*,/,.,cr, and bye.

+ pops the two integers at the top of the stack, adds them, and leaves the result on the stack.  The subtraction, multiplication, and division words ( -, *, and / ) perform similar operations.

. displays the top stack item.  Strings can be pushed onto the stack by just specifying a string in double-quotes or single quotes.

cr displays a newline on the console.

bye exits rpnrepl with return code 0.

rpnrepl.go

// Copyright 2013 - by Jim Lawless
// License: MIT / X11
// See: http://www.mailsend-online.com/license2013.php
//
// Bear with me ... I'm a Go noob.

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"regexp"
	"strconv"
)

const smax = 20

var stack []interface{}
var sptr int
var words map[string]func()

var patDquote = "[\"][^\"]*[\"]"
var patSquote = "['][^']*[']"
var patNumber = "[-]?\\d+"
var patWord = "\\S+"

var reDquote, reSquote *regexp.Regexp
var reNumber, reAll *regexp.Regexp

func push(val interface{}) {
	if sptr == 0 {
		log.Fatal("Stack overflow.")
	}
	sptr--
	stack[sptr] = val
}

func pop() interface{} {
	if sptr >= smax {
		log.Fatal("Stack underflow")
	}
	tmp := stack[sptr]
	sptr++
	return tmp
}

func add() {
	i, j := popTwo()
	push(i + j)
}

func sub() {
	i, j := popTwo()
	push(i - j)
}

func mul() {
	i, j := popTwo()
	push(i * j)
}

func div() {
	i, j := popTwo()
	push(i / j)
}

func dot() {
	fmt.Printf("%v", pop())
}

func cr() {
	fmt.Println()
}

func bye() {
	os.Exit(0)
}

func popTwo() (int, int) {
	j := pop().(int)
	i := pop().(int)
	return i, j
}

func repl() {
	var s string
	var k int
	var f func()

	reader := bufio.NewReader(os.Stdin)
	for {
		input, err := reader.ReadString('\n')
		if err != nil {
			log.Fatal(err)
		}
		tokens := reAll.FindAllString(input, -1)
		for i := 0; i < len(tokens); i++ {
			s = tokens[i]
			switch {
			case reDquote.MatchString(s):
				s = s[1 : len(s)-1]
				push(s)
			case reSquote.MatchString(s):
				s = s[1 : len(s)-1]
				push(s)
			case reNumber.MatchString(s):
				k, err = strconv.Atoi(s)
				if err != nil {
					log.Fatal(err)
				}
				push(k)

			default:
				f = words[s]
				if f != nil {
					f()
				} else {
					log.Fatal("Word '" + s + "' not found!")
				}
			}
		}
	}
}

func main() {
	sptr = smax
	stack = make([]interface{}, sptr+1)
	words = make(map[string]func())
	words["+"] = add
	words["-"] = sub
	words["*"] = mul
	words["/"] = div
	words["."] = dot
	words["cr"] = cr
	words["bye"] = bye

	reDquote, _ = regexp.Compile(patDquote)
	reSquote, _ = regexp.Compile(patSquote)
	reNumber, _ = regexp.Compile(patNumber)
	reAll, _ = regexp.Compile(patDquote + "|" + patSquote + "|" + patNumber + "|" + patWord)
	repl()
}

Lexical analysis of the input stream is performed by using regular expressions. Four regular-expressions are used to sift through the input:


var patDquote = "[\"][^\"]*[\"]"
var patSquote = "['][^']*[']"
var patNumber = "[-]?\\d+"
var patWord = "\\S+"

The regexes help me extract double-quote or single-quote strings or numbers.  The final regex is a catch-all ( any contiguous non-whitespace characters. )

rpnrepl uses a stack of interface {} elements.  This means that we can push any data-type onto our stack.

As the input is scanned, strings and numbers are immediately pushed onto the stack. Since we have a stack of interface {} entries, we can push instances of any data-type onto it. For now. we’ll stick to integers and strings.

As functions are encountered, they are executed. The map structure named “words” contains the rpnrepl commands that map to internal rpnrepl functions.

Here’s a sample that you might type into the rpnrepl console:


"Hey! 2 * 7 == " . 2 7 * . cr cr

The output you’d see is:


Hey! 2 * 7 == 14

If you create a script named test.rpn with the contents:


"Let's multiply 2 by 3" . cr cr
"2 times 3 == " . 2 3 * . cr cr
bye

You can then run the above script by using the command-line:


rpnrepl < test.rpn

The output you’ll see is:


Let's multiply 2 by 3

2 times 3 == 6

I have omitted any means to define subroutines or functions in rpnrepl. In a future post, we’ll define our own functions and will discuss intermediate compilation formats.

Advertisements

About Jim Lawless

I've been programming computers for about 36 years ... 30 of that professionally. I've been a teacher, I've worked as a consultant, and have written articles here and there for publications like Dr. Dobbs Journal, The C/C++ Users Journal, Nuts and Volts, and others.
This entry was posted in Programming and tagged , . Bookmark the permalink.

2 Responses to An RPN Interpreter in Go (Golang)

  1. Gus says:

    New to Go, but obviously not new to regular expressions. This was very useful in parsing command-line input and handling quotation marks — and it proved to be very robust. Thank you for sharing.

  2. Pingback: Pretty-Printing an S-Expression in Go | Jim Lawless' Other Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s