Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 43
Текст из файла (страница 43)
Например, имеет большое практическое значение вопрос: является ли данная НФБ-грамматика языка программирования неоднозначной (то есть допускает ли 4. К формальные свойства языков 153 4.1.3. Сложность алгоритма Иерархия Хомского до сих пор остается интригующей темой для исследований в теории программирования. Хотя лексический анализ и грамматический разбор хорошо изучены, все же осталось ещс множество вопросов, требующих решения. В этом разделе представлен обзор таких нерешенных вопросов. Таблица 4.1. Классы грамматик и абстрактных машин Уровень виерэрхии Хамского Класс грамматики Класс машин Неограниченные Контекстно-зависимые Контекстно-свободные Регулярные Машина Тьюринга Линейно-ограниченный автомат Автомат с магазинной памятью Конечный автомат Грамматика и машины.
Мы говорили, что существует опредслснное соответствие между классом грамматик и классом абстрактных машин. В табл. 4.1 вы найдете краткую сводку по этой теме, а на рнс, 4.2 соответствие классов машин и грамматик нрсдставлсно схематически. 1. Конечный автомат (рис. 4.2, а) состгтит из конечного графа состояний и рабочей ленты с возможностью перемсщсния по ней только в одном направлениии. При совершении очередной операции автомат считывает следующий символ с ленты и входит в новое состояние (узел на графе).
2. В автомате с магазинной памятью (рис. 4.2, б) в отличие от конечного автомата добавляется стек. При каждой опсрации автомат считывает следую- эта грамматика возможность нескольких вариантов синтаксического разбора программ или существует только один такой вариант для каждой программы)? Обычно каждый вариант синтаксического разбора соответствует определенному семантическому варианту прочтения программы, поэтому различные варианты синтаксического разбора приводят к различным значениям одной и той жс программы. Возникает вопрос: можно ли найти какую-нибудь общую для всех грамматик процедуру, определяющую, является ли данная грамматика неоднозначной? Теоретические исследования привели к неожиданному результату: искать такую процедуру бессмысленно, ее просто нет.
Формальное утверждение звучит следующим образом: вопрос об однозначности или неоднозначности НФБ-грамматики неразрешим, не существует никакой общей процедуры, позволяющей ответить на этот вопрос для любой НФБ-грамматики. Этот результат не может не разочаровывать, так как в случас сложной НФБ-грамматики, в которой имеются сотни различных правил, было бы очень удобно иметь такую протрамму, способную проверить эту грамматику на однозначность.
В большинство случаев мы можем написать программу, которая определяет, однозначна ли давнал грамматика; неразрешимость означает, что невозможно тгаписать одну тестируюгцую программу, которая давала бы ответ для всех программ. Для некоторых грамматик такой ответ не будет получен, как бы долго ни работала тестируюгцая программа. 154 Глава 4. Моделирование свойств языка щий символ с рабочей ленты и верхний символ стека, записывает новый символ в стек и входит в новое состояние.
3. Линейно-ограниченный автомат (рис. 4 2, а) похож на конечный автомат, но он может также записывать символы в ячейки рабочей ленты и перемещаться па ней в обоих направлениях. 4. Машина Тьюринга (рис. 4.2, г) похожа на линейно-ограниченный автомат, но только в данном случае лента является неограниченной в обоих направлениях. Все классы машин, кроме линейно-ограниченного автомата, уже обсуждались ранее. Линейно-ограниченный автомат, или ЛО-автомат ()йпеаг-Воипгтет) Ацгогпайоп, ВВА), определяется как машина Тьюринга, в которой можно использовать только ту часть рабочей ленты, которая содержит входные данные. Таким образом, объем памяти возрастает с увеличением обьема входных данных, и такой автомат способен распознавать более сложные цепочки. Тем не менее по сравнению с машиной Тьюринга возможности зтого автомата в отношении хранения информации не так велики, так как в данном случае рабочая лента не увеличивается неограниченно.
Рис. 4.2. Модели абстрактных машин: а — конечный автомат; б — автомат с магазинной памятью, в — линейно-ограниченный автомат; г — машина Тьюринга При обсуждении вычислительных возможностей детерминированной и недетерминированной версий абстрактной машины каждого типа мы получили следующие интересные результаты. 4д, Формальные свойства языков 155 Сравнениеверсий Тип машины Одинаковые Неодинаковые Конечный автомат Автомат с магазинной памятью Пинейно-ограниченный автомат Машина Тьюринга Одинаковые Как видно из этой таблицы, для языков типа 3 и 0 отсутствие детерминизма ничего не добавляет к вычислительным возможностям соответствующей абстрактной машины. Функциональные возможности недетерминированного автомата совпадают с возможностями эквивалентного детерминированного автомата.
Однако мы знаем, что для языков типа 2 педетерминированная версия абстрактной машины обладает большими возможностями. Мы можем распознавать строки-палиндромы при помоши недетерминированного автомата с магазинной памятью (см. раздел 3.3.5), так как этот автомат способен определять середину строки. Но при помощи недетсрминированного автомата с магазинной памятью ата задача не решается. Детерминированный автомат с магазинной памятью распознает детерминированные коитекстно-свободные языки, которые являются не чем иным, как языками ЕК(к), образующими основу для теории синтаксического разбора, используемой при построении компиляторов. К сожалению, для линейно-ограниченного автомата неизвестно, как соотносятся в смысле своих функциональных возможностей детерминированная и недетерминированцая версии ЛО-автомата.
Этой задачей ученые занимаются вот уже более тридцати лет. Полиномиальное время вычислений. Сложность решения проблемы детерминизма для ЛО-автоматов привела к возникновению специального раздела теоретической информатики, посвященного исследованию сложности алгоритмов. Детерминизм языка программирования можно соотнести с полипомцалъным временен вычисления. Этот термин означает следующее: если длина введенной строки равна п, то абстрактная машина выполнит обработку этой строки за время, которое можно оценитьсверхукакр(п),гдер — этонекоторыйполином(тоестьр(х) =а х" ч-аьх" ' чь ...
ь а„,х ч- а„). В противоположность атому можно цокаэатгч что в недетерминирован ком случае вычисление невозможно осуществить за полиномиальное время. Тогда задача об эквивалентности детерминированной и недетерминированной версий ЛО-автомата сводится к следующей задаче: если некоторое вычисление было выполнено эа неполиномиальное время (НП), сушествует ли такая машина, на которой это жс вычисление может быть выполнено за полиномиальное время (П)? Иначе говоря, верно ли, что НП = П? Эта задача для ЛО-автомата называется задачей Е1П-полноглы, а любая другая задача, эквивалентная этой, называется НП-полной. Следовательно, задача об эквивалентности детерминированной и не- детерминированной версий ЛО-автоматов является НП-полной.
Существует множество других задач, связанных с уже упомянутыми, для которых можно доказать, что они являются НП-полными; но пока у нас нет ответа на основной вопрос. Многие теоретики полагают, что ответа вообще не существует. Он просто находится за пределами аксиоматики используемого нами математического формализма. 156 Глава 4. Моделирование свойств языка Значение формальных моделей Тем, кто занимается практическим программированием, часто не хватает понимания важности теоретических моделей и исследований в области разработки языков и технологий программирования.
Может сложиться впечатление, что та степень абстрагирования от реальной задачи, которая необходима на первой стадии построения теоретической модели, иногда приводит к такому упроцгению этой задачи, что теряется весь ее смысл. Надо сказать, что довольно часто так и происходит. Выбрав неверную теоретическую модель, можно ее исследовать и получить какие-то результаты, которые, однако, невозможно будет преобразовать в решение исходной практической задачи.
Но если, как мы постарались показать в этом разделе, была найдена правильная модель, то ее теоретическое исследование может дать результаты, имеющие серьезное практическое значение. 4.2. Семантика языка О синтаксисе языка программирования известно довольно много; менее изучен вопрос корректного определения семантики языка. Руководство по использованию языка программирования должно включать описание каждой конструкции языка как по отдельности, так и в совокупности с другими конструкциями. Задача корректного определения семантики похожа на задачу определения синтаксиса. В языке имеется множество различных конструкций, точное определение которых необходимо как программисту, использующему язык, так и разработчику реализации этого языка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
