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

尝试用单个正则表达式匹配整个内容不会让你走得太远，因为正则表达式最多输出匹配子字符串位置的列表，而不是树状的。你需要一个词法分析器或语法来做这样的事情：

将输入划分为标记 - 诸如“{”、“|”和“世界”之类的原子片段，然后按顺序处理这些标记。从具有单个根节点的空树开始。

每次找到{，创建并转到一个子节点。

每次找到|，创建并转到兄弟节点。

每次找到}时，向上到父节点。

每次找到一个单词时，将该单词放入当前叶节点。

于 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这是我的第一个peg语法之一，它可以更好。另见http://en.wikipedia.org/wiki/Parsing_expression_grammar

于 2010-10-11T12:09:20.883 回答