如何解析python中的括号树？

Question

我需要帮助开发这个我正在研究的算法.我有一个树的输入格式如下:

(根(AB(ABC)(CBA))(CD(CDE)(FGH)))

这看起来是以下树.

                   Root
                     |
                ____________
              AB           CD
              |             |  
       __________         ___________
      ABC      CBA        CDE      FGH

该算法假设是读取括号格式并给出以下输出:

Root -> AB CD
AB -> ABC CBA
CD -> CDE FGH

它列出了根及其子女和所有其他有孩子的父母.我无法理解如何启动这个,有人可以帮我提示或提供一些参考或链接吗？

Answer 1

递归下降解析器是解析器的一种简单形式，可以解析许多语法。虽然整个解析理论对于堆栈溢出答案来说太大了，但最常见的解析方法涉及两个步骤：首先，标记化，它提取字符串的子词（这里可能是“Root”和“ABC”等单词） ，或者像'('和')'这样的括号），然后使用递归函数进行解析。

此代码解析输入（如您的示例），生成所谓的解析树，并且还有一个函数“show_children”，它接受解析树，并根据您的问题生成表达式的子视图。

import re

class ParseError(Exception):
    pass

# Tokenize a string.
# Tokens yielded are of the form (type, string)
# Possible values for 'type' are '(', ')' and 'WORD'
def tokenize(s):
    toks = re.compile(' +|[A-Za-z]+|[()]')
    for match in toks.finditer(s):
        s = match.group(0)
        if s[0] == ' ':
            continue
        if s[0] in '()':
            yield (s, s)
        else:
            yield ('WORD', s)


# Parse once we're inside an opening bracket.
def parse_inner(toks):
    ty, name = next(toks)
    if ty != 'WORD': raise ParseError
    children = []
    while True:
        ty, s = next(toks)
        if ty == '(':
            children.append(parse_inner(toks))
        elif ty == ')':
            return (name, children)

# Parse this grammar:
# ROOT ::= '(' INNER
# INNER ::= WORD ROOT* ')'
# WORD ::= [A-Za-z]+
def parse_root(toks):
    ty, _ = next(toks)
    if ty != '(': raise ParseError
    return parse_inner(toks)

def show_children(tree):
    name, children = tree
    if not children: return
    print '%s -> %s' % (name, ' '.join(child[0] for child in children))
    for child in children:
        show_children(child)

example = '( Root ( AB ( ABC ) ( CBA ) ) ( CD ( CDE ) ( FGH ) ) )'
show_children(parse_root(tokenize(example)))