Карпов - Основы построения трансляторов (2005) (943926), страница 13
Текст из файла (страница 13)
е. слова ~вернее. словоформы) естественного языка. 2.7.5. Языки сетей Петри Грамматики Хомского являются моделью„которая лежит в основе подавляющего большинства идей в области спецификации формальных языков. Нотация Бэкуса — Наура, например, является просто оолее удобным представлением правил грамматик Хомского типа 2, синтаксические диаграммы — их наглядным графическим представлением, а грамматики с рассеянным контекстом разрешают одновременную замену сразу нескольких нетерминалов в порождаемой строке, что является очевидным обобщением КС- грамматик. Но грамматики Хомского отнюдь не единственно возможный способ задания языков.
Фактически порождающим механизмом при задании языка может служить формальная модель любой природы, каким-то образом определяющая множество одномерных последовательностей объектов (символов) над конечным словарем. В этом разделе мы рассмотрим одну из таких моделей порождения — сети Петри. Сеть Петри — это ориентированный граф, состоящий из двух типов вершин, с ребрами, которые могут соединять только вершины разных типов. Вершины первого типа — позиции или места — обозначаются кружками„вершины другого типа — переходы — полочками.
В каждой позиции может быть некоторое количество маркеров. Динамика сети Петри выражается в том. что у нее может сработать переход, если он активный. Активным переход будет в случае, если во всех позициях, из которых в переход ведут ребра, находится по крайней мере один маркер. При срабатывании перехода из каждой позиции, из которой в этот переход ведут ребра, изымается по одному маркеру и в каждый переход, в который направлены ребра из данного перехода., по одному маркеру добавляется.
Сети Петри используются для моделирования систем параллельных процессов, События, которые могут произойти в системе, представляются в сети Петри переходами. Множество возможных последовательностей срабатыва- Распознавание предложений языков. порожденных трансформационными грамматиками, связано с рядом трудностей. Такие распознаватели могут работать только на основе метода проб и ошибок, являются очень медленными, их алгоритмы имеют экспоненциальную сложность. В связи с этим в настоящее время для задания и распознавания естественных языков чаще используются другие механизмы. Языки и грамматики ний переходов характеризует систему, которая моделируется сетью Петри. Пометим некоторые (существенные для конкретного приложения) переходы сети символами конечного алфавита.
Множество всех префиксов последовательностей пометок срабатываний переходов сети Петри является, очевидно, языком, который называется свободным префиксным языком сети Петри. Таким образом, язык определяется динамикой, работой сети Петри. Рис. 2.24. Сеть Петри для моделирования взаимного исключения На рис. 2.24 представлена сеть Петри, моделирующая использование семафора для решения проблемы взаимного исключения двух параллельных процессов.
Эта проблема заключается в том„чтобы синхронизировать два параллельных процесса (представленных здесь последовательностями позиций <рО, р1, р2> и <рЗ, р4, р5>) таким образом, чтобы в своих критических интервалах, связанных, например, с использованием общего ресурса, оба процесса не могли бы находиться одновременно. Критические интервалы в двух процессах нашего примера моделируются позициями р2 и р5.
События входа в критический интервал и выхода из него моделируются для двух процессов переходами ~1, ~2 в одном процессе, и ~4, г5 во втором. Именно эти интересующие нас события помечены ф, ~2 помечены а и о, а ~4, 15 помечены с и с~). Легко видеть, что префиксный язык, порождаемый этой сетью Петри — это язык, определяемый регулярным выражением (аЬ+са)*. Простейший анализ этого языка показывает, что проблема взаимного исключения здесь решена корректно. Действительно, все цепочки языка удовлетворяют требованию взаимного исключения: если один процесс вошел в свой критический интервал.
то другой не может войти в свой критический интервал, пока первый не выйдет из своего, что в терминах языка представлено так: цепочки языка не содержат фрагментов ас и са. Таким образом, анализ правильности функционирования двух параллельных процессов (а именно корректность решения Глава 2 80 Кроме префиксных языков иногда удобно рассматривать так называемые терминальные языки сетей Петри. Терминальным языком сети Петри называ- ется множество последовательностей пометок срабатывающих переходов се- ти, приводящих к некоторой заданной финальной маркировке сети. ПРИМЕР 2.25.
Г1усть в качестве финальной маркировки сети Петри рис. 2.25, а выбрана маркировка ~0, О, 1), т. е. такое состояние сети, при котором единственный маркер находится в позиции РЗ, а две других позиции не содержат маркеров. При достижении финальной маркировки эта сеть порождает терминальный язык Е = ~аЪ" ~ и > 0~, который. как известно, является КС-языком. Действительно, стартуя с начальной маркировки ~1, О, 0), переход (1 может сработать многократно произвольное число раз, после чего сработает переход (2.
Произвольное конечное число маркеров, равное числу срабатываний перехода ~1, накопится в позиции р2. Для достижения финальной маркировки все маркеры„появившиеся в позиции о2, должны исчезнуть, что возможно только при соответствующем числе срабатываний перехода ~3. Сеть Петри рис, 2.25, б при достижении финальной маркировки ~0, О, О, 1) порождает язык согласованных скобок ~язык Е; из равд. 2.2).
б) Рис. 2.25. Сети Петри, порождающие терминальные языки: а) язык ~ = (аЪ" ~ и > О~ и б) язык согласованных скобок Возникает вопрос: какой порождающей мощностью обладают сети Г1етри, иными словами, какие языки могут ими порождаться? Оказывается, что языки, порождаемые сетями Петри, занимают промежуточное положение между автоматными языками и языками, порождаемыми неограниченными грамматиками Хамского (и, следователыю, распознаваемыми машинами Тьюринга). Очевидно, что частным случаем сетей Петри являются конечные автоматы. Действительно, любая сеть Петри, в каждый переход которой входит ровно одна стрелка и из каждого перехода которой выходит ровно одна стрелка, проблемы взаимного исключения) проведен здесь с помощью языка, порож- даемого сетью Петри.
Языки и грамматики имеющая в качестве начальной маркировки ровно один маркер только в одной какой-нибудь позиции, представляет конечный автомат. Следовательно, все автоматные языки порождаются сетями Петри. Поскольку сети Петри могут порождать и неавтоматные языки (например, а Ь ), то они строго мощнее конечных автоматов. Легко построить сеть Петри, порождающую терминальный язык ~а"о"с" ~ Ж> О~ для терминальной маркировки (О, О, О, О, 1) (рис.
2.26). Этот язык не является КС-языком. Однако существуют КС-языки, которые не могут порождаться сетями Петри. Например, в ~П84~ это показано для языка ~всю ~ ие,'а, Ь~*, и — зеркальное отображение и ~. Отсюда следует справедливость теоремы 2,3. Рис. 2.26. Сеть Петри, порождающая терминальный язык (а" г>" с" ~ л > Ог ° ТЕОРЕМА 2.3. Класс помеченных сетей Петри строго мощнее класса конечных автоматов, не сравним с классом магазинных автоми'ов и строго менее мощен, чем машины Тьюринга. 2.8. Заключение В данной главе было введено понятие грамматики как конечного механизма задания бесконечного множества цепочек. Одним из наиболее простых и одновременно мощных механизмов задания языков является порождающая грамматика Хомского. Важнейшей идеей Хомского является то.
что для задания языка конечным образом необходимы объекты„отсутствующие в языке, которые по отношению к символам языка являются ибсгггракиггы.1ггг кагггегориялт, сггмволамгг метаязыка, которые пеоохойто тесиггг дато.'гните.гыго. когда чы еоворгглг о языке. Введение при задании языка таких абстрактных категорий, представляющих отдельные конструкции языка, а также правил, определяющих, как каждая конструкция может быть построена из символов языка (терминальных символов) и имен конструкций (нетерминальных символов) и составляет, по Хомскому, способ описания языка. Грамматику Хомского образует конечное множество таких правил.
Грамматика Хомского— это не алгоритм, любое правило грамматики можно применять при порожде- Глава 2 нии предложения языка, если выполнены условия его применения. Нетерминальные символы грамматики — это конструкции языка, они определяют множества цепочек — языки, выводимые из этих нетерминалов. Один из не- терминальных символов является стартовым, начальным символом: выводимое из него множество цепочек является языком, порождаемым грамматикой. Часто стартовый символ называется аксиомой грамматики. Важно отметить, что грамматика является внешней по отношению к языку, она может быть определена по-разному для одного и того же языка как множества цепочек. Как следствие, язык может задаваться различными эквивалентными между собой грамматиками, более точно, бесконечным числом возможных грамматик. Как мы увидим далее, из всех возможных грамматик, порождающих один и тот же язык, следует выбрать (или, что правильнее, построить) такую грамматику, для которой методы синтаксического анализа и семантические вычисления для данного языка будут просты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
