parsing - テキストトランスフォーマーの書き方は？

Question

簡単に解析できるテキストがあるとします。テキストと特別な識別子で構成されます。解析後、テキストに対応するトークンとテキスト内の特別な識別子のリストを取得します。

私が抱えている問題は、このトークンリストから他の形式に変換するにはどうすればよいですか？

この問題への取り組み方がわかりません。

解析ツリーを構築しようとしましたが、次に何をすべきかわかりません。

この構文解析の一般的な問題についてアドバイスしてください。

Answer 1

トークン ストリームを取得したら、パーサー ジェネレーターを使用して言語の文法を指定することにより、それを解析ツリーに変換できます。

使用するプログラミング言語に応じて、次のパーサー ジェネレーターを調べることができます。

C/C++ - yacc

Java - ANTLR (JavaCC、SableCC も)

Python - PLY (Python Lex / Yacc)

OCaml - ocamlyacc

文法についてよくわからない場合は、選択したパーサー ジェネレーターのドキュメントを読めば十分に理解できるはずです。

パーサーが完了すると、トークン ストリームを取得し、中間表現を使用してツリーを構築します。これは、言語のさまざまな部分を表すために定義するタイプです (テキストや言及した特別な識別子など)。その後、ツリーを好きなように操作できます。

編集：あなたのコメントに応えて-あなたが抱えている問題を正確に伝えることができないため、どのレベルの回答を提供するかはよくわかりません。まず、ツリー データ構造に精通していますか? もしそうなら、木の高さを見つける単純な再帰アルゴリズムを書く方法、または深さ優先検索を実行する方法を知っていますか? ツリーは情報を整理するための単なる手段であることを忘れないでください。その情報をどうするかは完全にあなた次第です。

異種ツリー (つまり、ノードのタイプが異なるツリー) にアルゴリズムを適用するための一般的な設計パターンは、Visitor パターンです。すでにツリーに精通している場合は、お気に入りの言語で Visitor パターンの例を調べることができます。ただし、概念が初めての場合は、練習用に単純なアルゴリズムから始めることを強くお勧めします。