Лабораторные работы по Теории вычислительных процессов и структур
МинистерствообразованияРоссийскойФедерации
Саратовскийгосударственныйтехническийуниверситет
ЛАБОРАТОРНАЯРАБОТА №1
Лексическийанализ входногоязыка транслятора
лабораторнаяработа по курсу«Теория вычислите-
льныхпроцессов иструктур» длястудентов
специальности220400 (ПВС)
Составилдоцент кафедрыПВС
Сайкин А.И.
Саратов, 2001г.
Введение
Даннаялабораторнаяработа предназначаетсядля студентовспециальностиПВС изучающих«Теорию вычислительныхпроцессов иструктур».Лабораторнаяработа рассчитанана 4 аудиторныхчаса и 6 часовсамостоятельнойработы по составлению
программы,изучение литературыи составлениеотчёта.
Объектисследования- трансляторыс алгоритмическихязыков программирования.Процесс трансляциис алгоритмическогоязыка можноусловно разбитьна три этапа:лексическийанализ, грамматическийразбор и генерациюмашинного кода.В данной работерассматриваетсязадача построениялексическогоанализатора
входноготекста транслятора.
Цельработы состоитв составлениипрограммы(сканера) производящейлексическийанализ текста,соответствующегозаданномуалфавиту играмматикеалгоритмическогоязыка.
Программасоставляетсяна языках Паскальи С++ по выборустудента всреде WINDOWS.
1. Содержаниеработы.
Этаплексическогоанализа текстаисходной программывыделяетсяв самостоятельныйэтап работытранслятора,как с методическойцелью, так и сцелью сокращениявремени компиляциипрограммы.Последнеедостигаетсяза счёт того,что
исходнаяпрограмма ввиде последовательностисимволов,преобразуетсяна этапе лексическойобработки кнекоторомустандартномувиду, что облегчаетдальнейшийанализ.
Под лексическиманализом понимаютпроцесс предварительнойобработкиисходной программы,на которомосновные лексическиеединицы программы- лексемы: ключевыеслова, идентификаторы, метки, константыприводятсяк единому форматуи заменяютсяусловнымикодами илиссылками насоответствующиетаблицы, а коментарииисключаютсяиз текста программы.Результатомлексическогоанализа являетсясписок лексем-дескрипторови таблицы. Втаблицах хранятсязначения выделенныхв программелексем.
Дескриптор-это пара вида:( . ),
где-это, как правило,числовой кодкласса лексемы,который означает,что лексемапринадлежитодному из конечногомножестваклассов слов,выделенныхв языке программирования;
-это может бытьлибо начальныйадрес областиосновной памяти,в которой хранитсяадрес этойлексемы, либочисло, адресующееэлемент таблицы,в которой хранитсязначение этойлексемы.
Количествоклассов лексемв языках программированияможет бытьразличным.Наиболеераспространёнными классами являются:
идентификаторы;
служебные(ключевые) слова;
разделители;
константы.
Могутвводиться идругие классы.Это обусловленов первую очередьтой ролью, которуюиграют различныевиды слов принаписанииисходной программыи переводе еёв машиннуюпрограмму. Приэтом наиболеепредпочтительнымявляется разбиениевсего множестваслов, допускаемыхв языке программирования,на такие классы,которые бы непересекалисьмежду собой.В общем случае все выделяемыеклассы являютсялибо конечными(ключевые слова,разделителии др.) - классыфиксированныхдля данногоязыка программированияслов, либо
бесконечнымиили очень большими(идентификаторы,константы,метки)- классыпеременныхдля данногоязыка программированияслов.
С этихпозиций кодылексем (дескрипторы)из конечныхклассов всегдаодни и те же вразличныхпрограммахдля данногокомпилятора.Коды же лексемиз бесконечныхклассов различныдля разныхпрограмм иформируютсявсякий раз наэтапе лексическогоанализа.
В ходелексическогоанализа значениялексем из бесконечныхклассов помещаютсяв таблицысоответствующихклассов. Конечностьтаблиц объясняетограничения,существующиев языках программированияна длины исоответственночисло используемыхв программеидентификаторови констант.
Числовыеконстанты передпомещениемих в таблицумогут переводитьсяиз внешнегосимвольногово внутреннеемашинноепредставление.Содержимоетаблиц, в особенноститаблицы идентификаторов,в дальнейшемпополняетсяна этапе семантическогоанализа исходнойпрограммы ииспользуетсяна этапе генерацииобъектнойпрограммы.
Вработе требуетсясоставитьпрограммулексическогоанализатора(сканер) входноготекста длятранслятора,которая бы
составлялатаблицы и производилабы кодированиеидентификаторов,разделителейи констант.Производилабы проверкуправильностинаписанияключевых словоператоров,стандартныхфункций ииспользованиеслужебныхсимволов.
Производилабы отображениетеста программыс комментариямии исключалабы их из текста,подлежащеготрансляции.Отображала
дескрипторныйтекст.
2. Заданиепо работе.
2.1. Получитьвариант заданияу преподавателя.
2.2. Всоответствиис выданнымвариантомвыполнитьследующее:
2.2.1. Составиттехническоезадание (ТЗ) наразработкупрограммысканера, производящейлексическийанализ произвольныхтекстов в пределахустановленногоалфавита.
2.2.2. СогласоватьТЗ с преподавателем.
2.2.3. Разработатьпрограмму-сканерна языках
Паскаль,С++ или в интегрированныхсредах пособственномуусмотрению.
2.2.4. Провеститестированиепрограммы,особенно длявсех случаеввыдачи пользователюсообщений обошибках.
2.2.5. Составитьотчёт по работеи приложитьк нему ТЗ.
3. Вариантызаданий.
Вариантзадания включаетномер, состоящийиз трёх цифр.
Перваяцифра означаетвыбор алфавитавходного языка,вторая цифраозначает выборзаданных ключевыхслов входногоязыка и третьяцифра означаетвыбор заданныхбиблиотечныхфункций.
Таблица1. Алфавит входногоязыка.
-
№ Алфавит 1 Латинский,строчные буквы 2 Латинский,заглавныебуквы 3 Кириллица,строчные буквы 4 Кириллица,заглавныебуквы 5 Латинский,строчные +заглавные 6 Кириллица,строчные +заглавные
Таблица2. Ключевые слова.
-
№ Дополнительныеключевые слова 1 Описаниециклов, массивов 2 Описаниеоператоровперехода,структурытипа switch
3 Описаниебезусловныхпереходов,
описаниефункций
Таблица3. Библиотечныефункции.
-
№ Стандартныефункции 1 sin, cos, tan, exp 2
sqrt, log, ln,nearby 3 abs, fact, code, sign
Например,1-2-3 означает, чтоиз первой таблицынеобходимовыбрать первуюстроку, из второйтаблицы - вторуюстроку, из третьейтаблицы - третьюстроку.
Для всехвариантовзадаётся общаячасть в которуювходит следующее.Ключевые словаобозначающиеначало и конецпрограммы,описание типа,ввод и вывод,присваивание.
Разделители: +, -, *, :, _, /, (, ), {, }, =, , [, ], ;, “, ‘, ‘,’и про-
бел.
Идентификаторыдолжны начинатьсяс буквы, не включатьв себя разделители,количествопозиций недолжно превышать14.
Текстпрограммыдолжен допускатьиспользованиекомментариев.
4. Методическиеуказания.
Рассмотримосновные идеи,которые лежатв основе построения
лексическогоанализатора,и проблемы,возникающиепри его разра-
ботке.
Первоначальнов тексте входнойпрограммысканер выделяетпоследовательностьсимволов, котораяпо его предположениюдолжна бытьсловом в программе, т.е. лексемой.Может выделятьсяне вся последовательность,а только одинсимвол, которыйсчитаетсяначалом лексемы.Это сделатьпросто, еслислова в программеотделяютсядруг от другаспециальнымиразделителями,
например,пробелами илизапрещеноиспользованиеслужебных словв качествепеременных,либо классылексем распознаютсяпо вхождениюпервых символовлексемы.
Затем,проводитсяидентификациялексемы. Оназаключается
в сборкелексемы изсимволов, начинаяс выделенногона предыдущемэтапе, и проверкиправильностизаписи лексемыданного класса.
Идентификациялексемы изконечногокласса выполняетсяпутём сравненияеё с эталоннымзначением.Основная проблемаздесь - минимизациявремени поискаэталона. В общемслучае можетпонадобитьсяполный переборслов данногокласса, особенно,если выделенноеслово содержитошибку. Уменьшитьвремя поискаможно, используяразличныеметоды ускоренногопоиска: упорядоченныйсписок, линейныйсписок, методрасстановкии др.
Дляидентификациииз очень большихклассов используютсяспециальныеметоды сборкилексем с одновременнойпроверкойправильностинаписания. Вэтих методахприменяетсяформальныйматематическийаппарат- теориярегулярныхязыков и конечныхраспознавателей.
Приуспешнойидентификациизначение лексемыиз бесконечногокласса помещаетсяв таблицуидентификациилексем данногокласса. Приэтом осуществляютпроверку: нехранится лиуже там значениеданной лексемы,т.е. необходимопроводитьпросмотр элементовтаблицы. Таблицапри этом должнадопускатьрасширение.Опять же дляуменьшениявремени доступак элементамтаблицы онадолжна бытьспециальнымобразом организована,при этом должныиспользоватьсяспециальныеметоды ускоренногопоиска элементов.
Послепроведенияуспешнойидентификациилексемы формируетсяеё образ - дескриптор,он помещаетсяв выходныеданные лексическогоанализатора.В случае неуспешнойидентификацииформируетсясообщение обошибках в написаниислов программы.
Входе лексическогоанализа могутвыполнятьсяи другие видылексическогоконтроля, вчастности,проверятьсяпарность скобоки других парныхсимволов, наличиеметки у оператора,следующегоза GOTO ит.д.
Результатыработы сканерапередаютсяв последствиина вход синтаксическогоанлизатора.Имеется двевозможностиих связи:
раздельнаясвязь и нераздельнаясвязь.
При раздельнойсвязи выходныеданные сканераформируютсяполностью изатем передаютсясинтаксическомуанализатору.При нераздельнойсвязи, когдасинтаксическомуанализаторутребуетсяочередной образлексемы, онвызывает лексическийанализатор,кото-
рый генерируетдескриптори возвращаетуправлениесинтаксическомуанализатору.
Второйвариант характерендля однопроходныхтрансляторов.
Такимобразом, процесслексическогоанализа достаточнопрост, но можетзанимать значительноевремя трансляции.
Рассмотримконкретныйпример. Пустьнам дана программана
некотором алгоритмическомазыке:
PROGRAMPRIMER;
VARX,Y,Z : REAL;
BEGIN
X:=5;
Y:=6;
Z:=X+Y;
END;
Применимследующие кодыдля типов лексем:
К1- ключевоеслово;
К2- разделитель;
К3-идентификатор;
К4- константа.
Лексическийанализ можнопроизводить,если нам заданалфавит,
списокключевых словязыка и служебныхсимволов. Пустьвсё это
имеется.Тогда внутренниетаблицы сканерапримут следующийвид.
Таблица 4.Ключевые слова.
-
№ Ключевоеслово 1 PROGRAM 2 BEGIN
3 END 4 FOR 5 REAL 6 VAR
Таблица5. Разделители.
-
№ Разделители 1 ; 2 , 3 + 4 - 5 / 6 * 7 : 8 =
9 .
Результатработы сканератаблица идентификаторови таблица констант
Таблица6. Идентификаторы.
-
№ Идентификаторы 1 PRIMER 2 X 3 Y 4 Z
Таблица7. Константы.
-
№ Знач.констант 1 5 2 6
На основаниисоставленныхтаблиц можнозаписать входнойтекст черезвведённыедескрипторы(дескрипторныйтекст):
(К1,1) (К3,1) (K2, 1)
(K1, 6) (K3, 2) (K2, 2) (k3, 3) ( K2, 2) (K3, 4) ( K2, 7) (K1, 5) (K2,1)
( K1, 2)
( K3, 2) (K2, 7) (K2, 8) (K4, 1) (K2, 1)
( K3, 3) (K2, 7) (K2, 8) (K4, 2) (K2, 1)
( K3, 4) (K2, 7) (K2, 8) (K3, 2) (K2, 3) (K3,3) (K2, 1)
( K1, 3) (K2, 9).
6. Содержаниеотчёта.
1. Титульныйлист.
2. Вариантзадания.
3. Полныйсписок выбранныхключевых слови стандартныхфункций.
4. Внутренниетаблицы сканера.
5. Техническоезадание наразработкусканера (поЕСПД).
6. Отладочныепримеры работысканера с выходнымитаблицами идескрипторнымтекстом.
7.Контрольныевопросы.
1. Дайтеопределениеграмматики.
2. Назовитеэтапы трансляциипрограммы.
3. Что такоелексема?
4. Вчём состоятзадачи лексическогоанализа?
5. Дайтеопределениеметаязыка.
6. Исходныеданные длясканера.
7. Результатыработы сканера.
8. Литература.
1. Бек Л.Введение всистемноепрограммирование.М,: Мир, 1988.
-448 с.
2.Компаниец Р.И.и др. Системноепрограммирование.Основы
построениятрансляторов.-СПб.: КОРОНАпринт, 2000.-256 с.
МинистерствообразованияРоссийскойФедерации
Саратовскийгосударственныйтехническийуниверситет
Применениеконечных автоматов
влексическоманализе
лабораторнаяработа длястудентов
специальностиПВС по курсу« Теория
вычислительныхпроцессов иструктур»
Составилдоцент кафедрыПВС
СайкинА.И.
Саратов,2001 г.
Введение.
Даннаялабораторнаяработа рассчитанана четыре аудиторныхчаса и ещё четыречаса для изученияматериала иоформлениеотчёта.
Объектисследованияпроцесс трансляциизаданного языкапрограммированияв машинныекоды. Цель изучениясостоит в примененииматематическогоаппарата конечныхавтоматов прилексическоманализе. Лексическийанализ этоначальный этаптрансляции,за которымследуют грамматическийразбор и этапгенерациимашинного кода.Наиболее трудоёмкимпо затратаммашинноговремени являетсяэтап лексическогоанализа. Длясокращенияобщего временитрансляциии упрощениялексическогоанализа целесообразноиспользоватьматематическийаппарат конечныхавтоматов.Метод исследованийкак раз и базируетсяна его применении.
Выполнениеработы производитсяв дисплейномклассе. Характерисследованийсостоит в сочетаниирезультатов,полученныхна ПЭВМ с иханалитическойобработкойстудентом.
1. Содержаниеработы.
Разработкалексическогоанализаторавыполняетсядостаточнопросто, есливоспользоватьсяхорошо разработаннымматематическимаппаратом -теорией регулярныхязыков и конечныхавтоматов. Врамках этойтеории классыоднотипныхлексем (идентификаторы,константы ит.д.) рассматриваютсякак формальныеязыки (языкидентификатороф,язык константи т.д.), множествопредложенийкоторых описываетсяс помощьюсоответствующейпорождающейграмматики.При этом языкиэти настолькопросты, что онипорождаютсяпростейшейиз грамматик- регулярнойграмматикой.Построеннаярегулярнаяграмматикаявляется источником,по которомув дальнейшемконструируетсявычислительноеустройство,реализующеефункцию распознаванийпредложенийязыка, порождаемогоданной грамматикой.Для регулярныхязыков такимустройствомявляется конечныйавтомат.
ПорождающаяграмматикаG(N,T,P,S), продукциикоторой имеютвид АаВили Св,где А,В,С - нетерминальныесимволы; а,в-терминальныесимволы, называетсярегулярнойили автоматной.ЯзыкL(G), порождаемыйрегулярнойграмматикойназываетсярегулярнымили автоматнымили языком сконечным числомсостояний.Основной задачейлексическогоанализа являетсяраспознаваниелексическихединиц. Математическоймоделью процессараспознаваниярегулярногоязыка являетсявычислительноеустройство,которое называетсяконечным автоматом.Термин «конечный»подчёркиваетто, что вычислительноеустройствоимеет фиксированныйконечный объёмпамяти и обрабатываетпоследовательностьвходных символов,принадлежащихнекоторомуконечномумножеству.Существуютразличные типыконечных автоматов,если результатомработы являетсялишь указаниена то, что входнаяпоследовательностьсимволов допустимаили нет, то такойконечный автоматназываетсяконечнымраспознавателем.
В даннойлабораторнойработе необходимопостроитьконечные автоматыдля каждоготипа распознаваемыхлексем. Проводялексическийанализ, конечныеавтоматы должнысообщать одопустимостиили не допустимостиконкретныхлексем. Программалексическогоанализаторадолжна распечатыватьвходной тексти выдаватьсообщения обовсех недопустимыхлексемах.Hеобходимотакже составитьтехническоезадание наразрабатываемуюпрограммулексическогоанализатора.
2. Варианты заданий.
Вариантзадания повторой лабораторнойработе совпадаетс вариантомзадания попервой лабораторнойработе, т.е. входнымдля лексическогоанализаторабудет текст программы,составленныйиз заданногоалфавита изаданных ключевыхслов в соответствиес вариантомзадания первойлабораторнойработы.
3. Методическиеуказания.
ЛюбаярегулярнаяграмматикаG=(N,T,P,S)может бытьпредставленанаправленнымграфом, с помеченнымиузлами и дугами.Каждый узелпомечаем символомиз N.Кроме одногоконечного узла,который помечаемсимволом #.Согласно принятымсоглашениям,узел, соответствующийначальномусимволу Sпомечаем стрелкой,а конечныйизображаемв виде прямоугольника.Каждая дугаграфа соответствуеттолько однойпродукциизаданной грамматикиG.
Например,пусть регулярнаяграмматикаGимеет следующиепродукции:
SaA|bB
AaA|a
BbB|b,
тогда граф,отображающийданную грамматикуG,будет иметьвид, представленныйна рис.1. Путьна графе всегдасоединяетначальнуювершину с конечнойвершиной графа.Метки, ассоциированныес дугами, составляющимиэтот путь, образуютнекоторуюстроку. Множествотаких строксовпадают сязыком L(G).Конкретныепути на графебудут соответствоватьнекоторой схемевывода. Например,SaAaaAaaaA
aaaa,т.е. от Sк А, от А к А, отА к #. Конечныйнаправленныйграф, имеющийначальный узели один или болееконечных узловсети - есть конечныйавтомат.
a
a
b
a
#
b
b
Рис.1.Граф конечногоавтомата.
Можнодать и второеопределениеконечногоавтомата. Конечнымавтоматом (КА)называетсясовокупностьпяти множеств:
КА={N,T, t, S, F}
где :N-конечноемножествосостоянийавтомата, совпадающеес множествомнетерминальныхсимволов грамматики;
T-множествотерминальныхсимволов автомата,совпадающеес множествомтерминальныхсимволов грамматики;
t-функцияпереходов,задаваемаятаблицей;
S-начальноесостояниеавтомата;
F-конечныесостоянияавтомата.
Ф
ункцияпереходов можетбыть представленаразличнымиспособами.Основные изних: спискомкоманд КА, диаграммойсостояний иматрицей переходов.Команда КАпредставляетсобой следующуюзапись:
(Ai,a j)Ak
котораяпредставляетсобой переходв автомате извешины А iв вершину А kпо дуге,отмеченнойa j.Для КА необходимосоставлятьсписок такихкоманд, причёмон должен обязательносодержатьпереходы вконечную вершину,для нормальногозавершенияработы автомата.
Диаграммасостояний этопо сути графКА. И он содержитполную информациюоб КА.
Матрицапереходов можетбыть записанав двух видах.Во-первых, строкиматрицы - этовершины КА(нетерминальныесимволы), столбцыматрицы - терминальныесимволы, приписываемыесоответствующимдугам графаКА. Элементыматрицы - этосостояния КА,в которыеосуществляетсяпереход. Повторому способуматрица переходовзаписываетсяв три колонки,соответствующиекомандам КА.Естественно,что все триспособа равнозначны.
КА могутбыть детерминированными ДКА и недетерминированнымиНДКА. В детерминированномавтомате изкаждой вершинывыходят дуги,отмеченныевсе различнымиметками. В НДКАимеется хотябы одна вершинас одинаковоотмеченнымидугами. ДляпрограммированияДКА гораздопроще. ДКА иНДКА по существузадают эквивалентныеязыки, но имеетместо теорема,что ДКА можетпринять некоторыйязык L,если этот языкпринимает НДКА.Переход от НДКАк ДКА осуществляетсятривиально,за счёт введениядополнительныхфиктивныхсостояний. Еслииз одной вершинывыходит дведуги, обозначенныеодинаково(НДКА), то однудугу обозначаемпо другому, нозамыкаем еёна фиктивноесостояние, изкоторого проводимранее переобозначеннуюдугу к требуемомусостоянию(ДКА).
Для практическихцелей необходимо,чтобы КА самопределялмомент окончаниявходной цепочкисимволов свыдачей сообщенияо правильностиили неправильностивходной цепочкисимволов. Дляэтих целейвходная цепочкасчитаетсяограниченнойсправа концевыммаркером, вкачестве которогомогут использоватьсяобычные разделители.И в диаграммусостояний КАводятся интерпретированныесостояния:допуститьвходную цепочкукак лексему,отвергнутьвходную цепочкукак лексему,запомнитьошибку во входнойцепочке.
В общемслучае можетбыть предложенследующийпорядок конструированиялексическогоанализатора(ЛА).
1. Выделитьво входномязыке L(G)на основанииописания егосинтаксисамножествоклассов лексем.
2. Построитьдля каждогокласса автоматную(регулярную)грамматику.
3. Длякаждой автоматнойграмматикипостроить КА.
4.Определитьусловия выходаиз ЛА ( переходего в начальноесостояние) придостиженииконца произвольнойлексемы изкаждого классалексем.
5. Разбитьсимволы входногоалфавита нанепересекающиесямножества.
6.Построитьматрицу переходовЛА.
7. Выбратьформат и кодобразов лекскм-дескрипторов(см. первуюлабораторнуюработу).
8.ЗапрограммироватьЛА.
4. Содержаниеотчёта.
В соответствиис вариантомзадания каждыйстудент сотавляетотчёт по работе,в который входят:
1. Титульныйлист.
2. Вариантзадания.
3. Техническоезадание наразработкупрограммы ЛА.
4. Описаниепрограммы ЛА.
5. Работающаяпрограмма ЛА(демонстрацияработы приотчёте).
6. Выводы поработе.
5. Контрольныевопросы.
1.Как задаётсяформальнаяграмматика?
2.Как определяетсярегулярнаяграмматика?
3.Чем отличаютсясентенции исентенциальныеформы?
4.Что такое лексема?
5.В чём смыслработы ЛА?
6.Назовите основныеэтапы проектированияЛА.
7.Как задаётсяКА?
8.Как преобразоватьНДКА в ДКА?
Литература.
1.Бек Л. Введениев системноепрограммирование.М.: Мир, 1988.
-448 с.
2.Компаниец Р.И.и др. Системноепрограммирование.Основы
построениятрансляторов.-СПб.: КОРОНАпринт 2000.-256 с.
МинистерствообразованияРоссийскойФедерации
Саратовскийгосударственныйтехническийуниверситет
Формульныйкомпилятор
методическиеуказания квыполнениюлабораторной
работыпо курсу «Теориявычислительныхпроцессов
и структурдля студентовспециальностиПВС
Составилдоцент кафедрыПВС
СайкинА.И.
Саратов- 2001 г.
Введение
Данная лабораторнаяработа рассчитанана четыре аудиторныхчаса. Самостоятельнаяработа по изучениюлитературы,оформлениеотчёта ещёшесть часов.
Объект исследованияформульныйтранслятор,Цель исследованиясостоит в изучениипроблематикиразработкитрансляторовс алгоритмическихязыков. Методпредполагаетиспользованиеалгоритмарекурсивногоспуска и написаниепрограммытранслятора.Работа выполняетсяв дисплейномклассе.
1.Содержаниеработы.
Формульныйтрансляторэта программа,которая переводитисходную программу,написаннуюна входномязыке, в объектныйпсевдокод,который впоследствии,после необходимойоптимизации,может бытьзаменён машиннымкодом с абсолютнойадресацией.
Для написания программы навходном языкенеобходимосоздать язык,в который бывходили: заголовокпрограммы,оператор описаниятипа переменной,оператор вводапеременной,оператор присвоенияи операторвывода результата.Для оператораприсвоениянеобходимопредусмотретьзнаки арифметическихопераций, скобкии элементарныефункции, которыевыдаются вместес вариантомзадания. А также,разделителии служебныесимволы. В связис этим разрабатываетсяконтекстно-свободнаяграмматика,которая в последствиипозволит провестиграмматическийразбор программына исходномязыке. Грамматическомуразбору долженпредшествоватьлексическийанализ, которыйобычно не вызываетзатруднений(см. лабораторныеработы №1 и №2).
Операторприсвоенияимеет общийвид для всехвариантов
Y=Y(x).
Результатомвыполненияпрограммыдолжен бытьтекст в объектномпсевдокоде.Для чего необходимооговорить егосодержание.В работе рекомендуетсяиспользоватьтак называемыечетвёрки, имеющиевид
КОП,А1, А2, А3,
где: КОП - кодоперации,
А1- адреспервого операнда,
А2 - адресвторого операнда,
А3 - адресрезультата.
Хотя возможныи другие варианты,например, подвухадреснойи одноадреснойсхемам.
Используемыеданные могутбыть как целыми,так и с плавающейточкой.
2. Заданиепо работе.
1. Получитьвариант заданияу преподавателя.
2. Разработатьязык формульноготранслятора.
3. На основеразработаннойрегулярнойграмматикиразработать
программулексическогоанализатора.
4. На основеразработаннойконтекстно-свободнойграмматики
разработатьпрограммуграмматическогоразбора исходного
текста навходном языке.
5. Во всех случаяхпредусмотретьсообщенияпользователюо
лексическихи синтаксическихошибках.
6. Разработатьи описать объектныйпсевдокод.
7.Составить иутвердитьтехническоезадание напрограммугенерации.
8. Разработатьпрограммугенерацииобъектногопсевдокода.
9. Составитьотчёт по работес описаниемвсех пунктовзадания,
представитьработающуюпрограмму.
3. Вариантызаданий.
Вариантзадания состоитиз трёх цифр.Каждая цифраозначаетсоответствующуюстроку таблицах1, 2 и 3. В соответствиис этим, операторприсвоенияможет содержатьуказанныематематическиефункции изуказанных строктаблиц.
Таблица1.
-
№ Функция 1 acos 2 asin 3 atan 4 sin 5 cos 6 sinh 7 cosh
Таблица2.
-
№ Функции 1 exp 2 abs 3 mod 4 sqrt 5 log 6 ln 7 log10
Таблица3.
-
№ Функции 1 tan 2 tanh 3 cotan 4 cotanh 5 trunk 6 round 7 nearbyint
Подробныесведения оперечисленныхфункциях можнонайти в справочникепрограммиста поС/C++.
4.Методическиеуказания.
В любомязыке программированияобязательносуществуютограничения.Поэтому следуетсразу оговорить,что переменыеобозначаютсяидентификаторами,начинающимисяс латинскойбуквы и несодержащимиразделителей.Следует оговоритьмаксимальнодопустимуюдлину дляидентификатора.Следует оговоритьприоритет ввыполненииарифметическихопераций, которыйдолжен совпадатьс общепринятым.
Лексическийанализ, грамматическийразбор и генерацияпсевдокодамогут бытьсовмещены водной программе,но методическиих лучше реализоватьпо отдельности:вначале лексическийанализ, затем грамматическийразбор и послеэтого, когдавсе ошибкибудут устранены- генерациямашинного кода.
Но в любомслучае написаниепрограммыявляется творческимпроцессом ивсё, что говорилосьранее, носиттолько рекомендательныйхарактер.
5. Контрольные вопросы.
1. Каков приоритетв выполненииарифметическихопераций в
выражении?
2. Что такоелексема?
3. Каково назначениелексическогоанализа?
4. Каково назначениеграмматическогоразбора?
5. Как определяетсяконтекстно-свободнаяграмматика?
6. Что такое«чевёрки»?
7. Зачем используютпсевдокод?
8. В чём особенностьобъектногокода?
9. Как из объектногокода получитьисполняемыйкод?
Литература.
1. Бек Л. Введениев системноепрограммирование.-М.: Мир, 1988.-448 с.
2. КомпаниецР.И., МаньковЕ.В., ФилатовН.Е. Системноепрограмми-
рование.Основы построениятрансляторов.-СПб.:КОРОНА принт,
2000 .-256 с.
3. Шильд Г.Справочникпрограммистапо С/С++.-М.:Издательскийдом
«Вильямс»,2000.-448 с.
МинистерствообразованияРоссийскойФедерации
Саратовскийгосударственныйтехническийуниверситет
Построениедетерминированногосинтаксического
анализатора.
методическиеуказания квыполнениюлабораторной
работы покурсу «Теориявычислительныхпроцессов
структур»для студентовспециальности ПВС
Составилдоцент кафедрыПВС
СайкинА.И.
Саратов,2001 г.
1. Введение.
Данная лабораторнаяработа рассчитанана 4 аудиторныхчаса и ещё 4 часасамостоятельнойработы дляизучения литературыи оформлениеотчёта.
Объект исследования- синтаксическийанализаторвходных текстов,записанныхна языке, порождаемыхзаданнойконтекстно-свободной(КС) грамматикой.Цель работысостоит в написаниипрограммысинтаксическогоанализатора,основывающегосяна магазинномавтомате.
Метод построениясинтаксическогоанализатораосновываетсяна примененииграмматик типаLL(1),что позволяетрешить задачу,используя детерминированныйалгоритм.
Лабораторнаяработа выполняетсяв дисплейномклассе. Результатпредставляетсобой работающуюпрограмму,которая можетанализироватьлюбые текстыи сообщать обошибках программирования.
2.Содержаниеработы.
Языки программированияописываютсяКС-грамматиками.Но описаниеязыка с помощьюКС-грамматикине являетсяописаниемалгоритмапорожденияпредложенийэтого языка.Правила подстановкиграмматики- это не последовательностьпредписаний,а совокупностьразрешений,причём порядокпримененияправил в грамматикепроизволен,тогда как валгоритмедолжен бытьзадан жёсткийпорядок примененияотдельныхинструкций.
Получениеалгоритмическогоописания процессараспознаванияязыка являетсяодной из первоочередныхзадач при разработкеблока синтаксическогоанализа транслятора.
Одним изспособов описанияалгоритмараспознаванияязыка являетсязадание егов виде некоторогораспознающегоустройства.Для КС-языковтакими устройствамиявляются магазинныеавтоматы - автоматыс магазиннойпамятью.
Методовсинтаксическогоанализа достаточномного, в даннойработе применяетсянисходящийсинтаксическийанализ, которыйв свою очередьпорождает рядпроблем. Во-первых,необходимоиз грамматикиязыка исключитьлеворекурсивныепродукции, воизбежаниезацикливанияв при работеанализатора.Вторая проблемасостоит в выбореальтернативныхпродукций взаданной грамматике,что достигаетсяза счёт заглядываниявперёд на несколько,в общем случаеК символов.В-третьих, возникаетпроблема локализацииошибок. Компилятордолжен локализироватьместо ошибки,помимо указания её наличия.Ошибка обнаруживается,когда все подходящиепродукцииграмматикииспользованы.Для локализацииошибки всеальтернативыподходят вравной степени,поэтому в грамматикунеобходимовставить правила,реагирующиена ошибки (ониописываютнеправильныеконструкции)и при срабатываниитакого правилавыдавать сигналоб ошибке илипытаться исправитьеё.
Существуетцелый классКС-грамматик,которые допускаютдетерминированныйразбор сверхувниз, т.е. выполняютразбор безвозвратов.Помимо высокойскорости разбора,детерминированныеметоды имеютпреимуществов компиляторах,где разбор идётпараллельнос построениемобъектнойпрограммы. Хотяподкласс КС-языков,разбираемыхдетерминировано,уже всего классаКС-языков, нооказалось, чтобольшинствоязыков программированияможно разбиратьдетерминировано.
В качествеКС-грамматикчаще всегоиспользуетсяLL(1) грамматикаи соответсвеннометод разбораязыков, порождаемыхLL(1) грамматикой,называют LL(1)методом нисходящегосинтаксическогоразбора.
Две буквыL означают,что цепочкасимволов разбираетсяслева направо,и используютсясамые левыепродукции.Цифра 1 означает,что вариантыпорождающихпродукцийвыбираютсяс помощью одногопредварительнопросмотренногосимвола. Этатерминологиябыла впервыепредложенаКнутом. ЕслиКС-грамматикане являетсяграмматикой типа LL(1), тоеё нужно привестик этому типу.
LL(1) грамматикадопускаетдетерминированныйразбор предложенийязыка, описываемогоэтой грамматикой.Если эта грамматиказадана, то магазинныйавтомат строитсяпо известномуправилу [1],а построенныйавтомат позволяетзапрограммироватьпроцесс синтаксическогоанализа, действуяформально, чтои предопределяетрешение задачи.
3. Заданиепо работе.
1. Вариантзадания к даннойлабораторнойработе совпадаетс вариантомзадания к 1лабораторнойработе.
2. ПостроитьКС-грамматикуи проверитьявляется лиона грамматикойтипа LL(1).
3. Привестиграмматикук типу LL(1).
4. По правилу[1]построитьмагазинныйраспознаватель,реализующийдетерминированныйразбор. Составитьуправляющуютаблицу автомата.
5. Составитьтехническоезадание наразработкупрограммысинтаксическогоанализатора.
6. Запрограммироватьработу синтаксическогоанализатора.
7. Представитьдва контрольныхпримера.
8. Составитьотчёт по работе.
4. Методическиеуказания.
Язык программированияописываетсяКС-грамматикой.Детерминированныйсинтаксическийанализ требует,чтобы КС-грамматикаотвечала определённымтребованиям.Во-первых, необходимопривести её,т.е. грамматикане должна содержатьциклы, -продукции,бесполезныеи недостижимыесимволы, левыерекурсии.
Недостижимыенетерминальныесимволы никогдане появятсяни в одной извыводимыхцепочек. Бесполезныесимволы неиграют никакойроли в построенииправильныхтерминальныхцепочек. Такиесимволы могутпоявиться вКС-грамматикев основном неиз-за ошибокразработчикаязыка- они могутбыть введеныв грамматикуалгоритмами,предназначеннымидля модификацииграмматик.
КС-грамматиканазываетсяграмматикойбез -продукций(-свободной),если множествопродукций Рне содержит-продукций,либо есть толькоодна продукцияSи Sне встречаетсяв правых частяхостальныхпродукций.
КС-грамматиканазываетсяграмматикойбез циклов,если в ней нетпродукций вида
АА, для АN.
АЛГОРИТМУСТРАНЕНИЯНЕДОСТИЖИМЫХ.
Пусть данаКС-грамматикаG={N,T,P,S}. ПостроимКС-грамматику G’={N’, T’,P’, S} безнедостижимыхсимволов.Метод состоитв следующем:
1. Положиммножество V={S}и i=1.
2. Положиммножество Vi= Vi-1{AP и AVi-1}.
3. ЕслиVi Vi-1, то i=i=1и перейтик шагу 2. В противномслучае
N’= N Vi, T’=TVi.Искомое множествопродукций Р’состоит
из множествапродукций Р,содержащихсимволы измножества Vi
АЛГОРИТМУСТРАНЕНИЯБЕСПОЛЕЗНЫХСИМВОЛОВ.
Пустьдана КС-грамматикаG={N,T,P,S}. ПостроимэквивалентнуюграмматикуG’={N’, T’,P’, S} безбесполезныхсимволов. Методсостоит в следующем:
1. ПоложимN0=,i=1.
2. ПоложиммножествоNi=Ni-1{A| A, i-1)}.
3. ЕслиNiNi-1,положим i=i+1и перейтик шагу 2. В противномслучае положимN0=Ni.
4. ПоложимG1={N0N,T,P’,S}, гдеP’Pсостоитиз продукциймножества Р,содержащихсимволы изN0.
5. Применивк G1алгоритмустраненияв грамматикенедостижимыхсимволов, получимG’={N’, T’,P’, S}.
АЛГОРИТМПРЕОБРАЗОВАНИЯГРАММАТИКИВ
ГРАММАТИКУБЕЗ -ПРОДУКЦИЙ.
Пусть данаКС-грамматикаG={N,T,P,S}.Построим -свободнуюграмматикуG’,эквивалентнуюграмматикеG.Метод состоитв следующем.
1. Применяемшаги 1-3 алгоритмаустранениябесполезныхсимволов, определяеммножество N0={A | A,A}.
2. МножествоP’ строим следующимобразом. ЕслипродукцияA0B11B22...Bkk,где k и Bi0,но ни один символв цепочках j(0j k) не принадлежитN0,добавим к Р’продукциивида A01122...kk,где Xiесть илиBi или ,не включая вP’продукцию A.
Если S0,то включим вP’продукцию видаS’| S, где S’новый нетерминальныйсимвол и положимN’=NS’,в противномслучае N’=N,S’=S.
3. ПоложимG’={N’,T’,P’, S’}.
АЛГОРИТМУСТРАНЕНИЯЦЕПНЫХ ПРОДУКЦИЙ.
Пусть намдана -свободнаяКС-грамматикаG={N,T,P,S}.Получим эквивалентнуюКС-грамматикуG’={N’, T’,P’, S’} свободнуюот цепных и-продукций.
Метод состоитв следующем.
1. Для каждогоAпостроиммножество NA={B| A}нетерминальныхсимволов, выводимыхиз А следующимобразом:
1.1. ПоложимN0={A}и i=1;
1.2. ПоложимNi={C| BCи Вi-1}i-1;
1.3. ЕслиNii-1,то положимi=i+1и повторим шаг1.2. В противномслучае положимNA=N.
2. Построиммножество P’:если (В)и не являетсяцепной продукцией,то включим вP’ продукциюA,для всех такихА, что ВА.
3. ПоложимG={N, T, P’,S}.
Данный алгоритмпозволяетустранить изграмматикии циклы, т.е. выводыА*,где А.
УСТРАНЕНИЕВ КС-ГРАММАТИКЕЛЕВОЙ РЕКУРСИИ.
Алгоритмысинтаксическогоанализа легчестроить тогда,когда КС-грамматикаG не обладаетсвойствамилеворекурсивности,т.е. в ней нетпродукций видаX.Это особенноважно прииспользованииметодов разборасверху внизи слева направо.Выбор продукциииз множестваальтернативныхв этих методахбазируетсяна сравнениипорождённогокрайнего левогосимвола промежуточнойцепочки с текущимсимволом входнойтерминальнойцепочки. Припоявлении жев выводе левойрекурсии произойдётзацикливание.Поэтому прииспользованииалгоритмовнисходящегоразбора левуюрекурсию необходимоудалить.
В общем случаелевая рекурсияв КС-грамматикеможет бытьявной, когдаесть продукциивида Aили неявной-когда в грамматикеесть взаимнорекурсивныепродукции вида:
A|...
B|...
Устранениелеворекурсивныхправил. ПустьG КС-грамматика,в которой естьлеворекурсивныеправила. ЭквивалентнаяграмматикаG’ получаетсяпутём заменымножествалеворекурсивныхправил грамматикиG намножествоправил вида:
A1’|2’|... |n’
A’1’|2’|... |n|
Здесь А’-новый вспомогательныйнетерминальныйсимвол.
ДЕТЕРМИНИРОВАННЫЙСИНТАКСИЧЕСКИЙАНАЛИЗ
СВЕРХУВНИЗ
В данномсинтаксическоманализе используютсяLL(1) грамматики,которые являютсяобобщениемS-грамматик.
КС-грамматиканазываетсяS-грамматикой,если выполняютсяусловия:
-правая частькаждой продукцииначинаетсятерминальнымсимволом;
-если две илиболее продукцийимеют совпадающиелевые части,то правые частиэтих продукцийдолжны начинатьсяс различныхтерминальныхсимволов.
Для заданнойS-грамматикимагазинныйавтомат (МП-распознаватель)с одним состояниемзадаётся следующимобразом:
1. А=Т{|-}
2. Г=N{t| tи (Аt)}{}.
3. Q={q}.
4. z0={#S| S- аксиома}.
5. q0=q.
6. КаждойпродукцииКС-грамматикисопоставляетсяэлемент управляющейтаблицы МП-распознавателя.Если продукцияимеет вид At,где Aи t,а {},то этому правилув строке А и встолбце tбудут соответствоватьоперации
ЗАМЕНИТЬ(r),СДВИГ
где r- цепочка,записаннаяв обратномпорядке длятого, чтобыудовлетворитьсоглашения«верхний символсправа».
Если продукцияимеет вид Аt,то строке А истолбцу tсоответствуютоперации
ЧТЕНИЕ,СДВИГ.
Если магазиннымсимволом являетсятерминал b,то элементомтаблицы в строкеbбудет
ЧТЕНИЕ,СДВИГ.
Элементомтаблицы, которыйнаходится встроке маркерадна магазина# иконцевогомаркера |-,является
ДОПУСТИТЬ.
Все остальныеэлементы таблицызаполняютсяоперацией
ОТВЕРГНУТЬ.
где: А- символы,записанныена входнойленте;
Г- символы,записанныев магазиннуюпамять;
Q-множествосостоянийавтомата;
z0-начальнаязапись в магазин;
q0-начальноесостояниеавтомата.
S-грамматики хотя и допускаютдетерминированныйнисходящийразбор, описываютдостаточноузкий классязыков. естественнымрасширениемэтого классабыло бы - разрешить,чтобы первыйсимвол в правыхчастях продукцийэтой грамматикимог быть нетерминалом,но при этомграмматикавсё же допускаладетерминированныйразбор.
Определим ПЕРВ()как множествотерминальныхсимволов, которыеявляются первымисимволамицепочек, выводимыхиз .
Цепочка называетсяаннулирующей,если .
Продукцияграмматикивида Атакже называетсяаннулирующим.
ВЫБОР(А)=ПЕРВ(),
если - не аннулирующая,и
ВЫБОР(А)=ПЕРВ()СЛЕД(А),
если -аннулирующаяцепочка. Приэтом СЛЕД(А) -множествоследующих заА терминаловв промежуточнойцепочке, выводимойиз S|-,где S-аксиомаграмматики.
Для того,чтобы КС-грамматикабыла типа LL(1),необходимо,чтобы множествавыбора дляправил с одинаковымилевыми частямине пересекались,т.е. неимели общихтерминальныхсимволов.
Если длявашей грамматикиэто так, то онабудет относитсяк типу LL(1) идля неё автоматстроится последующемуправилу.
ПРАВИЛАОПРЕДЕЛЕНИЯДЕТЕРМИНИРОВАННОГО
МП-РАСПОЗНАВАТЕЛЯПО LL(1) ГРАММАТИКЕ.
Для заданнойLL(1) грамматикиМП-распознавательзадаётся следующимобразом:
1. А=Т{|-};
2. Г=N{t| tи (Аt),,{}}{};
3. Q={q};
4. z0={#S};
5. q0=q;
6. Управлениеописываетсяуправляющейтаблицей содним состоянием,строки помеченымагазиннымисимволами изГ, столбцы - входнымисимволами изА. Элемент таблицысоздаётся длякаждой продукции.Если продукцияимеет вид Аt,то этому правилув строке А истолбце tбудут соответствоватьоперации
ЗАМЕНИТЬ(r),СДВИГ,
где r- цепочка,записаннаяв обратномпорядке длятого, чтобыудовлетворитьсоглашению«верхний символсправа»
Если продукцияимеет вид А,где =Хи Х,{}*,то ему в строкеА и во всех столбцах,принадлежащихмножеству ВЫБОР(А),будет соответствоватьпереход
ЗАМЕНИТЬ(r),ДЕРЖАТЬ.
Когда =,вместо ЗАМЕНИТЬ()можно использоватьЧТЕНИЕ.
Если продукцияимеет вид Аt,то ей в строкеА и в столбцеt соответствуетоперация
ЧТЕНИЕ.СДВИГ.
7. Если магазиннымсимволом являетсятерминал b,то элементомтаблицы в строкеb будет
ЧТЕНИЕ.СДВИГ.
8. Элементомтаблицы, которыйнаходится встроке маркерадна #и столбце концевогомаркера |-,является
ДОПУСТИТЬ.
9. Все остальныеэлементы таблицызаполняютсяоперацией
ОТВЕРГНУТЬ.
5. Содержаниеотчёта.
Отчёт составляетсякаждым студентоми содержитразвёрнутыеответы на всепункты задания.К отчёту прилагаетсятаблица переходовМП-распознавателяи работающаяпрограммаМП-распознавателя.
6. Контрольныевопросы.
1. Как определяетсяКС-грамматика?
2. Как определяетсянормальнаяформа Хомского?
3. Как задаётсянормальнаяформа Грейбах?
4. Как исключить-продукции?
5. Как устранитьнедосигаемыесимволы?
6. Как устранитьбесполезныесимволы?
7. Как устраняютсяциклическиесвязи в продукциях?
8. Как устранитьлевые рекурсиив грамматике?
9. Как определяетсямагазинныйавтомат?
10. КакопределяетсяLL(1) грамматика?
11. Как определяетсяS-грамматика?
Литература.
1. КомпаниецР.И., МаньковЕ.В., ФилатовН.Е. Основыпостроениятрансляторов.-СПб.: КОРОНАпринт, 2000. -256 с.
2. ХантерР. Проектированиеи конструированиекомпиляторов.М.: Финансы истатистика.1984 г.
3. Грис Д.Конструированиекомпиляторовдля цифровыхвычислительныхмашин. М.: Мир,1975г.