python - 括弧の挿入による演算子の優先順位の解析

Question

私は [mio-lang 1 ]と呼ばれる小さなおもちゃの実験的プログラミング言語に演算子の優先順位を追加しようと一晩中取り組んできました。 FreeNode の #io チャンネルの jer が好きです!

適切な場所でトークン ストリームに括弧を挿入しようとしています。このアルゴリズムは、再帰関数呼び出しではなくスタックを使用していることを除いて、トップダウン降下パーサーと呼ばれていると思います。

以下は、本物の単純なカットダウン スニペットです。

from collections import OrderedDict


operators = OrderedDict([
    ("*", (2)), ("/", (2)),
    ("+", (1)), ("-", (1)),
])


def precedence(tokens):
    lparen = "("
    rparen = ")"

    level = None
    levels = []
    output = []

    while tokens:
        if len(tokens) > 1 and tokens[1] == "=":
            return tokens[:2] + precedence(tokens[2:])
        else:
            if len(tokens) > 1 and tokens[1] in operators:
                level = operators.get(tokens[1])

                if levels:
                    if level > levels[-1]:
                        levels.append(level)
                        output.append(lparen)
                else:
                    levels.append(level)

            output.append(tokens.pop(0))
            while levels and level < levels[-1]:
                level = levels.pop()
                output.append(rparen)

    while len(levels) > 1:
        level = levels.pop()
        output.append(rparen)

    return output

このスニペットの完全なソース コードといくつかの単体テストは、http: //codepad.org/2yNEp2Prにあります。

私の機能とエッジケースを修正するための助けに大いに感謝します!