C言語を文脈自由にするには？

Question

IはC有名な例は、文脈自由言語ではないことを知っている：レクサーは3行目でfooは、識別子であるかどうか、知らないこの場合

int foo; 
typedef int foo; 
foo x; 

、又はtypedef。

私の質問は、これが唯一の理由です。文脈依存言語？

つまり、typedefを取り除くと、文脈自由言語になりますか？それ以外の理由（例）もありますか？

Answer 1

はい。 Cは古典的なlex + yaccのコンボで解析できます。あなたはlexのファイルから見ることができるように字句解析の定義とyacc文法が

http://www.quut.com/c/ANSI-C-grammar-l-2011.html と http://www.quut.com/c/ANSI-C-grammar-y-2011.html

で自由に利用できます、それはコンテキスト依存check_type()（およびcomment()以外は簡単ですが、技術的に処理するコメントプリプロセッサに属しています）、typedefがコンテキスト感受性の唯一の原因となります。 yaccファイルにはコンテキスト感受性を導入するトリックも含まれていないため、typedef -lessCは完全に文脈自由な言語になります。

Answer 2

番号Cは、厳密なコンテキストに依存しない言語であることはできません。そのためには、宣言されていない変数（これはコンテキスト）を、あなたの質問に記述したのと同様の方法で使用することができない構文を記述する必要があります。言語作成者は、ある種の文脈自由文法を使用して構文を記述しますが、言語の主な構文構造を記述するだけです。あなたが記述するケース（異なるトークンクラスに収まるようにタイプ識別子を作ることは、そうでなければならない場所に入ることができる）はほんの一例にすぎません。たとえば、static unsigned long long int variableのような順序での自由は、プログラマーが記憶している構文を単純化しますが、コンパイラーの作成者には複雑です。