構文解析
構文解析にはさまざまな手法が提案されており、それぞれの構文解析法に対して適用可能な文法の範囲が存在する。歴史的に、もっぱらプログラミング言語を対象に研究が進んだが、大まかに演算子順位法、トップダウン構文解析法、ボトムアップ構文解析法に分類できる。演算子順位法、トップダウン構文解析法は構文解析理論によって後から説明が加えられ、ボトムアップ構文解析法は理論主導で作成された。
演算子順位法とトップダウン構文解析法の手続きは人力で作成されることがコンパイラの初期の時代にはあった。特に、トップダウン構文解析法である再帰下降構文解析法はそのプログラムの実際のコードが文法の記述によく一致することが知られている。しかし、一般にボトムアップ構文解析は非常に多くの内部状態とその間の遷移規則を必要とし、その手続きを人力で作成するのは困難である。
現在は、主にボトムアップ構文解析法であるLALR(1)を使用した構文解析器がパーサジェネレータによって生成されることが多い。この手法を使用するパーサジェネレータにはyaccやbisonなどがあり、どちらも代表的なパーサジェネレータである。これらのパーサジェネレータがこの手法を採用する理由としては、適用可能な文法範囲が十分に大きく、効率もそこそこ悪くないことなどが挙げられる。その他に、トップダウン構文解析法であるLL法が使用・生成される場合もままある。
プログラミング言語の場合は一般にその性質から、文字列(ソースコード)から字句(トークン)の列を取り出す前処理段階である字句解析(lexical analysis)と、そのトークン列を受け取り構文木を作るなどする後処理段階の2段階に分けてその全体を広義の構文解析とし、特に後処理のみを指して狭義の構文解析とすることが多い(PEGのように融合して扱う場合も多い手法もある)。以下、その狭義の構文解析について述べる。
構文解析では、構文木や抽象構文木のようなデータ構造を生成し、プログラミング言語のコンパイラであれば、いわゆるコンパイラバックエンドに渡す。サンプルなどによく見られる四則演算の式の演算などのような簡単な場合は、構文解析と同時に、目的の処理をおこなってしまう場合もある。
形式言語とオートマトンの対応は、良く理論付けられており、構文解析のアルゴリズムは、その入力である形式言語に対応するオートマトンの実装にほかならない。
プログラミング言語の場合、実用上、プログラムとして正しい入力のみを受け付けるような構文規則を定めることは現実的でない。そのため、一般に構文規則では言語本来より制約を弱くし(つまり、本来の言語の文法よりも広く、不正な入力も受け付けるようにし)後で不正なものを排除するようにすることが多い。
構文解析器を一から作るのではなく、パーサジェネレータで生成することも広く行われている。