100

インタープリター/コンパイラーがどのように機能するかについて少し読んでいますが、混乱している領域の 1 つは、AST と CST の違いです。私の理解では、パーサーは CST を作成し、それをセマンティック アナライザーに渡して AST に変換します。しかし、私の理解では、セマンティック アナライザーは単純にルールが守られていることを確認します。具体的ではなく抽象的にするために実際に変更を加える理由がよくわかりません。

セマンティック アナライザーについて私が見逃しているものはありますか、それとも AST と CST の違いはやや人為的なものですか?

4

9 に答える 9

76

具体的な構文ツリーは、ソース テキストを解析された形式で正確に表します。一般に、ソース言語を定義する文脈自由文法に準拠しています。

ただし、具体的な文法とツリーには、ソース テキストを明確に解析可能にするために必要なものがたくさんありますが、実際の意味には寄与しません。たとえば、演算子の優先順位を実装するために、通常、CFG にはいくつかのレベルの式コンポーネント (用語、係数など) があり、演算子はそれらをさまざまなレベルで接続します (用語を追加して式を取得します。用語は、オプションで乗算された係数で構成されます)。など）。ただし、実際に言語を解釈またはコンパイルするには、これは必要ありません。演算子とオペランドを持つ Expression ノードだけが必要です。抽象構文ツリーは、具体的な構文ツリーを、プログラムの意味を表すために実際に必要なものまで単純化した結果です。このツリーの定義ははるかに単純であるため、実行の後の段階での処理が容易になります。

通常、具体的な構文ツリーを実際に構築する必要はありません。YACC (または Antlr、Menhir など) 文法のアクション ルーチンは、抽象構文ツリーを直接構築できるため、具体的な構文ツリーは、ソース テキストの構文解析構造を表す概念エンティティとしてのみ存在します。

于 2009-12-11T15:52:31.347 に答える
40

具体的な構文木は、文法規則が言う構文と一致します。抽象構文ツリーの目的は、「構文ツリー」に不可欠なものを「単純な」表現にすることです。

AST IMHO の真の価値は、CST よりも小さいため、処理にかかる時間が短いことです。(誰が気にするの?と言うかもしれませんが、私は一度に数千万のノードが存在するツールを使用しています!)。

構文ツリーの構築をサポートしているほとんどのパーサー ジェネレーターは、ツリー ノードが CST よりも「単純」であるという前提の下で、どのように構築されるかを個人的に正確に指定することを主張します (プログラマーはかなり怠惰）。ほぼ間違いなく、ツリー ビジター関数をコーディングする必要が少なくなることを意味します。これは、エンジニアリング エネルギーを最小限に抑えるという点でも価値があります。3500 のルールがある場合 (たとえば、COBOL の場合)、これは重要です。そして、この「シンプルさ」が「小ささ」の良さにつながります。

しかし、そのような AST を使用すると、そこにはなかった問題が生じます。文法と一致しないため、精神的に両方の AST を追跡する必要があります。そして、3500 の規則文法に対して 1500 の AST ノードがある場合、これは非常に重要です。そして、文法が進化する場合 (常に進化します!)、同期を保つ必要がある 2 つの巨大なセットがあります。

もう 1 つの解決策は、パーサーに CST ノードを単純に構築させ、それらを使用させることです。これは、文法を構築する際の大きな利点です。3500 の文法規則をモデル化するために 1500 の特別な AST ノードを発明する必要はありません。ツリーが文法と同型であることを考えてみてください。文法エンジニアの観点からは、これは完全に無知であり、文法を正しく理解し、心ゆくまでハッキングすることに集中できます。おそらく、より多くのノード ビジター ルールを作成する必要がありますが、それは管理できます。これについては後で詳しく説明します。

DMS Software Reengineering Toolkitで行うことは、(GLR) 解析プロセスの結果に基づいて CST を自動的に構築することです。次に、DMS は、スペース効率の理由から、値を持たない終端 (キーワード、句読点)、意味的に役に立たない単項生成を排除し、次のようなリストである文法規則ペアの直接インデックス可能なリストを形成することにより、「圧縮された」CST を自動的に構築します。

    L = e ;
    L = L e ;
    L2 = e2 ;
    L2 = L2  ','  e2 ;

そして、そのような形の多種多様なバリエーション。文法規則と仮想 CST の観点から考えます。ツールは圧縮された表現で動作します。脳にやさしく、実行時に高速/小型化。

驚くべきことに、この方法で構築された圧縮された CST は、手動で設計した AST によく似ています (例の最後にあるリンクを参照してください)。特に、圧縮された CST には、単なる具体的な構文であるノードは含まれていません。少し厄介な点があります。たとえば、式の部分文法で古典的に見られる '(' および ')' の具体的なノードはツリーにありませんが、「括弧ノード」は圧縮された CST に表示され、処理する必要があります。真の AST にはこれがありません。これは、AST 構造を指定する必要がないという利便性のために支払うかなり小さな代償のように思えます。そして、ツリーのドキュメントは常に利用可能で正確です。文法はドキュメントです。

「余分な訪問者」を避けるにはどうすればよいですか？完全ではありませんが、DMS は、AST をウォークし、CST と AST の違いを透過的に処理する AST ライブラリを提供します。DMS は「属性文法」エバリュエーター (AGE) も提供します。これは、ノードで計算された値をツリーの上下に渡す方法です。AGE はすべてのツリー表現の問題を処理するため、ツール エンジニアは、文法規則自体に直接効果的に計算を書き込むことだけを心配します。最後に、DMS は「表面構文」パターンも提供します。これにより、関連するノード タイプのほとんどを知らなくても、文法のコード フラグメントを使用して特定のタイプのサブツリーを見つけることができます。

他の回答の1つは、ソースを再生成できるツールを構築したい場合、ASTがCSTと一致する必要があることを示しています。これは正しくありませんが、CST ノードがあれば、ソースを再生成する方がはるかに簡単です。 DMSは両方にアクセスできるため、ほとんどの prettyprinter を自動的に生成します :-}

