3

文字列として与えられた再帰構造 (バイナリ ツリーなど) をトラバースするために、Perl にはどのようなメソッドがあるのだろうか。

より具体的には：

ここにツリーがあります。簡単にするために、構文解析ツリーと非常に短いものです。派手なタブやスペースのない文字列だと想像してください。

tree(Sentence, 
  tree(NounPhrase,
    leaf(Determiner, "a"),
    leaf(Noun, "man", "singular")
  ), 
  tree(VerbPhrase,
    leaf(Verb, "walks", "present", "3rd person")
  )
)

ルートの 2 つの直接の子ノードにアクセスしたいのですが、単純に正規表現でこれを行うことはできません。

m/tree \( \w+ , (group1) , (group2) \) /x

group1 と group2 を正しくキャプチャしたいと思います。つまり、group1 と group2 の開き括弧と閉じ括弧の数は偶数です。

それは非常に複雑な作業のように思えますが、それに対する一般的/最も簡単な解決策は何ですか?

たとえば、プロローグはこのタスクを簡単に消化します。

4

3 に答える 3

2

私は2つの関数を作成してみます：sub tree{}とsub leaf{}

leaf(Determiner, "a")それぞれがタグ付けされた用語を文字列として返します。たとえば、<Determiner>a</Determiner>

次に、処理したいファイルを実行するだけです。XML::DOM出力は、たとえばDOMパーサーで解析できるDOMのような構造になります

于 2012-10-06T04:50:00.447 に答える
0

わかりました、ありがとう、答えは「単純に、正規表現だけでは不可能です」です。

于 2012-10-06T11:59:31.907 に答える
0

正規表現の例が示唆するように、予想される子の数がわかっている場合、それはかなり簡単で、次のようなもので十分です。

my @children = m{ tree\(  \w+?, ( (?:tree|leaf)\(.+\) ), ( (?:tree|leaf)\(.+\) ) \) }x;

そうでない場合は、実際には単純ではありませんが、可能です。Jeffrey Friedl は、正規表現に関する著書の中で、ネストされたペアを照合するために、動的正規表現構成体と呼ばれるものを使用して再帰パターンを構築することを提案しています。

# first, strip your string
s{ ^ tree\( \w+ , (.+) \) $ }{$1}x;

# then, define the recursive pattern to match paired parentheses
my $recursion;
$recursion = qr{ (?> [^()]+ | \( (??{ $recursion }) \) )* }x;

# finally, match!
my @children = m{ ( (?: tree | leaf ) \( $recursion \) ) ,?}gx;

perlre では、これを延期された正規部分式と呼びます。実験的な機能として注目されています.

于 2013-12-10T17:20:43.723 に答える