Конструирование транслятора для модельного языка

 

Министерство образование Российской Федерации

Федеральное агентство образования

Государственное образовательное учреждение

высшего профессионального образования

«Оренбургский Государственный Университет»

Математический факультет

Кафедра администрирования информационных систем

Языки программирования и методы трансляции

Конструирование транслятора для модельного языка

Введение

Компилятор - это программа, которая осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или языке ассемблере.

Несмотря на более чем полувековую историю вычислительной техники, формально годом рождения теории компиляторов можно считать 1957, когда появился первый компилятор языка Фортран, созданный Бэкусом и дающий достаточно эффективный объектный код. До этого времени создание компиляторов было весьма «творческим» процессом. Лишь появление теории формальных языков и строгих математических моделей позволило перейти от «творчества» к «науке». Именно благодаря этому, стало возможным появление сотен новых языков программирования.

Несмотря на то, что к настоящему времени разработаны тысячи различных языков и их компиляторов, процесс создания новых приложений в этой области не прекращается. Это связно как с развитием технологии производства вычислительных систем, так и с необходимостью решения все более сложных прикладных задач. Такая разработка может быть обусловлена различными причинами, в частности, функциональными ограничениями, отсутствием локализации, низкой эффективностью существующих компиляторов. Поэтому, основы теории языков и формальных грамматик, а также практические методы разработки компиляторов лежат в фундаменте инженерного образования по информатике и вычислительной технике.

Цель курсовой работы:

-закрепление теоретических знаний в области теории формальных языков, грамматик, автоматов и методов трансляции;

-формирование практических умений и навыков разработки собственного компилятора модельного языка программирования;

закрепление практических навыков самостоятельного решения инженерных задач, развитие творческих способностей студентов и умений пользоваться технической, нормативной и справочной литературой.

В настоящее время в мире появляются более новые языки программирования и не каждый из ныне существующих трансляторов могут прочитать программы, написанный на новом языке, и перевести его в другой язык. Поэтому сейчас разрабатываются новые трансляторы, в этом и заключается актуальность данной курсовой работы.

1. Постановка задачи к курсовой работе

1.Разработать компилятор модельного языка, выполнив следующие действия.

2.В соответствии с номером варианта составить формальное описание модельного языка программирования с помощью:

а) РБНФ;

б) диаграмм Вирта;

в) формальных грамматик.

3.Написать пять содержательных примеров программ, раскрывающих особенности конструкций учебного языка программирования, отразив в этих примерах все его функциональные возможности.

.Составить таблицы лексем для тестовых примеров из п.3.

5.Разработать программное средство, реализующее лексический анализ текста программы на входном языке.

.Вывести примеры таблиц идентификаторов и чисел.

7.Реализовать синтаксический анализатор текста программы на модельном языке методом рекурсивного спуска.

8.Построить цепочку вывода и дерево разбора простейшей программы на модельном языке из начального символа грамматики.

.Дополнить синтаксический анализатор с процедурами проверки семантической правильности программы на модельном языке в соответствии с контекстными условиями вашего варианта.

.Показать динамику изменения содержимого стека при семантическом анализе программы на примере одного синтаксически правильного выражения.

.Записать правила вывода грамматики с действиями по переводу в ПОЛИЗ программы на модельном языке.

.Пополнить разработанное программное средство процедурами, реализующими генерацию внутреннего представления введенной программы в форме ПОЛИЗа.

13.Разработать интерпретатор ПОЛИЗа программы на модельном языке.

14.Составить набор контрольных примеров, демонстрирующих:

а) все возможные типы лексических, синтаксических и семантических ошибок в программах на модельном языке;

б) перевод в ПОЛИЗ различных конструкций языка;

в) представить ход интерпретации синтаксически и семантически правильной программы с помощью таблицы.

2. Формальная модель задачи

Существуют три основных метода описания синтаксиса языков программирования: формальные грамматики, формы Бэкуса-Наура и диаграммы Вирта.

Формальные грамматики

Определение 2.1. Формальной грамматикой называется четверка вида:

,

где VN - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

VT - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), VT ÇVN =Æ;

Р - множество правил вывода грамматики, являющееся конечным подмножеством множества (VTÈ VN)+ ´ (VTÈ VN)*; элемент (a, b) множества Р называется правилом вывода и записывается в виде a®b (читается: «из цепочки a выводится цепочка b»);

S - начальный символ грамматики, S ÎVN.

Для записи правил вывода с одинаковыми левыми частями вида используется сокращенная форма записи .

Формы Бэкуса-Наура (БНФ)

Метаязык, предложенный Бэкусом и Науром, использует следующие обозначения:

-символ «::=» отделяет левую часть правила от правой (читается: «определяется как»);

-нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки «<» и «>»;

терминалы - это символы, используемые в описываемом языке;

правило может определять порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или»).

Расширенные формы Бэкуса-Наура (РБНФ)

Для повышения удобства и компактности описаний, в РБНФ вводятся следующие дополнительные конструкции (метасимволы):

-квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;

-фигурные скобки «{» и «}» означают повторение заключенной в них синтаксической конструкции ноль или более раз;

сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз;

круглые скобки «(» и «)» используются для ограничения альтернативных конструкций.

Диаграммы Вирта

В метаязыке диаграмм Вирта используются графические примитивы, представленные на рисунке 2.1.

При построении диаграмм учитывают следующие правила:

-каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно изображаются на противоположных сторонах;

-каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;

альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием;

должна быть одна входная дуга (располагается обычно слева или сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа и снизу);

стрелки на дугах диаграмм обычно не ставятся, а направления связей отслеживаются движением от начальной дуги в соответствии с плавными изгибами промежуточных дуг и ветвлений.

БНФ

<Программа> ::= <Объявление переменных> <Описание вычислений>

<Описание вычислений> ::= Begin <Список присваиваний> End

<Объявление переменных> ::= Integer <Список переменных>

<Список переменных> ::= <Идент>; | <Идент> , <Список переменных>

<Список присваиваний>::= <Присваивание> |

<Присваивание> <Список присваиваний>|<Цикл с постусловием>;

<Присваивание> ::= <Идент> := <Выражение> ;

<Выражение> ::= <Ун.оп.> <Подвыражение> | <Подвыражение>

<Подвыражение>:: = <произведение> { <бинарная операция 1> <произведение>}

<произведение>:: = <множитель> { <бинарная операция 2> <множитель>}

<множитель>:: = <операнд> | (<выражение>)

<бинарная операция 1>: : = + | -

<бинарная операция 2>: : = * | /

<Ун.оп.> ::= "-"

< Цикл с постусловием >::=WHILE <Выражение> DO<Список операторов>

<Список операторов>::= <оператор > | <Оператор > <Список Операторов>

<оператор >::= <Присваивание> | <Присваивание> <Список присваивания>

<Операнд> ::= <Идент> | <Const>

<Идент> ::= <Буква> <Идент> | <Буква>

<Const> ::= <Цифра> <Const> | <Цифра>

<Буква>::= a|...|z)

<Цифра> ::= 0|1|…|9

PБНФ

<Программа> ::= <Объявление переменных> <Описание вычислений>

<Описание вычислений> ::= Begin <Список присваиваний> End

<Объявление переменных> ::= Integer {/<Список переменных>/}

<Список переменных> ::= <Идент>(; |{, <Список переменных>})

<Список присваиваний>::= {<Идент> := <Выражение> ; |<Цикл с постусловием>;}

<Выражение> ::= "-" <Подвыражение>

<Подвыражение>:: = <произведение> { <бинарная операция 1> <произведение>}

<произведение>:: = <множитель> { <бинарная операция 2> <множитель>}

<множитель>:: = (<Идент> | <Const>)| (<выражение>)

<бинарная операция 1>: : = + | -

<бинарная операция 2>: : = * | /

<Цикл с постусловием>::= WHILE<Логическое выражение> DO<Список операторов>ENDWHILE

<Список операторов>::={<Список присаиваний >}

<Идент> ::= {<Буква>}

<Const> ::= {<Цифра> }

<Буква>::= a|...|z)

<Цифра> ::= 0|1|…|9

Опишем РБНФ с помощью формальной грамматики, согласно принятым обозначениям металингвистических переменных нетерминалами формальной грамматики (таблица 1).

Формальные грамматики

P ? D2 B

B ? Begin S1 End

D2? Integer D1;? D (; | , { D1 } ) ? {D : = V1 ; | U}? - V? P { T1 P }? M {T2 M}? + | -? * | /? D | K | ( V1 )? { B1 }? { C }? WHILE V2 DO F ENDWHILE

F ? { S1 }? M I M? < | > | >= | <= | =? | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y |z ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Таблица 1 - Соответствия металингвистических переменных РБНФ и нетерминалов формальной грамматики

Нетерминал формальной грамматикиМеталингвистическая переменнаяP1<программа>D2<объявление переменных>B2<описание вычислений>S1<список присваиваний>V<Подвыражение>V1<Выражение>D1<Список переменных>D<Идент>K<Const>F<список операторов>B<буква>P<Произведение>M<множитель> V2<логическое условие>U<цикл с постусловием>

3. Разработка алгоритма решения задачи

.1 Лексический анализатор

Лексический анализатор (ЛА) или сканер - это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.

Лексема (лексическая единица языка) - это структурная единица языка, которая состоит из элементарных символов языка и не содержит с своем составе других структурных единиц языка. Лексемами языков программирования являются идентификаторы, константы, ключевые слова языка, знаки операций и .т.п.

В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, разделителей и ключевых слов.

Задача лексического анализа - выделить лексемы и преобразовать их к виду, удобно для последующей обработки.

Лексический анализатор имеет дело с такими объектами, как различного рода константы, идентификаторы, ключевые слова. Язык описания констант и идентификаторов в большинстве случаев является регулярным (автоматным), т.е. может быть описан с помощью автоматных грамматик. Распознавателями для автоматных языков являются конечные автоматы.

Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем с учетом характеристик каждой лексемы.

