ANTLR のツリー パーサーとは何ですか? ツリー パーサーを作成する必要がありますか?
https://stackoverflow.com/questions/697755
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は、Java 環境で実行される ANTLR の C の小さなサブセット用のレクサー/パーサーを作成しています。私は言語文法の世界には慣れていません。多くの ANTLR チュートリアルでは AST (抽象構文ツリー) を作成します。作成する必要がありますか?またその理由は何ですか?
解決 2
見つけました この答え ANTLR を作成した Terence Parr が書いた jGuru に関する質問に対して。この説明はリンク先のサイトからコピーしました ここ:
パーサー内のアクションで実行できるのは、単純な、いわゆる構文指向の変換のみです。この種の翻訳では、解析のその時点ですでに確認されている情報の関数である構成要素のみを吐き出すことができます。ツリー パーサーを使用すると、中間フォームをたどってそのツリーを操作し、いくつかの翻訳フェーズを経て、新しい翻訳として簡単に出力できる最終フォームに徐々にモーフィングすることができます。
タイトルが「n 個の項目があります」という HTML ページを出力する単純な変換の問題を想像してください。n は入力ストリームで見つかった識別子の数です。ID は次のようにタイトルの後に出力する必要があります。
<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>
入力から
Dog
Cat
Velociraptor
では、文法内の単純なアクションを使用して、どのようにしてタイトルを計算できるのでしょうか?入力内容をすべて読まないとできません。さて、中間フォームが必要であることがわかりました。通常、入力構造を記録するため、私が見つけた AST が最適です。この場合、これは単なるリストですが、私の主張を示しています。
さて、ツリーは単純な翻訳以外には適していることがわかりました。AST がある場合、そこから出力を取得するにはどうすればよいでしょうか?単純な式ツリーを想像してください。1 つの方法は、ツリー内のノードを PlusNode、IntegerNode などの固有のクラスにすることです。次に、各ノードにそれ自体を出力するよう要求するだけです。入力の場合、3+4 ではツリーが得られます。
+ | 3 -- 4
そしてクラス
class PlusNode extends CommonAST {
public String toString() {
AST left = getFirstChild();
AST right = left.getNextSibling();
return left + " + " + right;
}
}
class IntNode extends CommonAST {
public String toString() {
return getText();
}
}
式ツリーを指定すると、 t.toString() を使用してそれをテキストに変換し直すことができます。それで、これの何が問題なのでしょうか？とてもうまくいきそうですよね？この場合はシンプルなのでうまく機能するように見えますが、この単純な例であっても、ツリー文法の方が読みやすく、PlusNode.toString() でコーディングした内容を正確に形式的に説明したものであると私は主張します。
expr returns [String r]
{
String left=null, right=null;
}
: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT {r=i.getText();}
;
特定のクラス (「異種 AST」) アプローチでは、実際には #(+ INT INT) の完全な再帰降下パーサーが toString() で手動でエンコードされることに注意してください。パーサー ジェネレーターを使用している人なら、これにはうんざりするはずです。;)
異種 AST アプローチの主な弱点は、コンテキスト情報に簡単にアクセスできないことです。再帰降下パーサーでは、コンテキストをパラメーターとして渡すことができるため、コンテキストに簡単にアクセスできます。また、文法を確認することで、どのルールが他のどのルールを呼び出すことができるか (たとえば、この式は WHILE 条件なのか IF 条件なのか) を正確に知ることができます。上記の PlusNode クラスは、誰が toString() メソッドを呼び出すかわからない、切り離された孤立した世界に存在します。さらに悪いことに、プログラマは、それを読んでも、どのコンテキストで呼び出されるのかを知ることができません。
要約すると、入力パーサーにアクションを追加すると、次のような非常に単純な変換が可能になります。
- 出力構成の順序は入力順序と同じです
- すべての構成要素は、吐き出す必要がある時点までに解析された情報から生成できます。
これを超えると、中間形式が必要になります。通常は AST が最適な形式です。文法を使用して AST の構造を記述することは、文法を使用して入力テキストを解析することに似ています。ANTLR のようなドメイン固有の高級言語による形式化された記述は、手動でコーディングされたパーサーよりも優れています。ツリー文法のアクションには非常に明確なコンテキストがあり、呼び出しルールから渡される情報に簡単にアクセスできます。マルチパス翻訳のためにツリーを操作する翻訳も、ツリー文法を使用するとはるかに簡単になります。
他のヒント
