конспекты занятий по курсу «Теория и реализация языков программирования» Занятие 6
(<<<) предыдущий		наверх			следующий (>>>)
6. Контекстно-свободные языки (продолжение) 6.2. Преобразование МПА-КСГ Алгоритм преобразования описан в [1] без подробного примера его применения (на увеличение объёма печатного издания всегда имеются некоторые ограничения), в связи с чем у отдельных учащихся возникают сложности с пониманием алгоритма. Поэтому пример для простого случая приводим ниже.
Пример 6.2. Преобразование МПА-КСГ Переход от МП автомата к КС-грамматике. Рассмотрим МПА, соответствующий языку : В соответствии с условиями теоремы о переходе от МПА к КСГ правила последней имеют следующий вид (запишем сначала их обобщённо, затем подробно): Или, подставляя все значения i: и * * * Далее (при записи непустой цепочки в магазин): Для функции перехода это будет Или, подставляя все значения i и j: * * * Для функции перехода это будет Или, подставляя все значения i и j: * * * Наконец, для функций перехода, которые записывают пустую цепочку в магазин:
Для Для Для			- - -
Переобозначим полученные вспомогательные знаки в КСГ более кратко.
	До переобозначения			После переобозначения
Или, более плотно: Полученная грамматика оказалась неприведённой (например, знаки Е и H никуда не сводятся). После приведения грамматики число её правил заметно сократится: Опробуем её на примере: или . Задача 6.1. Измените МПА так, чтобы он принимал данный язык, начиная с n = 0 (т.е. и пустую цепочку) и самостоятельно перейдите от него к КСГ.
Совет. Познакомьтесь с описанием соответствующих алгоритмов в пособии [1] и введёнными при этом понятиями и обозначениями. == Ссылки == [1] Серебряков В.А. [и др.]. Теория и реализация языков программирования. М.: МЗ-Пресс, 2003 (1-е изд.) и 2006 (2-е изд). – 294 c. (681.3/ Т33).
(<<<) предыдущий		наверх			следующий (>>>)