В процедурных языках лексемы делятся на классы:

- служебные слова;

- ограничители;

- числа;

- идентификаторы

и помещаются в таблицу лексем с соответствующими номерами.

Так, что лексема представляется парой чисел (n,k), где n - номер таблицы, k - номер лексемы в этой таблице.

Приведем один из алгоритмов реализации лексического анализатора:

Вход: таблица ограничителей, таблица служебных слов, текст транслируемой программы.

Выход: файл лексем, таблица идентификаторов, сообщение об ошибке.

Алгоритм:

1.открыть файл транслируемой программы и считать i-тую строку;

2.в исходной строке считываем символы в новую строку s до тех пор, пока не встретится пробел, либо ограничитель.

.проверяем, принадлежит ли полученная строка s таблице служебных слов, если да то к пункту 4, иначе к пункту 5.

.записываем в таблице лексем числа k1, k2, k3, где k1 - номер лексемы в таблице, где k2 - номер таблицы, k3 - номер строки в транслируемой программе.

.проверяем, является ли s идентификатором. Если да, то записываем информацию в файл лексем, согласно пункту 4, и записываем s в таблицу идентификаторов.

.если s[j] принадлежит таблице ограничителей, то проверяем, является ли следующий за ним символ ограничителем. Если да, то записываем в новую строку str символы s[j], пока они являются ограничителями. Далее сравниваем строку str с ограничителями, если находятся равные, то записываем в файл лексем согласно пункту 4. Иначе сравниваем символ s[j] с ограничителями, если находятся равные, то записываем в файл лексем согласно пункту

.4.

.если конец строки, то i:=i+1, к пункту 1.

.программа выполняется до тех пор, пока не достигнут конец файла транслируемой программы.

3.2 Синтаксический анализатор

Синтаксический анализатор (СиА) - программа, производящая синтаксический анализ на соответствие транслируемой программы правилам заданного языка.

Рассмотрим простейший пример программы на модельном языке:

Пример 1

Integer i,n;:=i+1;

Составим для примера1 цепочку вывода:

P1 à D2B àInteger i;B àInteger D{,D};B àInteger i{,B1};B àInteger i,n;B àInteger i,n; Begin S1 End àInteger i,n; Begin D:=V1; End à Integer i,n; Begin i:=V1; End à Integer i,n; Begin i:=[ _ ]V; End à Integer i,n; Begin i:=P{T1 P}; End à Integer i,n; Begin i:=M{T1P}; End à Integer i,n; Begin i:=D{T1 P}; End à Integer i,n; Begin i:=i{T1 P}; End à Integer i,n; Begin i:=i + P; End à Integer i,n; Begin i:=i + M; End à Integer i,n; Begin i:=i + K; End à Integer i,n; Begin i:=i + 1; End

Построим дерево вывода для данного примера1 (рисунок 1).

Рисунок 1 - дерево разбора для примера1

Для синтаксического разбора используются КС-грамматика (контекстно-свободная грамматика).

Разбор по КС-грамматикам можно реализовать различными способами.

Одним из наиболее простых и потому одним из наиболее популярных методов нисходящего синтаксического анализа является метод рекурсивного спуска (recursive descent method) .

Метод рекурсивного спуска (РС-метод) реализует этот способ следующим образом:

-для каждого нетерминала грамматики создается своя процедура, носящая его имя;

-задача каждой такой процедуры - начиная с указанного места исходной цепочки найти подцепочку, которая выводится из этого нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом процедуры обработки ошибки, которая выдает сообщение о том, что цепочка не принадлежит языку, и останавливает разбор.

-Если подцепочку удалось найти, то работа процедуры считается нормально завершенной и осуществляется возврат в точку вызова.

-Тело каждой такой процедуры пишется непосредственно по правилам вывода соответствующего нетерминала: для правой части каждого правила осуществляется поиск подцепочки, выводимой из этой правой части. При этом терминалы распознаются самой процедурой, а нетерминалы соответствуют вызовам процедур, носящих их имена.

Метод рекурсивного спуска

Метод рекурсивного спуска применим в том случае, если каждое правило грамматики имеет вид:

a)либо , где и это единственное правило вывода для этого нетерминала, где V- множество терминалов, N- множество нетерминалов;)либо , где для всех ; для ; , т. е. если для нетерминала правил вывода несколько, то они должны начинаться с терминалов, причем все эти терминалы должны быть различными. Ясно, что если правила вывода имеют такой вид, то рекурсивный спуск может быть реализован по вышеизложенной схеме.

Естественно, возникает вопрос: если грамматика не удовлетворяет этим условиям, то существует ли эквивалентная КС-грамматика, для которой метод рекурсивного спуска применим? К сожалению, нет алгоритма, отвечающего на поставленный вопрос, т.е. это алгоритмически неразрешимая проблема.

