将字符串解析为树结构？

Question

我试图弄清楚如何将这种格式的字符串解析成一个像任意深度的数据结构的树.

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

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

我已经试过了一些正则表达式玩这个(如#"{([^ {}]*)}"),但我什么都尝试过,似乎"扁平化"树到列表的大名单.我可能从错误的角度接近这个,或者正则表达式不适合这项工作.

谢谢你的帮助!

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"

注意:我很快写了这个,所以它可能不完全正确.但它应该给你一个想法.