在Go语言中解析s表达式

Question

这里有一个链接可以了解lis.py： http://norvig.com/lispy.html 我正在尝试在Go语言中实现一个微型lisp解释器。我受到Peter Norvig在Python中实现的Lis.py lisp解释器的启发。

我的问题是，我无法想到一种相对高效的解析s表达式的方法。我想到了一个计数器，当它遇到“（”时加1，当它遇到“）”时减1。这样，当计数器为0时，你知道你有一个完整的表达式。

但问题在于，这意味着你必须循环遍历每个表达式，这将使得解释器对于任何大型程序都变得异常缓慢。

如果有任何其他替代方法，那就太好了，因为我目前也想不出更好的方法。

- Francis

---

这实际上是一个解析问题，而不是Lisp的问题。 s表达式的一个示例可以帮助回答。 - nouney

计数器不会起作用。就像lis.py一样，您需要使用堆栈或递归将代码解析为cons和符号。 - Sylwester

Answer 1

在Rosetta code上有一个用Go实现的S表达式解析器：

Go中的S表达式解析器

这可能会给你攻击这个问题的思路。

- soegaard

Answer 2

您可能需要一个名为"Sexpr"的接口，并确保符号和列表数据结构与该接口匹配。然后，您可以利用S表达式简单地表示为“单个符号”或“S表达式列表”的事实。

也就是说，如果第一个字符是“（”，那么它不是符号，而是一个列表，因此开始累积[]Sexpr，在读取每个包含的Sexpr时，直到在输入流中遇到“）”。任何包含的列表将已经消耗了其终端“)”。

如果它不是“（”，则正在读取一个符号，因此请阅读，直到找到一个非符号组成部分的字符，取消使用并返回该符号。

- Vatine

Answer 3

在2022年，您还可以测试John Jacobsen用Go编写的eigenhombre/l1，这是一个小型Lisp 1。

它是在"(Yet Another) Lisp In Go"中呈现的。

它包括对S表达式的解析和测试，其中commit b3a84e1已经被纳入。

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)"},
    }

- VonC