Изложенные выше ограничения являются достаточными, но не необходимыми.

Попытаемся ослабить требования на вид правил грамматики:

1)при описании синтаксиса языков программирования часто встречаются правила, описывающие последовательность однотипных конструкций, отделенных друг от друга каким-либо знаком-разделителем (например, список идентификаторов при описании переменных, список параметров при вызове процедур и функций и т.п.).

Общий вид этих правил:

(либо в сокращенной форме ) Формально здесь не выполняются условия применимости метода рекурсивного спуска, т.к. две альтернативы начинаются одинаковыми терминальными символами. Если принять решение, что в таких случаях будем выбирать самую длинную подцепочку (что и требуется при разборе реальных языков), то разбор становится детерминированным.

Тогда для метода рекурсивного спуска процедура будет такой:

Procedure L;

Begin if CH<>`a` then ER else ( CH=`,`) do L;

2)если грамматика не удовлетворяет требованиям применимости метода рекурсивного спуска, то можно попытаться преобразовать ее, т.е. получить эквивалентную грамматику, пригодную для анализа этим методом, например, т.е удалить левую рекурсию, провести левую факторизацию правил (см. лекцию).

3)если в грамматике есть нетерминал, у которого несколько правил вывода, и среди них есть правила, начинающиеся нетерминальными символами, т.е. имеют вид

. . .

где ; ; , то можно заменить вхождения нетерминалов их правилами вывода в надежде, что правило нетерминала станет удовлетворять требованиям метода рекурсивного спуска:

Исходная грамматика модельного языка соответствует требованиям для реализации метода рекурсивного спуска, поэтому используя метод рекурсивного спуска, опишем некий алгоритм реализации синтаксического анализатора:

Алгоритм решения задачи

Входные данные СиА - файл лексем (построенный на этапе лексического анализа)

Выходные данные - заключение о синтаксической правильности программы или предупреждение об имеющихся ошибках. Сообщения об ошибках должны быть построены на основе правил грамматики.

Алгоритм:

1.для каждого нетерминала грамматики создаем рекурсивную процедуру. Самой первой процедурой синтаксического анализатора является процедура Рroc_P1, внутри нее расположены процедуры D2 и B, которые вызываются поочерёдно в зависимости от их расположения

2.открываем файл лексем, созданный на этапе лексического анализатора

.считываем очередную лексему с помощью процедуры Nextsymb, и рекурсивно проходим по каждой процедуре

.при несоответствии считанной лексемы терминалу выдается сообщение об ошибке

.при успешном распознавании цепочки выдается сообщение об отсутствии ошибок в синтаксисе программы

3.3 Семантический анализ

В ходе семантического анализа проверяются отдельные правила записи исходных программ, которые не описываются КС-грамматикой. Эти правила носят контекстно-зависимый характер, их называют семантическими соглашениями или контекстными условиями.

Рассмотрим пример построения семантического анализатора (СеА) для программы на модельном языке М. Соблюдение контекстных условий для языка М предполагает три типа проверок:

) обработка описаний;

) анализ выражений;

) проверка правильности операторов.

В оптимизированном варианте СиА и СеА совмещены и осуществляются параллельно.

Обработка описаний

Задача обработки описаний - проверить, все ли переменные программы описаны правильно и только один раз. Эта задача решается следующим образом.

На этапе лексического анализа была создана таблица идентификаторов, обнаруженных в тексте исходной программы. На этапе семантического анализа создается множество S , в которое помещается все идентификатора описанные в объявлении переменных.

Анализ выражений

Задача анализа выражений - проверить описаны ли переменные, встречающиеся в выражениях, и соответствуют ли типы операндов друг другу и типу операции.

Эти задачи решаются следующим образом. На этапе семантического анализа создается множество S , в которое помещается все идентификаторы описанные в объявлении переменных. Если встречающийся идентификатор не находится в множестве S, то выводится сообщение об ошибке.

Проверка правильности операторов

Задачи проверки правильности операторов:

) выяснить, все ли переменные, встречающиеся в операторах, описаны;

) установить соответствие типов в операторе присваивания слева и справа от символа «:=»;

) определить, является ли выражение V2 в операторе цикла целым.

Из исходной грамматики заметим, что в семантическом анализе необходимо реализовать только обработку описаний и анализ выражений.

Рассмотрим алгоритм решения данной задачи

)Реализуем обработку описаний следующим образом:

Если лексема впервые встречается и не находиться в множестве , тогда в множество S записывается номер данной лексемы.

) Реализуем анализ выражений следующим образом:

Поскольку в исходной грамматике все идентификаторы имеют целый тип, то проверку выражений можно не реализовывать. Реализуем только проверку на описание всех идентификаторов в разделе описаний переменных. В процедурах S1 и M производим проверку на наличие входных лексем в множестве S, если входная лексема не расположена в множестве S, тогда сообщение об неизвестном идентификаторе.

4. Спецификация основных процедур и функций

.1 Лексический анализатор