結論: AST は、物理的および概念的な小規模の場合に適しています。CST から自動化された AST 構築は両方を提供し、2 つの異なるセットを追跡する問題を回避できます。

EDIT 2015 年 3 月: この方法で構築された CST と「AST」の例へのリンク

于 2009-12-16T18:33:07.867 に答える
30

これは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

于 2012-04-16T15:08:05.167 に答える
21

このブログ投稿が役立つ場合があります。

AST は、セマンティクスに寄与しない多くの中間的な文法/構造情報を「捨てる」ように思えます。たとえば、3 がアトムであること、項が因数であることは気にし3ません。累乗式などを実装しているときだけ気にします。

于 2009-12-11T15:41:25.350 に答える
11

具体的な構文ツリーは、言語の文法規則に従います。文法では、「式リスト」は通常、2 つの規則で定義されます。

  • expression_list は次のとおりです。
  • expression_list は次のとおりです: 式、expression_list

文字通り、これら 2 つの規則により、プログラムに表示される任意の式リストがくし形になります。

抽象構文ツリーは、さらに操作しやすい形式になっています。プログラムの書き方だけでなく、プログラムの意味を理解している人にとって意味のある方法で物事を表現します。上記の式リストは、関数の引数のリストである可能性があり、式のベクトルとして便利に表すことができます。静的解析では、式の総数を明示的に利用可能にし、その式によって各式にアクセスできる方がよいためです。索引。

于 2009-12-11T15:46:59.410 に答える
6

簡単に言うと、AST にはコードのセマンティクスのみが含まれ、解析ツリー/CST には、コードがどのように正確に記述されたかに関する情報も含まれます。

于 2016-04-25T05:43:36.277 に答える
2

それは違いを生まない違いです。

AST は通常、字句の内容を捨てることによってプログラミング言語の式のセマンティクスを近似する方法として説明されています。たとえば、文脈自由文法では、次の EBNF ルールを記述できます。

term: atom (('*' | '/') term )*

一方、AST の場合は、適切な算術演算を表すmul_ruleとdiv_ruleのみを使用します。

そもそもそれらのルールを文法に導入できないのでしょうか? もちろん。上記のコンパクトで抽象的なルールを、前述の AST ノードを模倣するために使用されるより具体的なルールに分割することで書き直すことができます。

term: mul_rule | div_rule
mul_rule: atom ('*' term)*
div_rule: atom ('/' term)*

ここで、トップダウン解析の観点から考えると、2 番目の項は、LL(1) パーサーが対処できないmul_ruleとdiv_ruleの間の FIRST/FIRST 競合を導入します。最初の規則形式は、効果的に構造を排除した 2 番目の形式の左因数分解バージョンでした。ここで LL(1) を使用するには、いくらかの賞金を支払う必要があります。

したがって、AST は、文法とパーサーの欠陥を修正するために使用されるアドホックな補足です。CST -> AST 変換はリファクタリングの動きです。追加のカンマやコロンが構文ツリーに格納されていても、誰も気にしませんでした。それどころか、いくつかの作成者は、さまざまなツリーを同時に維持したり、追加の推論エンジンを作成したりするのではなく、リファクタリングを行うために AST を使用することを好むため、それらを AST に改造しています。プログラマーは正当な理由で怠け者です。実際には、字句解析によって収集された行と列の情報も、エラー レポート用に AST に格納します。確かに非常に抽象的です。

于 2012-02-22T16:02:34.627 に答える
2

具体的な構文ツリーには、余分な括弧、空白、コメントなどのすべての情報が含まれ、抽象構文ツリーはこの情報を抽象化します。

 

注意:面白いことに、リファクタリング エンジンを実装すると、AST にはすべての具体的な情報が再び含まれますが、AST はこの分野で標準的な用語になっているため、AST として参照し続けます (長い以前は本来の意味を失いました）。

于 2009-12-12T16:55:25.313 に答える