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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.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>()

{+= 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 в вершину

равенства двух верхних элементов стека.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. Команды для арифметических операций приведены в таблице ниже.

Таблица

Таким образом, код для выражения 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

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

·