Основные процедуры и функции, с помощью которых реализован лексический анализатор (Таблица 2).

Таблица 2 - Основные процедуры и функции

Наименование модуляГлобальные данныеТипы данныхНазначениеОписание входных данныхОписание выходных данныхUnit 1Button1ClickпроцедураЗаполнение таблиц служебных слов Sender: TObject Отсутствует Button2ClickпроцедураЗаполнение таблиц ограничителей Sender: TObjectОтсутствуетButton4ClickпроцедураВывод примера программыSender: TObjectОтсутствуетButton5ClickпроцедураСинтаксический анализSender: TObject, файл лексемСообщение об ошибке, сообщение о правильности программы Button3Click процедура Лексический анализ Sender: TObject Таблица идентификаторов ,таблица цифр, и файл лексем Form Create процедура Очистка Sender: TObject Отсутствует

.2 Синтаксический анализатор

Рассмотрим процедуры и функции, с помощью которых реализован синтаксический анализатор (таблица 3).

Таблица 3 - Основные процедуры и функции

Наименование модуляГлобальные данныеТипы данныхНазначениеОписание входных данныхОписание выходных данныхUnit1NextsymbпроцедураРеализует переход на следующий символФайл лексемотсутствуетButton5ClickпроцедураСинтаксический анализ программыSender: TObject ,файл лексемСообщение об ошибке или об отсутствии синтаксических ошибокP1процедураГлавная процедура рекурсивного спускаСтрока лексем k1,k2, k3 из файла лексемотсутствуетD2 процедураРеализует проверку входных данныхСтрока лексем k1,k2, k3 из файла лексемотсутствуетBпроцедураРеализует проверку тела проверяемой программыСтрока лексем k1,k2, k3 из файла лексемотсутствуетS1процедураРеализует проверку выраженийСтрока лексем k1,k2, k3 из файла лексемотсутствуетV1процедураРеализует проверку на унарн. МинусСтрока лексемОтсутствуетVпроцедураРеализует проверку подвыраженийСтрока лексемОтсутствуетV2процедураРеализует проверку логическогого выраженияСтрока лексемОтсутствуетUпроцедураРеализует проверку циклаСтрока лексемОтсутствуетMпроцедураРеализует проверку множителейСтрока лексемОтсутствуетPпроцедураРеализует проверку произведенийСтрок лексемОтсутствуетD1Процедура Реализует проверку описания входных данных Строка лексемОтсутствует F процедура Реализует проверку списков операторовСтрока лексем Отсутствует Presymb процедура Реализует переход на предыдущую лексемуСтрока лексем отсутствует

4.3 Семантический анализатор

Рассмотрим процедуры и функции, с помощью которых реализован семантический анализатор (таблица 4).

Таблица 4 - Основные процедуры и функции

Наименование модуляГлобальные данныеТипы данныхНазначениеОписание входных данныхОписание выходных данныхUnit1S1процедураРеализует проверку на описание идентификаторовФайл лексемОтсутствуетD1процедураРеализует проверку на дубликат идентификаторафайл лексем ОтсутствуетMпроцедураРеализует проверку на наличие идентификатора в списке объявленных переменФайл лексем Отсутствует

5. Структурная организация данных

.1 Спецификация входных данных

.1.1 Этап лексического анализа

Для исходного языка представим несколько примеров программ.

Таблица 7 - Спецификации входных данных лексического анализа

Пример 1 Integer i,n; Begin i:=i+1; End Пример 2 Integer i,n; Begin WHILE i<n DO i:=i+1; ENDWHILE EndПример 3 Integer i,n; Begin i:=i+n; WHILE i<n DO i:=(i+1); i:=i+n; ENDWHILE End Пример 4 Integer i,n; Begin i:=i+n; WHILE i<n DO i:=(i+1); WHILE i<n DO i:=(i+1); ENDWHILE i:=i+n; ENDWHILE EndПример 5 Integer I; Begin I:=1 Endпрограммирование синтаксис анализатор семантический

5.1.2 Этап синтаксического анализа

На этапе синтаксического анализа входными данными является таблица лексем (рисунок 1).

Рисунок 1 - файл лексем

В данной таблице первая цифра означает номер лексемы в этой таблице, вторая - номер таблицы, третья - номер строки в транслируемой программе.

5.1.3 Этап семантического анализа

Семантический анализатор реализуется совместно с синтаксическим анализатором, поэтому входными данными на этапе семантического анализатора является также файл лексем.

5.2 Спецификация выходных данных

.2.1 Этап лексического анализа

На этом этапе выходными данными являются: файл чисел(рис. 1), файл идентификаторов( рис. 2), сообщение об неправильности идентификатора.

Рисунок 1 - Файл идентификаторв

Рисунок 2 - Файл чисел

Таблица 8 - Таблица лексем для исходного примера

111 141721241121212143223143323133123314

5.2.2 Этап синтаксического анализа

На данном этапе выходными данными являются сообщение об ошибке и сообщение об отсутствии синтаксических ошибок в программе (таблица 9).

