文脈自由文法

文脈自由文法 (CFG)

文脈自由文法（CFG）は、形式言語理論における基礎的な構造であり、非終端記号と終端記号を用いて文法規則を記述します。この文法の主な特徴は、非終端記号を前後の文脈に関係なく適切な終端記号または非終端記号に置換できる点です。これにより、構文解析やプログラミング言語の仕様を規定するのに利用されます。

背景と歴史

文脈自由文法は、言語学の巨匠ノーム・チョムスキーによる句構造文法の研究から生まれました。自然言語の文法を数理的に表現する手法として発展しました。CFGは入れ子構造を自然に表現できるため、自然言語やプログラミング言語の文法を簡潔に定義できますが、一方で一致や参照のような自然言語特有の機能をうまく表現することは難しい場合があります。

この文法は、オートマトン理論と密接に関係しているため、構文解析においても多くの応用を持っています。たとえば、ALGOLのような初期のプログラミング言語の仕様をバッカス・ナウア記法によって表現する際にも利用されました。文脈自由文法によって生成される言語は、文脈自由言語と呼ばれ、多くのプログラミング言語がこの概念を元に構文を構築しています。

定義と構造

CFGは、次の4つの要素からなる4-タプルで表されます。

• - V：非終端記号の有限集合
• - Σ：終端記号の有限集合（非終端記号の集合との交わりはない）
• - R：生成規則の集合（非終端記号から終端または非終端記号の列への関係）
• - S：開始記号

生成規則は「文法の規則」と呼ばれ、文法に従った生成過程を通じて様々な文字列が導出されます。例として、非終端記号を用いた単純な文法規則を考えると、生成される言語は
{a^n b^n : n ≥ 0} という形になります。これは、aとbの個数が等しいひとつのタイプの言語を表します。

文法の応用

文脈自由文法は、さまざまな形式言語に応用されるだけでなく、特定の文法の下で生成される公式の言語や数式を記述する際に役立ちます。たとえば、数学の数式やプログラミングコードを記述するのに非常に便利です。さらに、CFGは多くのコンピュータプログラミング言語の構文解析に用いられていますが、実際のプログラミング言語では文法規則だけでは表現しきれない部分も多く、それ分の意味的なルールを補完することが一般的です。

導出と構文木

文脈自由文法において、文字列の導出は「左端導出」と「右端導出」の2つの方法で表現されることができます。左端導出は、常に最も左の非終端記号から生成規則を適用していく方法です。この導出過程によって生成される構文木は、文字列の構造を示す重要なビジュアル表現として用いられます。

課題と制約

CFGには限界も存在します。その一例が、ある言語がCFGによって表現できるかどうかを判断する問題であり、これは決定不能であることが知られています。また、文脈依存の規則や非決定性の問題も存在し、全ての文法が文脈自由であるわけではありません。

今後、文脈自由文法を拡張する研究が進められており、自然言語の複雑な特性をより正確に捉えるために、新たな形式的な手法が模索されています。

もう一度検索