parsing - ツリーを作成する Ocaml 解析文字列

Question

私はこれに似た問題を抱えています：

Ocamlでツリー構造を文字列に高速に出力するには?

しかし逆に、すでに文字列があり、それを解析してツリーに戻したいとします。

たとえば、私は

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

そして、私は 1+2*3+4 のような文字列を持っています (上記のリンクとは少し*異なり+ます
。Prod(Plus(1,2), Plus(3, 4))

これについて話している可能性のある別のリンクを見つけましたが、それが私の問題を解決する方法であるかどうかはわかりません:

OCaml を使用した文法の解析

いくつかのアイデアを共有してください、ありがとう。

Answer 1

OCaml ディストリビューションにはocamlyacc、まさに必要なことを行うためのツールが含まれています (Kristopher が指摘したように、他のツールも存在します)。

の優れた説明については、たとえば、このチュートリアルと関連する例ocamlyaccを参照してください。ここでは、小さな式言語 (あなたのものに似ています) のパーサーが定義されています。

Answer 2

これは標準的な構文解析の問題です: すべてのコンパイラ/インタープリターなどで直面しています.この問題を攻撃する方法はいくつかあります.

• 独自の再帰降下パーサーを作成する
• パーサー ジェネレーターから生成されたパーサーを使用する

あなたが取り組んでいるのは、抽象構文ツリー (問題で言及した「ツリー」) が必要な場所のようです。OCaml パーサー ジェネレーターを使用して、そのようなことを簡単に実現できます。Menhir が良いでしょう。 独自のパーサーを作成することもできますが、Menhir や ocamlyacc などのツールを使用してそれを行うことは、非常に用途が広く迅速な解決策です (単純な再帰降下で LL(1) 以外のものを処理する厄介なことをいじることと比較して)パーサー)。