Таблица 9- Возможные сообщения на этапе синтаксического анализа

Сообщения об ошибкенет begin в строкенет End в строке нет Integer в строке нет := в строке нет ; или , в строке нет ( в строке нет ) в строке нет WHILE в строке нет DO в строке нет ENDWHILE в строке нет < | > | <= | >= | = в строкенет ; в строкенет идентификатора в строке Сообщение о выполнении синтаксического анализаУспешно выполнен анализ

5.2.3 Этап семантического анализа

На этапе семантического анализа возможны сообщения об ошибке (таблица 10).

Таблица 10 -Сообщения об ошибке на этапе семантического анализа

Сообщения об ошибкеДанный идентификатор уже объявленНеобъявленный идентификатор

6. Установка и эксплуатация программного средства

Cистемные требования (минимум)

1.1.5 Мб свободного пространства на жестком диске

2.128 Мб оперативной памяти

.1.8 ГГц частота ядра процессора

Установка: для установки поместите папку «Анализ» в удобное для вас место на жестком диске. Эта папка содержит файлы:

1.Project1.exe

2.Unit1.pas

3.Project1.dpr

4.Project1.res

5.Project1.dof

6.Project1.cfg

7.Unit1.dfm

8.Unit1.ddp

9.Unit1.dcu

10.Unit1.C++ Builder Form

11.Lex.txt

12.Id.txt

13.Num.txt

14.Kod.txt

.Огран.txt

.Слова1.txt

Папку «sin» содержащую файлы:

.Project1.exe

2.Unit1.pas

3.Project1.dpr

4.Project1.res

5.Project1.dof

6.Project1.cfg

7.Unit1.dfm

8.Unit1.ddp

9.Unit1.dcu

10.Unit1.C++ Builder Form

7. Работа с программным средством

Для работы с данным программным средством необходимо выполнить следующие действия:

1.Откройте папку с именем «Программа».

2.Откройте приложение. Нажмите кнопки «Вывести служ. слова»: для вывода служебных слов для вывода ограничителей.

3.Кликнув по кнопке в окне приложения появиться код транслируемой программы по умолчанию .

4.Далее кликнув по кнопке , осуществиться лексический анализ программы. Если анализ прошел успешно, то в окне приложения, расположенного над кнопкой появиться таблица составленная из лексем.

.Кликнув по кнопке появится второе окно приложения в котором будет произведен синтаксический анализ кода транслируемой программы.

6.Если анализ прошел успешно то в окне приложения появится сообщение об успешном выполнении синтаксического анализа:

7.иначе выдастся сообщение об ошибке. Например:

Заключение

Мы создали лексический, синтаксический и семантический анализы с заданного подмножества языка программирования TURBO PASCAL с незначительными модификациями и изменениями. Также изучили составные части, основные принципы построения и функционирования компиляторов. Разработали РБНФ, БНФ и диаграммы Вирта для данной грамматики.

Для разработки лексический анализатор мы использовали таблицы ограничителей, служебных слов и код транслируемой программы. Выходными данными являются таблицы лексем, идентификаторов и чисел. Которые являются входными данными синтаксического и семантического анализатора.

Также мы изучили различные виды синтаксического анализа такие как цепочка вывода, дерево разбора и метод рекурсивного спуска. Который мы использовали для написания синтаксического анализа.

Данный проект позволит разобраться студентам с методами анализа программы и на практике проверить знания, полученные при изучении предмета «Системное программное обеспечение». Также является основой для дальнейшей разработки учебного комплекса.

Список использованных источников

1.Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты.: Пер. с англ. - М.: Изд. дом «Вильямс», 2001. - 768с.

2.Опалева Э. А., Самойленко В. П. Языки программирования и методы трансляции. - СПб.: БХВ-Петербург, 2005. - 480 с.: ил.

.Ишакова Е. Н. Разработка компиляторов: Методические указания к курсовой работе. - Оренбург: ГОУ ОГУ, 2005. - 50 с.

.Афанасьев А.Н. Формальные языки и грамматики: Учебное пособие. - Ульяновск: УлГТУ, 1997. - 84с.

.Волкова И.А., Руденко Т.В. Формальные языки и грамматики. Элементы теории трансляции. - М.: Диалог-МГУ, 1999. - 62 с.

.Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под ред. А. Матросова. - СПб: Питер, 2002. - 688с.

7.Рейуорд-Смит В. Теория формальных языков. Вводный курс: Пер. с англ. - М.: Радио и связь, 1988. - 128с.

.Соколов А.П. Системы программирования: теория, методы, алгоритмы: Учеб.пособие. - М.: Финансы и статистика, 2004. - 320с.

.Федоров В.В. Основы построения трансляторов: Учебное пособие. - Обнинск: ИАТЭ, 1995. - 105с.

Приложение A

Текст программы

Лексический анализ

