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

 

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

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

Введение

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

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

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

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

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

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

·Представить синтаксис языка в БНФ. Определить терминалы, нетерминалы, начальный символ и набор правил для данного языка.

·Создать каркас транслятора.

·Построить лексический анализатор. Результатом работы анализатора должна быть таблица лексем.

·Построить синтаксический анализатор. Приведение выражений к обратной польской записи.

·Построить генератор кода.

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

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

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

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

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

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

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

В информатике лексический анализ - процесс аналитического разбора входной последовательности символов (например, такой как исходный код на одном из языков программирования) с целью получения на выходе последовательности символов, называемых «токенами <#"justify">1.3 Синтаксический анализатор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

N={

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

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

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

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

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

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

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

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

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

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

O=<Операнд>

C=<Const>

N=<Цифра>

}

Терминалы:

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

T={begin, end, integer, print}

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

R={:=, .();}

Алфавит:

A={a|…|z}

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

B={+|-|/|*}

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

U={-}

Цифры:

C={0|…|9}

Правила:

1.S=DF

.F=begin G end

.G=A

.G=AG

.A=I:=E

.I=LI

.I=L

.E=UH

.E=H

.H=(E)

.H=O

.H= HBH

.O=I

.O=C

.C=NC

.C=N

.D=integer V

.V=I;

.V=I,V

.P=print I

2.2 Каркас транслятора

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

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

///<summary>

///Парсер

///</summary>

///<summary>

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

///</summary>

///<summary>

///Лексемы

///</summary>

{, Name, Number, Begin, End, Multiplication, Division,, Minus, Equal, NotEqual, Less, LessOrEqual, More, MoreOrEqual, Int,, LeftBracket, RightBracket, Semi, Comma, EOF, Determine,, Until, Do, EndUntil

}

///<summary>

///Ключевоеслово

///</summary>

{word;;

}

///<summary>

///Категория

///</summary>

{, Var, Type

}

///<summary>

///Тип

///</summary>

{, Int, LInt, Bool

}

///<summary>

///Идентификатор

///</summary>

{name;category;type;

}

///<summary>

///Таблицаимен

///</summary>

///<summary>

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

///</summary>

///<summary>

/// Генератор постфиксной записи

///</summary>

///<summary>

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

///</summary>

Дальше создаем необходимый для удобной работы интерфейс (рис.1), с верхним меню:

Рис.1 Интерфейс приложения

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

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

publicenumLexems

{, Name, Number, Begin, End, Multiplication, Division,, Minus, Equal, NotEqual, Less, LessOrEqual, More, MoreOrEqual, Int,, LeftBracket, RightBracket, Semi, Comma, EOF, Determine,, Until, Do, EndUntil

}

Далее создаем отдельную структуру, описывающую данный тип лексемы:

///<summary>

///Ключевоеслово

///</summary>

{word;;

}Initialize()

{= newKeyWord[10];= 0;= 0;= null;("Begin", Lexems.Begin);("End", Lexems.End);("Integer", Lexems.Int);("Long Integer", Lexems.LongInt);("Print", Lexems.Print);("UNTIL", Lexems.Until);("DO", Lexems.Do);("ENDUNTIL", Lexems.EndUntil);

}

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

///<summary>

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

///</summary>

