2

わかりました、次の条件で単純なパーサーを作成しようとしています。

d = {
    'a': [1,2,3,4],
    'b': [2,3,4,5],
    'c': [2,4,6,7]
}

そして、次の 2 つの関数:

def _and(l1, l2):
    return [i for i in l1 if i in l2]

def _or(l1, l2):
    return list(set(l1+l2))

"a||(b&c)"文字列 (例: ) を取り込んで、次のように解析しようとしています。

_or(d['a'],_and(d['b'],d['c']))

私はこれまでパーサーを書いたことがなかったので、少し戸惑いました。パーサーはOR、ANDおよび括弧をサポートする必要があります。誰かが私を正しい方向に向けることができますか? Python での同様の例は、誰かが知っていれば素晴らしいでしょう。

4

1 に答える 1

2

この問題へのアプローチ方法を概説します。

入力文字列をトークンに分割し、これらのトークンのリストを構文ツリーに変換する必要があります。あなたの場合、次のようなものが必要です。

  • a
  • ||
  • (b&c)
    • b
    • &
    • c

括弧内のコンポーネントにも同じ解析手法を適用して、b&cそれをトークンに分割する必要がある可能性があります (示されているように)。したがって、この構文解析手順は、任意にネストされた括弧を処理するために、再帰的である可能性が非常に高くなります。ANTLRなど、これに役立つ既存のツールがあります。

ここから、演算子の優先順位に基づいて構文ツリーを作成します。この場合、式は次のツリーで示すことができます。

   また
  / \
    と_
     / \
    紀元前   _

次に、このツリーを再帰的にトラバースし、子ノードに基づいて各ノードの「操作」を実行できます。明らかに、これはすべて実装するよりも言うのは簡単です。私がとったアプローチの 1 つは、クラスを作成することNodeです。クラスのインスタンスを使用してツリーを形成します。それぞれに、その結​​果を返すメソッドを含めるNodeことができます。evaluate葉a、bおよびcの場合、結果は単純d['a']に 、d['b']およびd['c']です。ORおよびの場合、結果はユーザーが定義した関数およびANDに基づいています。_and_or

于 2013-07-29T14:40:42.947 に答える