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