{[] keywords;;;;

///<summary>

///Инициализировать

///</summary>Initialize()

{= newKeyWord[10];= 0;= 0;= null;("Begin", Lexems.Begin);("End", Lexems.End);("Integer", Lexems.Int);("Long Integer", Lexems.LongInt);("Print", Lexems.Print);("UNTIL", Lexems.Until);("DO", Lexems.Do);("ENDUNTIL", Lexems.EndUntil);

}

///<summary>

///Текущееимя

///</summary>

{

{;

}

}

///<summary>

///Текущаялексема

///</summary>

{

{;

}

}

///<summary>

///Добавитьключевоеслово

///</summary>

///<param name="keyword">слово</param>

///<param name="lex">лексема</param>

///<returns></returns>(string keyword, Lexemslex)

{(keywordPointer<keywords.Length)

{kw = newKeyWord();

kw.word = keyword;.lex = lex;

keywords[keywordPointer++] = kw;;

};

}

///<summary>

///Получитьключевоеслово

///</summary>

///<param name="keyword">слово</param>

///<returns></returns>(string keyword)

{(inti = keywordPointer - 1; i>= 0; i--)

{(keywords[i].word == keyword)

{keywords[i].lex;

}

}.Name;

}

///<summary>

///Разоьрать следующую лексему

///</summary>

publicstaticvoidParseNextLexem()

{(char.IsWhiteSpace(Reader.CurrentChar)).ReadNextChar();(char.IsLetter(Reader.CurrentChar))();(char.IsDigit(Reader.CurrentChar))();(Reader.CurrentChar == '\n')

{.ReadNextChar();= Lexems.None;

}(Reader.CurrentChar == '<')

{.ReadNextChar();(Reader.CurrentChar == '=')

{.ReadNextChar();= "<=";= Lexems.LessOrEqual;

}

{= "<";= Lexems.Less;

}

}(Reader.CurrentChar == '>')

{.ReadNextChar();(Reader.CurrentChar == '=')

{.ReadNextChar();= ">=";= Lexems.MoreOrEqual;

}

{= ">";= Lexems.More;

}

}(Reader.CurrentChar == '=')

{.ReadNextChar();(Reader.CurrentChar == '=')

{.ReadNextChar();= "==";= Lexems.Equal;

}

{= "=";= Lexems.Determine;

}

}(Reader.CurrentChar == '!')

{.ReadNextChar();(Reader.CurrentChar == '=')

{.ReadNextChar();= "!=";= Lexems.NotEqual;

}.Error("Неизвестный символ");

}(Reader.CurrentChar == '+')

{.ReadNextChar();= "+";= Lexems.Plus;

}(Reader.CurrentChar == '*')

{.ReadNextChar();= "*";= Lexems.Multiplication;

}(Reader.CurrentChar == '/')

{.ReadNextChar();= "/";= Lexems.Division;

}(Reader.CurrentChar == ',')

{.ReadNextChar();= ",";= Lexems.Comma;

}(Reader.CurrentChar == ';')

{.ReadNextChar();= ";";= Lexems.Semi;

}(Reader.CurrentChar == '(')

{.ReadNextChar();= "(";= Lexems.LeftBracket;

}(Reader.CurrentChar == ')')

{.ReadNextChar();= ")";= Lexems.RightBracket;

}(Reader.CurrentChar == char.MinValue)

{= "EOF";= Lexems.EOF;

}.Error("Недопустимый символ!");

}

///<summary>

///Разобратьидентификатор

///</summary>()

{= string.Empty;count = 0;

{+= Reader.CurrentChar;(identificator == "Long")

{.ReadNextChar();+= Reader.CurrentChar;++;

}.ReadNextChar();(++count > 20).Error("Chars overflow");

}(char.IsLetter(Reader.CurrentChar));= identificator;= GetKeyword(identificator);

}

///<summary>

///Разобратьчисло

///</summary>()

{number = string.Empty;

{+= Reader.CurrentChar;.ReadNextChar();

}(char.IsDigit(Reader.CurrentChar));

{.Parse(number);

}(OverflowException)

{.Error("Не является числом");

}= number;= Lexems.Number;

}

}

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

После того как был создан класс classReader, далее начнем заполнять его функционалом.

Напишем класс и процедуру, которая будет отвечать за перевод выражения в обратную польскую запись:

publicstaticclassPostFix

