Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 38
Текст из файла (страница 38)
Альтернативой является нисходяптий метод 1Л.-грамматики, обобщающий метод рекурсивного спуска. Большинство современных языков программирования разработано на основе одной из грамматик, ЗЕВ, ЕК или Е1., и для них можно использовать инструменты генсрапии распознавателей типа 'т'АСС для автоматического создания распознавателя, соответствующего заданной грамматике. Детермттнированные МП-автоматы эквивалентны 1 К(1с)-грааиматикам н имеют значение при разработке практических компиляторов для языков программирования. В большинстве языков, построенных на основе грамматик, для определения синтаксиса используется некоторая 1 К()с)-грамматика.
Подробное изучение 1К1й)-грааиматик выходит за рамки этой книги, но в разделе ЗА мы приведем краткое описание грамматического разбора на основе метода рекурсивного спуска как пример грамматического разбора контекстно-свободных языков. 3.4. Грамматический разбор на основе метода рекурсивного спуска В задачи этой книги, как уже было сказано, не входит изучение полного спектра методов грамматического разбора. Тем не менее метод рекурсивного спуска является относительно простым в описании и реализации, и на его примере можно показать, как связано формальное описание языка программирования с возможностью генерации выполняемого кода для программ на этом языке.
Напомним, что мы всегда можем ттерсписап грамматику, используя расширенную НФБ-нотацпю. Например, для синтаксиса оператора присваивания, представленного в табл. З.З, арифметическое выражение описывается следующим образом; <арифие гичес<ое выраиеиие> , = <терияП+ ~ -) <терпя)* Это означает, что в первую очередь должна распознаваться синтаксическая категория <терн>. Если следующим символом окажется «+и или « — », то за ним должна последовать другая синтаксическая категория, <терн>. Предположим, что переменная пехтсцаг всегда содержит первый символ соотнстствующего нетерминального символа, а функция пегсьаг считывает символ.
Тогда мы можем непосредственно переписать прежнее правило, записанное в расширенной НФБ-нотации, н ниде следующей рекурсивной процедуры; ргосебцге Ехргевюоп; Ьер'п Теги, !*вызов процедуры Тегп лля поиска первого терла*! ыВПТе Ппехг сцаг= 'и > ог (пехссцаг= '- П бо Ьедяп пехсспаг:- Чегспаг. я*пропуск сиивола операции*! Те па епб епб 134 Глава 3. Вопросытрансляции языка йнстинг 3л . распознаватели на основе метода рекурсивного спуска для арифметических операторов' ргосебвге Азмдп5свс Ье91п Уаг1ао)е. 1Т пехссоаг '-' свеи Еггог е)ае Ьед1п пехсспаг:- дессоаг; Еяргезщ оп епо' епб: ргосецоге Ехргезз(оп Ье91и Тегв; нЬ1)е ((пехссоаг - ' -')ог(пехгсоаг- '-')) Оо Ьед1и пехгспаг:- дегсоаг; Тегв епо епб: ргосееоге Тегв Ьед1и Рг1пагу; нЬ1)е ((пехгсоаг - 'х')ог(пехгсоаг" '!')) бо Ьед1и пехгсиаг - десспаг; Рг1вагу епц егк(: ргосебоге Ргзвагу Ьедтп 1Г пехссоаг = )есгег слеп Чагзао)е е)зе 1Г пехгспаг - глдса слеп МнвЬег е)ае 1Г пехгсоаг - '(' сиеп Ье91п пехгсоаг:- дегсиаг: Ехргезз(оп: 1Г пехтспаг " ')' СЬеп пехсспаг := цейспаг е)зе Еггог/*Пропувено ')' */ епо' е)зе Еггог)*лропувено '(' *! епб; ргосеиоге уаг1ао)е; Ье9зп !((епа;Г1ег: 11 пехайааг = 'Е' СЬеп Ьед1 и пехгспаг: дегсоаг: 5оЫ(атл 1Г пехгсоаг = ')' Сани пехасоаг :- де(сиаг ез)е Еггогт*Пропущено ')' *Г епб енса В листинге 31 (оеп(1г1 ег и нввьег — это функции, предназначенные лля чтения идентификаторов и чисел соответственно при помощн лексического распознавателя на основе КА, 3.5.
Обзор языка Рааса) 135 ргосеевге 5всьтвт: Ьедтп Ехргевв1оп; епые пехтслаг - '.' Оо: Ьедтп пехтспаг - десслаг; Ехргевиоп епо епвц В листинге 3.1 полностью представлен распознаватель на основе метода рекурсивного спуска для операторов присваивания, задаваемых грамматикой, представленной в табл. 3.3.
Чтобы закончить разговор о грамматическом разборе, следует указать, что постфиксная запись выражения Ьегп)1 + Ьегп)в выглядит следующим образом;1егв, Ьегп)в (впрочем, мы еще вернемся к этому в разделе 8.2.1). Как будет показано далее, преобразование операторов исходной программы в постфиксную запись позволяет использовать удобную в прилтенении стратегию вычисления выражений.
Если у нас имеются процедуры для распознавания арифметических выражений, то не составляет труда произвести постфиксную запись этих выражений. Предположим, что каждая процедура производит постфиксную запись для собственных подвыражений, используя процедуру оцсрцц Постфиксная запись для арифметического выражения в процедуре ехргеавтоп может быть получена следующим образом: ргосеппге Ехргеви пп: Ьед1п ваг Р)ввтуре: слаг; Тего: !*вязов процеауре Тегп дпв повсха первого терла*! епме ((пехт сваг- '+') ог (пехтслаг- '-')) оо Ьедтп Р)ввТуре:-пехтслаг: пехтслаг := дегслаг: Тегп: остры 1Р)автуры епо епе Все остальные процедуры можно модифицировать аналогичным образом.
Постфиксная запись для оператора перепеьиав - выражение выглядит как перепеннав ввраяение ",для выражения множитель1х мпожительв — соответственно множительп мпояптелмхи т.д. 3.5. Обзор языка Равса! История создания. Рааса! разрабатывался с 1968 по 1970 г. Николаусом Виртом ()х)йг!аца Ю!гг!)). Цель заключалась в том, чтобы создать язык, лишенный многочисленных недостатков АЕ.ООЦ Рааса! был назван в честь французского математика Блеза Паскаля, который еще в 1642 г. изобрел цифровой калькулятор. С конца 70-х до конца 80-х гг. этот язык доминировал среди языков, используемых на начальном этапе обучения программированию; позже его заменили С и С++, а затем )ауа. А100!.
60 был первой попыткой создания языка на основе формального описания, однако его реализация оказалась сложной. В частности, оказалось достаточно трудно реализовать передачу параметров по имени, хотя это довольно эле- 136 Глава 3. Вопросы трансляции языка гантный механизм.
В языке А1 СОЕ 60 не были определены операторы ввода-вывода, поскольку э то эремя считалось, что они зависят от реализации, да и собственную статическую память также трудно было реализовать. Помимо того, н 60-х гг. были разработаны новые практические решения, например типы данных и структурное программирование. Языки типа ЕОВТВА!к! были популярны благодаря своей эффективности при ныполнении программ, несмотря на отсутствие элегантности. В 1965 г., во время работы в Стенфордском университете (5гапг!(огг! ()пгкегз!еу), Вирт разработал новую, расширенную версию АЕСОЕ 60 для компьютерое серии 1ВМ 360, в которую вошло определение указателей и структур данных. Этот язык, известный как АЕСО1 Ю, использовался в нескольких университетах, но его реализация ограничивалась только компьютерами 1ВМ 360.
Для выполнения программ на этом языке требовался значительный по размерам пакет программ поддержки обработки строк, не шест венных чисел д ной ной точности и других сложных типов данных. Таким образом, АЕСОЕ ЪЧ в качестве системного языка программирования оказался малоэффективным. В 1968 г.
Вирт вернулся в Швейцарию и начал работу над преемником АЕСОЕ Ю вЂ” языком, который мог бы компилироваться за один проход. Для создания исходного компилятора был использован алгоритм рекурсивного спуска. Этот компилятор выполнялся на компьютере Сопгго! Оага. Также был разработан широко известный теперь интерпретатор Р-кода. Компилятор языка Рааса! сначала транслировал исходную программу в про~рамму на языке гипотетической машины со стековой архитектурой. Благодаря такой своей организации Рааса! легко переносился на компьютеры других систем. Компилятор Разса! был написан на одноименном языке. Все, что требовалось для перехода в другую систему, — это переписать соответствующим образом интерпретатор Р-кода. Появившийся в 1970 г. Разса! начал зааоевывать признание.
В 1983 г. был разработан американский стандарт языка (1ЕЕЕ 770/ АХ51 Х3.97 [70!), а вскоре был разработан стандарт 150 (150 7185). Краткий обзор языка. Структура программ на языке Разса! напоминает программы на С. Тем не менее в Рааса! предусмотрена возможность описания внутренних локальных процедур и создания вложенной иерархии имен. Программа на Разса1 представляет собой единый программный блок, в котором содержатся определения используемых подпрограмм.
В Разса! имеется достаточно широкий набор простых и структуриронанных типов данных: целые и вещественные числа, символьные данные, перечисления, логические (булевы) значения, массивы, записи, последовательные файлы и ограниченный тип множеств. Оператор гуре позволяет программисту определять новые типы данных, хотя не обеспечивает группирование и инкапсуляцию определения нового типа данных с набором подпрограмм, обеспечивак>щих выполнение основных операций над объектами данных этого нового типа.
Кроме того, указатель и операция создания новых объектов данных любого типа позволяют программисту конструиронать новые объекты связанных данных непосредственно во время выполнения программы. Подпрограммы принимают форму функций (если они возвращают одно какое- либо значение) или процедур (если их действие сводится к модификации пере- 3.5. Обзор языка Рааса! 13У данных параметров или глобальных переменных). Операторы управления последовательностью действий базируются на конструкциях структурного программирования; составных операторах, условных операторах и операторах выбора (сазе), а также трех видах операторов цикла.
В Разов! имеется также оператор 0о[о, который редко используется и без которого практически всегда можно обойтись. Вызов подпрограмм и возврашение значений осуществляется с помощью обычной рекурсивной структуры вызова-возврата. Поскольку Разса! имеет блочную структуру, большая часть структур управления данными для ссылок на переменные использует стандартные статические п равила определения области видимости и характеристику вложенности блока в самой программе. Параметры могут передаваться по ссылке или позначению. Рааса! можно эффективно реализовать на обычном аппаратном компьютере. Идеология языка включает только те языковые свойства, для которых сушествуют хорошо изученные и эффективные методики реализации. Во время трансляции почти для всех операций возможен статический контроль типов, так что необходимость в динамическом контроле минимальна, но при этом обеспечивается полная безопасность выполнения.
Обычно программа транслируется в выполняемый машинный код, но в некоторых реализациях Разса1 результатом трансляции является виртуальный машинный код, который затем интерпретируется и выполняется при помоши некоторого программно-моделируемого интерпретатора. Во время выполнения программ на Разса! центральный стек используется для записей активации подпрограмм, область динамически распределяемой памяти отводится под обьекты данных, созданных для прямого манипулирования с помошью переменных-указателей, а область статически распределяемой памяти используется для хранения сегментов кода подпрограмм и вспомогательных подпрограмм из библиотеки поддержки выполнения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
