80

または、もう少し正確に言うと、どのプログラミング言語が文脈自由文法によって定義されているのでしょうか。

私が収集したものから、C ++は、マクロやテンプレートなどの理由で文脈自由ではありません。私の腸は、関数型言語は文脈自由かもしれないと言っていますが、それをバックアップするためのハードデータはありません。

簡潔な例のための追加の担当者:-)

4

9 に答える 9

57

どのプログラミング言語が文脈自由ですか？[...]

私の腸は、関数型言語は文脈自由かもしれないと私に言っています[...]

短いバージョン：単語の意味が文脈自由である実際のプログラミング言語はほとんどありません。言語が文脈自由であるかどうかは、それが機能していることとは何の関係もありません。それは単に構文がどれほど複雑かという問題です。

これが命令型言語BrainfuckのCFGです：

Program → Instr Program | ε
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'

そして、これが機能的な SKIコンビネータ計算のCFGです：

Program → E
E → 'S' E E E
E → 'K' E E
E → 'I'
E → '(' E ')'

これらのCFGは、非常に単純であるため、2つの言語のすべての有効なプログラムを認識します。

長いバージョン：通常、文脈自由文法（CFG）は、言語の構文を大まかに指定するためにのみ使用されます。構文的に正しいプログラムと、正しくコンパイル/評価されるプログラムを区別する必要があります。最も一般的には、コンパイラは言語分析を、コードの一般的な構造を構築および検証する構文解析と、プログラムの意味を検証するセマンティック分析に分割します。

「文脈自由言語」が「...すべてのプログラムがコンパイルされる」という意味の場合、答えは次のとおりです。ほとんどありません。この法案に適合する言語には、変数の存在、空白の感度、型システム、またはその他のコンテキストなど、規則や複雑な機能はほとんどありません。ある場所で定義され、別の場所で信頼される情報。

一方、「文脈自由言語」が「...すべてのプログラムが構文解析に合格する」だけを意味する場合、答えは構文だけがどれほど複雑かという問題です。CFGだけでは説明が難しい、または不可能な構文上の特徴がたくさんあります。これらのいくつかは、カウンターやルックアップテーブルなどを追跡するためにパーサーに状態を追加することで克服されます。

CFGでは表現できない構文機能の例：

  • PythonやHaskellのようなインデントや空白に敏感な言語。任意にネストされたインデントレベルを追跡することは、本質的にコンテキスト依存であり、インデントレベルに個別のカウンターが必要です。各レベルに使用されるスペースの数とレベルの数の両方。

    固定量のスペースを使用して固定レベルのインデントのみを許可すると、インデントのレベルごとに文法を複製することで機能しますが、実際にはこれは不便です。

  • C Typedef構文解析の問題では、Cプログラムは、文法だけでは既存の型の通常の識別子またはtypedefエイリアスであるかどうかを知ることができないため、字句解析中にあいまいであると言われています。

    例は次のとおりです。

      typedef int my_int;
  my_int x;

    セミコロンで、タイプ環境をmy_intのエントリで更新する必要があります。ただし、レクサーがすでにmy_intを先読みしている場合は、タイプ名ではなく識別子としてレクサーが使用されます。

    文脈自由文法の用語では、X → ...トリガーされるルールはあいまいです。識別子を生成するルールか、 'edタイプmy_intを生成するルールのいずれかです。typedefどちらが文法自体を超えてルックアップテーブル（コンテキスト）に依存しているかを知る。

  • Lisp、C ++、Template Haskell、Nimなどのマクロベースおよびテンプレートベースの言語。構文解析中に構文が変わるため、1つの解決策は、パーサーを自己変更プログラムにすることです。C ++は文脈自由ですか、それとも文脈依存ですか？も参照してください。

  • 多くの場合、演算子の優先順位と結合性は、可能であってもCFGで直接表現されません。たとえば、^が×よりも強く結合し、×が+よりも強く結合する、小さな式の文法のCFGは、次のようになります。

      E → E ^ E
  E → E × E
  E → E + E
  E → (E)
  E → num

    ただし、このCFGはあいまいであり、優先順位/結合性の表が付いていることがよくあります。たとえば、^は最も強く結合し、×は+よりも強く結合し、^は右結合であり、×と+は左結合です。

    優先順位と結合性は、機械的な方法でCFGにエンコードできるため、明確になり、演算子が正しく動作する構文ツリーのみが生成されます。上記の文法の例：

      E₀ → EA E₁
  EA → E₁ + EA
  EA → ε
  E₁ → EM E₂
  EM → E₂ × EM
  EM → ε
  E₂ → E₃ EP
  EP → ^ E₃ EP
  E₃ → num
  E₃ → (E₀)

    ただし、あいまいなCFG +優先順位/結合性テーブルは、読みやすく、さまざまなタイプのLRパーサージェネレーターライブラリが、より大きなサイズの明確な変換された文法を処理する代わりに、シフト/削減の競合を排除することで、より効率的なパーサーを生成できるため、一般的です。

