почему синтаксический анализатор сверху вниз не может обрабатывать левую рекурсию?

Подумайте, что он делает. Предположим, у нас есть леворекурсивное продукционное правило A -> Aa | b, и прямо сейчас мы пытаемся сопоставить это правило. Итак, мы проверяем, можем ли мы сопоставить A здесь, но для этого мы должны сначала проверить, можем ли мы сопоставить A здесь. Это звучит невозможно, и в основном это так. Используя парсер рекурсивного спуска, это, очевидно, представляет собой бесконечную рекурсию.

Это возможно с использованием более продвинутых методов, которые по-прежнему работают сверху вниз, например, см. [1] или [2].

[1]: Ричард А. Фрост и Рахматулла Хафиз. Новый алгоритм синтаксического анализа "сверху вниз" для учета неоднозначности и левой рекурсии за полиномиальное время. Уведомления SIGPLAN, 41(5):46–54, 2006 г.
[2]: Р. Фрост, Р. Хафиз и П. Каллаган, Модульный и эффективный нисходящий анализ неоднозначных леворекурсивных грамматик, ACL-IWPT, стр. 109–120, 2007.

Нисходящие синтаксические анализаторы не могут обрабатывать левую рекурсию Нисходящий синтаксический анализатор не может обрабатывать леворекурсивные продукции. Чтобы понять, почему нет, возьмем очень простую леворекурсивную грамматику.

1. S → a
2. S → S a Существует только одна лексема a и только один нетерминал S. Таким образом, таблица синтаксического анализа содержит только одну запись. Обе продукции должны войти в эту одну запись таблицы.

Проблема в том, что при просмотре вперед синтаксический анализатор не может знать, будет ли после просмотра вперед другой a. Но решение о том, какую продукцию использовать, зависит от этой информации.