問題タブ [concrete-syntax-tree]

文法と解析ツリーの作成方法の例を含む優れたオンライン リソースの場所を知っている人はいますか? できれば入門資料。n00b フレンドリーな情報ですが、Google で良いことは何も見つかりませんでした。

編集：特定のパーサーソフトウェアではなく、理論について考えています。

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

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

pyPEGを使用して、単純な文法の解析ツリーを作成しています。ツリーは、リストとタプルを使用して表されます。次に例を示します。

私の質問は、この時点でそれをどうするかということです。私は自分が何をしようとしているかに大きく依存することを知っていますが、解析ツリーの消費/使用についてはあまり見つけることができず、作成するだけです。誰かが私が使用する可能性のある参照へのポインタを持っていますか？

ご協力いただきありがとうございます。

セクション7.8.1のECMAScript仕様によると、aは次のように定義されています。NullLiteral

私が理解しようとしているのは、セクション7.6.1と7.8NullLiteralにある次のプロダクションにaが含まれている場合に、これがツリー形式でどのように表されるかです。

それがどのように見えるかについての私の最もよい推測はこれです：

しかし、これは私には正しくないようです。

ノート

私の調査によると、言語文法から実際にCSTを生成するコンパイラはほとんどないようです。もちろん理由は理解できますが、これは私にとって学習演習であるため、パーサジェネレータを使用するなど、より専門的な構文解析手段に移行する前に、これを正しく理解したいと思います。

私はコンパイラの研究をしています。レクサーは非常に単純なようです。「文」を取り、それを単語（またはトークン）に分割します。正しい文法を保証するには、パーサーが必要です。パーサーは通常、トークンを受け取り、ルートノード（単語から文、段落、ページなど）になるツリーを構築します。

この質問から、パーサーはASTを構築するように思われます。ASTにはコードの実行に必要なものだけが含まれているため、演算子の優先順位がASTに組み込まれているため、括弧などは不要です。ASTはおそらくコンパイラが必要とするすべてです。

しかし、ある言語から別の言語にコードを変換するのはどうでしょうか？作成された言語（文法）または既存の文法を使用して、演算子の優先順位規則が異なる場合と異なる場合がある別の言語に変換しますか？演算子の優先順位はCSTにも「組み込まれています」か？

例として、私が言語を作り、それをPHPコードに翻訳したいとしましょう。ほとんどの言語の三項演算子には、右から左への結合性があります。PHPは、左から右への結合性を誤って使用します（これについて詳しくは、こちらをご覧ください）。「私の言語」で右から左を使用したいのですが、結果のPHPコードは、PHPで正しい結果を得るには、括弧を適用する必要があります（Wikipediaへのリンクを使用すると、結果は「馬」ではなく「電車」である必要があります）。

では、言語翻訳の場合、CSTの方が優れているでしょうか？通常、演算子の優先順位はCSTに組み込まれていますか？間に何かありますか？両方のツリーを単純な代数方程式と比較する例はありますか？三項演算子を示す例はありますか？

（「トランスコード」は「プログラミング言語翻訳」の正しい用語ですか？Google検索で変換メディアが表示されます。）

私が理解しようとしているのは、次のとおりです。一方を他方の上に使用する方が適切なのはいつですか。

HTML または XML ファイルを解析した後、DOM ツリーを取得できます。

C、C++、または JavaScript を解析した後、構文ツリーを取得できます。

構文ツリーは、有効な C/C++/JS プログラムを指定する文脈自由文法に基づいて構築されていることに注意してください。

しかし、DOM ツリーは、HTML/XML ファイルによってのみ指定された純粋な階層構造にすぎないようです。本当？解析後にスキーマ検証が行われたのはそのためですか? これら 2 種類の解析ツリーの根本的な違いは何ですか?

構文木 (具体的な構文木) を抽象構文木に縮小するための一般的な戦略は何ですか?

たとえば、次の文法規則があります。

これを解析ツリーのままにしておくと、次のようなファニング出力が生成されます

各ノードの子を連結すると (ステートメント リストは解析後に固有の意味を持たないため)、次のことを実現できます。

これはうまくいきました - しかし、私はこれを行うための「ルール」を知りません。簡素化する必要がある特定の文法規則はありますか? それは感覚の問題ですか、それとももっと機械的なプロセスがありますか?

例えば：：

型のノードの元の値を保持しながら、パーサーに Python ソース ファイルを構文ツリーに変換させるにはどうすればよいstrですか? たとえば、「1.2」を、精度をまったく失うことなく、できるだけ正確な分数を使用して正確な値に変換する必要があるためです (値 1.2 は浮動小数点形式で正確に表すことはできません)。

できれば、パーサーを再実装せずにこれを行いたいと考えています。astおそらく、モジュールよりもこれに適したパーサーが他にあるでしょう。

ところで、式だけでなくプログラムも解析する必要があります。

テーブル駆動の LR(1) パーサーをコーディングしましたが、非常にうまく機能していますが、解析を構文ツリー/抽象構文ツリーに変換する段階で少し切断されています。これは私が非常に情熱を注いでいるプロジェクトですが、ここで行き詰まりを迎えました。よろしくお願いいたします。

編集: また、私のパーサーは、2 次元配列とアクション オブジェクトを使用して、次に移動する場所や、移動先とポップするアイテムの数を減らすかどうかを指示します。多くの人がビジターパターンを使用していることに気付きました。彼らがどのタイプのノードを作成するかをどのように知っているかわかりません。

コンテキストのプッシュダウンオートマトンは次のとおりです