文脈自由文法
文脈自由文法はノーム・チョムスキーによる句構造文法の研究の中から、形式言語の類別(形式言語の階層やチョムスキー階層の記事を参照)のひとつとして見出されたものである。
文脈自由文法の形式性は、言語学が伝統的に自然言語の文法を形式的に記述してきた既存の方法(例えばパーニニ)に倣っている。たとえば、入れ子(nesting)を自然に捉えていることや、形式的であることから形式的な手法が使えるという利点がある。一方で問題もあり、たとえば自然言語の文法の重要な機能である一致や参照といった属性は綺麗に表すことができない(自然言語に限らず、プログラミング言語でもしばしば文脈自由文法から「はみ出している」仕様がある)。
文脈自由文法は、(チョムスキーらによって言語学で)提唱されてすぐに、(形式言語と密接な関係にあるオートマトン理論のような理論計算機科学の分野にとどまらず)プログラミング言語 ALGOLの仕様策定において、構文の仕様を示すバッカス・ナウア記法という形でとり入れられ、その後コンピュータ科学一般に、あるいはもっと広く実務にも応用されている。