6

Java環境で実行されるANTLRのCの小さなサブセット用のレクサー/パーサーを書いています。私は言語文法の世界に不慣れで、多くの ANTLR チュートリアルで AST - 抽象構文ツリーを作成します。作成する必要があるのはなぜですか?

4

3 に答える 3

7

ANTLR を使用した AST の作成は、文法に組み込まれています。これを行う必要はありませんが、より複雑な要件には非常に優れたツールです。これは、使用できるツリー構築に関するチュートリアルです。

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

ANTLRにはたくさんあります。まだお持ちでない場合は、本を入手することをお勧めします。

于 2009-03-30T16:00:43.113 に答える
3

ANTLR を作成した Terence Parr によって書かれた jGuru に関する質問に対するこの回答を見つけました。ここにリンクされているサイトからこの説明をコピーしました：

パーサー内のアクションで実行できるのは、単純な、いわゆる構文指向の変換のみです。これらの種類の翻訳は、解析のその時点ですでに見られた情報の関数である構成要素のみを吐き出すことができます。ツリー パーサーを使用すると、中間フォームをたどってそのツリーを操作し、いくつかの翻訳フェーズを経て、新しい翻訳として簡単に出力できる最終フォームに徐々にモーフィングできます。

タイトルが「There are n items」である 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 が与えられた場合、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() メソッドを呼び出すかわからない、分離された孤立した世界に存在します。さらに悪いことに、プログラマーはそれを読んでもどのコンテキストで呼び出されるのかわかりません。

要約すると、入力パーサーにアクションを追加すると、次のような非常に単純な翻訳で機能します。

  1. 出力構造の順序は入力順序と同じです
  2. すべての構成要素は、それらを吐き出す必要がある時点までに解析された情報から生成できます

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

于 2009-03-30T18:02:15.300 に答える