6

この形式の文字列を任意の深さのデータ構造のようなツリーに解析する方法を理解しようとしています。

"{{Hello big|Hi|Hey} {world|earth}|{Goodbye|farewell} {planet|rock|globe{.|!}}}"

[[["Hello big" "Hi" "Hey"]
  ["world" "earth"]]
 [["Goodbye" "farewell"]
  ["planet" "rock" "globe" ["."
                            "!"]]]]

このためにいくつかの正規表現（＃ "{（[^ {}] *）}"など）を試してみましたが、試したすべてのことで、ツリーが「フラット化」されてリストの大きなリストになっているようです。間違った角度からこれにアプローチしている可能性があります。あるいは、正規表現がその仕事に適したツールではない可能性があります。

ご協力いただきありがとうございます！

4

4 に答える 4

9

このタスクには正規表現を使用しないでください。より簡単な方法は、文字列を文法 (BNF または EBNF) で記述してから、文法に従って文字列を解析するパーサーを作成することです。EBNF と BNF から解析ツリーを生成できるため、自然にツリー構造になります。

次のようなものから始めることができます。

element      ::= element-type, { ["|"], element-type }
element-type ::= primitive | "{", element, "}"
primitive    ::= symbol | word
symbol       ::= "." | "!"
word         ::= character { character }
character    ::= "a" | "b" | ... | "z"

注: ざっと書いたので、完全に正しいとは限りません。しかし、それはあなたにアイデアを与えるはずです。

于 2010-09-29T22:39:30.823 に答える
4

全体を 1 つの正規表現で一致させようとしても、うまくいきません。正規表現は、一致する部分文字列の位置のリストを出力するだけで、ツリーのようなものは何もないからです。次のようなことを行うレクサーまたは文法が必要です。

入力をトークン ('{'、'|'、'world' などのアトミック ピース) に分割し、それらのトークンを順番に処理します。ルート ノードが 1 つの空のツリーから始めます。

を見つけるたび{に、子ノードを作成して移動します。

を見つけるたび|に、兄弟ノードを作成して移動します。

を見つけるたび}に、親ノードに移動します。

単語を見つけるたびに、その単語を現在のリーフ ノードに配置します。

于 2010-09-29T22:46:53.587 に答える
3

クイックハックが必要な場合：

  • { 文字を [ に置き換えます
  • } 文字を ] に置き換えます
  • | を置き換えます。スペースを含む文字
  • スペースを入力しないでください。

readネストされた配列として表示されます。

ps:正規表現ではこれができないことに同意します。

pss: * read-eval * を false に設定します (入力を自分自身で実行する必要はありません)

于 2010-09-29T22:45:08.637 に答える
1

amotoenを使用して文法を構築し、これを解析できます。

(ns pegg.core
  (:gen-class)
  (:use
   (com.lithinos.amotoen
    core string-wrapper))
  (:use clojure.contrib.pprint))

(def input "{{Hello big|Hi|Hey} {world|earth}|{Goodbye|farewell} {planet|rock|globe{.|!}}}")

(def grammar
     {
      :Start :List
      :ws #"^[ \n\r\t]*"
      :Sep "|"
      :String #"^[A-Za-z !.]+"
      :Item '(| :String :List)
      :Items [:Item '(+ [:Sep :Item])]
      :List [:ws "{" '(* (| :Items :Item)) "}" :ws]
      })

(def parser (create-parser grammar))

(defn parse
  [^String input]
  (validate grammar)
  (pprint (parser (wrap-string input))))

結果：

pegg.core> (parse input)
{:List [{:ws ""} "{" ({:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "Hello big"}} ([{:Sep "|"} {:Item {:String "Hi"}}] [{:Sep "|"} {:Item {:String "Hey"}}])]}) "}" {:ws " "}]}} {:Items [{:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "world"}} ([{:Sep "|"} {:Item {:String "earth"}}])]}) "}" {:ws ""}]}} ([{:Sep "|"} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "Goodbye"}} ([{:Sep "|"} {:Item {:String "farewell"}}])]}) "}" {:ws " "}]}}])]} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "planet"}} ([{:Sep "|"} {:Item {:String "rock"}}] [{:Sep "|"} {:Item {:String "globe"}}])]} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "."}} ([{:Sep "|"} {:Item {:String "!"}}])]}) "}" {:ws ""}]}}) "}" {:ws ""}]}}) "}" {:ws ""}]}

PS これは私の最初のペグ文法の 1 つであり、より良いものになる可能性があります。http://en.wikipedia.org/wiki/Parsing_expression_grammarも参照してください。

于 2010-10-11T12:09:20.883 に答える