Дана контекстно-свободная грамматика с левой рекурсией A -> A a | b; преобразуйте её в эквивалентную без левой рекурсии, объясните, почему это важно для LL(1)-парсеров и как сохраняется язык
Пусть исходная грамматика \[ A \to A\,a \mid b \] (немедленная левая рекурсия). Эквивалентная без левой рекурсии форма: \[ A \to b\,A' \qquad A' \to a\,A' \mid \varepsilon \] Почему это важно для LL(1)/рекурсивного нисходящего парсера: - Левая рекурсия приводит к бесконечной рекурсии при реализации через рекурсивные вызовы (например, при рекурсивном нисходящем парсинге): правило \(A\to A\,a\) сразу вызывает разбор \(A\) снова и снова. - LL(1)-парсер требует отсутствие левой рекурсии и наличие разрешимости по одному символу (различимые FIRST/FOLLOW множества) чтобы выбирать единственное правило по текущему входному символу. Устранив левую рекурсию, грамматика становится пригодной для построения таблицы LL(1). Почему язык сохраняется (короткое доказательство эквивалентности): - Исходный язык: любая цепочка получается либо сразу как \(b\), либо применяя \(A\to A\,a\) \(n\) раз, затем \(A\to b\). Следовательно строки имеют вид \[ \{\,b\,a^n \mid n\ge 0\,\}. \] - В преобразованной грамматике сначала выводится \(b\), затем нетерминал \(A'\) порождает любую (возможно нулевую) последовательность символов \(a\) через правила \(A'\to aA'\) или завершает через \(\varepsilon\). Это даёт точно те же строки \(\{b\,a^n\mid n\ge 0\}\). - Соответствие шагов вывода: каждое применение левой рекурсивной продукции \(A\to A\,a\) в исходной грамматике соответствует одному применению \(A'\to a\,A'\) в преобразованной; завершение через \(A\to b\) соответствует \(A\to bA'\) с последующим \(A'\to\varepsilon\). Таким образом преобразование устраняет проблемную левую рекурсию, не меняя порождаемый язык.
\[
A \to A\,a \mid b
\]
(немедленная левая рекурсия). Эквивалентная без левой рекурсии форма:
\[
A \to b\,A' \qquad A' \to a\,A' \mid \varepsilon
\]
Почему это важно для LL(1)/рекурсивного нисходящего парсера:
- Левая рекурсия приводит к бесконечной рекурсии при реализации через рекурсивные вызовы (например, при рекурсивном нисходящем парсинге): правило \(A\to A\,a\) сразу вызывает разбор \(A\) снова и снова.
- LL(1)-парсер требует отсутствие левой рекурсии и наличие разрешимости по одному символу (различимые FIRST/FOLLOW множества) чтобы выбирать единственное правило по текущему входному символу. Устранив левую рекурсию, грамматика становится пригодной для построения таблицы LL(1).
Почему язык сохраняется (короткое доказательство эквивалентности):
- Исходный язык: любая цепочка получается либо сразу как \(b\), либо применяя \(A\to A\,a\) \(n\) раз, затем \(A\to b\). Следовательно строки имеют вид
\[
\{\,b\,a^n \mid n\ge 0\,\}.
\]
- В преобразованной грамматике сначала выводится \(b\), затем нетерминал \(A'\) порождает любую (возможно нулевую) последовательность символов \(a\) через правила \(A'\to aA'\) или завершает через \(\varepsilon\). Это даёт точно те же строки \(\{b\,a^n\mid n\ge 0\}\).
- Соответствие шагов вывода: каждое применение левой рекурсивной продукции \(A\to A\,a\) в исходной грамматике соответствует одному применению \(A'\to a\,A'\) в преобразованной; завершение через \(A\to b\) соответствует \(A\to bA'\) с последующим \(A'\to\varepsilon\).
Таким образом преобразование устраняет проблемную левую рекурсию, не меняя порождаемый язык.