BNF文法をJavaに変換する

Question

この単純な（再帰的な）文法をJavaにどのように変換できますか？

C --> a | not C | C and C | C or C ; 

この質問は、オブジェクト指向のパラダイムを使用して、このシンプルな文法を、私は（JavaCCのかANTLRのような）文法を解析するために使用する必要がどのようなツールを意味しますが、モデルへの道はありません。

Answer 1

私はOOPを使ってこれをモデル化する単一の方法はないと考えています。これに近づく方法も同様に多くあります。以下は、これがコード内でどのように見えるかについて考えるための合理的な戦略の1つです。

通常、式を解析するとき、目標は入力用の抽象構文ツリーを再構築することです。そのツリー構造は、可能な異なるプロダクションに基づいて異なるタイプのノードを持っています。そして、Javaでは多態型でそれらを表現するでしょう。たとえば、子クラスASTNodeの子クラスがANode,NotNode、AndNode、およびOrNodeの子クラスがあるとします。これらの最後の3つの型は、複合式を構成する部分式へのポインタを格納します。

これらの型を取得したら、入力を受け取り適切なツリーを構築するための何らかのパーサー（場合によってはスキャナ）を組み込む必要があります。異なる優先順位を持つ異なる演算子で構成される文法を調べているので、構文解析を行うにはDijkstra's shunting-yard algorithmのような単純な先行構文解析プログラムを使用できます。このアルゴリズムは比較的簡単に実装できます。

この時点では、実際にあなたがASTで何をしたいかによって決まります。たとえば、入力が提供されているかどうかによって式を評価する場合は、という抽象メソッドをASTNode型に追加して、それぞれの派生型に適切な操作を実行する実装を提供できます。ビジターパターンを使用して、ASTを歩き回り、各ステップで適切な操作を実行する訪問者を構築することも検討できます。

これは役に立つかもしれませんが、私はしばしば私がよく教えるクラスの命題論理の真理値表を生成するためにあなたが見ているものと非常によく似たものを書きました。ツール自体はavailable hereであり、よくコメントされているソースファイルはavailable hereです。これはJavaではなくJavaScriptで書かれていますが、ASTノードタイプ、構文解析を行うシャントヤードアルゴリズム、および異なる式を評価するためのオーバーライドされたメソッドを示しています。

Answer 2

これは実際に特定のツールを言及しなくても非常に幅広い質問です。パーサーを実装するために選択した言語に応じて、さまざまな方法で文法の実装が行われる可能性があります。あなたがANTLRやJavaccを挙げたようなツールのソースは、他の人がツールやトップダウンパーサーを開発するために使ったテクニックをどのように実装したかを明らかにします。マニュアルに、公式言語仕様では、例えば ：言語の正確な記述が必要とされているところはどこでも彼らが適用されている

：

BNF

は、言語だけの構造を記述する正式な方法を与えるために使用されます、およびプログラミング言語理論に関する の教科書。

これは、プログラマが言語ツールとAPIで実装されている方法を決定するために、入力から期待されるものを分かりやすくするためだけに使用されるため、正規表現がjavaでもstringでもあなたの言語のパーサを生成するためのツールを使って作業しています。このツールは、この質問に答えることができます。