Parse chaîne dans une structure d'arbre?

Question

J'essaye de comprendre comment analyser une chaîne dans ce format dans une arborescence comme la structure de données de profondeur arbitraire.

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

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

J'ai essayé de jouer avec des expressions régulières pour cela (tels que # « {([^ {}] *)} »), mais tout ce que j'ai essayé semble « aplatir » l'arbre dans une grande liste de listes. Je pourrais aborder cela sous le mauvais angle, ou peut-être une regex n'est tout simplement pas le bon outil pour le travail.

Merci pour votre aide! Ne pas utiliser d'expressions régulières pour cette tâche.

Answer 1

Une méthode plus simple serait de décrire votre chaîne avec une grammaire (BNF ou EBNF), puis écrire un analyseur pour analyser la chaîne en fonction de la grammaire. Vous pouvez générer un arbre d'analyse à partir de votre EBNF et BNF et vous vous retrouvez naturellement avec une structure arborescente.

Vous pouvez commencer avec quelque chose comme ceci:

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

Note: J'ai écrit ce rapidement, et il peut ne pas être tout à fait correct. Mais cela devrait vous donner une idée.

Answer 2

si vous voulez un hack rapide:

• remplacer les {caractères avec [
• remplacer les} caractères avec]
• remplacer le | caractères avec des espaces
• espérons que vous n'avez pas d'entrée avec des espaces.

read il en sorte qu'il apparaît comme des tableaux imbriqués. Ps: Je suis d'accord qu'un reg-ex ne peut pas faire cela.

pss: set * lecture eval * false (vous ne voulez pas l'entrée en cours d'exécution, il est auto)

Answer 3

Essayer de faire correspondre le tout avec une seule expression régulière ne va pas vous prendre trop , puisque les expressions régulières sortent au plus une liste de positions de sous-chaînes correspondantes, rien de semblable à un arbre. Vous voulez un lexer ou une grammaire qui ressemble à ceci:

Divisez l'entrée en jetons - morceaux atomiques comme '{', '|', et 'monde', puis traitez ces jetons dans l'ordre. Commencez avec un arbre vide avec un seul noeud racine.

Chaque fois que vous trouvez {, créez et accédez à un noeud enfant.

Chaque fois que vous trouvez |, créez et accédez à un nœud frère.

Chaque fois que vous trouvez }, allez au nœud parent.

Chaque fois que vous trouvez un mot, placez ce mot dans le nœud feuille courant.

Answer 4

Vous pouvez utiliser amotoen pour construire la grammaire et analyser ceci:

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

Résultat:

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 ""}]} 

post-scriptum C'est l'une de mes premières grammaires et ça peut être mieux. Voir aussi http://en.wikipedia.org/wiki/Parsing_expression_grammar