А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 233
Текст из файла (страница 233)
159-169. 21. БЬапг, М. апо' А. Рппей, "Тччо арргоасЬев го 1пгегргосеопи! дага йозч апа1у- яв", )п 8. МпсЬп)с)г апд Ы. 1опев (ейя) Ргойгат Р!озч Апа!угйя ТЬеогу ат( Арр!каг!опв, СЬаргег 7, рр. 189 — 234. Ргепйсе-Най, ()ррег БайПе К!чег Ы1, 1981. 22. Бгеепвйаагг), В., "Ро!и!в-!о апа1уяв ш Ппеаг !1ше", Тзчепгу-ТЬ!п1 АСМ Бутровгит оп Рг1пс(р!ез о~Ргодгаттгпй йапдиайез (1996). ПРИЛОЖЕНИЕ А Завершенный пример начальной стадии компилятора В данном приложении представлен завершенный пример начальной стадии компилятора, основанный на простом компиляторе, неформально описанном в разделах 2.5-2.8.
Основное отличие от компилятора из главы 2 заключается в том, что приведенная здесь начальная стадия генерирует для булевых выражений безусловные переходы, как описано в разделе б.б. Мы начнем с синтаксиса исходного языка программирования, описываемого грамматикой, которая должна быть адаптирована для нисходящего синтаксического анализа. Код транслятора на языке программирования 1ача состоит из пяти пакетов: жа1п, 1ехег, вувЬо1в, ратвет и 1птет. Пакет 1п~ет содержит классы для конструкций языка в абстрактном синтаксисе.
Поскольку код синтаксического анализатора взаимодействует с остальными пакетами, он будет описан ниже. Каждый пакет хранится в виде отдельного каталога с файлами, по одному для каждого класса. Исходная программа, поступающая в синтаксический анализатор, представляет собой поток токенов, так что код синтаксического анализатора далек от объектной ориентированности. Выход синтаксического анализатора представляет собой исходную программу в виде синтаксического дерева, причем конструкции и узлы реализованы как объекты. Эти объекты выполняют следующие задачи: строят узлы синтаксического дерева, проверяют типы и генерируют трехадресный промежуточный код (см.
пакет 1птек). А.1 Исходный язык Программа на исходном языке программирования состоит из блока с необязательными объявлениями и инструкциями. Токен Ьаяс представляет базовые типы. ((З4 Приложение А. Завершенный пример начальной стадии компилятора Объектно-ориентированный и фазо-ориентированный подходы В случае объектно-ориентированного подхода весь код конструкции собирается в одном классе, соответствующем этой конструкции. Альтернативным является фазо-ориентированный подход, при котором код группируется по фазам, так что процедура проверки типов может иметь по ветви для каждой конструкции, как и процедура генерации кода и т.д. Объектно-ориентированный подход упрощает изменение или добавление конструкции, такой, например, как инструкция аког; фазо-ориентированный же подход делает проще изменение или добавление фазы, такой, например, как проверка типов. При работе с объектами новая конструкция может быть добавлена путем написания самодостаточного класса, но изменение фазы, такое как, например, добавление кода для преобразования типов, требует внесения изменений во все затрагиваемые классы.
В случае фаз добавление новой конструкции может привести к необходимости внесения изменений во все процедуры для данной фазы. Ь(оса ргоята!л Ь(ос/г — ( а!ес(з згшгз ) — с1ес(з Ыес1 ) е — !уре Ы ! — (уре ( пщп ) ~ Ьаз!с — Бипм згл!! ~ е Нес(з Ыес1 !уре я!Рн!я Рассмотрение присваиваний как инструкций, а не как операторов в выражениях упрощает трансляцию.
згт! — 1ос = Ьоо1 ! Ы ( Ьоо1 ) згш! Ы ( Ьоо( ) згт! е(яе з!т! ттййе ( Ьоо1 ) згл!! до згш! ттййе ( Ьоо1 ) ! Ьгеай ! Ыос~с 1ос — ~ 1ос ( Ьоо! ) ) Ы Продукции для выражений обрабатываются с учетом ассоциативности и приоритета операторов. Для каждого уровня приоритета используется свой нетер- ПЗб А.2. Мага минал, а также нетерминал /асгог для выражений в скобках, идентификаторов, обращений к массивам и констант. — ~ Ьоо! ( ( /о(п ) !от — /о!п 66 ег!иа11/у ( ег!иа1(!у — ег!иа1(!у== ге! ) ег!иа1((у! = ге! ! ге! ехрг < ехрг ~ ехрг <= ехрг ~ ехрг >= ехрг ехрг > ехрг ~ ехрг ехрг + !егт ~ ехрг — 1егт ~ 1егт (егт * ипа!у ~ !егт / ипагу ~ ипагу — ! ипагу ~ — ипагу ~ /ас(ог — ( Ьоо1 ) ) 1ос ! Внп) ! геа) ( ггне ! га)ае Ьоо! /о!и едиай!у ге1 ехр! 1егт ипагу /ас1ог А.2 Ма1п () расхаде ваап; // Файл Ма!а/ага 2) Тврогс зача.ао.*; гврогГ 1ехег.*; 1врогГ рагзег.*; 3) рпЪ11с с1азз Маап ( 4) рпвтас зсаГ1с чоЫ ва1п(ЯГг1пд() агдз) олгаз 1ОЕхсерггоп ( 5) йехег 1ех = пею аехег(); 6) Рагзег рагзе = пею Рагзег(1ех)! 7) рагзе.ргодгав(): 8) Яузеев.опб.иггсе(' 1п'): 9) ) !О) ) А.З Лексический анализатор Пакет 1ехег представляет собой расширение кода лексического анализатора, представленного в разделе 2.б.5.
Класс Тад определяет константы для токенов. Файл Тая!аха 1) расхаде 1ехег! // 2) рпЪ11с с1азз Тад ( 3) рпЪ11с Еапа1 зсасас Тпс 4) АНО = 256, ВАЯТС = 257, 5) Еовв = 260, ЕО 261, 6) 10 = 264, 1Р = 265, 7) М1НОЯ = 268, МЕ = 269, 8) ВЕАа = 272, ТЕМР = 273, 9) ) ВВЕАК = 258, ОО РАаЯЕ = 262, ЯЕ 1НОЕХ = 266, 1Е НОМ = 270, ОН ТВОЕ = 274, ИН1аŠ— 259, = 263, = 267, = 271, = 275; Выполнение начинаегся с метода п(ахп в классе Махп, Метод п(ахп создает лексический анализатор и синтаксический анализатор, а затем вызывает метод ргоцга(п синтаксического анализатора. 1136 Приложение А. Завершенный пример начальной стадии компилятора Три константы — 1Н)3ЕХ, М1М()Б и ТЕМР— не являются лексическими токенами; они будут использованы в синтаксических деревьях.
Классы То)сеп и Мип] те же, что и в разделе 2.6.5, но с добавлением метода соЯсгйпд. // Файл То)сел./ача 1) расКаде 1ехег; 2) риЫТс с1азз То)сеп ( 3) риЬ11с Тспа1 1пг Сад; 4) риЬ11с Тохеп(ьпг С) ( Сад = С; 5) риЫТс Яггьпд СоЯггьпд(] (гегигп "" + (сЬаг)гад;) 6) 1) рассаде 1ехег; // Файл Асилс/ача 2) риЬ11с с1аяз Мопс ехгепбз То]сеп ( 3) риЫ1с Тьпа1 1пс ча1ие; 4) риЫ1с Мшп(спг ч) ( зирег(Тад.нон); ча1ие = ч; ) 5) риЫТс ягг1пд Сояггьпд() ( гегигп "" + ча1ие; ) 6) ) Класс Иогб работает с лексемами для зарезервированных слов, идентификаторов и составных токенов наподобие 66.
Он также используется для работы с прописными формами операторов в промежуточном коде — наподобие унарного минуса; например, исходный текст -2 имеет промежуточный вид шгпия 2. !) рас]саде 1ехег; // Фас1л Иьпй/ача 2) риЬ11с с1аяя Иогб ехгепбз То]сеп ( 3) риЬ11с ЯггТпд 1ехепсе = 4) риЫТс Иогб(вггьпд з, Тпг Сад) [ яирег(гад); 1ехепсе = з; ! 5) риЬ11с яггтпд Сояггьпд() ( гегигп 1ехеве; 6] риЫТс яСагтс Тьпа1 Иогб 7) апб = пеи иогб( "ая", тад.хмп ), Я) ог = пеи Иогб( "!!", Тад.ОР.
), 9) ес( = пеи Иогб( "==", Тад.Е(] ), 10) пе = пеи Иогб( "1=", Тад.МЕ ), 11) 1е = пеи Иогб( "< ", Тад.1,Е ), 12) де = пеи Иогс1( ">=", Тад.ОЕ ), 13) талия = пеи Иогб( "спспиз", Тад.И1МПЯ ), 14] Тгие = печ Иогб( "ггие", Тад.ТНПЕ ), 15) Ра1яе = печ Иогб( 5ва1яе", Тад.РАЬЯЕ ), 16) Сепср = пеи Иогс1( "С", Тад.ТЕНР ); 17) ) Класс Веа1 предназначен для работы с числами с плавающей точкой. 1) расваде 1ехег; // Файл )(еа!/ача 2) риЬ11с с1азз Неа1 ехгепбз Тохеп [ 3) риЫ1с Тйпа1 Т1оаг ча1ие; 4) риЬ11с Ееа1(Т1оаг ч) [ зирег(тад.ВЕАЬ)! ча1ие = ч; ) 5) риЫ1с яггвпд Сояггапд() ( гегигп "" + ча1ие; ) 6) 1137 А.З. Лексический анализатор Основной метод класса ) ехег — функция всап — распознает числа, идентификаторы н зарезервированные слова (см.
раздел 2.6.5). В строках 9-13 класса З.ехег резервируются выбранные ключевые слова. В строках 14 — 16 резервируются лексемы для объектов, определенных в других местах. Объекты 9)огс(. Тгце и Хогг(. г а1зе определены в классе (яог((; объекты базовых типов Тпс, сЬаг, Ь001 и Т10ас определены в классе Туре, подклассе (яогс(. Класс Туре находится в пакете вутаЬ01В.
1) расхаде 1ехег; // Файл Еятят)ича 2) 1ярогт Зача.то.*; Твороге зача.птг1.*; 1ярогт зутпЬо1з.*; 3) рпЬ11с с1авв Ъехег ( 4) рпЬ1гс зтатгс Тпт 1гпе = 1; 5) онат реех = 6) НазнтаЬ1е вогез = печ НазнтаЫе(); 7) чоът) гезегче(исто ч) ( вогез.рот(ч.1ехеяе, ч); 8) рагс Ъехег() ( 9) гезегче( печ ного("1Т", Тад.тр) ); 10) геяетче( печ Иогл(("е1зе", Тас.ЕЪВЕ) ); 11) геяегче( печ ноге("чйъ1е", тад.иитЪЕ) ); 12) гезетче( печ Исто("с(о", Тас.оо) ); 13) гезегче( печ ного("Ьгеа1с", Тад.ВНЕХК) ); 14) гезегче ( Иогс. Тгпе ); гезетче ( Иогб. Га1яе ); 15) гевегче( Туре.тпт ); теветче( Туре.СЬаг ); 16) гезегче( Туре.воо1 ); гезегче( Туре.Г1оат ); 17) ) 18) 19) 20) 21) 22) 23) 24) 25) ) чоъо геассЬ() ГЬгояв 10Ехсерт1оп ( реет = (снег)вувтев.ъп.геао(); Ьоо1еап геал(сн(сиат с) тьгочя 10Ехсертъоп ( геас)си О: 1Г( реек 1= с ) гетпгп Га1яе; реет = гетпгп ггпе; Функция зсап начинается с пропускания всех пробельных символов (строки 27 — 31).
Она распознает составные токены наподобие <= (строки 32 — 51) и числа наподобие 365 и 3. 14 (строки 52-65), после чего переходит к сбору слов (строки 66-77). 26) рпЫТс Тохеп зсап() тнгочз 10Ехсерттоп ( 27) Тот( ; ; геас)сн() ) ( Функция геас(сЬ ( ) (строка ! 8) используется для чтения очередного входного символа в переменную рее)т. Имя геас(сЬ повторно используется или перегружается (строки 19 — 25) для распознавания составных токенов. Например, если во входном потоке встречается символ <, вызов геас(сЬ ( ' = ' ) считывает очередной символ в переменную рее)т и проверяет, является ли он символом =. 1138 Приложение А. Завершенный пример начальной стадии компилятора 28) 29) 30) 31) 32) 33) 34) 35) 36) 37) 38) 39) 40) 41) 42) 43) 44) 45) 46) 47) 48) 49) 50) 51) 52) 53) 54) 55) 56) 57) 58) 59) 60) 61) 62) 63) 64) 65) бб) 67) 68) 69) 70) 71) 72) 73) 74) 75) 76) 77) Тй( рееК = ' ' !! реек == '1Г' ) соптьпиез е1зе Тй( реек == '1п' ) 11пе = 11пе + 1; е1ве Ьгеа!<3 зи1.гоп( рееК ) ( саве 'а': гТ( геабсп('а') ) гетигп Иогб.апйз е1зе гетигп пею Тоиеп('а')з саве ьй( геайсп('!') ) гегигп Иогй.огз е1яе гетигп пеи Точен('!')з сазе Ы ( геайсп(' ') ) гегигп Иогй.ес!3 е1зе гесигп пеи Тоиеп('='); саяе ' !': 18( геабсп('=') ) гетигп Иогй.пез е1зе гетигп пеи Тоиеп('!')3 сазе '<' з 18( геабсп('=') ) гетигп Иогб.1ез е1зе гетигп пеи Тоиеп('<')3 саве '>'з 18( геабсп('=') ) гетигп Иогб.дез е1зе гепигп пеи Токеп('>')3 ! 1Е( Спагастег.бз0501Г(реек) ! ( Тпс ч - Оз йо ( ч = 10*ч + Спагаспег.бгдТГ(рееК, 10); геабсп()з ) иь11е( сьагасгег.1зО191г(реек) ) з 18( реек 1= '.' ) гетигп пеи Мшп(ч)з Т1оас х = чз Г1оаГ б = 10з Тог(зз) ( геайсЬ()' 58( ! Спагастег.1зпад3Ь(рееК) ) Ьгеаиз х - х + Спагаспег.бьд1Г(рееМ, 10) / йз й = й*103 ! гегигп пеи Яеа1(х)з ) Тт( сьагасгег.
1вьеггег(реек) ) Ятг1пдВиТТег Ь пеи ЯсгйпдВитбег()з бо ( Ь.аррепй(реек)з геайсп()з ) ИЬ11е( Спагастег. 1зьестегОгпйдга(рееК) )3 яггьпд з = ь.гоягг1пд()з Иогй и = (Иогй)иогйз.дев(з)з 18( и 1= пи11 ) гесигп из и - пеи Иогй(з, Тад.10)з юогбв.рис(я, и)з гегигп юз 1139 А.4. Таблицы символов и типы Наконец, все остальные символы возвращаются как токены (строки 78 — 81). 78) Тохеп Гох = пеы Тохеп(реек) ! реех = 79) гепигп го!и! 80) ! 81) А.4 Таблицы символов и типы Пакет вуп!Ьо1в реализует таблицы символов и типы. Класс Епч по сути остался неизменным, таким как на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
