comp.theory リストでこの素晴らしい投稿を読みました。
http://coding.derkeiler.com/Archive/General/comp.theory/2004-03/0189.html
ポスターは、ほとんどのプログラミング言語がコンテキストフリーのコアを定義し、構文解析ツリーで実行される追加のアルゴリズムを使用して、言語で違法な構造を除外することを強調しています。
これにより、言語の文脈に依存しない部分と文脈に依存する部分が分離されます。これは、一般的に優れた実践 (言語設計のための一種のモジュール化された「プログラミング」規律) と見なされます。
この手法を説明するために「Hello World」の例を提供できますか? つまり、単純な文脈依存言語を提供し、文脈自由コアを特定してから、文脈自由コアを使用して入力を解析する方法をスケッチし、続いて解析ツリーで不正な構造を除外します。
このテクニックについて説明している記事や本を紹介してもらえますか?
文脈自由ではない最も単純な言語の 1 つは、単語がa n b n c n型(a、b、および c が同じ回数繰り返される、つまり、abc、aabbcc、aaabbbccc、. ..)。
c の数が制限されていない文脈自由言語 {a n b n c m } の文法を使用して解析できます。構文木を取得したら、別のアルゴリズムを使用して、c の繰り返し回数が a と b の繰り返し回数と等しいことを確認します。
通常、フィルタリングは、言語の過大な近似を明確にするためにも行われます。あいまいだが明確なプログラミング言語の文脈自由文法を記述し、ツリー ウォーカーまたはその他のメカニズムを使用して不要な派生を削除します。
1 つの参照:
一方で、抽象構文ツリーを処理する型チェッカーをそのようなフィルターと見なすこともできます。型チェッカーは、非ローカル (コンテキスト) 情報に基づいてパーサーによって生成されたツリーを拒否します。例えば：
1 + "1"
次の理由により、文法によって受け入れられます。
E ::= Int | String | E "+" E;
しかし、型チェッカーは、整数と文字列の間で加算が機能しないと言い、言語から文を拒否します。型チェッカーは、加算記号を解析して識別した後、ツリーをトラバースしてこれを行い、テーブル内の有効なオペランドの組み合わせを検索し、組み合わせが有効でない場合は文句を言い始めます。それが通常、コンパイラの仕組みだと思います。アホらを参照してください。ドラゴンブック。抽象的に話すともっと面白く聞こえます:-)