xml - F# でのパターンマッチング XML

Question

新しいライブラリ: XParsec

この質問は、F# 3.0 でのストリームと型に依存しない、非線形で拡張可能なパーセクの実装につながりました - FParsec に触発され、Char と線形ストリームから解放され、簡素化されました: http://corsis.github.com/XParsec/

パターン

1 = < font=?'Bold' bbox=F'l ..' s      >                       ;       < ~s >*
2 = < font=!'Bold' bbox=F'l ..' s=?'(' > | [ 1.l < 2.l ]       ;       < ~s >*
3 = < font=!'Bold' bbox=F'l ..' s=?')' > | [ 1.l < 3.l ]

どこ

element names are left unspecified
font, bbox and s are attributes

V = string, N = string

?  :: V -> bool                -- value          contains string
!  :: V -> bool = not . (?)    -- value does not contain  string
~  :: N -> bool                -- value of attribute N is empty or whitespace
F  :: V -> [(N, float)]        -- extracts a list of named floats from value
RM :: V -> bool                -- value matches regular expression
[] :: [bool]                   -- list of conditions

コード

open System.Xml.Linq
open System.Collections.Generic

let inline (-?-)  a b = (a : string).Contains b
let inline (~~) s = s |> String.IsNullOrWhiteSpace
let inline (!>) x = ( ^a : (static member op_Implicit : ^b -> ^a) x )

let inline (@)  (x : XElement) n   = let a = x.Attribute(!> n) in if a <> null then a.Value else String.Empty
let inline (@<) (x : XElement) n v = x.SetAttributeValue(!> n, v)

type XE = XElement IEnumerator

let inline bbox e    = (e @ "bbox") |> fun s -> s.Split [| ' ' |] |> Seq.map float |> Seq.toList
let inline left bbox = match bbox with l::_ -> l | _ -> nan

let mark n = let id = Guid.NewGuid() in Seq.iter <| fun e -> e @< "class-" + n <| id

let speaker  (n : XE) =
  let  c1 = n.Current
  if   c1 @? "font" <| "Bold"
  then let  l1 = c1 |> bbox |> left
       while n.MoveNext() && ~~(n.Current @ "s") do ()
       let  c2 = n.Current
       if  (c2 @ "font") -?- "Bold" |> not
       then let  l2 = c2 |> bbox |> left
            if   l1 < l2
            then let  s2 = c2 @ "s"
                 if        s2 -?- "("
                 then if   s2 -?- ")"
                      then [c1; c2] |> mark "speaker"
                      while n.MoveNext() && ~~(n.Current @ "s") do ()
                      let  c3 = n.Current
                      if  (c3 @ "font") -?- "Bold" |> not
                      then let  l3 = c3 |> bbox |> left
                           if   l1 < l3
                           then if   (c3 @ "s") -?- ")"
                                then [c1; c2; c3] |> mark "speaker"  


let test (x : XElement) =
  let spans = x.Descendants(!> "span") |> Seq.toArray
  for i = 29 to spans.Length - 1 do
    let n = (spans |> Seq.skip i).GetEnumerator()
    n.MoveNext() |> ignore
    speaker n

入力

<doc>
<block bbox="63.2999 550.846 246.865 561.875">
  <line bbox="63.2999 550.846 246.865 561.875">
    <span bbox="63.2999 550.846 189.001 561.875" font="TimesNewRoman,Bold" size="9.96" s="Dr. Frank-Walter Steinmeier " />
    <span bbox="189 550.846 246.865 561.875" font="TimesNewRoman" size="9.96" s="(SPD)  . . . . . ." />
  </line>
</block>
<block bbox="63.2999 567.766 246.875 578.796">
  <line bbox="63.2999 567.766 246.875 578.796">
    <span bbox="63.2999 567.766 136.004 578.796" font="TimesNewRoman,Bold" size="9.96" s="Rainer Brüderle " />
    <span bbox="136.02 567.766 246.875 578.796" font="TimesNewRoman" size="9.96" s="(FDP) . . . . . . . . . . . . . . . . ." />
  </line>
