Yacc
まず一般的なコンパイラの構成について簡単に説明する。
ソースコードを中間表現あるいは機械語に変換するコンパイラは、ソースコードを入力として受け取り、構文木を構築して出力する構文解析部(A)と、その構文木を入力として受け取り、目的の中間表現ないし機械語のコードを生成して出力するコード生成部(B)からなる。
このうち構文解析部(A)は、文字列からトークンを切り出しトークン列とする字句解析器(レキシカルアナライザ、トークナイザ、スキャナ、図のA-1)と、構文規則に従ってトークン列に対し構文解析をおこない、構文木を出力する(狭義の)構文解析器(パーサ,パーザ、図のA-2)から成る。(必ずしもこのようにする必要はないが、典型的な構成としてはこのようにする)
構文解析器は直接書くこともできるが、煩雑になる部分があり、特にボトムアップ構文解析のプログラムを手で書くのは現実的ではない。そういった構文解析器を、機械可読な構文規則群から自動生成してくれるツールがパーサジェネレータである。YaccはLALR、通常LALR(1)の構文解析器を生成する。