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

Министерство образования  и науки РФ

Федеральное государственное  бюджетное

Образовательное учреждение  высшего профессионального образования  ТвГТУ

 

 

 

Кафедра программного обеспечения

 

 

 

 

 

 

 

 

 

 

Курсовой проект

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

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

 

 

 

 

 

 

 

 

 

 

 

Выполни:

Студент 4 курса

Специальности ПОВТ0906

Евграфов Д.С.

Проверил:

Калабин А.Л.

 

Содержание

Введение………………………………………………………………………3

1. Теоретическая часть…………………………………………………..4
1. Транслятор………………………………………………………...4
2. Лексический анализатор………….………………………………4
3. Синтаксический анализатор……………………………………...5
4. Генератор кода…………………………………………………….6
2. Практическая часть……………………………………………………8
1. Синтаксис языка в БНФ. Терминалы, нетерминалы, начальный символ и правила………………………..………………………...8
2. Лексический анализатор…………………………………………..10
3. Синтаксический анализатор………………………………………13
4. Генератор кода……………………………………………………..17

Заключение…………………………………………………………………….20

 

Введение

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

1. Корректная обработка  исходного(входного) текста.

2. Корректная обработка  всевозможных исключительных ситуаций.

3. Универсальность.

4. Оптимизированная работа.

5. Наличие на выходе  корректного результата обработки  исходного текста.

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

Целью данной курсовой работы является разработка транслятора. Для  достижения поставленной цели необходимо решить следующие задачи:

1. Представить синтаксис языка в БНФ. Определить терминалы, нетерминалы, начальный символ и набор правил для данного языка.
2. Создать каркас транслятора.
3. Построить лексический анализатор. Результатом работы анализатора должна быть таблица лексем.
4. Построить синтаксический анализатор. Приведение выражений к обратной польской записи.
5. Построить генератор кода.
6. Протестировать приложение.

 

1. Теоретическая  часть

1.1 Транслятор

Транслятор — программа или техническое средство, выполняющее трансляцию программы.

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

Транслятор обычно выполняет  также диагностику ошибок, формирует  словари идентификаторов, выдаёт для  печати тексты программы и т. д.

Язык, на котором представлена входная программа, называется исходным языком, а сама программа — исходным кодом. Выходной язык называется целевым  языком или объектным кодом.

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

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

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

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

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

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

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

Каждый токен можно представить в виде структуры, содержащей идентификатор токена (или идентификатор класса токена) и, если нужно, последовательность символов лексемы, выделенной из входного потока (строку, число и т. д.).

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

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

В информатике, синтакси́ческий ана́лиз (па́рсинг) — это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно применяется совместно с лексическим анализом. Синтаксический анализатор (парсер) — это программа или часть программы, выполняющая синтаксический анализ.

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

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

Типы алгоритмов:

Нисходящий парсер (англ. top-down parser) — продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов.

• LL-анализатор

Восходящий парсер (англ. bottom-up parser) — продукции восстанавливаются из правых частей, начиная с токенов и кончая стартовым символом.

• LR-анализатор
• GLR-парсер

1.4  Генератор  кода

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

 В данной работе  мы будем генерировать программу  на языке ассемблера. Чтобы облегчить  написание генератора кода и  освободить его от посторонних  соображений, связанных с конкретными  особенностями какой-либо ЭВМ,  будем использовать гипотетический  процессор (виртуальную машину). Этот процессор не существует  на самом деле (в аппаратном  виде). При выборе его архитектуры  требовалась максимальная простота  и, в то же время, возможность  легко выполнять на нем программы  на языках, реализуемых в процессе  выполнения лабораторных работ  и курсового проектирования.  Особенностью архитектуры является то, что все действия выполняются только над элементами в вершине стека, результаты операций также помещаются в вершину стека . Поэтому в арифметических и логических операциях нет необходимости в указании адреса операндов. Если операция имеет 2 операнда, то ее выполнения подразумевает перенос элемента из вершины стека в регистр-аккумулятор и «понижение» на один элемент вниз указателя стека. Второй операнд, оказавшийся в вершине стека, подается непосредственно в АЛУ. Результат операции помещается в вершину стека вместо него.

 

2. Практическая  часть

2.1 Синтаксис языка в БНФ. Терминалы, нетерминалы, начальный символ и правила

Вариант задания:

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

<Описание  вычислений> ::= Begin <Список присваиваний> End <Объявление переменных> ::= Var <Список переменных>

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

<Присваивание> <Список присваиваний> <Присваивание> ::= <Идент> = <Выражение>

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

< Подвыражение > <Бин.оп.> <Подвыражение>

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

<Бин.оп.> ::= "-" | "+" | "*" | "/"

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

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

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

<Оператор печати>::=Print <Идент>

 

На одной  строке может быть только объявление переменных или один оператор присваивания.

Форма Бекуса – Наура  – набор правил, последовательным применением которых можно построить  любое предложение.

Грамматика определяется, как следующая четверка Vt – алфавит, символы которого называются терминалами из них строятся цепочки порождаемые грамматикой; Vn – алфавит, символы которого называется нетерминальными (не терминалами), используются при построении цепочек. P – Набор правил, по которым строится грамматика; S – начальное правило. 

Нетерминалы:

S=<Программа>

D=<Объявление переменных>

F=<Описание вычислений>

P=<Оператор печати>

V=<Список переменных>

I=<Идентификатор>

G=<Список присваиваний>

A=<Присваивания>

E=<Выражение>

H=<Подвыражение>

O=<Операнд>

C=<Константа>

T=<Оператор печати>

N=<Цифра>

 

Терминалы:

Ключевые слова языка:

T = {Begin | End | Var | Print | Case | of | Endcase}

Разделители:

R ={=|;|()|,}

Алфавит:

L = {a|..|z}

Бинарные операции:

B = {+|-|*|/ }

Унарные операции:

U ={-}

Цифры:

N = {0|..|9}

 

Правила:

1)S -> DFTs

2) D -> Var V

3) V -> I

4) V -> I, V

5) F -> Begin G End

6) G -> A

7) G-> AG

8) A -> I=E

9) I->LI

10) I -> L

11) E-> UH

12) E-> H

13) H -> E

14) H -> O

15) H -> HBH

16) O ->I

17) O -> C

18) C -> NС

19) C -> N

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

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

Классы лексем различаемые лексическим анализатором:

/// <summary>

    /// список всех возможных лексем языка

    /// </summary>

    public enum Lexemes

    {

      Begin, End, Print, Plus, Minus, Multiplication, Division, Type, EndOfOperation,

      Separator, Identificator, Number, Assignment, LexemError, LeftBracket, RightBracket, EndOfFile,

  Case, Of, EndCase, CaseBlock

    }

Примеры входного и выходного файлов для лексического анализатора

Входной файл: