Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

а) РБНФ;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

Р - множество правил вывода грамматики, являющееся конечным подмножеством множества (V_T V_N)⁺ (V_T V_N)^*; элемент (, ) множества Р называется правилом вывода и записывается в виде (читается: «из цепочки выводится цепочка »);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размещено на http://www.allbest.ru/

БНФ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ENDWHILE

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

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

<Операнд> ::= <Идент> | <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;

D1> D (; | , { D1 } )

S > {D : = V1 ; | U}

V1> - V

V > P { T1 P }

P > M {T2 M}

T1 > + | -

T2 > * | /

M > D | K | ( V1 )

D > { B1 }

K > { C }

U > WHILE V2 DO F ENDWHILE

F > { S1 }

F > M I M

I > < | > | >= | <= | =

B1 > | 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

C > 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. Разработка алгоритма решения задачи

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

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

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

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

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

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

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

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

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

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

3 - числа;

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

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

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

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

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

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

Алгоритм:

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

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

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

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

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

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

7. 4.

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

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

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

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

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

Пример 1

Integer i,n;

Begin

i:=i+1;

End

Составим для примера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).

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

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

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

a) либо , где и это единственное правило вывода для этого нетерминала, где V- множество терминалов, N- множество нетерминалов;

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

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

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

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

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

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

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

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

Procedure L;

Begin if CH<>`a` then ER else

While ( CH=`,`) do L;

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

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

. . .

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

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

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

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

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

Алгоритм:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наименование модуля	Глобальные данные	Типы данных	Назначение	Описание входных данных	Описание выходных данных
Unit1	Nextsymb	процедура	Реализует переход на следующий символ	Файл лексем	отсутствует
	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 - Основные процедуры и функции

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

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

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

5.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 Спецификация выходных данных

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

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



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

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

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

1	1	1
1	4	1
7	2	1
2	4	1
1	2	1
2	1	2
1	4	3
2	2	3
1	4	3
3	2	3
1	3	3
1	2	3
3	1	4

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

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

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

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

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

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

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

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

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

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

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

2. 128 Мб оперативной памяти

3. 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

15. Огран.txt

16. Слова1.txt

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложение A

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

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

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

StringGrid2: TStringGrid;

Button1: TButton;

Button2: TButton;

Memo1: TMemo;

Button3: TButton;

Button4: TButton;

Memo2: TMemo;

StringGrid3: TStringGrid;

StringGrid4: TStringGrid;

Button5: TButton;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Button5Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

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

a5:textfile;

s5:string;

k1,k2,k3:string;

S:set of byte;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var a:textfile;

c:string;

i:integer;

begin

assignfile(a,'слова1.txt');

reset(a);

i:=0;

while eof(a)<>true do

begin

readln(a,c);

stringgrid1.cells[1,i]:=c;

stringgrid1.cells[0,i]:=inttostr(i+1);

stringgrid1.RowCount:=stringgrid1.RowCount+1;

i:=i+1;

end;

closefile(a);

end;

procedure TForm1.Button4Click(Sender: TObject);

var c:textfile;

s:string;

begin

assignfile(c,'kod.txt');

reset(c);

memo2.lines.Clear;

while eof(c)<>true do

begin

readln(c,s);

memo2.lines.add(s);

end;

closefile(c);

end;

procedure TForm1.Button3Click(Sender: TObject);

type

char1=set of char;

var m,r,f,d:textfile;

bykva,number,ogran1,ogran2,ogran3:char1;

i,j,n,nlex,ntab,nstr,error:integer;

str,stroka:string;

flag:boolean;

numVal:Extended;

begin

Form1.Memo1.Clear;

for j:=0 to Form1.StringGrid3.Cols[0].Count-1 do

begin

Form1.StringGrid3.Cells[0,j]:='';

Form1.StringGrid3.Cells[1,j]:='';

end;

for j:=0 to Form1.StringGrid4.Cols[0].Count-1 do

begin

Form1.StringGrid4.Cells[0,j]:='';

Form1.StringGrid4.Cells[1,j]:='';

end;

bykva:=['A'..'z'];

number:=['0'..'9'];

ogran1:=[' ','.',',',';',':','=','(',')','+','-','*','>','<','/','!','_'];

ogran2:=[' ',',',';',':','=','(',')','+','-','*','>','<','/','!','_'];

ogran3:=['=','>'];

for i:=0 to Form1.memo2.lines.count-1 do

begin

stroka:=Form1.Memo2.Lines[i]+' ';

n:=1;

while n<=length(stroka) do

if stroka[n] in bykva then

begin

str:=stroka[n];

inc(n);

while (stroka[n] in ogran1)=false do

begin

str:=str+stroka[n];

inc(n);

end;

flag:=false;

for j:=0 to Form1.StringGrid1.Cols[0].Count-1 do

