Математическая теория формальных языков



             

Восходящий разбор - часть 2


Пример 13.2.9.

Рассмотрим контекстно-свободную грамматику

из примера 13.1.17. Язык

распознается недетерминированным МП-автоматом , где

и

Можно проверить, что МП-автомат M является восходящим магазинным анализатором для грамматики G из примера 13.1.17.

Определение 13.2.10.

Контекстно-свободная грамматика

принадлежит классу LR(1), если для любых , , , , , , , ,

из условий

следует, что A1 = A2

и .

Замечание 13.2.11.

Классу LR(1) принадлежат те языки, для которых возможен восходящий разбор слова при чтении слева направо с заглядыванием на один символ вперед.

Замечание 13.2.12.

Буква L в названии класса LR(1) означает, что входное слово читается слева направо (left-to-right). Буква R означает, что строится правосторонний вывод (rightmost derivation). Число 1 указывает на то, что на каждом шаге для принятия решения используется один символ неразобранной части входного слова.

Теорема 13.2.13.

Для каждой грамматики из класса LR(1) существует детерминированный восходящий магазинный анализатор.

Доказательство можно найти в [2, с. 420-447].

Теорема 13.2.14.

Грамматики из класса LR(1) порождают только детерминированные контекстно-свободные языки.

Теорема 13.2.15.

Каждая грамматика из класса LL(1) принадлежит также классу LR(1).

Упражнение 13.2.16.

Найти все правые разборы слова bbacba в грамматике

Упражнение 13.2.17.

Найти детерминированный восходящий магазинный анализатор для грамматики

Упражнение 13.2.18.

Найти детерминированный восходящий магазинный анализатор для грамматики




Содержание  Назад