Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 40
Текст из файла (страница 40)
Покажите, что й" также является регулярным множеством. (Подсказка: решите сначала предыдущую задачу для 5'.) Глава 4. Моделирование свойств языка На начальном этапе развития компьютерных технологий среди профессионалов в этой области господствовало мнение, что формальный синтаксис (например, НФ Б-грамматика) достаточен для описания атрибутов языка программирования и, следовательно, для полного и однозначного описания поведения программы.
Но оказалось, что это не так, и в разделе 3.3.2 были приведены некоторые примеры, демонстрирующие недостаточность НФБ-грамматики для точного описания поведения программы. НФБ-грамматика является прекрасным инструментом для ответа на вопрос как должна выглядеть программа на конкретном языке? В этой главе' мы рассмотрим несколько формальных теорий, которые расширяют НФБ-грамматику и позволяют ответить на вопрос что делает данная программа? Для этого мы введем следующие формальные модели.
1. Формальные грамматики. НФБ-грамматика и регулярная грамматика — всего л ишь два примера более сложной структуры, разработанной в 50-е гг. прошлого столетия профессором Массачусетсского технологического института (М1Т) Ноамом Хомским. Мы познакомим с нерархией грамматик Хомского и дадим краткое описание их свойств. Мы покажем, что, к сожалению, к интересующим нас проблемам языков программирования имеют отношение только уже исследованные нами НФБ-грамматика и регулярная грамматика.
Тем не менее другие классы грамматик обладают важными свойствами, отражающими природу вычислений, и в этой главе мы познакомим читателя с концепциями неразрешимости и алгоритмической сложности. 2. Семантика языка. Для разработки моделей языков программирования помимо формальной грамматики используются и другие подходы. Одним из первых среди них стала атрибутивная грамматика, предложенная профессором Стенфордского университета (Бгапс)(огс1 ()пгрегз)гу) Дональдом Кнутом (1)опа!б Кппгй). В атой модели к обычной НФБ-грамматике, описывающей язык, добавлена некоторая семантическая информация.
Более формальной моделью является денотационная семантика, которая записывает программу в виде математической функции. Эта глава несколько сложнее остальных глав втой книги, поэтому она предназначена только лля тех читателей, которым требуется дополнительная информапия. Остальные могут пропустить ее, эа исключением раздела 4.2.3, в котором приведен обзор языка Мц 4.1, Формальные свойства языков 143 3. Верификация прогроммьс Третий подход заключается в верификации программы. Целью здесь является скорее не формальное описание программы, а демонстрация эквивалентности программы и некоторого другого способа записи — например, логики предикатов.
Например, если требуется написать программу, вычисляющую куб заданного числа, то в данном способе предлагается доказать, что программа и уравнение х = уз, где х — это выходное значение, ау — введенное число, ведут себя одинаково. В данном случае нас интересует не столько то, что представляет собой программа, сколько правильность ее поведения. Исходно эта технология была разработана в 1960 г. Робертом Флойдом (КоЬегг Р[оуг[) и Т. Хоором (Топу Ноаге). Хотя ее трудно реализовать, она имеет достаточно большое значение в определенных приложениях, для которых важнейшим требованием является правильность программы (например, в приложениях, контролирующих работу ядерных реакторов).
4.1. Формальные свойства языков Современная цивилизация основана на взаимодействии науки и техники, целью которого является объяснение устройства окружаюгцего мира и развитие технологий, способствующих дальнейшему прогрессу. Общая модель этого взаимодействия может быть представлена следую|цей схемой: Мы проводим исследования и получаем некоторое знание (например, мы узнаем, что в программах неизбежны ошибки и, вообще, программирование — сложное занятие), развиваем теории разработки языков программирования (например, структурное программирование, НФБ-грамматики, абстракции данных), а затем оцениваем действенность этих теорий (например, используем их для создания языков).
Это приводит к дальнейшему развитию теории (например, развитие концепции объектно-ориентированных классов в результате усовершенствования понятия абстракций данных или методов разбора на основе ЯЖ[1]- и 1 АЩ1]- грамматик в результате развития метала разбора на основе (.2[1]-грамматики) и оказывает благотворное влияние на весь процесс в целом. В предыдущих главах мы уже обсудили некоторые из общепринятых методов разработки языков программирования. В данном разделе мы продолжим этот разговор и коротко расскажем о некоторых других теоретических моделях, которые влияют на разработку языков программирования.
Разработка и реализация большинства ранних языков программирования основывались на практических соображениях. Вопрос стоял таким образом: как извлечь пользу из использования некоторого примитивного устройства, принадлежащего к аппаратной части компьютера, при создании больших программ, необходимых для решения таких задач, как конструирование самолета, или анализ 144 Глава 4. Моделирование свойств языка данных радара, или управление ядерной реакцией? Возникновение многих ранних языков было обусловлено необходимостью решения подобных задач, при этом роль теории была незначительна. Многочисленные проблемы, встретившиеся разработчикам на этом пути, равно как и удачные решения, привели к возникновению ранних формальных моделей синтаксиса и семантики языков программирования, что, в свою очередь, способствовало созданию более совершенных языков программирования. В новых языках по-прежнему встречались многочисленные недоработки и упущения как в стадии разработки, так и при их реализации.
Совершенствование теоретических моделей вело к прогрессу в разработке языков программирования. Теоретическая модель может быть концептуальной (то есть качественной), в таком случае она описывает язык в терминах лежащих в ее основе базовых понятий и не претендует на формальное математическое описание этих понятий. Именно в этом смысле в предыдущих главах была построена теоретическая модель базовых понятий, лежащих в основе разработки и реализации языков программирования.
С другой стороны, теоретическая модель может быть формальной (то есть количественной), в которой исследуемое явление описывается в терминах точной математической модели, которую можно изучать, анализировать и преобразовывать, используя доступный математический аппарат. Теоретические модели, рассматриваемые в этой главе,— это формальные модели. Их описания, которые вы здесь найдете, не претендуют на полноту, но содержат достаточно информации для понимания проблемы н возможных путей ее решения. 4.1.1. Иерархия грамматик Хомского Как было сказано в разделе 3.3.1, НФБ-грамматики оказались очень полезными при описании синтаксиса языков программирования.
Однако зти НФБ-грамматики (или контекстно-свободные грамматики) — всего лишь один из элементов класса грамматик, описанных Ноамом Хомским в 1959 г. ~ 27]. Мы приводим здесь краткое описание первоначально предложенной им модели грамматик. Типы грамматик В разделе 3.3.1 мы представили базовый синтаксис правил, или продукций, НФБ- грамматики. Граммигпики определяется как совокупность множества нетерминальных символов, множества терминальных символов, начального символа (один из нетерминальных) и множества правил. Классы грамматик различаются между собой в зависимости от имеющегося набора допустимых правил.
В случае НФБ-грамматики язык определяется просто как набор конечных последовательностей (цепочек) символов некоторого произвольного алфавита, выведенных из одного начального символа. Алфавит — это набор символов, которые используются при написании программ, и каждая законченная программа представляет собой нх последовательность. Мы можем говорить о множестве цепочек, генерируемых грамматикой (то есть цепочек терминальных символов, выведенных из начального символа), или, наоборот, мы можем сказать, что грамматика распозниет цепочки (то есть по некоторой цепочке всегда можно построить дерево синтаксического разбора и вернуться к исходному начальному символу).
4.1. Формальные свойства языков 145 Будем называть языком типа и язык, который генерируется грамматикой типа и, если нет грамматики типа и и- 1, которая также генерирует этот язык. Из этого определения следует, что любая грамматика типа и является также и грамматикой типа и — 1. Грамматики типа 3 — это просто регулярные грамматики, определяюшие автоматные языки, моделируюшие лексические единицы языка. Грамматики типа 2— это зпакомыс нам НФБ-грамматики.
Грамматики типа 1 и О не илтеют большого практического значения для моделирования языков программирования, но в области теоретических исследований они играют сушественную роль. Обзору каждого из упомянутых типов посвящены следующие несколько разделов. Регулярные грамматики (тип 3) Как было сказано ранее, конечный автомат и регулярные грамматики обеспечивают модель лля конструирования лексического анализатора в трансляторе некоторого языка программирования (см. раздел 3 3 2).
Свойства регулярных грамматик таковы: + Большинство свойств такой грамматики разрешимы. (Это означает, что можно получить ответы, например, на такие вопросы; генерирует ли данная грамматика любые цепочки? Сгенерирована ли этой грамматикой заданная цепочка символов языка? Ограничено ли количество цепочек в языке7) + Для любой конечной последовательности а и целого и регулярная грамматика может генерировать строки вида сх". Это означает, что регулярная грамматика может распознавать любое количество образцов конечной длины.
+ С помощью регулярной грамматики можно реализовать счет до любого конечного целого числа. Например, вы можете распознать цепочку (а" ! и -- 147). если построите КА, в котором будет как минимум 148 состояний (рис. 4.1). Ввод первых 146 символов не приведет КА в конечное состояние, тогла как очерслной ввод символа под номером 147 будет принят.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
