Карпов - Основы построения трансляторов (2005), страница 39

Эти попытки связаны с обобщением грамматик Хомского в том или ином отношении с тем„чтобы формализовать в новой области основную идею Хомского — идею структурного анализа объекта. Грамматики Хомского могут порождать цепочки символов, которые можно рассматривать как одномерные последовательности из конечного множества объектов. Очевидно, что символы (как терминальные, так и нетерминальные) можно рассматривать как объекты.

имеющие ровно две точки связи — левую и правую, а строку символов — как такое их соединение, в котором правая точка связи одного символа связывается с левой точкой связи своего соседа. Простое обобщение порождающих грамматик Хомского можно построить, рассматривая в качестве символов произвольные объекты с несколькими точками соединения. Простейшей математической моделью такого рода является граф.

Правила такой обобщенной грамматики, порождающей графы, должны определять, как более сложные графы (конструкции) строятся из менее сложных, соединяясь в допустимых точках связи. 8.1. Плекс-грамматики Одним из первых расширений понятия порождающей грамматики Хамского для порождения структур„отличных от цепочек символов. явились так называемые текс-гралтитики (р!ех дгап1таг~).

Слово рохин в английском языке означает переплепгеаие. В соответствии с названием, такие грамматики порождают структуры произвольных объектов, соединенных в заранее определенных точках связи. Плекс-грамматики были введены впервые в ~ Г7! ~. Глава 8 Терминальные и нетерминальные символы плекс-грамматики называются нэйпами. Нэйп — это произвольный объект„имеющий произвольное конечное число точек связи (от англ. ларе (п айасйпд роп11 епй~у) — объект с л точками связи). Нэйп представляется именем и точками связи.

Аналогом не- терминалов в грамматиках Хомского является нетерминальный нэйп — конструкция или объект с несколькими точками связи. Правила плекс-грамматики определяют, как сложные нэйпы формируются из примитивных нэйпов и других структур. Рассмотрим простейший пример плекс-грамматики (рис. 8.1). Терминальные символы грамматики составляют вертикальное и горизонтальное ребра, каждое с двумя точками связи, обозначенными 1 и 2. Рис. 8.1. Простейший пример плекс-грамматики Правило грамматики представлено на рис. 8.2. Это правило определяет нетерминальную структуру„поименованную 1 и имеющую три точки связи, пронумерованные по порядку 1, 2 и 3. Структура строится из двух терминальных объектов ~' (это показывает первый член правой части продукции) только одним соединением: второй точки связи первого с первой точкой связи второго.

Именно это и показывают первые две группы в правой части правила. Третья группа характеризует точки связи (1, 2 и 3) новой нетерминальной структуры. Первая точка связи у 1 образуется только из первой точки связи первого связанного объекта (обозначено 10), вторая точка связи 1 — это объединение второй точки связи первого составляющего структуру объекта с первой точкой связи второго (обозначено 21). Третья точка связи 1 — это просто вторая точка связи второго объекта структуры (обозначено 02). Очевидно, что правила плекс-грамматики можно представлять либо в графической форме, либо в эквивалентной текстовой форме. Рис.

8.2. Правило грамматики Обобщения грамматик Хомского Формально, контекстно-свободная плекс-грамматика имеет продукции в форме: где А — имя нетерминального объекта грамматики, Л,.~ — это список внешних точек соединений нетерминальной конструкции А„р — это список компонентов структуры, образующей А, 1~ — список взаимосвязей подструктур правой части при образовании конструкции А.

Наконец, Л~ — это список соответствия, показывающий, как каждая внешняя точка связи у конструкции А соотносится с точками связи составляющих А подконструкций. Следующее порождающее правило нашей плекс-грамматики связывает три объекта. Первый из них — нетерминальный объект У, два остальных — это горизонтальные терминальные объекты грамматики, каждый со своими точками связи (рис. 8.3). Рис. 8.3. Правило ллекс-грамматики связывает три объекта Поясним правило. Конструкция Г с тремя внешними точками связи, обозначенными 1, 2 и 3, строится из трех подконструкций — конструкции 7 и двух одинаковых конструкций Ь. Соединяются эти подконструкции для получения Г в двух точках.

Первое соединение получено соединением точки связи 1 первого объекта и точки связи 1 второго. Третий объект не участвует в этом соединении. Таким образом, эта точка соединения представлена в списке Г~ как 110. Вторая точка соединения (201) получена соединением второй точки связи первого объекта — У и первой точки связи третьего объекта А, второй объект в этой связи не участвует.

Список соответствия Л~ здесь построен для трех внешних точек конструкции К Первая внешняя точка связи Г образована второй точкой связи второго объекта, первый и третий объекты в этой связи не участвуют. Вторая внешняя точка связи Г образована второй точкой связи третьего объекта, первый и второй в этой связи не участвуют. Наконец, третья внешняя точка Г образована третьей точкой связи первого из составляющих эту конструкцию объектов. Третье правило грамматики имеет очевидный смысл (рис. 8.4). Порожденная конструкция — буква Р— будет иметь в этой грамматике следующее дерево вывода (рис.

8.5). Глава 8 Рис. 8.4. Третье правило грамматики Рис. З.б. Дерево вывода порожденной конструкции Следует отметить, что эта грамматика двусмысленна. Действительно, легко видеть, что можно построить несколько различных деревьев вывода одной и той же структуры в этой грамматике. Рассмотрим пример плекс-грамматики совсем из другой области — органической химии.

