基于Python实现Lisp方言的词法分析方案求助

我对Lisp语言感兴趣，想做一款极简Lisp方言——这个方言里所有内容都是列表，列表以命令开头，参数也能是列表。为此我定义了如下KList类：

class KList:
    def __init__(self, command, args=None):
        self.command = command
        self.args = args

现在需要把(+ 1 2)这类Lisp表达式转换成KList('+', [KList('1'), KList('2')])的结构，同时得满足两个要求：

• 不依赖任何词法分析库
• 用纯函数式Python实现，不能有语句和变量突变

纯函数式实现方案 #

1. 词法分析（Tokenize）

先把输入的表达式字符串拆分成可处理的token，全程用递归和列表拼接，避免变量修改：

def tokenize(s):
    def helper(s, tokens):
        if not s:
            return tokens
        c = s[0]
        if c in '()':
            return helper(s[1:], tokens + [c])
        elif c.isspace():
            return helper(s[1:], tokens)
        else:
            # 提取连续的非空格、非括号字符作为原子token
            end = 1
            while end < len(s) and not s[end].isspace() and s[end] not in '()':
                end += 1
            return helper(s[end:], tokens + [s[:end]])
    return helper(s, [])

2. 语法解析（Parse）

把token列表转换成KList结构，同样用递归实现，无变量突变：

def parse(tokens):
    def helper(tokens):
        if not tokens:
            raise ValueError("输入意外结束")
        token = tokens[0]
        if token == '(':
            # 递归解析列表内的参数
            def parse_args(tokens, args):
                if not tokens:
                    raise ValueError("未闭合的括号")
                if tokens[0] == ')':
                    return args, tokens[1:]
                arg, rest = helper(tokens)
                return parse_args(rest, args + [arg])
            args, rest = parse_args(tokens[1:], [])
            if not args:
                raise ValueError("不允许空列表")
            # 第一个参数作为命令，剩下的作为参数列表
            cmd = args[0].command if isinstance(args[0], KList) else args[0]
            return KList(cmd, args[1:]), rest
        elif token == ')':
            raise ValueError("意外的右括号")
        else:
            # 原子项直接转为无参数的KList
            return KList(token), tokens[1:]
    result, rest = helper(tokens)
    if rest:
        raise ValueError(f"意外的token: {rest}")
    return result

使用示例

# 测试基础表达式(+ 1 2)
expr = "(+ 1 2)"
tokens = tokenize(expr)
klist = parse(tokens)
print(klist.command)  # 输出: '+'
print([arg.command for arg in klist.args])  # 输出: ['1', '2']

# 测试嵌套表达式(* (+ 3 4) 5)
expr2 = "(* (+ 3 4) 5)"
klist2 = parse(tokenize(expr2))
print(klist2.command)  # 输出: '*'
print(klist2.args[0].command)  # 输出: '+'
print([arg.command for arg in klist2.args[0].args])  # 输出: ['3', '4']
print(klist2.args[1].command)  # 输出: '5'

实现说明 #

• tokenize通过递归遍历字符串，把字符拆分为括号、原子符号等token，全程用列表拼接而非修改已有变量，符合纯函数式要求。
• parse递归处理token列表，遇到左括号就解析内部参数，组装成KList；原子项直接转为无参数的KList，全程没有变量赋值修改。
• 整个实现没有依赖任何第三方库，只用了Python内置的字符串和列表操作。

内容的提问来源于stack exchange，提问作者KianFakheriAghdam