O'Caml stringa di analisi per fare albero

Question

Ho un problema simile a questo:

How to print a tree structure into a string fast in Ocaml?

Ma in un modo opposto, che ho già una stringa e voglia di analizzare di nuovo a essere un albero.

Per esempio, ho

type expr = 
    Number of int 
|Plus of expr*expr 
|Prod of expr*expr 

e ho una stringa come 1 + 2 * 3 + 4 (un po 'diverso dal link sopra, assumere * ha procedence superiore +)
Poi voglio che il mio risultato essere un tipo espr Prod(Plus(1,2), Plus(3, 4))

ho trovato un altro link che potrebbero parlare di questo, ma non è sicuro se si tratta di un modo di fare il mio problema:

Parsing grammars using OCaml

Si prega di condividere alcune idee, grazie.

Answer 1

Questo è un problema di analisi di serie: di fronte a tutti i compilatori/interpreti/etc ... Ci sono un certo numero di modi per attaccare questo problema, che bollire in fondo verso il seguente:

• Scrivi la tua ricorsiva discesa parser
• Utilizzare un parser generato da un generatore di parser

suona come quello che si sta lavorando è qualcosa in cui è necessario un Abstract Syntax albero (l ' "albero" si parla nel problema). Puoi facilmente usare un generatore di parser di OCaml per fare queste cose, una buona sarebbe Menhir. Mentre puoi anche scrivere il tuo parser, usare uno strumento come Menhir o ocamlyacc per farlo è una soluzione molto versatile e veloce (rispetto a scherzando con la pochezza di trattare con cose non LL (1) in un semplice parser ricorsivo di discendenza).

Answer 2

La distribuzione di OCaml contiene ocamlyacc uno strumento per fare esattamente quello che ti serve (esistono altri strumenti, come ha sottolineato Kristopher).

Per una bella spiegazione di ocamlyacc, vedere ad esempio this tutorial e related example dove è definito un parser per un linguaggio di piccole espressioni (simile al proprio).