Чому ліва рекурсія є проблемою?

Ця проблема виникає тому, що граматика використовує ліву рекурсію в продукціях 1, 2, 4 і 5. З лівою рекурсією синтаксичний аналізатор зверху вниз може циклювати нескінченно без генерації початкового термінального символу, якому аналізатор може відповідати (і просувати вхідні дані).

Ліва рекурсія часто створює проблеми для парсерів через те, що це призводить їх до нескінченної рекурсії (як у випадку більшості низхідних парсерів) або тому, що вони очікують правил у нормальній формі, які це забороняють (як у випадку багатьох низхідних парсерів).

Проблема лівої рекурсії полягає в тому якщо ліва рекурсія присутня в граматиці, то це породжує неоднозначність, і під час синтаксичного аналізу в частині компіляції, присвяченій аналізу синтаксису, існує ймовірність того, що граматика створить нескінченний цикл.

На відміну від парсерів зверху вниз (LL), які не підтримують ліву рекурсію, Синтаксичні аналізатори знизу вгору (LR) підтримують як ліву рекурсію, так і праву рекурсію. Визначаючи конструкцію, подібну до списку, користувач генератора аналізатора LR, такого як Menhir, стикається з вибором між цими двома варіантами.

Вступ: ліва рекурсія — поширена проблема, яка виникає в граматиці під час синтаксичного аналізу під час компіляції. Важливо видалити ліву рекурсію з граматики, оскільки це може створити нескінченний цикл, що призведе до помилок і значного зниження продуктивності.

З ліворекурсивною граматикою, синтаксичний аналізатор зверху вниз може нескінченно розширювати кордон без генерації початкового термінального символу, який аналізатор може або зіставити, або відхилити. Щоб вирішити цю проблему, автор компілятора може перетворити ліво-рекурсивну граматику так, щоб вона використовувала лише праву рекурсію.