unit Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Grids;= class(TForm): TStringGrid;: TStringGrid;: TButton;: TButton;: TMemo;: TButton;: TButton;: TMemo;: TStringGrid;: TStringGrid;: TButton;Button1Click(Sender: TObject);Button2Click(Sender: TObject);Button4Click(Sender: TObject);Button3Click(Sender: TObject);FormCreate(Sender: TObject);Button5Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;:string = 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯабвгдеёжзийклмнопрстуфхцчшщьыъэюя';:textfile;:string;,k2,k3:string;:set of byte;

{$R *.dfm}TForm1.Button1Click(Sender: TObject);a:textfile;:string;:integer;(a,'слова1.txt');(a);:=0;eof(a)<>true do(a,c);.cells[1,i]:=c;.cells[0,i]:=inttostr(i+1);.RowCount:=stringgrid1.RowCount+1;:=i+1;;(a);;TForm1.Button4Click(Sender: TObject);c:textfile;:string;(c,'kod.txt');(c);.lines.Clear;eof(c)<>true do(c,s);.lines.add(s);;(c);;TForm1.Button3Click(Sender: TObject);=set of char;m,r,f,d:textfile;,number,ogran1,ogran2,ogran3:char1;,j,n,nlex,ntab,nstr,error:integer;,stroka:string;:boolean;:Extended;.Memo1.Clear;j:=0 to Form1.StringGrid3.Cols[0].Count-1 do.StringGrid3.Cells[0,j]:='';.StringGrid3.Cells[1,j]:='';;j:=0 to Form1.StringGrid4.Cols[0].Count-1 do.StringGrid4.Cells[0,j]:='';.StringGrid4.Cells[1,j]:='';;:=['A'..'z'];:=['0'..'9'];:=[' ','.',',',';',':','=','(',')','+','-','*','>','<','/','!','_'];:=[' ',',',';',':','=','(',')','+','-','*','>','<','/','!','_'];:=['=','>'];i:=0 to Form1.memo2.lines.count-1 do:=Form1.Memo2.Lines[i]+' ';:=1;n<=length(stroka) dostroka[n] in bykva then:=stroka[n];(n);(stroka[n] in ogran1)=false do:=str+stroka[n];(n);;:=false;j:=0 to Form1.StringGrid1.Cols[0].Count-1 doForm1.StringGrid1.Cells[1,j]=str then:=StrToInt(Form1.StringGrid1.Cells[0,j]);:=1;:=i+1;.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));:=true;;flag=false thenj:=0 to Form1.StringGrid3.Cols[0].Count-1 doForm1.StringGrid3.Cells[1,j]=str then:=4;:=StrToInt(Form1.StringGrid3.Cells[0,j]);:=i+1;.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));:=true;;flag=false thenj:=0 to Form1.StringGrid3.Cols[0].Count-1 doForm1.StringGrid3.Cells[0,j]='' then.StringGrid3.Cells[0,j]:=IntToStr(j+1);.StringGrid3.Cells[1,j]:=str;:=StrToInt(Form1.StringGrid3.Cells[0,j]);:=i+1;:=4;.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));:=true;;;;

//Числаstroka[n] in Number then:=stroka[n];(n);(stroka[n] in ogran2)=false do:=str+stroka[n];(n);;(str, numVal, error);error=0 then:=false;j:=0 to Form1.StringGrid4.Cols[0].Count-1 doForm1.StringGrid4.Cells[1,j]=str then:=StrToInt(Form1.StringGrid4.Cells[0,j]);:=3;:=i+1;.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));:=true;;flag=false thenj:=0 to Form1.StringGrid4.Cols[0].Count-1 doForm1.StringGrid4.Cells[0,j]='' then.StringGrid4.Cells[0,j]:=IntToStr(j+1);.StringGrid4.Cells[1,j]:=str;:=StrToInt(Form1.StringGrid4.Cells[0,j]);:=3;:=i+1;.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));;;('Ошибка синтаксиса в '+IntToStr(nstr+1)+' строке: '+str);;;

//Ограничители(stroka[n] in ogran1) or (stroka[n] in ogran2) thenstroka[n]=' ' then(n);:=false;:=stroka[n];(n);stroka[n] in ogran3 then:=str+stroka[n];(n);;j:=0 to Form1.StringGrid2.RowCount-1 doForm1.StringGrid2.Cells[1,j]=str then:=StrToInt(Form1.StringGrid2.Cells[0,j]);:=2;:=i+1;.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));;;;elsePos(stroka[n], rus)<>0 then('Недопустимы символы русского алфавита.'+'Ошибка в '+IntToStr(nstr+1)+' строке');;;;(m,'num.txt');(m);:=0;Form1.StringGrid4.Cells[1,i]<>'' do:=Form1.StringGrid4.Cells[1,i];(m,str);(i);;(m);(r,'id.txt');(r);:=0;Form1.StringGrid3.Cells[1,i]<>'' do:=Form1.StringGrid3.Cells[1,i];(r,str);(i);;(r);(a5,'Lex.txt');(a5);i:=0 to Memo1.Lines.Count-1 do:=Memo1.Lines.Strings[i];(a5,s5);;(a5,'');(a5);;TForm1.Button2Click(Sender: TObject);gr:textfile;:integer;:string;(gr,'огран.txt');(gr);:=0;eof(gr)<>true do(gr,c);.cells[1,i]:=c;.cells[0,i]:=inttostr(i+1);.RowCount:=stringgrid2.RowCount+1;:=i+1;;(gr);;TForm1.FormCreate(Sender: TObject);.Memo1.Clear;.Memo2.clear;;