Плекс-грамматика, порождающая сложные СН-структуры, может выглядеть следующим образом. Пусть терминальные нэйпы этой грамматики — это атомы углерода и водорода с соответствующими валентностями, представленными точками связи (рис. 8.6). Рис. 8.6. Пример плекс-грамматики из органической химии Обобщения грамматик Хомского 285 Рассмотрим плекс-грамматику, порождающую цепочки соединений углерода и водорода. Грамматика содержит пять правил (рис, 8.7). 1 2 1 2 ~1 21 2 к» вЂ” <Цепь> — е -ч» о — <Секция> ~ ~ е — «Секция> ~ <Цепь> — е 3.

Рис. 8.7. Плекс-грамматика, порождающая цепочки соединений углерода и водорода Текстовая запись продукций этой грамматики более компактна, хотя и менее наглядна: 1. <Цепь>(1, 2) — + <Секция>() (1, 2) ~ <Секция> <Цепь> (21) (10, 02) 2. <Секция>(1, 2) — + <СН ><С><СНз><СН><СН >(21000, 02100, 03020, 04010, 00031) (10000, 00002) 3.

<СНз>(1) -+ <СН2> <Н> (21) (10) 4. <СН2>(1, 2) — + СН> <Н> (21) (10, 30) 5. <СН> (1, 2, 3 — + <С> <Н> (41) (10, 20, 30) Эта грамматика порождает цепочки произвольной конечной длины, пред- ставляющие собой структуру молекулы резины (рис. 8.8). 266 Глава 8 Рис. 8.8. Грамматика структуры молекулы Резины Нет сомнений, что свойства химических соединений зависят не только от их состава, но также и от структуры молекул, образующих соединение. Использование графовых порождающих грамматик для описания таких структур может позволить автоматическое распознавание структур сложных молекул и, следовательно, автоматический анализ свойств соответствующих химических соединений, если семантический анализ входной структуры производить в соответствии с принципами синтаксически-ориентированной трансляции, Список литературы ~АСУ011 Ахо А., Сети Р., Ульман Дж.

Компиляторы. Принципы, технологии, инструменты. — М.: СПб. Киев, Вильямс, 2001. ~АУ78~ Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, т. 1, 2, 1978. ~В771 Вайнгартен Ф. Трансляция языков программирования. — М.: Мир, 1977.

~Г66~ Гладкий А. В. Лекции по математической лингвистике для студентов НГУ. — Изд-во Новосибирского Госуниверситета, 1966. ~Г70~ Гинзбург С. Математическая теория контекстно-свободных языков.— М.: Мир„1970. ~Г73~ Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973. ~ГХ751 Грейбах Ш., Хопкрофт Дж.

Грамматики с рассеянным контекстом. В сб. "Языки и автоматы" под ред. А. Н. Маслова и 3. Д. Стоцкого. — М.: Мир, 1975. ~К84~ Котов В. Е. Сети Петри. — М.: Наука, 1984. ~ЛН74~ Линдсей П., Норман Д. Переработка информации у человека. — М.: Мир, 1974. ~П84~ Питерсон Дж. Теория сетей Петри и моделирование систем. — М.: Мир, 1984. ~С861 Саломаа А. Жемчужины теории формальных языков.

— М.: Мир, 1986. ~ХС82~ Хеллерман Х., Смит А. АПЛ-360. Программирование и применения. — М.: Машиностроение„1982. ~Х621 Хомский Н. Три модели для описания языка. — "Кибернетический сборник", вып. 2, ИЛ, 1962. ~Х62а~ Хомский Н. О некоторых формальных свойствах грамматик. — "Кибернетический сборник", вып. 5, ИЛ, 1962.

Список литера туры ~ЗШ89~ Эрбс Х.-З., Штольц О. Введение в программирование на языке Паскаль. — М.: Мир, 1989. ~В941 Г)еге!с В1с! ег~оп. Т11е опупев оГ 1шушь6с ипЫегка!ь: Вагвш апс1 СЬошь1су ~оуейег адаш 0 Ьпюегя1у оГ На~ай, 1994. ~СМ58~ С11оп1Жу Х., М111ег 6. Гшйе йа1е !апр~адея. — "1Ыогп1аиоп апс3 Соп1го!", 1(2):91-112, Мау, 1958. ~!'711 Герцег 3. Р1ех !ащиадеь. 1пГогшайоп ~с1епсе~ 3, 1971. 1К68~ К~шй О.

