LL法
1990年代中ごろまで、k が 1 より大きい LL(k) の構文解析はほとんど実用化されなかった。というのも、k が増えると指数関数的に構文解析表が大きくなるためである。この状況を変えたのは1992年の PCCTS の登場である(現在ではANTLRと呼ばれている)。PCCTS は多くのプログラミング言語を LL(k)構文解析器で効率的に構文解析でき、最悪ケースの問題も発生しないことを示した。さらに、先読みが限定されていてもLL法が有効な場合もあることが示された。一方、従来からの構文解析器生成ツール(yaccやbison)はLALR(1)構文解析表に基づいており、限定された先読みによるLR法を使っている。
LL法またはLL構文解析とは、文脈自由文法のサブセットのためのトップダウン構文解析法の一種である。入力文字列を左 (Left) から構文解析していき、左端導出 (Leftmost Derivation) を行う(このため、LL法と呼ぶ。LR法も参照されたい)。この方式で構文解析可能な文法のクラスを LL文法 と呼ぶ。
以下では、表駆動型の構文解析を解説する。他の手法として、個々の構文規則に対応するサブルーチンの呼び出しから成る再帰下降構文解析もある。表駆動型は計算機による生成に向き、再帰下降構文解析はコードの手書きに向いている(しかし、再帰下降構文解析のコードを自動生成する ANTLR のようなツールもある)。
k 個の字句(トークン)を先読みする場合、LL(k) と表記する。ある文法について LL(k) 構文解析器が存在し、バックトラッキングなしで構文解析できる場合、その文法を LL(k) 文法であるという。LL(1) 文法は機能が限定されるが、次のトークンだけを先読みすればよいため、構文解析器の生成が容易であり、よく使われている。一般に設計に問題がある言語は大きな k が必要となる傾向があり(k が大きいということは、人がプログラムを読む場合にも、たくさん読まないと意味を把握できないということである)、構文解析が大変になる。