1

我得到了一个使用括号和 + 的表达式，例如 (((a+b)+c)+(d+e))。

我需要找到它的解析树，然后打印出这个解析树的列表形式，如：[ [ [a, b], c ], [d, e] ]

我在想我会使用类似 ast 的东西，然后是 ast2list。但是，由于我没有完全理解这些，我反复收到语法错误。这就是我所拥有的：

import ast
import parser

a = ast.parse("(((a+b)+c)+(d+e))", mode='eval')
b = parser.ast2list(a)


print(b)

谁能指导我正确的方向？谢谢。

4

5 回答 5

2

Colleen 的评论可以通过以下方式实现：

str = "(((a+b)+c)+(d+e))"


replacements = [
    ('(','['),
    (')',']'),
    ('+',','),
    # If a,b,c,d,e are defined variables, you don't need the following 5 lines
    ('a',"'a'"),
    ('b',"'b'"),
    ('c',"'c'"),
    ('d',"'d'"),
    ('e',"'e'"),
]

for (f,s) in replacements:
    str = str.replace(f,s)

obj = eval(str)

print(str)       # [[['a','b'],'c'],['d','e']]
print(obj)       # [[['a', 'b'], 'c'], ['d', 'e']]
# You can access the parsed elements as you would any iterable:
print(obj[0])    # [['a', 'b'], 'c']
print(obj[1])    # ['d', 'e']
print(obj[1][0]) # d
于 2012-10-12T23:32:48.033 回答
2

查看描述该类的ast 模块的文档。NodeVisitor

import ast
import sys

class MyNodeVisitor(ast.NodeVisitor):
    op_dict = {
        ast.Add : '+',
        ast.Sub : '-',
        ast.Mult : '*',
    }

    type_dict = {
        ast.BinOp: lambda s, n: s.handleBinOp(n),
        ast.Name: lambda s, n: getattr(n, 'id'),
        ast.Num: lambda s, n: getattr(n, 'n'),
    }

    def __init__(self, *args, **kwargs):
        ast.NodeVisitor.__init__(self, *args, **kwargs)
        self.ast = []

    def handleBinOp(self, node):
        return (self.op_dict[type(node.op)], self.handleNode(node.left), 
                    self.handleNode(node.right))

    def handleNode(self, node):
        value = self.type_dict.get(type(node), None)
        return value(self, node)

    def visit_BinOp(self, node):
        op = self.handleBinOp(node)
        self.ast.append(op)

    def visit_Name(self, node):
        self.ast.append(node.id)

    def visit_Num(self, node):
        self.ast.append(node.n)

    def currentTree(self):
        return reversed(self.ast)

a = ast.parse(sys.argv[1])
visitor = MyNodeVisitor()
visitor.visit(a)
print list(visitor.currentTree())

看起来像这样：

 $ ./ast_tree.py "5 + (1 + 2) * 3"
 [('+', 5, ('*', ('+', 1, 2), 3))]

享受。

于 2012-10-12T23:52:31.073 回答
2

如果你真的想做一个解析器，首先不要编写任何代码，而是要了解你的语法应该如何工作。Backus-Naur 格式或 BNF 是用于定义语法的典型符号。中缀表示法是一个常见的软件工程解析主题，中缀表示法的基本 BNF 结构如下：

letter ::= 'a'..'z'
operand ::= letter+
term ::= operand | '(' expr ')'
expr ::= term ( '+' term )*

关键是它term包含您的字母操作数或包含在 () 中的整个子表达式。该子表达式与整个表达式相同，因此此递归定义负责所有括号嵌套。然后，表达式是一个术语，后跟零个或多个术语，使用二进制“+”运算符添加。（您也可以扩展term以处理减法和乘法/除法，但我不会让这个答案变得过于复杂。）

Pyparsing 是一个包，它可以使用 Python 对象轻松地将 BNF 转换为工作解析器（Ply、spark 和 yapps 是其他解析器，它们遵循更传统的 lex/yacc 解析器创建模型）。这是直接使用pyparsing实现的BNF：

