将字符串解析为树形结构？

Question

我正在尝试弄清楚如何将一个以此格式表示的字符串解析为任意深度的树形数据结构。

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

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

我尝试使用一些正则表达式进行匹配（例如#"{([^{}]*)}"），但是我尝试过的所有方法似乎都将树形结构“平铺”成了一个大型列表。 我可能从错误的角度来处理这个问题，或者正则表达式只是不适合这项工作。

感谢您的帮助！

- erikcw

Answer 1

不要使用正则表达式来完成这个任务。更简单的方法是用语法（BNF或EBNF）描述您的字符串，然后编写解析器根据语法解析字符串。您可以从EBNF和BNF生成解析树，因此您自然会得到一棵树形结构。

您可以从以下内容开始：

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

注意：我很快地写了这篇文章，所以可能不完全正确，但它应该能让你有个大概的思路。

- Vivin Paliath

---

那么，在拥有了语法之后，需要使用解析器生成器根据这个语法生成解析器，是吗？此外，应该将句子输入解析器，然后才能产生树形结构，对吧？ - Bikash Gyawali

@Bikash - 是的和不是。如果你想的话，你可以使用解析器生成器（如yacc或bison），或者你可以编写自己的递归下降解析器（它非常简单）。如果你使用yacc或bison，你需要编写实际构建树的操作。我认为yacc/bison本身并没有给你树。它们只是识别语法。 - Vivin Paliath

Answer 2

尝试使用单个正则表达式匹配整个内容是不太可行的，因为正则表达式最多只能输出匹配子字符串的位置列表，没有树形结构。您需要一个词法分析器或语法分析器来执行以下操作：

将输入分成标记 - 原子片段，如 '{'， '|' 和 'world'，然后按顺序处理这些标记。从一个带有单个根节点的空树开始。

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

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

每次找到 } 时，返回到父节点。

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

- aschepler

---

那么这如何处理 {{text} {text}} 这种情况呢？我认为他的字符串有点模糊不清...所有兄弟节点或许应该用 "|" 分隔。 - Vivin Paliath

是的，这个例子有一些令人困惑的地方。像 Hey 和 world 之间的 } { 以及 earth 和 Goodbye 之间的 }|{ 在树的不同深度上具有兄弟关系。我只能猜测为什么会这样。(我自己算法中另一个问题是：如果 { 紧接在单词后面，比如对于 '地球'?)所以这不是一个完整的解决方案，但是"类似于"它应该可以适应解决这种类型的问题。 - aschepler

Answer 3

如果您想要一个快速的技巧：

- 将 { 字符替换为 [ - 将 } 字符替换为 ] - 将 | 字符替换为空格 - 希望您不会输入带有空格的内容。

将其读入，以便它呈现嵌套数组。

附言：我同意正则表达式无法做到这一点。

附言2：将 * read-eval * 设置为 false（您不希望输入运行自己）。

- Arthur Ulfeldt

---

他的示例字符串实际上在其中一个段落中包含了一个空格。 - Rayne

@Rayne：那是编辑进去的。原帖中没有在任何结果叶字符串中包含空格。 - aschepler

哦，我也曾考虑过这个解决方案，直到我看到了空间。然后我哭着入睡了。 - Rayne

Answer 4

您可以使用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 ""}]}

附言：这是我第一次使用PEG语法，可以更好。另请参阅http://en.wikipedia.org/wiki/Parsing_expression_grammar

- edbond