Дана грамматика, порождающая язык арифметических выражений с приоритетами; объясните, как устранить левую рекурсию и почему это важно для построения LL‑парсеров
Приведу конкретно и коротко. Исходная (типичная) грамматика с леворекурсией: \[ E \to E + T \mid E - T \mid T \] \[ T \to T * F \mid T / F \mid F \] \[ F \to (E) \mid \text{num} \] Почему левую рекурсию надо убирать: - LL‑парсер (топ‑даун, рекурсивный спуск или таблица LL(1)) при попытке применить правило \(E \to E + T\) начнёт рекурсивно разбирать \(E\) снова и получит бесконечную рекурсию — разбор не завершится. - Левые рекурсивные правила приводят к конфликтам FIRST/FIRST и делают невозможным построение предиктивной (LL(1)) таблицы. Как устраняют непосредственную левую рекурсию (общий приём): для всех правил вида \[ A \to A\alpha_1 \mid A\alpha_2 \mid \dots \mid \beta_1 \mid \beta_2 \mid \dots \] где каждая \(\beta_i\) не начинается с \(A\), переписывают как \[ A \to \beta_1 A' \mid \beta_2 A' \mid \dots \] \[ A' \to \alpha_1 A' \mid \alpha_2 A' \mid \dots \mid \varepsilon \] Применим к нашей грамматике (сохранится приоритет операций): \[ E \to T\ E' \] \[ E' \to +\ T\ E' \mid -\ T\ E' \mid \varepsilon \] \[ T \to F\ T' \] \[ T' \to *\ F\ T' \mid /\ F\ T' \mid \varepsilon \] \[ F \to (E) \mid \text{num} \] Это устраняет левую рекурсию и одновременно сохраняет приоритеты: \(T\) (умножение/деление) вложено в \(E\) (сложение/вычитание), поэтому умножение имеет более высокий приоритет. Как устраняют косвенную (непосредственную) левую рекурсию: - Упорядочить нетерминалы \(A_1,\dots,A_n\). - Для i от 1 до n: для каждого правила \(A_i \to A_j \gamma\) с \(j<i\) подставить все правые части \(A_j\); затем убрать непосредственную левую рекурсию для \(A_i\) стандартным приёмом. Коротко о значении для LL‑парсеров: - Устранение левой рекурсии обеспечивает конечность рекурсивного спуска (нет бесконечной левой рекурсии). - Тогда можно вычислить корректные множества FIRST/FOLLOW и построить единственную предиктивную продукцию — парсер становится детерминированным и эффективным (LL(1) или расширения LL(k)).
Исходная (типичная) грамматика с леворекурсией:
\[
E \to E + T \mid E - T \mid T
\]
\[
T \to T * F \mid T / F \mid F
\]
\[
F \to (E) \mid \text{num}
\]
Почему левую рекурсию надо убирать:
- LL‑парсер (топ‑даун, рекурсивный спуск или таблица LL(1)) при попытке применить правило \(E \to E + T\) начнёт рекурсивно разбирать \(E\) снова и получит бесконечную рекурсию — разбор не завершится.
- Левые рекурсивные правила приводят к конфликтам FIRST/FIRST и делают невозможным построение предиктивной (LL(1)) таблицы.
Как устраняют непосредственную левую рекурсию (общий приём):
для всех правил вида
\[
A \to A\alpha_1 \mid A\alpha_2 \mid \dots \mid \beta_1 \mid \beta_2 \mid \dots
\]
где каждая \(\beta_i\) не начинается с \(A\), переписывают как
\[
A \to \beta_1 A' \mid \beta_2 A' \mid \dots
\]
\[
A' \to \alpha_1 A' \mid \alpha_2 A' \mid \dots \mid \varepsilon
\]
Применим к нашей грамматике (сохранится приоритет операций):
\[
E \to T\ E'
\]
\[
E' \to +\ T\ E' \mid -\ T\ E' \mid \varepsilon
\]
\[
T \to F\ T'
\]
\[
T' \to *\ F\ T' \mid /\ F\ T' \mid \varepsilon
\]
\[
F \to (E) \mid \text{num}
\]
Это устраняет левую рекурсию и одновременно сохраняет приоритеты: \(T\) (умножение/деление) вложено в \(E\) (сложение/вычитание), поэтому умножение имеет более высокий приоритет.
Как устраняют косвенную (непосредственную) левую рекурсию:
- Упорядочить нетерминалы \(A_1,\dots,A_n\).
- Для i от 1 до n: для каждого правила \(A_i \to A_j \gamma\) с \(j<i\) подставить все правые части \(A_j\); затем убрать непосредственную левую рекурсию для \(A_i\) стандартным приёмом.
Коротко о значении для LL‑парсеров:
- Устранение левой рекурсии обеспечивает конечность рекурсивного спуска (нет бесконечной левой рекурсии).
- Тогда можно вычислить корректные множества FIRST/FOLLOW и построить единственную предиктивную продукцию — парсер становится детерминированным и эффективным (LL(1) или расширения LL(k)).