¿Analizar cadena en una estructura de árbol?

Question

Estoy tratando de averiguar cómo analizar una cadena en este formato en un árbol como la estructura de datos de profundidad arbitraria.

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

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

He intentado jugar con algunas expresiones regulares para ello (como # "{([^ {}] *)}"), pero todo lo que he intentado parece "aplanar" el árbol en una gran lista de listas Podría estar acercándome a esto desde el ángulo equivocado, o tal vez una expresión regular simplemente no es la herramienta adecuada para el trabajo.

Gracias por su ayuda!

Answer 1

No use expresiones regulares para esta tarea. Un método más fácil sería describir su cadena con una gramática (BNF o EBNF) y luego escribir un analizador para analizar la cadena de acuerdo con la gramática. Puede generar un árbol de análisis desde su EBNF y BNF y así, naturalmente, termina con una estructura de árbol.

Puede comenzar con algo como esto:

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

Nota: Escribí esto para arriba rápidamente, y por lo que puede no ser del todo correcta. Pero debería darte una idea.

Answer 2

si quieres un corte rápido:

• reemplazar los caracteres con {[
• reemplazar los caracteres con}]
• reemplazar el | Caracteres con espacios
• Espero que no entres en espacios.

read en lo que aparece como matrices anidadas.

ps: Estoy de acuerdo en que un reg-ex no puede hacer esto.

pss: set-eval * * leer en false (no desea que la entrada de correr es uno mismo)

Answer 3

tratando de igualar todo con una sola expresión regular no se va a conseguir que demasiado , dado que las expresiones regulares generan como máximo una lista de posiciones de subcadenas coincidentes, nada parecido a un árbol. Desea un lexer o gramática que haga algo como esto:

Divida la entrada en tokens - piezas atómicas como '{', '|' y 'world', luego procese esos tokens en orden. Comience con un árbol vacío con un único nodo raíz.

Cada vez que encuentre {, cree e vaya a un nodo secundario.

Cada vez que encuentre |, cree e vaya a un nodo hermano.

Cada vez que encuentre }, vaya al nodo primario.

Cada vez que encuentre una palabra, coloque esa palabra en el nodo de hoja actual.

Answer 4

Puede utilizar amotoen para construir la gramática y analizar esto:

(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)))) 

Resultado:

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. Esta es una de mi primera gramática y puede ser mejor. También vea http://en.wikipedia.org/wiki/Parsing_expression_grammar