再帰下降構文解析
バックトラックのない再帰下降パーサを 予言的パーサ(predictive parser)と呼ぶ。予言的構文解析は文脈自由文法の一種であるLL(k)文法クラスでのみ可能であり、ある正の整数 k が存在し、再帰下降構文解析で次に使用すべき生成規則を選択するのに k 個のトークンを調べることで決定可能である。LL(k)文法には曖昧さがなく、左再帰も含まれない。文脈自由文法は左再帰のない形式に変換可能だが、左再帰を排除しただけでLL(k)文法となるわけではない。予言的パーサは線形時間で動作する。
バックトラックのある再帰下降構文解析では、各生成規則を毎回試すことで適用すべき生成規則を決定する。バックトラックのある再帰下降構文解析はLL(k)文法以外にも適用できるが、LL(k)以外の文法で有限時間以内に構文解析が完了するかどうかは保証されない。また完了したとしても、バックトラックのある再帰下降構文解析は指数関数時間を要する。
予言的パーサはよく使われているものの、文法をLL(k)形式に変換するよりも、LR法やLALR法のパーサを作成することも多い。