1

それで、最近これを締めくくる質問をしたところ、非常に良い答えが返ってきました。ただし、説明されている手順は、具体的な構文ツリーを作成する手順のように見えました。

LR 解析プロセスの各縮小は、解析ツリーの内部ノードに対応します。削減されるルールは内部 AST ノードであり、スタックからポップされた項目はその内部ノードの子に対応します。goto でプッシュされたアイテムは内部ノードに対応し、shift アクションによってプッシュされたアイテムは AST のリーフ (トークン) に対応します。

これらすべてをまとめると、リダクションを行うたびに新しい内部ノードを作成し、すべてを適切に接続することで、簡単に AST を構築できます。〜クリス・ドッド

実行した手順によって解析ツリーが暗示されることはわかっていますが、解析ツリーを明示的に構築したくありません。また、リダクションごとにノードを生成すると、解析ツリー全体が生成されるように見えます。特定の状態が見られた場合にのみノードを構築することを検討しました。ただし、これは正しく機能しないようです。

4

1 に答える 1

1

すべてのリダクションでノードを構築する必要はありません。構築するノードには、リダクションされるすべてのシンボルを含める必要はありません。また、縮小されたシンボルが解析と同じ順序で表示される必要もありません。

多くの場合、AST は完全な構文木を簡略化したものであり、上記に対応します。

yacc のようなパーサー ジェネレーターを使用した式文法の簡単な例:

expr: term            { $$ = $1; /* see below */ }
    | expr '+' term   { $$ = new_sum_node($1, $3); }
term: factor          { $$ = $1; /* see below */ }
    | term '*' factor { $$ = new_product_node($1, $3); }
factor: '(' expr ')'  { $$ = $2; /* See below */ }
      | ID            { $$ = new_variable_node($1); }
      | NUMBER        { $$ = new_literal_node($1); }

AST は、非終端記号のセマンティック値として構築されます。関数new_*_nodeは、指定されたタイプの新しく割り当てられたノードを返すことが期待されています。(ここでは、ポインターからそれがどのタイプのノードであるかを推測する何らかのメカニズムがあると想定しています。たとえば、サブタイピングと仮想関数を使用することが可能です。)

Yacc (および同様のパーサー ジェネレーター) では、すべてのシンボル (終端記号または非終端記号) に関連する「値」があり、すべてのプロダクションには、プロダクションが縮小されたときに実行されるアクションが関連付けられています。プロダクションのアクションは、削減される非ターミナルの「値」を割り当てることができます。アクションは、右側のコンポーネントの「値」を利用できます。これは、各コンポーネントが終端 (スキャナによって値が設定されたもの) または既に削減された非終端のいずれかであるためです。実際、これはS 属性の文法です。

上記の削減の一部は、AST にはまったく表示されません。特に、単位削減 (expr:termおよびterm:factor) は、右辺の AST を単純に通過します。同様に、かっこの削減term:'(' expr ')'は の AST を単純に通過するためexpr、結果としてかっこは AST から効果的に削除されます。(これはすべての言語で正しいわけではありません。一部の言語では、明らかに冗長な括弧が実際にセマンティクスに影響を与えるため、事実を記録するために AST ノードを作成する必要があります。)

Yacc では、$$ = $1アクションが指定されていない場合のデフォルトの削減アクションであり、ほとんどのユニット削減は AST から除外されるため、通常は削減アクションなしで表示されます。私は教訓的な目的でそれらを明確にしました。実際には、そうすべきではありません。

于 2015-05-27T02:57:09.670 に答える