CODEWITHSUNDEEP
golispinterpreters-expression
Francis
Francis

Reputation: 99

Parsing s-expressions in Go

Here's a link to lis.py if you're unfamiliar: http://norvig.com/lispy.html

I'm trying to implement a tiny lisp interpreter in Go. I've been inspired by Peter Norvig's Lis.py lisp implementation in Python.

My problem is I can't think of a single somewhat efficient way to parse the s-expressions. I had thought of a counter that would increment by 1 when it see's a "(" and that would decrement when it sees a ")". This way when the counter is 0 you know you've got a complete expression.

But the problem with that is that it means you have to loop for every single expression which would make the interpreter incredibly slow for any large program.

Any alternative ideas would be great because I can't think of any better way.

Upvotes: 3

Views: 1578

Answers (3)

VonC
VonC

Reputation: 1323343

In 2022, you can also test eigenhombre/l1, a small Lisp 1 written in Go, by John Jacobsen .

It is presented in "(Yet Another) Lisp In Go"

It does include in commit b3a84e1 a parsing and tests for S-expressions.

func TestSexprStrings(T *testing.T) {
    var tests = []struct {
        input sexpr
        want  string
    }{
        {Nil, "()"},
        {Num(1), "1"},
        {Num("2"), "2"},
        {Cons(Num(1), Cons(Num("2"), Nil)), "(1 2)"},
        {Cons(Num(1), Cons(Num("2"), Cons(Num(3), Nil))), "(1 2 3)"},
        {Cons(
            Cons(
                Num(3),
                Cons(
                    Num("1309875618907812098"),
                    Nil)),
            Cons(Num(5), Cons(Num("6"), Nil))), "((3 1309875618907812098) 5 6)"},
    }

Upvotes: 0

Vatine
Vatine

Reputation: 21258

You'd probably need to have an interface "Sexpr" and ensure that your symbol and list data structures matches the interface. Then you can use the fact that an S-expression is simply "a single symbol" or "a list of S-expressions".

That is, if the first character is "(", it's not a symbol, but a list, so start accumulating a []Sexpr, reading each contained Sexpr at a time, until you hit a ")" in your input stream. Any contained list will already have had its terminal ")" consumed.

If it's not a "(", you're reading a symbol, so read until you hit a non-symbol-constituent character, unconsume it and return the symbol.

Upvotes: 1

soegaard
soegaard

Reputation: 31147

There is an S-expression parser implemented in Go at Rosetta code:

S-expression parser in Go

It might give you an idea of how to attack the problem.

Upvotes: 1

Related Questions