{<string> res;<Lexems> stack;

///<summary>

///Инициализировать

///</summary>Initialize()

{= newList<string>();= newStack<Lexems>();

}

///<summary>

///Добавить

///</summary>

///<param name="lexem"></param>Add(Lexemslexem)

{(lexem)

{.Name:

{temp = LexicalAnalyzer.CurrentName;.Add(temp);

};.Number:

{temp = LexicalAnalyzer.CurrentName;.Add(temp);

};.LeftBracket:

{.Push(Lexems.LeftBracket);

};.RightBracket:

{(stack.Peek() != Lexems.LeftBracket)

{.Add(ConvertToString(stack.Pop()));

}.Pop();

};.Minus:.Plus:

{= newLexems();(stack.Count> 0)= stack.Peek();(lex == Lexems.Plus

|| lex == Lexems.Minus

|| lex == Lexems.Multiplication

|| lex == Lexems.Division)

{.Add(ConvertToString(stack.Pop()));(stack.Count> 0)= stack.Peek();;

}.Push(lexem);

};.Multiplication:.Division:

{= newLexems();(stack.Count> 0)= stack.Peek();(lex == Lexems.Multiplication

|| lex == Lexems.Division)

{.Add(ConvertToString(stack.Pop()));(stack.Count> 0)= stack.Peek();;

}.Push(lexem);

};.Determine:

{.Push(lexem);

};

}

}

Далее создаем различные методы, для синтаксического анализа отдельных частей исходного кода: Блок объявления переменных, блок непосредственно выполнения каких либо операция, блок вывода на печать, блок цикла UNTIL.

publicstaticvoidCompille()

{.Initialize();.DeclairDataSegment();.Initialize();.Initialize();();.DeclairVariables();.DeclairSegmentOfStackAndCode();(Lexems.Semi);(LexicalAnalyzer.CurrentLexem == Lexems.Begin).ParseNextLexem();();(Lexems.End);.DeclairEndMainProc();.DeclairPrint();.DeclairCodeEnd();(Errors.ErrorsCount == 0).Error("Compille success");

}()

{(Lexems.Until);.AddLabel();= CodeGenerator.GetCurrentLabel();.AddLabel();

stringlowerLabel = CodeGenerator.GetCurrentLabel();.AddInstruction(upperLabel + ":");();(Lexems.Do);();(Lexems.EndUntil);.AddInstruction("jmp " + upperLabel);.AddInstruction(lowerLabel + ":");

}()

{(Lexems.None);(Lexems.Int);(LexicalAnalyzer.CurrentLexem != Lexems.Name)

Errors.Error("Не является идентификатором");

else

{.AddIdentificator(LexicalAnalyzer.CurrentName, tCat.Var);.ParseNextLexem();

}(LexicalAnalyzer.CurrentLexem == Lexems.Comma)

{.ParseNextLexem();(LexicalAnalyzer.CurrentLexem != Lexems.Name).Error("Не является идентификатором");

else

{.AddIdentificator(LexicalAnalyzer.CurrentName, tCat.Var);.ParseNextLexem();

}

}

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

LITconst - поместитьконстантуввершинустека.

LOAD n - поместить переменную, размещенную по адресу n в вершину

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

равенства двух верхних элементов стека.k - переход к команде, расположенной по адресу k, если число в вершине стека меньше следующего за ним числа стека.k - переход к команде, расположенной по адресу k, если число в вершине стека меньше или равно следующему за ним числу стека.k - переход к команде, расположенной по адресу k, если число в вершине стека больше следующего за ним числа стека.k - переход к команде, расположенной по адресу k, если число в вершине стека больше или равно следующему за ним числу стека.k - переход к команде, расположенной по адресу k в случае неравенства двух верхних элементов стека.- содержимое регистра адреса данных помещается в вершину стека.- содержимое вершины стека помещается в регистр адреса данных.- сложение двух верхних элементов стека, результат помещается в вершину стека.- умножение двух верхних элементов стека, результат помещается в вершину стека.- вычитание элемента в вершине стека из следующего за ним элемента стека, результат помещается в вершину стека.- деление на элемент в вершине стека следующего за ним элемента стека, результат помещается в вершину стека.- логическое "И" (логическое умножение) двух верхних элементов стека, результат помещается в вершину стека.- логическое "ИЛИ" (логическое сложение) двух верхних элементов стека, результат помещается в вершину стека.- деление на элемент в вершине стека следующего за ним- сложение по модулю 2 двух верхних элементов стека, результат помещается в вершину стека. NOT - знаковая инверсия элемента в вершине стека- поразрядная логическая инверсия элемента в вершине стека. NOP - пустая операция .

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

///<summary>

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

///</summary>

{MAX_NUMBER_STRINGS = 1000;[] code = newstring[MAX_NUMBER_STRINGS];= 0;= 0;

///<summary>

///Добавитьинструкцию

///</summary>

///<param name="instraction"></param>(stringinstraction)

{[codePointer++] = instraction;

}

///<summary>

///Добавитьметку

///</summary>()

{++;

}

///<summary>

///Вернутьтекущуюметку

///</summary>

///<returns></returns>()

{"label" + countLabels.ToString();

}

///<summary>

///Описатьсегментданных

///</summary>()

{("data segment para public data");

}

///<summary>

/// Описать сегмент стэка и кода

///</summary>()

{("PRINT_BUF DB ' ' DUP(10)");("BUFEND DB '$'");("data ends");("stk segment stack");("db 256 dup (?)");("stk ends");("code segment para public code");("main proc");("assume cs:code,ds:data,ss:stk");("movax,data");("movds,ax");

}

///<summary>

/// Описать конец главной процедуры

///</summary>

publicstaticvoidDeclairEndMainProc()

{("mov ax,4c00h");("int 21h");("main endp");

}

///<summary>

/// Описать коней сегмента кода

///</summary>

publicstaticvoidDeclairCodeEnd()

{("code ends");("end main");

}

///<summary>

///Описатьпеременные

///</summary>()

{<Identificator> node = NameTable.GetIdentificators.First;(node != null)

{(SyntaxAnalyzer.Type == tType.Int)(node.Value.name + " dw 1");(SyntaxAnalyzer.Type == tType.LInt)(node.Value.name + " dl 1");

node = node.Next;

}

}

///<summary>

///Опичать процедуру вывода на печать

///</summary>()

{("PRINT PROC NEAR");("MOV CX, 10");("MOV DI, BUFEND - PRINT_BUF");("PRINT_LOOP:");("MOV DX, 0");("DIV CX");("ADD DL, '0'");("MOV [PRINT_BUF + DI - 1], DL");("DEC DI");("CMP AL, 0");("JNE PRINT_LOOP");("LEA DX, PRINT_BUF");("ADD DX, DI");("MOV AH, 09H");("INT 21H");("RET");

AddInstruction("PRINT ENDP");

}

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

Таблица

ОперацияИнструкция ассемблера+add-sub*mul/div

Таким образом, код для выражения a + b будет выглядеть следующим образом:

mov ax, ab, bx

Результат этой последовательности команд будет сохранен в регистре ax. Но в ситуации со сложными выражениями необходимо где-то сохранять промежуточные результаты. Для этих целей мы будем использовать ассемблерный стек: инструкция push - помещение значения регистра на верхушку стека, pop - извлечение из стека в регистр. После каждой атомарной операции мы будем сохранять результат в стек, чтобы не потерять его.

3.Тестирование приложения

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

Пример 1:,s,r;=c+b; a;

End

Результат выполнения программы:

Таблица

Пример 2:a,s,r;=5;=9;=0;=s+r;=((a*4)/2)ggg*r+10;Результат:

Таблица

Заключение

В данной курсовой работе была рассмотрена разработка транслятора, в среде VisualStudio 2008, на языке C#.

Поставленная цель была достигнута путём решения следующих задач:

·Построен лексический анализатор с отлавливанием ошибок на данном этапе трансляции.

·Построен синтаксический анализатор с отлавливанием ошибок на данном этапе трансляции.

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

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

·

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

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