Scorretta stringa in una struttura ad albero?

Question

Sto cercando di capire come analizzare una stringa in questo formato in una struttura ad albero come dati di profondità arbitraria.

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

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

Ho provato a giocare con alcune espressioni regolari per questo (come # "{([^ {}] *)}"), ma tutto quello che ho provato sembra "appiattire" l'albero in una grande lista di liste. Potrei avvicinarmi a questo da un angolo sbagliato, o forse una regex non è lo strumento giusto per il lavoro.

Grazie per il vostro aiuto!

Answer 1

Non utilizzare espressioni regolari per questa attività. Un metodo più semplice sarebbe quello di descrivere la stringa con una grammatica (BNF o EBNF) e quindi scrivere un parser per analizzare la stringa in base alla grammatica. È possibile generare un albero di analisi da EBNF e BNF e quindi si finisce con una struttura ad albero.

Si può iniziare con qualcosa di simile:

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

Nota: ho scritto questo in fretta, e quindi potrebbe non essere del tutto corretto. Ma dovrebbe darti un'idea.

Answer 2

se volete un trucco veloce:

• sostituire i caratteri {con [
• sostituire i caratteri} con]
• sostituire l'| caratteri con spazi
• spero che tu non entri con gli spazi.

read in modo che si presenti come matrici annidate.

ps: Sono d'accordo che un reg-ex non può farlo.

pss: set * read-eval * su false (non si vuole l'ingresso di esecuzione è di per sé)

Answer 3

cercando di abbinare il tutto con una sola espressione regolare non sta per arrivare troppo lontano , poiché le espressioni regolari generano al massimo un elenco di posizioni di sottostringa corrispondenti, nessuna struttura ad albero. Vuoi un lexer o una grammatica che faccia qualcosa del genere:

Dividi l'input in token - pezzi atomici come '{', '|', e 'world', quindi elabora quei token in ordine. Inizia con un albero vuoto con un singolo nodo radice.

Ogni volta che si trova {, creare e passare a un nodo figlio.

Ogni volta che trovi |, crea e vai a un nodo fratello.

Ogni volta che trovi }, vai al nodo genitore.

Ogni volta che trovi una parola, metti quella parola nel nodo foglia corrente.

Answer 4

È possibile utilizzare amotoen per costruire la grammatica e analizzare questo:

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

Risultato:

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. Questa è una delle mie prime grammatiche di peg e può essere migliore. Vedi anche http://en.wikipedia.org/wiki/Parsing_expression_grammar