理論的には、文字列のすべての有限セットは正規言語であるため、制限されたサイズのすべての合法的なプログラムは正規です。正規言語は文脈自由言語のサブセットであるため、サイズに制限のあるすべてのプログラムは文脈自由です。議論は続く、

言語が100万行未満のプログラムのみを許可することは許容できる制限であると主張することはできますが、プログラミング言語を正規言語として説明することは現実的ではありません。説明が大きすぎます。
     — Torben Morgensenのコンパイラ設計の基礎、ch。2.10.2

同じことがCFGにも当てはまります。サブ質問に少し異なる方法で対処するには、

文脈自由文法で定義されているプログラミング言語はどれですか？

ほとんどの実世界のプログラミング言語はそれらの実装によって定義され、実世界のプログラミング言語のほとんどのパーサーは手書きであるか、文脈自由構文解析を拡張するパーサージェネレーターを使用します。残念ながら、お気に入りの言語の正確なCFGを見つけることはそれほど一般的ではありません。その場合、通常はバッカスナウア記法（BNF）、または純粋に文脈自由ではない可能性が高いパーサー仕様になります。

野生からの文法仕様の例：

于 2013-07-16T20:18:45.113 に答える
46

構文的に正しいプログラムのセットは、ほとんどすべての言語で文脈自由です。

コンパイルするプログラムのセットは、ほとんどすべての言語で文脈自由ではありません。たとえば、すべてのコンパイルCプログラムのセットが文脈自由である場合、正規言語（正規表現とも呼ばれます）と交差することにより、一致するすべてのコンパイルCプログラムのセット

^int main\(void\) { int a+; a+ = a+; return 0; }$

文脈自由ですが、これは明らかに文脈自由ではないことがよく知られている言語a ^ kba ^ kba^kと同型です。

于 2009-05-22T15:37:22.427 に答える
8

質問をどのように理解するかによって、答えは変わります。しかし、IMNSHO、正しい答えは、すべての最新のプログラミング言語は実際には状況依存であるということです。たとえば、構文的に正しいCプログラムのみを受け入れる文脈自由文法はありません。Cのyacc/bison文脈自由文法を指摘する人々は、その要点を見逃しています。

于 2011-08-02T06:50:53.430 に答える
6
于 2009-08-18T03:14:29.610 に答える
3

私があなたの質問を理解しているなら、あなたは文脈自由文法（cfg）で記述できるプログラミング言語を探しているので、cfgはすべての有効なプログラムと有効なプログラムだけを生成します。

したがって、ほとんどの（すべてではないにしても）最新のプログラミング言語は文脈自由ではないと思います。たとえば、ユーザー定義の型（現代言語では非常に一般的）を取得すると、自動的に状況依存になります。

構文の検証とプログラムのセマンティックの正当性の検証には違いがあります。構文のチェックは文脈自由ですが、セマンティックの正しさのチェックはそうではありません（これもほとんどの言語で）。

ただし、これはそのような言語が存在できないことを意味するものではありません。たとえば、型指定されていないラムダ計算は、文脈自由文法を使用して記述でき、もちろんチューリング完全です。

于 2012-06-25T13:46:31.917 に答える
2
于 2009-05-22T15:46:43.393 に答える
2

最新のプログラミング言語のほとんどは、文脈自由言語ではありません。証拠として、CFLのルートを詳しく調べると、対応するマシンPDAは。のような文字列マッチングを処理できません{ww | w is a string}。したがって、ほとんどのプログラミング言語はそれを必要とします。

例：

int fa; // w
fa=1; // ww as parser treat it like this
于 2013-04-01T14:51:32.890 に答える
0

Swiftを見てみましょう。ここでは、ユーザーが演算子の優先順位や結合性などの演算子を定義できます。たとえば、演算子+と*は、実際には標準ライブラリで定義されています。

文脈自由文法と字句解析器はa+b --c * d + eを解析できる場合がありますが、セマンティクスは「演算子+、-、*、および+で区切られた5つのオペランドa、b、c、d、およびeです。 "。これは、パーサーが演算子について知らなくても達成できることです。文脈自由文法と字句解析器は、a +-+ b-+-cを解析できる場合もあります。これは、演算子+-+と-+-で区切られた3つのオペランドa、b、cです。

パーサーは、文脈自由Swift文法に従ってソースファイルを「解析」できますが、それは完了した仕事にはほど遠いものです。もう1つのステップは、演算子に関する知識を収集してから、a + b --c * d +eのセマンティクスをoperator+（operator-（operator +（a、b）、operator *（c、d））と同じになるように変更することです。 e）。

したがって、文脈自由文法があります（または、あるかもしれませんが、私は綿密にチェックしていません）が、それはプログラムを解析するためにこれまでのところしか得られません。

于 2020-09-08T22:13:54.783 に答える
-1

HaskellとMLは文脈自由をサポートしていると思います。Haskellについてはこのリンクを参照してください。

于 2012-06-22T07:39:11.333 に答える