from pyparsing import Suppress, Word, alphas, Forward, Group, ZeroOrMore

LPAR, RPAR, PLUS = map(Suppress, "()+")
operand = Word(alphas)

# forward declare our overall expression, necessary when defining a recursive grammar
expr = Forward()

# each term is either an alpha operand, or an expr in ()'s
term = operand | Group(LPAR + expr + RPAR)

# define expr as a term, with optional '+ term's
expr << term + ZeroOrMore(PLUS + term)

# try it out
s = "(((a+b)+c)+(d+e))"
print expr.parseString(s)

给予：

[[[['a', 'b'], 'c'], ['d', 'e']]]

识别操作优先级的中缀表示法是一个非常常见的解析器，或者是更大解析器的一部分，因此 pyparsing 包含一个帮助器内置调用operatorPrecedence来处理所有嵌套/分组/递归等。这是使用 编写的同一个解析器operatorPrecedence：

from pyparsing import operatorPrecedence, opAssoc, Word, alphas, Suppress

# define an infix notation with precedence of operations
# you only define one operation '+', so this is a simple case
operand = Word(alphas)
expr = operatorPrecedence(operand,
    [
    ('+', 2, opAssoc.LEFT),
    ])

print expr.parseString(s)

给出与以前相同的结果。

可以在 pyparsing wiki 上在线找到更详细的示例——fourFn.py 中的显式实现和simpleArith.py中的 operatorPrecedence 实现。

于 2012-10-13T03:38:00.870 回答
0

我也会做翻译。通过 ast 来实现这个目的有点麻烦。

[tw-172-25-24-198 ~]$ cat a1.py 
import re

def multiple_replace(text, adict):
    rx = re.compile('|'.join(map(re.escape, adict)))
    def one_xlat(match):
        return adict[match.group(0)]
    return rx.sub(one_xlat, text)

# Closure based approach
def make_xlat(*args, **kwds):
    adict = dict(*args, **kwds)
    rx = re.compile('|'.join(map(re.escape, adict)))
    def one_xlat(match):
        return adict[match.group(0)]
    def xlat(text):
        return rx.sub(one_xlat, text)
    return xlat

if __name__ == "__main__":
    text = "((a+b)+c+(d+(e+f)))"
    adict = {
        "+":",",
        "(":"[",
        ")":"]",
    }
    translate = make_xlat(adict)
    print translate(text)

应该给

[[a,b],c,[d,[e,f]]]

注意 - 我的收藏中一直有这个片段。它来自 Python Cookbook。它对字符串进行多次替换，一次通过字典中的替换键和值。

于 2012-10-12T23:49:55.423 回答
0

这是一个足够简单的问题，您可以从头开始编写解决方案。这假定所有变量名称都是一个字符长，或者表达式已正确转换为标记列表。我投了支票以确保所有括号都匹配；显然你应该换掉CustomError你想抛出的任何异常或你想采取的其他行动。

def expr_to_list(ex):
    tree = []
    stack = [tree]
    for c in ex:
        if c == '(':
            new_node = []
            stack[-1].append(new_node)
            stack.append(new_node)
        elif c == '+' or c == ' ':
            continue
        elif c == ')':
            if stack[-1] == tree:
                raise CustomError('Unmatched Parenthesis')
            stack.pop()
        else:
            stack[-1].append(c)
    if stack[-1] != tree:
        raise CustomError('Unmatched Parenthesis')
    return tree

测试：

>>> expr_to_list('a + (b + c + (x + (y + z) + (d + e)))')
['a', ['b', 'c', ['x', ['y', 'z'], ['d', 'e']]]]

对于多字符变量名称，使用正则表达式进行标记化：

>>> tokens = re.findall('\(|\)|\+|[\w]+', 
                        '(apple + orange + (banana + grapefruit))')
>>> tokens
['(', 'apple', '+', 'orange', '+', '(', 'banana', '+', 'grapefruit', ')', ')']
>>> expr_to_list(tokens)
[['apple', 'orange', ['banana', 'grapefruit']]]
于 2012-10-13T02:36:50.763 回答