3

質問は自給自足だと思います。C 言語の構文は、文脈自由文法によって完全に定義されていますか、それとも構文解析の過程で文脈自由でない定義を必要とする可能性のある言語構造がありますか?

私が考えた非CFL構造の例は、使用前の変数の宣言でした。しかし、Compilers(Aho Ullman Sethi) では、C 言語は名前に基づいて識別子を区別しないと述べられています。すべての識別子は、字句解析器によって「id」としてトークン化されます。C が CFG によって完全に定義されていない場合、C の非 CFL 構造の例を教えてください。

4

5 に答える 5

3

問題は、「C の構文」を定義していないことです。

それを CS の意味での言語 C、つまりすべての有効な C プログラムのセットとして定義すると、C は、turpits と Lisp を除いて事実上すべての他の言語と同様に、コンテキスト フリーではありません。その理由は、C プログラムの解釈の問題(たとえば、乗算か宣言かの決定) とは関係ありません。代わりに、文脈自由文法は、与えられた文字列が有効な C プログラムであるかどうかを判断するのに役立たないからです。(1) 戻り値の型を記憶し、(2) の後に発生するものはすべて戻り値の型と一致することを確認する必要があるため、単純なものであっても文脈自由文法よりも強力なメカニズムが必要です。a * b;int main() { return 0; }returna * b;も同様の問題に直面しています。それが乗算かどうかを知る必要はありませんが、乗算である場合、それは と の型に対して有効な演算でなければなりませaんb。未定義の動作を除外したとしても、有効な C プログラムのいくつかの制限は非常に微妙であるため、状況依存の文法が C のすべてに十分かどうかは実際にはわかりません(そのうちのいくつかは決定できない可能性さえあります)。

もちろん、上記の概念はほとんど役に立ちません。一般に、文法について話すとき、有効なプログラムのかなり良い概算にのみ関心があります: 文法が過度に複雑になることなく、できるだけ多くの C ではない文字列を除外する文法が必要です (たとえば、1 aor (-)) . それ以外はすべてコンパイラの後のフェーズに委ねられ、セマンティック エラーまたは同様のものと呼ばれて、最初のクラスのエラーと区別されます。これらの「近似」文法はほとんど常に文脈自由文法 (C の場合を含む) であるため、有効なプログラムのセットのこの近似を「構文」と呼びたい場合、C は確かに文脈自由文法によって定義されます。多くの人がそうしているので、あなたは良い仲間になるでしょう.

于 2013-10-25T17:34:58.827 に答える
1

C言語標準で定義されている言語には、プリプロセッサが含まれています。以下は、構文的に正しい C プログラムです。

#define START int main(
#define MIDDLE ){

START int argc, char** argv MIDDLE return 0; }

文法自体があいまいであり、言語。その CFG は興味深く、さらに便利ですが、C ではありません。

実際、標準のプロダクションでは、構文的に正しいソース ファイルとは何かを説明しようとさえしていません。彼らは次のように説明しています。

  1. ソースファイルの字句構造 (前処理後の有効なトークンの字句構造とともに)。

  2. 個々のプリプロセッサ ディレクティブの文法

  3. 後処理言語の文法のスーパーセット。 と の他の用途を区別する他のメカニズム、および と の他の用途を区別するメカニズムに依存してtypedef-nameいidentifierます。constant-expressionconditional-expression

ポイント3の問題は「構文」ではなく「意味」であると主張する人がたくさんいます。ただし、C の性質 (およびその従兄弟である C++ の性質はさらにそうです) は、プログラムの解析から「セマンティクス」を解きほぐすことが不可能であることです。たとえば、次は構文的に正しい C プログラムです。

#define base 7
#if base * 2 < 10
  &one ?= two*}}
#endif

int main(void){ return 0; }

したがって、「CFG によって定義された C 言語の構文である」ということを本当に意味するのであれば、答えはノーでなければなりません。「C 言語でのプログラムの翻訳の中間生成物である文字列を表す言語の構文を定義する CFG はありますか」という意味であれば、答えはイエスである可能性があります。 aconstant-expressionと aが何であるかを正確にする必要性は、typedef-name他の言語にはない方法で、構文を必然的に文脈依存にする必要があります。

于 2013-10-25T21:13:53.277 に答える
1

C 言語の構文は Context Free Grammars によって完全に定義されていますか?

はい、そうです。これは、BNF での C の文法です。

http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf

規則の左側に 1 つの記号しか表示されない場合、その文法は文脈自由です。それがまさに文脈自由文法の定義です(ウィキペディア) :

形式言語理論では、文脈自由文法 (CFG) は、すべての生成規則が次の形式である形式文法です。

V → w

ここで、V は単一の非終端記号であり、w は終端および/または非終端の文字列です (w は空にすることができます)。

あいまいさは他の人が言及しているので、少し明確にしたいと思います。次の文法を想像してください。

A -> B x | C x
B -> y
C -> y

これはあいまいな文法です。ただし、これは依然として文脈自由文法です。これら 2 つは完全に別の概念です。

明らかに、C のセマンティクス アナライザーはコンテキスト依存です。重複した質問からのこの回答には、さらに説明があります。

于 2013-10-25T17:26:44.667 に答える
0

ここには 2 つのことがあります。

  1. 言語の構造 (構文): 何が識別子で何が関数かを理解するために周囲を知る必要がないため、これはコンテキスト フリーです。
  2. プログラムの意味 (セマンティクス): 識別子が宣言されているかどうか、参照するときにどのタイプであるかを知る必要があるため、これはコンテキスト フリーではありません。
于 2013-10-25T17:04:18.047 に答える
0

「C の構文」によって、一部の C コンパイラが受け入れるすべての有効な C 文字列を意味し、プリプロセッサを実行した後、入力エラーを無視する場合、これが答えです。はい、ただし明確ではありません。

まず、入力プログラムが C 標準に従ってトークン化されていると想定できます。文法は、裸の文字ではなく、これらのトークン間の関係を記述します。このような文脈自由文法は、C に関する書籍や、パーサー ジェネレーターを使用する実装に見られます。かなりの作業が C の「字句解析」に費やされているため、このトークン化は大きな仮定です。したがって、語彙レベルを記述するために文脈自由文法を使用していない場合、文脈自由文法で C を記述していないと主張します。 . トークナイザーとパーサーの間のステージングと、スキャナー ジェネレーターによって課される順序付け (優先キーワード、最長一致など) を組み合わせると、計算能力が大幅に向上しますが、これは文脈自由文法では簡単にはシミュレートできません。

したがって、たとえばシンボル テーブルを使用して型名と変数名を区別できるトークナイザーを想定しない場合、文脈自由文法は難しくなります。ただし、ここでの秘訣はあいまいさを受け入れることです。トークンを含む C の構文は、文脈自由文法で完全に記述できます。文法だけがあいまいになり、同じ文字列に対して異なる解釈が生成されます。たとえばA *a;、乗算とポインター宣言の両方の派生があります。問題ありません。文法は、要求どおりに C 構文を記述していますが、明確ではありません。

プリプロセッサも最初に実行したと仮定していることに注意してください。あなたの質問は、プリプロセス前のコードに関するものではなかったと思います。構文の正しさはユーザー定義マクロの展開のセマンティクスに依存するため、文脈自由文法を使用することは単なる狂気です。基本的に、プログラマーはマクロが定義されるたびに C 言語の構文を拡張しています。CWI では、C 言語を拡張する一連の既知のマクロ定義を考慮して、C の文脈自由文法を作成しましたが、それはうまくいきましたが、それは一般的な解決策ではありません。

于 2013-10-26T10:20:49.243 に答える