Parsing Expression Grammar
PEGはそのまま再帰下降構文解析の構文解析器に変換可能である。ただしそれをナイーブに実装すると最悪の場合、最後まで先読みして失敗し、また最初から繰返すことにより指数時間かかる可能性がある構文解析器になってしまう。
しかし、PEGが21世紀に入って以降に見直される傾向となったのは、再帰下降構文解析の途中結果をメモ化し、各構文解析関数が同じ入力位置について高々1回までしか呼ばれないようにするPackrat Parserの実用性が確認されたためである。メモ化のためにメモリ領域を必要とすることと引き換えに、理論的には常に線形時間で動作する。遅延評価の言語では自然に実装できることもこれを後押しした。
ただし実際のプログラミング言語などでは、典型的にはC言語においてtypedefで「型の名前」として扱われるべき名前が追加されることによる大域的な文脈依存性などで、再度の解析が必要となる場合があるが、そういったものも含め、たいていは実用的な範疇である。