1. ホーム
  2. compiler-construction

[解決済み] 解析木と抽象構文木(AST)の違いは何ですか?

2022-10-05 11:28:18

質問

これらはコンパイルプロセスの異なるフェーズで生成されるのでしょうか?それとも、同じものを表す別の名前なのでしょうか?

どのように解決するのですか?

これは 式評価器 の文法に基づいています。

この例の文法。

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に括弧が存在しないことに注意してください。

より詳細な説明については コンパイラとコンパイラ・ジェネレータ pg. 23

または 抽象構文木 の21ページにある プログラミング言語の文法と意味論