//СинтаксисTForm1.Button5Click(Sender: TObject);('fas\Project1.exe',SW_SHOW);;.

Синтаксический анализ

unit Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Grids;= class(TForm): TButton;: TStringGrid;Button1Click(Sender: TObject);FormCreate(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;:textfile;,k2,k3:string;:integer;:set of byte;

{$R *.dfm}Er(r:integer);forward;Nextsymb;:=num+1;:='';:='';:='';:=form1.stringgrid1.Cells[0,num];:=form1.stringgrid1.Cells[1,num];:=form1.stringgrid1.Cells[2,num];;Presymb;:=num-1;:='';:='';:='';:=form1.stringgrid1.Cells[0,num];:=form1.stringgrid1.Cells[1,num];:=form1.stringgrid1.Cells[2,num];;D2;forward;B;forward;Proc_P1;;;;S1;forward;B;;((k1<>'2')or(k2<>'1'))then Er(1);;((k1<>'3')or(k2<>'1'))then Er(2)(17);;;D1;forward;D2;;((k1<>'1')or(k2<>'1'))then Er(3);;U;forward;D1;;k2<>'4' then Er(4)strtoint(k1) in S then Er(16)S:=S+[strtoint(k1)];;(k2='2') then(k1<>'1')then(k1<>'7') then Er(15);;;V1;forward;S1;(k2<>'4') then((k1='4')and(k2='1')) then U;not(strtoint(k1) in S) then Er(5);;((k1<>'2')or(k2<>'2')) then Er(6);((k1<>'1')or(k2<>'2')) then Er(7);;;(k2='4')or((k1='4')and(k2='1')) then S1;;V;forward;V1;;(k2='2') and (k1='4') then;;;;;P;forward;V;;((k1='3')or(k1='4')) do;;M;forward;P;;;((k1='5')or(k1='6')) do;;V2;forward;F;forward;M;;((k2<>'4')and(k2<>'3')) then((k1<>'8')or(k2<>'2')) then Er(8);((k1<>'9')or(k2<>'2')) then Er(9);;;k2='4' then if not(strtoint(k1) in S) then Er(10);;U;((k1<>'4')or(k2<>'1')) then Er(11);;((k1<>'5')or(k2<>'1')) then Er(12);;

//Nextsymb;((k1<>'6')or(k2<>'1')) then Er(13);;;;V2;;;((k1<>'11')and(k1<>'12')and(k1<>'13')and(k1<>'14')and(k1<>'15')or(k2<>'2'))then(14)M;;F;;;TForm1.Button1Click(Sender: TObject);:=-1;:=[];_P1;;TForm1.FormCreate(Sender: TObject);:string;,j:integer;,s2,s3:string;(a5,'Lex.txt');(a5);:=0;not(eof(a5)) do:='';:='';:='';(a5,s);:=1;eof(a5) then exit;s[i]<>' ' do:=s1+s[i];:=i+1;;.stringgrid1.Cells[0,j]:=s1;:=i+1;s[i]<>' ' do:=s2+s[i];:=i+1;;.stringgrid1.Cells[1,j]:=s2;:=i+1;(i<=length(s))and(s[i]<>' ') do:=s3+s[i];:=i+1;;.stringgrid1.Cells[2,j]:=s3;:=j+1;.StringGrid1.RowCount:=Form1.StringGrid1.RowCount+1;;:=-1;(a5);;Er(r:integer);r of

: showmessage('нет begin в строке '+k3);

: showmessage('нет end в строке '+k3);

: showmessage('нет Integer в строке'+k3);

4: showmessage('нет идентификатора в строке'+k3);

: showmessage('необъявленный идентификатор в строке '+k3);

: showmessage('нет := в строке '+k3);

: showmessage('нет ; в строке '+k3);

: showmessage ('нет ( в строке '+k3);

: showmessage('нет )в строке '+k3);

: showmessage('необъявленный идентификаторв в строке '+k3);

: showmessage('нет While в строке '+k3);

: showmessage('нет Do в строке '+k3);

13: showmessage ('нет EndWhile в строке '+k3);

: showmessage('нет >|<|>=|<=|= в строке '+k3);

15: showmessage('нет ; или , в строке '+k3);

: showmessage('данный идентификатор в строке '+k3+' уже объявлен');

:showmessage('успешно выполнен анализ');;

halt;;.

Министерство образование Российской Федерации Федеральное агентство образования Государственное образовательное учреждение высшего профессионального об

Больше работ по теме: