Ocaml parsing a string to create a tree

Question

I have a problem with this:

How to quickly print a tree structure in a row in Ocaml?

But on the contrary, I already have a string and you want to parse it to be a tree.

For example, I have

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

and I have a line like 1 + 2 * 3 + 4 (slightly different from the link above, suppose * has a higher procedure than + )
Then I want my result to be an expression like Prod(Plus(1,2), Plus(3, 4))

I found another link that could talk about this, but not sure if this is the way to make my problem:

Parsing grammars using OCaml

Please share some ideas, thanks.

Answer 1

This is a standard parsing problem: found in all compilers / interpreters, etc. There are several ways to attack this problem, which basically boils down to the following:

• Write your own recursive descent parser
• Use a parser generated by a parser generator

It looks like you're working on where you need the abstract syntax tree (the "tree" you mention in the problem). You can easily use the OCaml parser generator to perform such tasks; Menhir can be a good one . Although you can also write your own parser using a tool such as Menhir or ocamlyacc to do this for you, it is a very versatile and quick solution (compared to messy handling of non-LL (1) things in a simple recursive descent parser) .

Answer 2

The OCaml distribution contains an ocamlyacc tool for doing exactly what you need (other tools exist, as Christopher pointed out).

For a nice explanation of ocamlyacc see, for example, this tutorial and where the parser is defined for a small expression language (similar to yours).