3

次の形式で行を解析しようとしています:

(OP something something (OP something something ) ) ( OP something something )

OP は論理ゲート (AND、OR、NOT) の記号であり、評価したいものは何かです。

探している出力は次のようなものです。

{ 'OPERATOR': [condition1, condition2, .. , conditionN] }

条件自体が dict/list のペアになる場合があります (ネストされた条件)。これまでのところ、次のようなことを試しました：

        tree = dict()
        cond = list()
        tree[OP] = cond


    for string in conditions:
        self.counter += 1
        if string.startswith('('):
            try:
                OP = string[1]
            except IndexError:
                OP = 'AND'
            finally:
                if OP == '?':
                    OP = 'OR'
                elif OP == '!':
                    OP = 'N'

            # Recurse
            cond.append(self.parse_conditions(conditions[self.counter:], OP))
            break

        elif not string.endswith(")"):
            cond.append(string)

        else:
            return tree

    return tree

他の方法も試しましたが、この再帰全体に頭を悩ませることはできないので、ここでいくつかのポインターを取得できるかどうか疑問に思っています.Webを見回して、再帰降下解析に関するいくつかのものを見つけましたが、チュートリアルはすべて試していました必要以上に複雑なことをするために。

PS: 既存の python ライブラリでこれを行うことができることはわかっていますが、それを行うことで何を学ぶことができますか?

4

1 に答える 1

3

学習目的で、コメントなしでこれを投稿しています（実際にはライブラリを使用してください）。エラー チェックがないことに注意してください (宿題です!)。

わからないことがあれば遠慮なく聞いてください。

# PART 1. The Lexer

symbols = None

def read(input):
    global symbols
    import re
    symbols = re.findall(r'\w+|[()]', input)

def getsym():
    global symbols
    return symbols[0] if symbols else None

def popsym():
    global symbols
    return symbols.pop(0)

# PART 2. The Parser
# Built upon the following grammar:
#  
#     program = expr*
#     expr    = '(' func args ')'
#     func    = AND|OR|NOT
#     args    = arg*
#     arg     = string|expr
#     string  = [a..z]

def program():
    r = []
    while getsym():
        r.append(expr())
    return r

def expr():
    popsym() # (
    f = func()
    a = args()
    popsym() # )
    return {f: a}

def func():
    return popsym()

def args():
    r = []
    while getsym() != ')':
        r.append(arg())
    return r

def arg():
    if getsym() == '(':
        return expr()
    return string()

def string():
    return popsym()

# TEST = Lexer + Parser

def parse(input):
    read(input)
    return program()

print parse('(AND a b (OR c d)) (NOT foo) (AND (OR x y))')
# [{'AND': ['a', 'b', {'OR': ['c', 'd']}]}, {'NOT': ['foo']}, {'AND': [{'OR': ['x', 'y']}]}]
于 2013-03-28T11:32:31.677 に答える