</block>
<block bbox="63.2999 584.626 250.351 651.456">
  <line bbox="63.2999 584.626 246.826 595.656">
    <span bbox="63.2999 584.626 152.105 595.656" font="TimesNewRoman,Bold" size="9.96" s="Sahra Wagenknecht " />
    <span bbox="152.16 584.626 246.826 595.656" font="TimesNewRoman" size="9.96" s="(DIE LINKE)  . . . . . . ." />
  </line>
  <line bbox="63.2999 600.362 250.351 613.34">
    <span bbox="63.2999 601.546 139.327 612.576" font="TimesNewRoman,Bold" size="9.96" s="Siegfried Kauder " />
    <span bbox="139.38 601.546 247.762 612.576" font="TimesNewRoman" size="9.96" s="(Villingen-Schwenningen) " />
    <span bbox="247.861 600.362 250.351 613.34" font="Symbol" size="9.96" s=" " />
  </line>
  <line bbox="74.6404 612.526 246.911 623.556">
    <span bbox="74.6404 612.526 246.911 623.556" font="TimesNewRoman" size="9.96" s="(CDU/CSU) . . . . . . . . . . . . . . . . . . . . . . . ." />
  </line>
  <line bbox="63.2999 628.202 191.909 641.18">
    <span bbox="63.2999 629.386 126.374 640.416" font="TimesNewRoman,Bold" size="9.96" s="Jürgen Trittin " />
    <span bbox="126.419 629.386 189.433 640.416" font="TimesNewRoman" size="9.96" s="(BÜNDNIS 90/" />
    <span bbox="189.419 628.202 191.909 641.18" font="Symbol" size="9.96" s=" " />
  </line>
  <line bbox="74.6394 640.426 246.813 651.456">
    <span bbox="74.6394 640.426 246.813 651.456" font="TimesNewRoman" size="9.96" s="DIE GRÜNEN)  . . . . . . . . . . . . . . . . . . . . ." />
  </line>
</block>
</doc>

出力

<doc>
<block>
  <line>
    <span font="TimesNewRoman,Bold" size="9.96" s="Dr. Frank-Walter Steinmeier " class-speaker="1f2e4dca-80d5-4c5e-91b6-6bd2e4a8acaf" />
    <span font="TimesNewRoman" size="9.96" s="(SPD)  . . . . . ." class-speaker="1f2e4dca-80d5-4c5e-91b6-6bd2e4a8acaf" />
  </line>
</block>
<block>
  <line>
    <span font="TimesNewRoman,Bold" size="9.96" s="Rainer Brüderle " class-speaker="eaa75d02-0ac6-4480-bcbe-f17bddfe6e81" />
    <span font="TimesNewRoman" size="9.96" s="(FDP) . . . . . . . . . . . . . . . . ." class-speaker="eaa75d02-0ac6-4480-bcbe-f17bddfe6e81" />
  </line>
</block>
<block>
  <line>
    <span font="TimesNewRoman,Bold" size="9.96" s="Sahra Wagenknecht " class-speaker="6b193f23-9b8b-4b37-9118-d8488fba25a2" />
    <span font="TimesNewRoman" size="9.96" s="(DIE LINKE)  . . . . . . ." class-speaker="6b193f23-9b8b-4b37-9118-d8488fba25a2" />
  </line>
  <line>
    <span font="TimesNewRoman,Bold" size="9.96" s="Siegfried Kauder " class-speaker="a0162e4e-1167-412a-ac11-ac13ef1aa46e" />
    <span font="TimesNewRoman" size="9.96" s="(Villingen-Schwenningen) " class-speaker="a0162e4e-1167-412a-ac11-ac13ef1aa46e" />
    <span font="Symbol" size="9.96" s=" " />
  </line>
  <line>
    <span font="TimesNewRoman" size="9.96" s="(CDU/CSU) . . . . . . . . . . . . . . . . . . . . . . . ." class-speaker="a0162e4e-1167-412a-ac11-ac13ef1aa46e" />
  </line>
  <line>
    <span font="TimesNewRoman,Bold" size="9.96" s="Jürgen Trittin " class-speaker="81fd6735-c57f-464b-a08f-7e7cb3bccfa8" />
    <span font="TimesNewRoman" size="9.96" s="(BÜNDNIS 90/" class-speaker="81fd6735-c57f-464b-a08f-7e7cb3bccfa8" />
    <span font="Symbol" size="9.96" s=" " />
  </line>
  <line>
    <span font="TimesNewRoman" size="9.96" s="DIE GRÜNEN)  . . . . . . . . . . . . . . . . . . . . ." class-speaker="81fd6735-c57f-464b-a08f-7e7cb3bccfa8" />
  </line>
