左再帰
左再帰を含む形式文法は、以上のように単純にトップダウンの再帰下降構文解析で構文解析しようとすると無限再帰(無限ループ)に陥るため、なんらかの回避策が必要である。一方、LALR法などのボトムアップ構文解析では対照的に、右再帰よりも左再帰の方がスタックが深くならないので、むしろ効率が良いと言える。以下に示すような近年の研究では、トップダウン構文解析でも左再帰型の文法を扱える手法がいくつか示されている。2006年、Frost と Hafiz は、左再帰を含む曖昧な文法を扱う認識アルゴリズムを示した。2007年、Frost、Hafiz、Callaghan はこのアルゴリズムを拡張し、間接左再帰も直接左再帰も多項式時間で扱える構文解析アルゴリズムとし、非常に曖昧な文法であっても指数関数的な数になる構文木を多項式サイズでコンパクトに表現できることを示した。その後、このアルゴリズムは Haskell で書かれた構文解析器生成器で実装された。その実装の詳細は上記研究者らが PADL'08 で発表した論文で示されている。X-SAIGAには、このアルゴリズムや実装についてのより詳しい記述がある。