110

それらはコンパイル プロセスのさまざまな段階で生成されますか? それとも同じものの名前が違うだけですか？

4

8 に答える 8

110

これはTerrence Parr によるExpression Evaluator文法に基づいています。

この例の文法:

grammar Expr002;

options 
{
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}

prog    :   ( stat )+ ;

stat    :   expr NEWLINE        -> expr
        |   ID '=' expr NEWLINE -> ^('=' ID expr)
        |   NEWLINE             ->
        ;

expr    :   multExpr (( '+'^ | '-'^ ) multExpr)*
        ; 

multExpr
        :   atom ('*'^ atom)*
        ; 

atom    :   INT 
        |   ID
        |   '('! expr ')'!
        ;

ID      : ('a'..'z' | 'A'..'Z' )+ ;
INT     : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS      : ( ' ' | '\t' )+ { skip(); } ;

入力

x=1
y=2
3*(x+y)

解析木

解析ツリーは、入力の具体的な表現です。解析ツリーは、入力のすべての情報を保持します。空のボックスは空白、つまり行末を表します。

解析木

AST

AST は、入力の抽象表現です。アソシエーションはツリー構造から導出できるため、AST には括弧が存在しないことに注意してください。

AST

詳細な説明については、Compilers and Compiler Generators pg. を参照してください。23
またはpg の抽象構文ツリー。- 21位プログラミング言語の構文と意味論

于 2012-03-25T22:14:09.030 に答える
34

ここでは、コンパイラの構築に関連して、解析ツリー(具象構文ツリー、CST) と抽象構文ツリー(AST) について説明します。これらは似たようなデータ構造ですが、異なる方法で構築され、異なるタスクに使用されます。

解析木

通常、構文解析ツリーは、字句解析 (ソース コードを一連の文字列ではなく、意味のある単位と見なすことができる一連のトークンに変換する) の後の次のステップとして生成されます。

それらは、端子の入力文字列 (ソース コード トークン) が問題の言語の文法によってどのように生成されたかを示すツリー状のデータ構造です。解析ツリーのルートは、文法の最も一般的な記号 - 開始記号 (たとえば、statement ) であり、内部ノードは、開始記号が展開される非終端記号を表します (開始記号自体を含めることができます) 。、ステートメント、用語、関数呼び出し。葉は文法の末端であり、言語/入力文字列の識別子、キーワード、および定数として現れる実際の記号です (例: for、9、ifなど)。

解析中、コンパイラはさまざまなチェックを実行して構文の正確性を確認し、構文エラー レポートをパーサー コードに埋め込むことができます。

これらは、中置式を後置式に変換するなどの単純なタスクのために、構文指向の定義または変換スキームを介した構文指向の翻訳に使用できます。

以下は、式の解析ツリーをグラフィカルに表現したものです9 - 5 + 2(ツリー内の端子の配置と、式文字列からの実際のシンボルに注意してください)。

ここに画像の説明を入力

抽象構文木

ASTは、一部のコードの構文構造を表します。式、フロー制御ステートメントなどのプログラミング構造のツリー - 演算子 (内部ノード) とオペランド (葉) にグループ化されます。たとえば、式の構文ツリーではi + 9、演算子+がルート、変数iが演算子の左側の子、数値9が右側の子になります。

ここでの違いは、AST は文法や文字列の生成ではなくプログラミング構造を扱うため、非終端記号と終端記号は役割を果たさないことです。したがって、AST は文法によって生成される方法ではなく、そのような構造間の関係を表します。 .

演算子自体は特定の言語のプログラミング構造であり、実際の計算演算子である必要はありません (is のよう+に):forループもこのように扱われます。たとえば、for [ expr, expr, expr, stmnt ](インラインで表される) のような構文ツリーを持つことができます。ここforで、 は演算子であり、角括弧内の要素はその子 (C のfor構文を表す) であり、演算子などから構成されます。

AST は通常、構文解析 (解析) フェーズでもコンパイラによって生成され、後で意味解析、中間表現、コード生成などに使用されます。

AST のグラフィカルな表現を次に示します。

ここに画像の説明を入力

于 2014-10-12T22:23:53.987 に答える
17

私が理解していることから、AST はソース コードのコンポーネント間の抽象的な関係に重点を置いているのに対し、解析ツリーは、言語によって利用される文法の実際の実装に重点を置いており、細かい部分も含まれています。「解析ツリー」の別の用語は「具体的な構文ツリー」であるため、これらはまったく同じではありません。

于 2011-02-17T08:30:45.393 に答える
11

Martin FowlerのDSL ブックは、これをうまく説明しています。AST には、さらなる処理に使用されるすべての「有用な」要素のみが含まれますが、解析ツリーには、解析する元のドキュメントのすべてのアーティファクト (スペース、ブラケットなど) が含まれます。

于 2011-02-17T08:36:15.547 に答える
11

AST はソース コードを概念的に記述します。一部のソース コードを解析するために必要なすべての構文要素 (中括弧、キーワード、括弧など) を含める必要はありません。

パース ツリーは、ソース コードをより厳密に表します。

AST では、IF ステートメントのノードに 3 つの子のみを含めることができます。

  • 調子
  • イフケース
  • その他のケース

C に似た言語の場合、解析ツリーには「if」キーワード、括弧、中括弧のノードも含める必要があります。

于 2011-05-11T17:54:57.673 に答える
5

パスカルの割り当て Age:= 42; を取ります。

構文ツリーは、ソース コードと同じように見えます。以下では、ノードを括弧で囲んでいます。[年齢][:=][42][;]

抽象ツリーは次のようになります [=][Age][42]

割り当ては、Age と 42 の 2 つの要素を持つノードになります。アイデアは、割り当てを実行できるということです。

また、パスカル構文が消えることにも注意してください。したがって、複数の言語で同じ AST を生成することができます。これはクロスランゲージ スクリプト エンジンに役立ちます。

于 2015-08-04T14:26:59.917 に答える