76

私はASTとは何かについての一般的な考えを持っていますが、ASTの構築方法を知りたいです。

文法と構文解析ツリーが与えられた場合、どのようにASTを構築しますか？

文法と表現が与えられたらどうしますか？

4

3 に答える 3

42

まず、文法を使用して、式から解析ツリーを構築します。したがって、すでに解析ツリーがある場合は、文法は必要ありません。

パーサーが実行する作業の量によっては、式の解析から形成される結果のツリーは、すでに抽象構文ツリーである可能性があります。または、astを構築するために2回目のパスを必要とする単純な解析ツリーである可能性があります。

文法と式から解析ツリーを構築するには、最初に文法を機能するコードに変換する必要があります。通常、作業を、式を表す入力ストリームをトークンのリストに分割するトークナイザーと、トークンのリストを取得してそこから解析ツリーを構築するパーサーに分割します。

したがって、式1 + 2*(3+4)は次のようなトークンのリストに分割される可能性があります。

1 - int
+ - add_operator
2 - int
* - mul_operator
( - lparen
3 - int
+ - add_operator
4 - int
) - rparen

最初の列は実際のテキスト値です。2番目はトークンタイプを表します。これらのトークンは、文法から構築され、トークンを認識して解析ツリーを構築するパーサーに供給されます。

では、字句トークナイザーと実際のパーサーをどのように作成するのでしょうか。手で転がすことができます。または、より一般的には、coco、antlr、lex/yaccなどのパーサジェネレーターを使用します。これらのツールは、文法の説明を受け取り、tokenzierとパーサーのコードを生成します。（コードジェネレーターは、最も人気のある言語といくつかの人気のない言語にも存在します。）

パーサーを構築する方法は、使用する言語に大きく依存します。Haskellでパーサーを作成する方法は、たとえばCで作成する方法とはまったく異なります。

  • これは、独自の再帰下降パーサーを構築する方法を示すチュートリアルです。

  • Cocoは、さまざまな言語用のパーサージェネレーターであり、開始方法に関するドキュメントも付属しています。

  • Pythonがあなたのものなら、おそらくあなたのためにpyparsingします。

于 2009-11-12T11:46:37.070 に答える
4

「ASTの作り方」という問いに答えるのは不十分でした。

シリーズCraftingInterpretersからアーカイブされたこの記事 は、初心者のためにきちんと簡単に答えます。実装を完了します。Stackoverflowはリンクの場所ではないので、要点をコピーします。

再帰下降構文解析

パーサーコンビネーター、アーリーパーサー、シャントなどのよりエキゾチックな獣とともに、名前が主に「L」と「R」の組み合わせであるように見える解析手法のパック全体があります（LL（k）、LR（1）、LALR）。ヤードアルゴリズム、およびpackrat解析。私たちの最初の通訳者にとっては、再帰下降という1つの手法で十分です。

再帰下降はパーサーを構築する最も簡単な方法であり、Yacc、Bison、ANTLRなどの複雑なパーサージェネレーターツールを使用する必要はありません。必要なのは、簡単な手書きのコードだけです。ただし、その単純さにだまされないでください。再帰下降パーサーは高速で堅牢であり、高度なエラー処理をサポートできます。実際、GCC、V8（ChromeのJavaScript VM）、Roslyn（C＃で記述されたC＃コンパイラ）、およびその他の多くのヘビーウェイトプロダクション言語の実装では、再帰下降が使用されます。お尻を蹴る。

トップダウンパーサーと見なされるのは、最上位または最外部の文法規則（ここでは式）から始まり、最終的に構文ツリーのリーフに到達する前に、ネストされた部分式に向かって進むためです。これは、一次式で始まり、それらを構文のより大きなチャンクに構成するLRのようなボトムアップパーサーとは対照的です。

再帰下降パーサーは、文法の規則を命令型コードに直訳したものです。各ルールは関数になります。ルールの本体は、おおよそ次のようなコードに変換されます。

Grammar notation    Code representation
Terminal            Code to match and consume a token
NonterminalCall     to that rule’s function
|                   if or switch statement
* or +              while or for loop
?                   if statement

これは「再帰下降」と呼ばれます。これは、文法規則がそれ自体を（直接的または間接的に）参照する場合、再帰的なメソッド呼び出しに変換されるためです。

サイドノート：

文法をたどるので「再帰下降」と呼ばれます。紛らわしいことに、「高」と「低」の優先順位について話すときは、比喩的に方向も使用しますが、方向が逆になります。トップダウンパーサーでは、優先順位の最も低い式に最初に到達します。これは、優先順位の高い部分式が含まれている可能性があるためです。優先度の高い順にトップダウンの文法規則。

元の画像のリンク

式の方向の解析

CSの人々は本当に集まって、比喩を正す必要があります。スタックがどの方向に成長するのか、私に始めさせないでください。

于 2020-09-12T09:17:34.857 に答える
3

レクサーやパーサーについて話すことなく、一般的な観点からこれに答えます。

構文解析ツリーには、文脈自由文法の一部である非終端記号が含まれており、再帰的かどうかに関係なく、終端記号で構成される文字列を取得するための一連の生成を示します。したがって、解析ツリーがある場合、文法は必要ありません。解析ツリーから文法を導出できます。

ASTには非終端記号は含まれていません。記号のみが含まれています。

例：

 E
 |
 E + T
 |   |
 T   M * M
 |   |   |
 M   a   b
 |
 a

これは、表示の非常に簡単なバージョンですa+a*b。抽象構文ツリーが解釈される方法は、ツリーの優先順位、実行するトラバーサルのタイプ（順序、事前順序、事後順序）によって異なることに注意してください。これは、検索ツリーにコーディングする一般的な関数です。ただし、一般に、その解析ツリーのASTは次のようになります。

   +
 |   |
 a   * 
    | |
    a b
于 2016-05-09T10:07:03.657 に答える