Транслятор

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАСТВЕННОЕ  ОБРАЗОВАТЕЛЬНОЕ УЧЕРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

ИНСТЕТУТДОПОЛНИТЕЛЬНОГО ДОПОЛНИТЕЛЬНОГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

 

Кафедра «Программное обеспечение вычислительной техники»

 

 

 

 

 

 

 

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

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

 

 

 

 

 

 

 

 

 

 

Выполнил:

Студентки 3 курса

Специальности ПОВТ 1з 348-10

Беляков М.А.

Проверил:

Калабин А.Л.

 

 

 

                                                 

 

Тверь 2013

Содержание

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

1.Транслятор………………………………………………………....4

2.Лексический анализатор………….…………………………….…5

3.Синтаксический анализатор……………………………………....6

4.Генератор кода………………………………………………..…….6

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

6.Лексический анализатор…………………………………………..10

7.Синтаксический анализатор………………………………………11

8.Генератор кода……………………………………………………..20

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

Список литературы…………………………………………………………….25

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

        Компиляторы   составляют   существенную   часть   программного

обеспечения ЭВМ.  Это связано с тем, что языки  высокого уровня

стали основным  средством разработки  программ.  Только  очень

незначительная  часть   программного  обеспечения,   требующая

особой эффективности.

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

 

Цель работы:

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

№ варианта	Конструкция языка
4.	IF <Выражение> THEN <Список операторов> {ELSE <Список операторов >}
	ENDIF

4. Провести тестирование приложения, для проверки правильности работы.

 

 

 

 

 

 

 

 

 

 

 

1. Транслятор

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

Транслятор - в узком смысле - программа, преобразующая: программу, написанную на одном (входном) языке в программу, представленную на другом (выходном) языке. 

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

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

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

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

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

 

 

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

4.  Генератор кода

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

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

 

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

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

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

 

Вариант 3

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

 

Нетерминалы

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

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

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

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

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

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

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

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

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

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

O=<Операнд>

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

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

N=<Цифра>

 

Терминалы

T = {  Var,Print 0,1,;,(,)=}

L=a|..|z буквы

B=+|-|*| / бинарные

U= - унарный

N = 0,1…9 цифры

 

Правила

1) S -> DF 

2) F-> G;

3) D-> VAR V

4) G -> A

5) G-> GA

6) V -> I

7)V -> I,V

8) A -> I=E

9) E-> UH

10) E -> H

11) H-> E

12) H-> O

13) H -> HOH

14) I -> LI

15) I -> L

16) C ->NC

17) C -> N

18) P-> PRINT I

 

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

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

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

namespace Compilyator

{

    /// <summary>

    /// перечесление, содержащее типы лексем

    /// </summary>

    public enum LexemType

    {

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

        Separator, Identificator, Number, Assignment, LexemError, LeftBracket, RightBracket, EndOfFile, LessOrEqual, Less, MoreOrEqual, More, Equal, If, Then, Else, EndIf,

        NotEqual

    }

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

Var a,b;

[

a=1;

b=5;

If a<b Then

a=a+1;

Else

a=a+2;

EndIf

Print a;

]

 

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

string 1 Var -> Type

string 1 a -> Identificator

string 1 , -> Separator

string 1 b -> Identificator

string 2 ; -> EndOfOperation

string 3 [ -> Begin

string 3 a -> Identificator

string 3 = -> Assignment

string 3 1 -> Number

string 4 ; -> EndOfOperation

string 4 b -> Identificator

string 4 = -> Assignment

string 4 5 -> Number

string 5 ; -> EndOfOperation

string 5 If -> If

string 5 a -> Identificator

string 5 < -> Less

string 5 b -> Identificator

string 6 Then -> Then

string 6 a -> Identificator

string 6 = -> Assignment

string 6 a -> Identificator

string 6 + -> Plus

string 6 1 -> Number

string 7 ; -> EndOfOperation

string 8 Else -> Else

string 8 a -> Identificator

string 8 = -> Assignment

string 8 a -> Identificator

string 8 + -> Plus

string 8 2 -> Number

string 9 ; -> EndOfOperation

string 10 EndIf -> EndIf

string 10 Print -> Print

string 10 a -> Identificator

string 11 ; -> EndOfOperation

string 11 ] -> End

 

 

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