if Form1.StringGrid1.Cells[1,j]=str then

begin

nlex:=StrToInt(Form1.StringGrid1.Cells[0,j]);

ntab:=1;

nstr:=i+1;

Form1.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));

flag:=true;

end;

if flag=false then

begin

for j:=0 to Form1.StringGrid3.Cols[0].Count-1 do

if Form1.StringGrid3.Cells[1,j]=str then

begin

ntab:=4;

nlex:=StrToInt(Form1.StringGrid3.Cells[0,j]);

nstr:=i+1;

Form1.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));

flag:=true;

end;

if flag=false then

for j:=0 to Form1.StringGrid3.Cols[0].Count-1 do

if Form1.StringGrid3.Cells[0,j]='' then

begin

Form1.StringGrid3.Cells[0,j]:=IntToStr(j+1);

Form1.StringGrid3.Cells[1,j]:=str;

nlex:=StrToInt(Form1.StringGrid3.Cells[0,j]);

nstr:=i+1;

ntab:=4;

Form1.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));

flag:=true;

break;

end;

end;

end

else

//Числа

if stroka[n] in Number then

begin

str:=stroka[n];

inc(n);

while (stroka[n] in ogran2)=false do

begin

str:=str+stroka[n];

inc(n);

end;

Val(str, numVal, error);

if error=0 then

begin

flag:=false;

for j:=0 to Form1.StringGrid4.Cols[0].Count-1 do

if Form1.StringGrid4.Cells[1,j]=str then

begin

nlex:=StrToInt(Form1.StringGrid4.Cells[0,j]);

ntab:=3;

nstr:=i+1;

Form1.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));

flag:=true;

end;

if flag=false then

for j:=0 to Form1.StringGrid4.Cols[0].Count-1 do

if Form1.StringGrid4.Cells[0,j]='' then

begin

Form1.StringGrid4.Cells[0,j]:=IntToStr(j+1);

Form1.StringGrid4.Cells[1,j]:=str;

nlex:=StrToInt(Form1.StringGrid4.Cells[0,j]);

ntab:=3;

nstr:=i+1;

Form1.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));

break;

end;

end

else

begin

ShowMessage('Ошибка синтаксиса в '+IntToStr(nstr+1)+' строке: '+str);

halt;

end;

end

else

//Ограничители

if (stroka[n] in ogran1) or (stroka[n] in ogran2) then

begin

if stroka[n]=' ' then

begin

inc(n);

flag:=false;

end

else

begin

str:=stroka[n];

inc(n);

if stroka[n] in ogran3 then

begin

str:=str+stroka[n];

inc(n);

end;

begin

for j:=0 to Form1.StringGrid2.RowCount-1 do

if Form1.StringGrid2.Cells[1,j]=str then

begin

nlex:=StrToInt(Form1.StringGrid2.Cells[0,j]);

ntab:=2;

nstr:=i+1;

Form1.Memo1.Lines.Add(inttostr(nlex)+' '+inttostr(ntab)+' '+inttostr(nstr));

end;

end;

end;

end else

if Pos(stroka[n], rus)<>0 then

begin

Showmessage('Недопустимы символы русского алфавита.'+'Ошибка в '+IntToStr(nstr+1)+' строке');

halt;

end;

end;

AssignFile(m,'num.txt');

rewrite(m);

i:=0;

while Form1.StringGrid4.Cells[1,i]<>'' do

begin

str:=Form1.StringGrid4.Cells[1,i];

writeln(m,str);

inc(i);

end;

closefile(m);

AssignFile(r,'id.txt');

rewrite(r);

i:=0;

while Form1.StringGrid3.Cells[1,i]<>'' do

begin

str:=Form1.StringGrid3.Cells[1,i];

writeln(r,str);

inc(i);

end;

closefile(r);

assignfile(a5,'Lex.txt');

rewrite(a5);

for i:=0 to Memo1.Lines.Count-1 do

begin

s5:=Memo1.Lines.Strings[i];

writeln(a5,s5);

end;

writeln(a5,'');

closefile(a5);

end;

procedure TForm1.Button2Click(Sender: TObject);

var gr:textfile;

i:integer;

c:string;

begin

assignfile(gr,'огран.txt');

reset(gr);

i:=0;

while eof(gr)<>true do

begin

readln(gr,c);

stringgrid2.cells[1,i]:=c;

stringgrid2.cells[0,i]:=inttostr(i+1);

stringgrid2.RowCount:=stringgrid2.RowCount+1;

i:=i+1;

end;

closefile(gr);

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Form1.Memo1.Clear;

Form1.Memo2.clear;

end;

//Синтаксис

procedure TForm1.Button5Click(Sender: TObject);

begin

winexec('fas\Project1.exe',SW_SHOW);

end;

end.

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

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;

type

TForm1 = class(TForm)

Button1: TButton;

