cadena de análisis sintáctico para hacer Ocaml árbol

Question

Tengo un problema similar a este:

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

Pero de una manera opuesta, que ya tengo una cadena y quiero analizar de nuevo a ser un árbol.

Por ejemplo, tengo

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

y tengo una cadena como 1 + 2 * 3 + 4 (un poco diferente del enlace anterior, asumir * tiene procedencia más alta que +)
Entonces quiero que mi resultado ser un tipo expr Prod(Plus(1,2), Plus(3, 4))

me encontré con otro vínculo que pudiera hablar de esto, pero no está seguro de si se trata de una forma de hacer mi problema:

Parsing grammars using OCaml

Por favor, comparta algunas ideas, gracias.

Answer 1

Se trata de un problema de análisis estándar: enfrentado en todos los compiladores/intérpretes/etc ... Hay un número de maneras de atacar este problema, que básicamente se reducen a lo siguiente:

• Escriba su propia recursiva analizador descenso
• Utilizar un analizador generado a partir de un generador de analizadores sintácticos

suena como lo que está trabajando es algo donde se necesita un árbol de sintaxis abstracta (el "árbol" se menciona en el problema). Puede usar fácilmente un generador de analizador OCaml para lograr tales cosas, uno bueno sería Menhir. Si bien también puede escribir su propio analizador, usar una herramienta como Menhir o ocamlyacc para hacerlo por usted es una solución muy versátil y rápida (en comparación con meterse con el placer de lidiar con cosas que no son LL (1) en un simple analizador de descenso recursivo).

Answer 2

La distribución OCaml contiene ocamlyacc una herramienta para hacer exactamente lo que necesita (existen otras herramientas, como señaló Kristopher).

Para una buena explicación de ocamlyacc, consulte por ejemplo this tutorial y related example donde se define un analizador para un lenguaje de expresiones pequeñas (similar al suyo).