基于关键字嵌套字典列表

jtw3ybtb  于 2021-09-29  发布在  Java
关注(0)|答案(1)|浏览(352)

我正在编写一个小小的lisp解释器,作为python的学习练习。我有一组函数,可以将一个lisp代码字符串解析为一个字典列表。例如,对于字符串:

"(defun hello-name (name) 
    (quote (+ "Hello, " name)))"

解析器函数将输出:

[{'type': 'identifier', 'value': '('},
 {'type': 'identifier', 'value': 'defun'},
 {'type': 'identifier', 'value': 'hello-name'},
 {'type': 'identifier', 'value': '('},
 {'type': 'identifier', 'value': 'name'},
 {'type': 'identifier', 'value': ')'},
 {'type': 'identifier', 'value': '('},
 {'type': 'identifier', 'value': 'quote'},
 {'type': 'identifier', 'value': '('},
 {'type': 'identifier', 'value': '+'},
 {'type': 'string_literal', 'value': 'Hello, '},
 {'type': 'identifier', 'value': 'name'},
 {'type': 'identifier', 'value': ')'},
 {'type': 'identifier', 'value': ')'},
 {'type': 'identifier', 'value': ')'}]

我希望它能够根据前面有多少个左括号嵌套标识符,例如,解析器的输出应该如下所示:

[
    {'type': 'identifier', 'value': 'defun'},
    {'type': 'identifier', 'value': 'hello-name'},
        [ 
            {'type': 'identifier', 'value': 'name'},
        ] 

        [ 
            {'type': 'identifier', 'value': 'quote'},
                [
                    {'type': 'identifier', 'value': '+'},
                    {'type': 'string_literal', 'value': 'Hello, '},
                    {'type': 'identifier', 'value': 'name'},
                ]
        ]
]

这里的不同之处在于,“(”或“)”的每一次出现都被列表中的另一个嵌套所取代。
在python中如何实现这一点?

whlutmcx

whlutmcx1#

虽然您应该包含一些自己尝试过的代码,但您是一个初学者,这是一个半挑战性的问题,所以请提供一些帮助。
这是一种非常标准的令牌解析方法,基本上是跟踪开括号的数量,开括号内的项放在一个数组中进行递归计算,括号外顶层的项返回时保持不变。打开和关闭支架将被丢弃。

def reduce(parsed_expression):
    nested = []
    open_count = 0
    for line in parsed_expression:
        if line["type"] == "identifier" and line["value"] == "(":
            open_count += 1
            if open_count == 1:     # First opening bracket
                continue        # Discard opening bracket
        elif line["type"] == "identifier" and line["value"] == ")":
            open_count -= 1
            if open_count == 0:     # Closing all brackets
                yield list(reduce(nested))  # Evaluate nested expression
                nested = []
                continue

        if open_count == 0:
            yield line   # Return item unchanged
        if open_count > 0:
            nested.append(line)    # Add to nested expression

如果你这样称呼它:

expression = [{'type': 'identifier', 'value': '('},
              {'type': 'identifier', 'value': 'defun'},
              {'type': 'identifier', 'value': 'hello-name'},
              {'type': 'identifier', 'value': '('},
              {'type': 'identifier', 'value': 'name'},
              {'type': 'identifier', 'value': ')'},
              {'type': 'identifier', 'value': '('},
              {'type': 'identifier', 'value': 'quote'},
              {'type': 'identifier', 'value': '('},
              {'type': 'identifier', 'value': '+'},
              {'type': 'string_literal', 'value': 'Hello, '},
              {'type': 'identifier', 'value': 'name'},
              {'type': 'identifier', 'value': ')'},
              {'type': 'identifier', 'value': ')'},
              {'type': 'identifier', 'value': ')'}]

res = list(reduce(expression))

您将得到以下结果:

exp = [[
    {'type': 'identifier', 'value': 'defun'},
    {'type': 'identifier', 'value': 'hello-name'},
    [
        {'type': 'identifier', 'value': 'name'}
    ],
    [
        {'type': 'identifier', 'value': 'quote'},
        [
            {'type': 'identifier', 'value': '+'},
            {'type': 'string_literal', 'value': 'Hello, '},
            {'type': 'identifier', 'value': 'name'}
        ]
    ]
]]

注意两件事:你必须把 reduce 进入 list 因为它是一个生成器,你想把它折叠成一个列表。此外,它与您预期的略有不同,因为它是顶级的
( ) S

相关问题