形式文法
プログラミング言語処理系の実装のフロントエンドとしてさかんに研究されたため、それに関係する構文解析についての論文は非常に多い。それらでは、解析対象の言語を形式的に定義し、そこから動作可能な構文解析器を生成することが目標である。自然言語についても計算言語学や自然言語処理などで必要であり、研究されている。いくつかの例を示す。
Yacc
The Language Machine は制限のない分析的文法を直接実装したものである。置換規則は入力を変換して出力とふるまいを生成する。このシステムは、制限のない分析的文法の規則を適用したときに何が起きているかを図示することもできる。
Top-Down Parsing Language、TDPL:1970年代初期に開発された高度なミニマリスト分析的文法であり、下降型構文解析のふるまいを研究することがその目的である。
Parsing Expression Grammar:TDPLをさらに汎用化したもので、プログラミング言語やコンパイラ作成者が実用的な表現をするために設計したものである。
リンク文法:言語学者によって設計された分析的文法の形式。単語間の所有関係を調べる文法構造を導く。
形式文法(けいしきぶんぽう、Formal Grammar)は、形式的に与えられた(形式体系を参照)文法である。「言語」をその言語における文の集合として与えるものとして、ここでは、(有限の)文字群上の有限長の文字列の(通常無限な)集合が、形式的に記述される。
形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。#チョムスキー階層の節および単独記事に詳細があるが、両者は対応するので、ある意味では同じものをそれぞれ逆の側から見たものにすぎない。
以下で「文法の規則(構文規則)の集まり」と呼んでいるのは、具体的には、句構造規則#基本モデルにあるようなものである。また終端記号と非終端記号の記事も参照のこと。
生成文法(Generative grammar)は、文法の規則(構文規則)の集まりを「トップレベルの非終端記号(たとえば <文>)から始めて、右辺に書き換える書き換え規則を適用していくことによって言語の文字列を生成することができる規則の集まり」と見るものである。