Яешапйс~ оГСогйех1-аггее 1 апр~аоек. — Ма111. Буй. ТЬеогу, ч 2„ Хо 2, 1968. Русский перевод: Д. 3. Кнут. Семантика контекстно- свободных языков. В сб. "Семантика языков программирования". — М.: Мир, 1980. ~Р921 Рагюпз Т. 1п1гос1исйоп го Сошр1!ег Сом1госйоп. — Соп1ро1ег ~сйепсе Ргеы„1992. ~К75~ КоЬшюп 3..1. РегГоггпапсе дгагпшагз д 1п: В.К.В.есЫу ес1., "Яреес11 Кесоуп16оп. 1пи1ед Рарегь ргезеп~ед а1 йе 1974 1ЕЕЕ 8ушрояшш". МУ, Асас1епис Ргею, 1975, рр. 401 — 427. [Т971 !'еггу Р.

В. Сошр~!его апд Сошр11ег бепега1огк: Ап 1п1госЬс6оп %1Й С++ 0 Ы. Т11ошюп Сошро1ег Ргею, 1997. Предметный указатель Завершатель 254 Идентификаторы 171 Интерпретатор 14 Инфиксная запись 119 Исходный код 14 Бэктрскинг 58, 149 Бэкуса — Наура форма 70 Лексема 167 Автомат: с магазинной памятью 65, 174 О конечный 69 О линейно-ограниченный 65 О распознающий 60 Алгоритм: О Кока — Янгсра — Касами 251, 257 О распознавания 188 О Эрли 251 О перевода в ПОЛИЗ 119 О символьного дифференцирования 128 Алгоритмическая проблема 146 Арность операции 119 Атрибутная грамматика 91, 94 Грамматика: О 11(К) 153 О распознающая 31 О предшествования 216 О типа 0 56 О Хомского 81 О автоматные 153 О рекурсивного спуска 153, 178 Грамматическая структура 20 Граф: О автоматной грамматики 154 О переходов конечного автомата 159 Деревья вывода 251 Детерминированный нисходящий синтаксический анализ 149 Ключевые слова 171 Код: О объектный 14 О исходный 14 Компилятор 14, 188 Конечный автомат 69 Константы 171 КС-грамматика: О -свободная 137 О ациклическая 139 О базовая 77 О лсворекурсивная 139 О неукорачивающая 137 О редуцированная 136 Т Операторы 17! Операция типа: О сложения 122 О умножения 122 Факторизация 181 Функция: О 1=! ЮТ 143 О Г011 ОЧ~ 143 О Г01.1 0%(А) 197 О М ЕХТ(А — +и) 197 1Яслсвая машина 14 Язык 29 О входной 186 О выходной 187 О исходный 14 О Милан 102 О объектный 14 Машина Тьюринга 62 Метаязык 70 Метод нисходяшего синтаксического анализа 154 Нетерминалы тупиковые 136 Неукорачивающисся грамматики 58 Нормальная Форма: О Грейбах 142 О Хомского 141 Нотация Бэкуса — Наура 70 НС-грамматики 77 Нэйп 262 О имя 262 О точка связи 262 Пи-код 15 Плекс-грамматики 261 ПОЛИЗ ! 20 Польская инвсрсная запись 119 Постфиксная запись 119 Правила преобразования 77 Прсдсказатсль 254 Препроцессор 15 Префиксная запись 119 Простые 1.йф)-анализаторы 227 Распознаватель 62 О входного языка 1б! Свободный прсфиксный язык 79 Связка 149, 209 Семантика 16, 132 Предметный указа тепь Семантические атрибуты 91 О синтезированный 94 О унаследованный 94 Семантические правила 93 Сеть Пстри 78 Символ КС-грамматики, производящий 135 Символьная цепочка 153 Символьные последовательности 153 Сингулярная продукция 138 Синтаксис 16 Синтаксическая диаграмма 177 Синтаксически-ориентированная трансляция 17 Ситуация 217 С-маркер 77 Стековая машина 187 Структура транслятора 88 Считыватель 254 Таблица переходов 174 Типы продукций 154 Транслятор 13 Ун и всрсал ьн ыс алгоритмы 251 Условный оператор 106 'с и с я: " ф Пыт з Мызы жт Е к тета и т рборий и тбкйолотнй могрдвбцтйцтййяий ОСНОВЫ ПОСТРОЕНИЯ ТРАНСЛЯТОРОВ цепью «нити явп тся пес ановкв баязвык4йртязтйчм ктябрин "трср— * фф~ 'Йвсьнык юыюе, резькснвние звцач псстрсення тр вне мооров Пред- Х р ставпена основная «снцы|ци» транстиции .

смттаксически ариан пбтзванная обработка предиикений вкодщяо языка. В рамкак зтсй концепцни рассмвтривакяся основные зтаты трансляции: воссев нсепение стррктрры вксднспт текста. еычиспение гмыспа текста по ертрй ызк Ч:Внюзпсттое т яэавнснмт От текнспппти и среде ы и» созда.зщ ;*;.. б изб~ив методики транспыезк прцсспаяынныв в ысобии.

читвмпь ~~ф.„,„. м~~;~ф~ Кыяа пред азначвнв дты стртычпы аузты напраяпяым "Информатика и аычиспитепы ее тазика" и "СИстемный мылив и упраапение", е также дерти родственнык напраапений. ттттз е тзу н*.з 3 .