</block>
</doc>

質問

簡潔なパターン宣言からコードの実行まで自動的に移行するために、次のことを考えています。

FParsec を使用して AST へのパターン宣言を解析する
ASTを評価する

しかし、私が何かをする前に、私は知りたいです:

AST に頼らずに、F# 関数とコンポジションを直接使用してコードを宣言するための (適用可能な) EDSL (/その一部) を誰でも作成できますか?
XML で同様のパターンマッチが可能なライブラリはありますか?
私のアプローチに関するコメントはありますか？

score 4 · Accepted Answer

質問の内容がよくわかりません。既に存在する XML 用の既存のパターンマッチング言語を使用したいですか (あなたの例のように)、それとも一般的に XML 処理について質問していますか?

LINQ to XML Jack P. が言ったように、おそらく F# での XML 処理の最良の選択肢は、標準Seq関数をそのまま使用することです。これは少し長くなりますが、非常に読みやすいです。

XPathもう 1 つの方法は、XML でノードを選択するための非常に簡潔な (そして完全に標準的な) 方法である XPath を使用することです。たとえば、指定した属性値を持つノードを選択するには、次のように記述できます。

#r "System.Xml.Linq"
open System.Xml.Linq
open System.Xml.XPath

let doc = XDocument.Parse("<r><a n=\"f\">foo</a><a n=\"b\">bar</a></r>")
doc.XPathSelectElement("//a[@*='f']").Value

ドメイン固有言語独自の簡潔な言語を記述したい場合は、必ずしもカスタムパーサーなどを使用する必要はありません。F# 演算子を巧妙に使用するだけで、かなり遠くまで行くことができます。このF# スニペットはその好例です。次のようなものを書くことができます：

printfn "Matches: %A" (!/foo/bar/(baz@=true)/quux/= x)
printfn "Doesn't Match: %A" (!/foo/bar/(baz@=false)/quux/= x)
printfn "Values: %A" (!/foo/bar/quux/(baz@=42)/! x)

パターンは F# コンパイラによって型チェックされることに注意してください。

score 2 · Accepted Answer

IMO、このようなものを実装できる最良の方法は、それを XLinq (LINQ-to-XML) の上に重ねることです。すべてのパターンマッチングロジックを「手動で」実装する場合と比較して、コーディングが簡単で、保守が容易で、同等の (より優れていない場合でも) パフォーマンスが得られる可能性があります。

DSL を使用して、照合するパターンを定義することもできます。基本的に、FParsec を使用して DSL を解析して AST に変換し、AST をトラバースして同等の LINQ クエリに変換します (「」を参照System.Linq.Expressions namespace)。クエリを表す LINQ 式を取得したら、それを任意の数のに適用してXDocument、パターンマッチを実行します。

また、機能設計の観点から XML プログラミングについて説明している Erik Meijer の論文XLinq: XML Programming Refactored (The Return Of The Monoids)もお読みください。

score 1 · Accepted Answer

質問 2 へ:

私は F# コードを理解していないと思いますが、Pascal でxml パターンマッチングライブラリを作成しました ( online example、cli example )。(ただし、パターンを「テンプレート」と呼んでいますが、xml ノードを選択するだけで、変更はしません)。

私のテンプレートでは、これ

<doc>
<block>
  <line>
    <span>{.}</span>*
  </line>*
</block>*
</doc>

入力内のすべてのスパンに一致します。（そうなるように<span>{.}</span>*）

または別の例:

<doc>
<block>
  <line>
    <span font="TimesNewRoman,Bold">{@s}</span>*
  </line>*
</block>*
</doc>

話者の名前を含む属性と一致します。

xml - F# でのパターン マッチング XML

新しいライブラリ: XParsec

パターン

コード

入力

出力

質問

3 に答える 3

Related

Reference

xml - F# でのパターンマッチング XML