Разобрать строку в древовидную структуру?

Я пытаюсь понять, как разобрать строку в этом формате в древовидную структуру данных произвольной глубины.

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

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

Я пытался играть с некоторыми регулярными выражениями для этого (например, #"{([^{}]*)}" ), но все, что я пробовал, похоже, "сглаживает" дерево в большой список списков. Я мог подойти к этому с неправильной точки зрения, или, может быть, регулярное выражение просто не подходит для этой работы.

Спасибо за вашу помощь!


parsing clojure tree text-processing text-parsing
person erikcw    schedule 29.09.2010    source источник

Ответы (4)


arrow_upward
9
arrow_downward

Не используйте регулярные выражения для этой задачи. Более простым методом было бы описать вашу строку с помощью грамматики (BNF или EBNF), а затем написать синтаксический анализатор для анализа строки в соответствии с грамматикой. Вы можете сгенерировать дерево синтаксического анализа из ваших EBNF и BNF, и, таким образом, вы, естественно, получите древовидную структуру.

Вы можете начать с чего-то вроде этого:

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

Примечание: я написал это быстро, поэтому это может быть не совсем правильно. Но это должно дать вам представление.

person Vivin Paliath    schedule 29.09.2010
comment
Итак, после того, как у вас есть эта грамматика, необходимо использовать генератор синтаксических анализаторов для создания синтаксического анализатора на основе этой грамматики, не так ли? Далее парсер надо скормить предложением и тогда можно было бы получить дерево, нет? - person bikashg; 18.03.2011
comment
@Bikash - и да, и нет. Вы можете использовать генератор синтаксических анализаторов (например, yacc или bison), если хотите, или вы можете написать свой собственный синтаксический анализатор с рекурсивным спуском (это удивительно просто). Если вы используете yacc или bison, вам нужно написать действия, которые фактически построят дерево. Я не думаю, что yacc/bison сам по себе даст вам дерево. Они просто узнают грамматику. - person Vivin Paliath; 18.03.2011

arrow_upward
4
arrow_downward

Попытка сопоставить все это с помощью одного регулярного выражения не приведет вас слишком далеко, поскольку регулярные выражения выводят самое большее список совпадающих позиций подстрок, ничего древовидного. Вам нужен лексер или грамматика, которые делают что-то вроде этого:

Разделите ввод на токены — атомарные части, такие как «{», «|» и «мир», затем обработайте эти токены по порядку. Начните с пустого дерева с одним корневым узлом.

Каждый раз, когда вы найдете {, создайте и перейдите к дочернему узлу.

Каждый раз, когда вы находите |, создавайте и переходите к родственному узлу.

Каждый раз, когда вы находите }, поднимайтесь к родительскому узлу.

Каждый раз, когда вы находите слово, помещайте это слово в текущий конечный узел.

person aschepler    schedule 29.09.2010
comment
Как это относится к делу {{text} {text}}? Я думаю, что его строка неоднозначна... возможно, все одноуровневые узлы должны быть разделены символом | - person Vivin Paliath; 30.09.2010
comment
Да, в примере есть некоторые непонятные моменты. Похоже, что } { между Hey и world и }|{ между землей и Goodbye вызывают родственные отношения на разных глубинах дерева. Я мог только догадываться, почему это так. (Еще одна проблема, которую я заметил с моим собственным алгоритмом: что, если { стоит сразу после слова, например, для «глобуса»?) Так что это не полное решение, но что-то вроде этого должно быть адаптировано для решения этого типа проблемы. - person aschepler; 30.09.2010

arrow_upward
3
arrow_downward

если вы хотите быстрый взлом:

  • замените символы { на [
  • замените символы } на ]
  • заменить | символы с пробелами
  • надеюсь, вы не вводите пробелы.

read так что он выглядит как вложенные массивы.

ps: я согласен, что регулярное выражение не может этого сделать.

pss: установите для * read-eval * значение false (вы не хотите, чтобы ввод выполнялся сам по себе)

person Arthur Ulfeldt    schedule 29.09.2010
comment
Строка в его примере фактически включает пробел в одном из сегментов. - person Rayne; 30.09.2010
comment
@Rayne: Это было отредактировано. ОП не включал пробел ни в одну из полученных строк листьев. - person aschepler; 01.10.2010
comment
Ой. Я также рассматривал это решение, пока не увидел пространство. Потом я плакала, чтобы уснуть. - person Rayne; 01.10.2010

arrow_upward
1
arrow_downward

Вы можете использовать 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 ""}]}

P.S. Это одна из моих первых грамматик привязки, и она может быть лучше. См. также http://en.wikipedia.org/wiki/Parsing_expression_grammar.

person edbond    schedule 11.10.2010