StringGrid1: TStringGrid;

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

a5:textfile;

k1,k2,k3:string;

num:integer;

S:set of byte;

implementation

{$R *.dfm}

procedure Er(r:integer);forward;

procedure Nextsymb;

begin

num:=num+1;

k1:='';

k2:='';

k3:='';

k1:=form1.stringgrid1.Cells[0,num];

k2:=form1.stringgrid1.Cells[1,num];

k3:=form1.stringgrid1.Cells[2,num];

end;

procedure Presymb;

begin

num:=num-1;

k1:='';

k2:='';

k3:='';

k1:=form1.stringgrid1.Cells[0,num];

k2:=form1.stringgrid1.Cells[1,num];

k3:=form1.stringgrid1.Cells[2,num];

end;

procedure D2;forward;

procedure B;forward;

procedure Proc_P1;

begin

D2;

B;

end;

procedure S1;forward;

procedure B;

begin

Nextsymb;

if ((k1<>'2')or(k2<>'1'))then Er(1)

else

begin

Nextsymb;

S1;

if ((k1<>'3')or(k2<>'1'))then Er(2)

else

Er(17);

end;

end;

procedure D1;forward;

procedure D2;

begin

Nextsymb;

if((k1<>'1')or(k2<>'1'))then Er(3)

else

D1;

end;

procedure U;forward;

procedure D1;

begin

Nextsymb;

if k2<>'4' then Er(4)

else

begin

if strtoint(k1) in S then Er(16)

else S:=S+[strtoint(k1)];

Nextsymb;

if (k2='2') then

if (k1<>'1')then

if (k1<>'7') then Er(15)

else

D1;

end;

end;

procedure V1;forward;

procedure S1;

begin

if (k2<>'4') then

begin

if ((k1='4')and(k2='1')) then U;

end

else

begin

if not(strtoint(k1) in S) then Er(5);

Nextsymb;

if ((k1<>'2')or(k2<>'2')) then Er(6)

else

V1;

if ((k1<>'1')or(k2<>'2')) then Er(7);

end;

Nextsymb;

if (k2='4')or((k1='4')and(k2='1')) then S1;

end;

procedure V;forward;

procedure V1;

begin

Nextsymb;

if (k2='2') and (k1='4') then

begin

V;

end

else

begin

Presymb;

V;

end;

end;

procedure P;forward;

procedure V;

begin

P;

while ((k1='3')or(k1='4')) do

P;

end;

procedure M;forward;

procedure P;

begin

M;

Nextsymb;

while ((k1='5')or(k1='6')) do

M;

end;

procedure V2;forward;

procedure F;forward;

procedure M;

begin

Nextsymb;

if ((k2<>'4')and(k2<>'3')) then

begin

if ((k1<>'8')or(k2<>'2')) then Er(8)

else

begin

V1;

if ((k1<>'9')or(k2<>'2')) then Er(9);

end;

end;

if k2='4' then if not(strtoint(k1) in S) then Er(10);

end;

procedure U;

begin

if ((k1<>'4')or(k2<>'1')) then Er(11)

else

begin

V2;

Nextsymb;

if ((k1<>'5')or(k2<>'1')) then Er(12)

else

begin

Nextsymb;

F;

//Nextsymb;

if ((k1<>'6')or(k2<>'1')) then Er(13);

end;

end;

end;

procedure V2;

begin

M;

Nextsymb;

if ((k1<>'11')and(k1<>'12')and(k1<>'13')and(k1<>'14')and(k1<>'15')or(k2<>'2'))then

Er(14)

else M;

end;

procedure F;

begin

S1;

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

num:=-1;

S:=[];

Proc_P1;

end;

procedure TForm1.FormCreate(Sender: TObject);

var

s:string;

i,j:integer;

s1,s2,s3:string;

begin

assignfile(a5,'Lex.txt');

reset(a5);

j:=0;

while not(eof(a5)) do

begin

s1:='';

s2:='';

s3:='';

readln(a5,s);

i:=1;

if eof(a5) then exit;

while s[i]<>' ' do

begin

s1:=s1+s[i];

i:=i+1;

end;

form1.stringgrid1.Cells[0,j]:=s1;

i:=i+1;

while s[i]<>' ' do

begin

s2:=s2+s[i];

i:=i+1;

end;

form1.stringgrid1.Cells[1,j]:=s2;

i:=i+1;

while (i<=length(s))and(s[i]<>' ') do

begin

s3:=s3+s[i];

i:=i+1;

end;

form1.stringgrid1.Cells[2,j]:=s3;

j:=j+1;

Form1.StringGrid1.RowCount:=Form1.StringGrid1.RowCount+1;

end;

num:=-1;

closefile(a5);

end;

procedure Er(r:integer);

begin

case r of

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

end;

halt;

end;

end.

Размещено на Allbest.ru