1. ホーム
  2. 質問と答え
  3. ANTLRのツリーパーサーとは何ですか？私はそれを書くことを余儀なくされていますか？

ANTLRのツリーパーサーとは何ですか？私はそれを書くことを余儀なくされていますか？

2009-03-30 17 views

答えて

3

ANTLRを作成したTerence Parrが作成したjGuruの質問には、this answerが見つかりました。私はリンクされたサイトからこの説明をコピーしましたhere：

パーサ内のアクションでは、単純な、いわゆる構文指向の翻訳しかできません。この種の翻訳は、構文解析のその時点で既に見られている情報の関数である構文を吐き出すだけです。ツリー構文解析ツールを使用すると、中間フォームを処理し、そのツリーを操作し、いくつかの翻訳フェーズにかけて徐々に変換し、新しい翻訳として簡単に印刷することができます。

タイトルが "There are n items"というhtmlページをプリントアウトしたいという単純な翻訳問題を考えてみましょう。ここで、nは入力ストリームで見つかった識別子の数です。 IDSは、このようなタイトルの後に印刷されなければならない：

<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"）アプローチは、実際に（のtoString手で＃（+ INT INT）のための完全な再帰下降パーサをコードすることに注意）。パーサージェネレータとして、これはあなたにうんざりさせるはずです。 ;）

異種ASTアプローチの主な弱点は、コンテキスト情報に便利にアクセスできないことです。再帰的降下パーサでは、パラメータとして渡すことができるため、コンテキストに簡単にアクセスできます。また、文法を調べることによって、どのルールがどの他のルール（たとえば、この式WHILE条件またはIF条件ですか）を呼び出すことができるかを正確に知ることができます。上のPlusNodeクラスは、分離された孤立した世界に存在し、誰がそれをtoString（）メソッドを呼び出すのか分かりません。さらに悪いことに、プログラマーは、それを読み込んでどのコンテキストで呼び出すのかを知ることはできません。要約すると

、あなたの入力パーサにアクションを追加することが非常に簡単翻訳のために働く：出力構築物の順序は、すべての構築物は、最大解析された情報から生成することができる入力順

  • と同じである

    1. あなたが唾を吐く必要がある時まで

    これを超えると、通常はASTが最も良い形態です。文法を使用してASTの構造を記述することは、文法を使用して入力テキストを解析することに似ています。 ANTLRのようなドメイン固有の高水準言語の形式化された記述は、手書きのパーサよりも優れています。ツリー文法内のアクションは、非常に明確なコンテキストを持ち、呼び出すルーツから渡された情報に便利にアクセスできます。マルチパス翻訳のためにツリーを操作する翻訳は、ツリー文法を使用する方がずっと簡単です。

    • 出典

    2009-03-30 18:02:15 HipsterZipster

    7

    ANTLRでASTを作成することが文法に組み込まれています。これを行う必要はありませんが、より複雑な要件のための本当に良いツールです。これはあなたが使うことができるツリー構造上のtutorialです。

    基本的に、ソースが解析されているときにANTLRを使用すると、いくつかのオプションがあります。文法の書き換え規則を使用してコードまたはASTを生成できます。 ASTは、基本的にソースのメモリ表現です。そこから、あなたができることはたくさんあります。

    ANTLRにはたくさんのことがあります。まだお持ちでない場合は、the bookをお勧めします。

    出典

    2009-03-30 16:00:43

    1

    ASTの作成はオプションです。 Abstract Syntax Treeは、解析されたプログラムの意味解析のような後続の処理に役立ちます。

    あなたが作成する必要があるかどうかは、あなただけが決定できます。あなたの唯一の目的が構文的な検証であれば、それを生成する必要はありません。 javacc（ANTLRに類似）にはユーティリティJJTreeがあり、ASTの生成が可能です。ですから、これはANTLRでもオプションです。

    出典

    2009-03-30 16:04:10

    関連する問題

     関連する問題