木構造の正規表現ですか？

Question

ツリー構造を検索および変更するための正規表現に相当するものはありますか？簡潔なミニ言語（perl正規表現のような）が私が探しているものです。

ここでは、私が探しているものを明確にする例があります。

<root> 
    <node name="1"> 
    subtrees .... 
    </node> 
    <node name="2"> 
    <node name="2.1"> 
    data 
    </node> 
    other subtrees... 
    </node> 
</root> 

上記ツリーに可能であろう動作が「 にノード1におけるサブツリーのノード2.1で移動サブツリー」であります演算の結果があればそのデータは「a」と「b」と交換で始まるすべてのノードを見つけ、次のようになり..

<root> 
    <node name="1"> 
    subtrees .... 
    <node name="2.1"> 
    data 
    </node> 
    </node> 
    <node name="2"> 
    other subtrees... 
    </node> 
</root> 

検索し、少なくとも2人の子供を持つすべてのノードを見つけるような操作を交換するかもしれませんサブツリーには少なくとも2人の他の兄弟などがサポートされるべきです。

文字列の場合、唯一の次元が文字列の長さ全体にわたる場合、正規表現を使用して上記の操作の多く（またはその1D相当）を実行できます。私は木に相当するものがあるのだろうかと思います。 （単一の正規表現の代わりに、変換規則のセットを書く必要があるかもしれませんが、それは問題ありません）。

私はいくつかの単純なミニ言語（regex per.seではなく、ライブラリなどを介して正規表現としてアクセス可能なもの）があるかどうかを知りたいと思います。これらの操作を実行するには？好ましくは、Pythonライブラリとして。

Answer 1

スタンフォード出身のツルジョンとトレジェックスがそうすることができます。ライブラリはhttp://nlp.stanford.edu/software/tregex.shtml

Answer 2

バイナリ検索ツリーをナビゲートするには、有限状態オートマトンでは実行できない状態（ノードが何であるか）と比較（その値がそれよりも小さいか大きいか）が必要です。

確かに、特定の値でノードを検索することはできますが、親を知らない場合は葉ではないノードをどのように削除できますか？

ノードによって提供される情報を介して親を知っていても、左のサブツリーの最小値をどのように決定したら、それを削除してノードに配置しますか？

私はあなたがFSAにあまりにも多くを求めていると思います。

Answer 3

私はそれを行うことができる一般的なlangugaeを知りませんが、あなたはXPathのようなものを探しているようです。

Answer 4

パターンベースのツリー書き換えにはTXLがあります。パターンと書き換え

ツリーはまた、ボトムアップツリー書き換え、グーグルBURS又はBURGとそのようなANTLR

コード生成などのパーサーツールキットを用いて行われます。

Answer 5

This記事には、再帰的なPerl正規表現についてのヒントがいくつか掲載されていますが、正直なところ、この方法ではツリー構造が近づくのはまれです。

より一般的には、正規マシンを使用してツリー内の特定のノードを解析するステートマシンスタイルのパーサーを作成します。

Expatおそらく良い例です。

Answer 6

Scala、F＃、Erlang、Haskellなどの言語で提供されるパターンマッチングは、再帰で使用すると木などのデータ構造を簡潔に操作するように設計されています。

hereは、Scalaでpattrenのマッチングができることを非常に高いレベルで示しています。示された例は実際に正当なパターンマッチングをしません。

ウィキペディアには、パターンマッチングの参照がいくつかあります。 Hereおよびhere。

Answer 7

XSLTは答えとして出てこなかったと私は多少驚いています。確かに、私はそれが特にエレガントな言語だとは思っていません。ほとんどの既存のソリューションは、パターンマッチングではなく手続き的アプローチを優先する傾向があり、XMLがXMLに適用されているという理由だけで盲目的に適用されてしまいますそれは法案に適合します。しかし、その正式な表現は非常に冗長ですが、...