Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 39
Текст из файла (страница 39)
Из вспомогательных подпрограмм нужны в основном стандартные программы ввода-вывода для последовательных файлов и процедуры для управления ресурсами памяти. Хотя Рааса! в целом очень удобный и полезный язык, у него есть свои недостатки, перечень которых приведен ниже. 1.
В определении этого языка имеется некоторое противоречие между идеологией самого языка и его реализацией. Например, конструкция [огиз гб нужна только для того, чтобы компиляция могла выполняться в один проход,— зто следствие представлений о том, что таким образом достигается максимальная эффективность компиляции, Но это не всегда верно. Например, компилятор Р[./С для языка Р[.,~1 совершал три прохода и вместе с тем являлся одним из самых эффективных среди наиболее распространенных компиляторов своего времени !32!. Кроме того, в настоящее время при использовании недорогих быстродействующих компьютеров скорость компиляции не имеет большого значения.
2. Возможно, самой главной слабостью языка Разса! является то, что массивы рассматриваются как отдельные типы, а не как агрегация различных объектов одного типа. Это приводит к тому, что, например, аггзу[1 .. 101 ог ! п[е0ег и аггау[1 ..201 о[ ~пгеуег представляют собой разные шипы данных. В результате алгоритмы обработки массивов усложняются, поскольку массивы различных размеров невозможно передать общей подпрограмме (например, 138 Глава 3. Вопросы трансляции языка подпрограмме перемножения матриц). Строки реализованы как массивы символов, что также затрудняет их обработку в случае строк различной длины. 3.
Синтаксис определения процедуры в Рааса! выглядит следующим образом: заголовок процевуры локальные перекенные локальные паракетры Ьедтп тело процедуры епд Поскольку в программе может содержаться большое количество вложенных локальных процедур, то определение локальной переменной, которая используется в какой-либо процедуре, оказывается (синтаксически) сильно отдаленным от места ее использования в теле подпрогралгмы. Это приводит к затруднениям при создании документации и чтении больших программ на Рааса[, 4. Возможности, предоставляемые языком, должны выполняться не с помощью пропуска некоторой информации, а явным указанием этой информации.
В Рааса! передача параметров нарушает это правило. Все параметры в Рааса! передаются по значению, если только в списке параметров не указан явным образом атрибут наг, который означает, что соответствующий параметр должен передаваться по ссылке. Многие начинающие программисты (в том числе один из авторов этой книги) часами рассматривали листингии программ, стараясь обнаружить ошибку, связанную с пропуском ключевого слова уаг, 5. Рааса! был реализован таким образом, что компиляция программы представляла собой единый процесс, то есть не была предусмотрена возможность компилировать отдельные программные модули. В большинстве реализаций, однако, эту проблему удалось решить: было принято соглашение, что допускаются дополнительные внегнние процедуры, аналогичные заголовочным файлам с расширением .!т в языке С.
Но такая нестандартная реализация ограничивает возможность перенесения программ на Рааса! на другие магпины. 6. Хотя в Рааса! допускается определение новых типов данных для поддержки абстракций, в нем фактически не предусмотрена возможность инкапсуляции и сокрытия информации. (Это замечание является скорее не критикой данного языка, а комментарием, касающилгся общего уровня развития программирования в 1970 г., когда создавался Рааса!.) 3.6. Рекомендуемая литература Имеется довольно обширная литература по синтаксису и трансляции языков программирования.
В книгах Ахо, Сетхи и Ульмана [В], а также Фишера и Лебланка [41! достаточно подробно исследуется процесс трансляции программ. В главе 10 книги Берманна [17! эта же тема представлена в более простом, обзорном виде. Идеология диагностирующих компиляторов описана в документации языков 3.7. Задачи и упражнения 139 СОВС [311 и Р[/1 [32[, разработанных в Корнельском университете.
Исправление синтаксических ошибок обсуждается в работе Моргана [84[. Практические соображения по разработке синтаксиса языков программирования также нашли свое отражение в печатных работах. В частности, многие вопросы по этой тематике освещаются в соответствующих работах Саммета [951. В документации по таким языкам программирования, как Ат[а [58] дается обоснование решений, принятых при разработке этих языков.
3.7. Задачи и упражнения 1. Рассмотрим следующие правила НФБ-грамматики: «рор> :.= [«Ьор>. <рор>][<оор> <Ьор> ..= <Ьоор> П<рор>) <Ьоор>;;= х[у!т Для каждой из перечисленных ниже строк укажите все синтаксические категории, к которым они относятся [если такие существуют): + с + Ы + [у] + 1[х.у]) + [(х),у] + [(х),[у х]) 2.
Предложите однозначную грамматику для языка, определяемого следуютцим правилом: 5 > 55П5) П) 3. Покажите, что любое заданное дерево грамматического разбора может быть результатом нескольких выводов [например, покажите, что существует несколько выводов, генерирукнцих дерево, показанное на рис. ЗА). Что можно сказать о дереве грамматического разбора, если грамматика является однозначной7 Неоднозначной? 4. Определим левый вывод как вывод, в ко~ором правило применяется к самому левому из всех нетервтиттальттых символов в каждой сентенциальной форме. Покажите, что грамматика является неоднозначной в том и только том случае, если в языке существует цепочка, имеющая два различных левых вывода. 5.
Напишите НФБ-грамматику для языка, состоящего из всех двоичных чисел, которые содержат по меньшей мере три последовательно идутцие единицы (Язык включает, например, цепочки 011101011, 000011110100 н 1111110, но не 0101011.) 6. Синтаксис обезьяньего языка очень прост, но только обезьяны умеют говорить на нелт, не делая ошибок. Алфавит состоит из [а,!т,т],тг), причем т) используется в качестве пробела.
Грамматика задана следующим образом; <остановка> ::= Ь[О <звук>:;= <остановка>а <слог> ::- <звук>!<звук><остановка>/а<звук>/а<остановка> 140 Глава 3. Вопросы трансляции языка <слово> ::= <слог>><слог><слово><сваг> <преллпкение>;;= <слово>)<преллпкение»у<слово>.
Кто из перечисленных ниже ораторов — секретный агент, замаскированный под обезьяну? Горилла: Ьауабабабаба>)бабШбаббаба Шимпанзе. аббабаабаЬ/)аба Бабуин: баб>)абуабаабаб>)Ьабаббааб 7. Приведите регулярные выражения: + для всех бинарных цепочек, заканчивающихся на 01; + для целых десятичных чисел, кратных 5; + для идентификаторов языка С; + для бинарных цепочек, состоящих либо из нечетного количества единиц, либо нечетного количества нулей. 8, Покажите, что любой КА может быть представлен регулярной грамматикой и лк>бая регулярная грамматика может быль распознана КА. Чтобы решить зту задачу, следует связать каждый нетерминальный символ в грамматике с состоянием КА. Например, схема, представленная на рис.
3.10, соответствует правилу А — > хВ. (Как вы обработаете конечные состояния?) Я вЂ” 'Я Переход конечного автомата А — ~хв Правило регулярной греммвтики Рис. 3. 10. Связь грамматики и КА 9. Постройте конечный автомат и регулярную грамматику для следующих цепочек; + (аЬчЬа)*ч(аЬ)*; + (11*)*(110м01); + всех цепочек, состоящих из 0 и 1 и содержащих подцспочку 010; + всех цепочек, состоящих из 0 и 1 и не содержащих подцепочку 010. 10. Напишите расширенную НФБ-грамматику для языков, определенных конечными автоматами, изображспным на рис. 3.6 н 3.7.
11. Постройте дерево грамматического разбора для следук>щих операторов присваивания, используя ПФБ-грамматику, представленную в табл. 3.1: + А[2):= В +1 + А[1,)1:= А[).11 + Хг0-УхИ<Х/У + Р:= 0 / СУ / (и' / Х)) 3.7. Задачи и упражнения 141 12. Определение недетерминированного КА включает в себя определение детерминированного КА как особый случай. Предположим, однако, что у нас имеется недетерминированный конечный автомат М.
Покажите, что тогда существует детерминированный автомат о, который принимает тот же самый язык. Это означает, что отсутствие детерминированности у КА не увеличивает вычислительную мощность автомата й. Для того чтобы показать это, рассмотрим, скольких состояний в и' мы можем достичь из заданного состояния и заданного входного символа Назовем зто множество состояний Сосаояния,. Для автомата й, содержащего и состояний, таких подмножеств будет 2". Это определяет множество состояний нашего детерминированного КА, 13.
Пусть 5 — зто регулярное множество (то есть множество, распознаваемое конечным автоматом). Покажите, что 5' гобращенное множество 5, то есть множество цепочек из 5, каждая из которых записана в обратном порядке) также является регулярным множеством. 14. Пусть й — регулярное множество. Пусть йэ' — зто множество, составленное из левых «половинок» элементов к, то есть если элемент и принадлежит к и длина этого элемента 2х, то первые 1 символов из и являются элементом к"'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
