なぜ右回帰パーサーが無限ループしないのですか？

Question

左回帰はパーサーを無限ループにします。それでは、正しい再帰ではなぜ同じことは起こりませんか？

Answer 1

再帰的降下パーサーでは、A -> B C | Dのような文法規則は、現在の位置でBを解析しようとすると、Bが終了した位置でCを解析しようとすると実装されます。いずれかが失敗した場合は、現在の位置でDを解析しようとします。

CがA（右回帰）に等しい場合、それは問題ありません。つまり、Bが成功した場合、Bの後ろの位置でAを解析しようとします。つまり、最初にBを解析し、Aを新しい位置で再試行するか、Dを試してみることを意味します。

しかし、BがA（左回帰）に等しい場合、それは非常に問題です。今、Aを解析するので、まず現在の位置でAを解析しようとします。現在の位置でAを解析しようとします...無限になります。私たちは決してポジションを進めず、A（自分自身を試し続けている）を除いて決して何も試していないので、私たちが終了するかも知れないポイントには決して行きません。

¹フルバックトラッキングを仮定します。それ以外の場合は、BやCがトークンを消費した場合には、Dを試行せずに失敗する可能性があります（先読みしたトークン以上のトークンですが、この話題はありません）。