|
конспекты
занятий по курсу «Теория и реализация языков программирования» Занятие 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). |
|
||||||
|
|
|||||||
|
|
|
||||||