Geum.ru

России Бориса Николаевича Ельцина Кафедра "Информационные технологии и автоматизация проектирования" курсовая

Вид материалаКурсовая

Содержание


Operation = 1
Подобный материал:
  1   2   3

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

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

ГОУ ВПО «Уральский государственный технический университет – УПИ

Имени первого президента России Бориса Николаевича Ельцина»

Кафедра “Информационные технологии и автоматизация проектирования”


Курсовая работа

По предмету “Теория языков и методы трансляции”


Руководитель: Копорушкин П.А.

Группа: М-45072

Студент: Рудаковский К.И.


Екатеринбург

2008

Задание:

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


Создание программы для курсовой работы было разбито на несколько этапов.

  1. На первом этапе нам надо было написать программу, которая бы с помощью конечного автомата проверяла правильность введенной цепочки. Автомат задавался матрицей смежности, которая загружалась в программу, при этом происходил анализ по поиску повторяющихся и недопустимых состояний.
  2. На втором этапе надо было составить автомат для анализа выражения, состоящего из чисел и знаков + , - , * , /, . Реализовать Математический блок, который бы считал выражение без приоритета операций.
  3. Реализовать программу на основе конечного автомата, которая бы разбивала исходный текст на лексемы.
  4. Реализовать МП-распознаватель, который исходя из заданной грамматики проверял бы последовательность лексем.
  5. Реализовать МП-транслятор, который в процессе распознавания, выполняло бы определенные действия.

На первом этапе был реализован конечный автомат.

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

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

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

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


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

Матрица смежности для такого конечного автомата выглядит как:
с
,
+
-
*
/


0
1
-1
-1
-1
-1
-1
-1

1
1
2
0
0
0
0
0

2
3
-1
-1
-1
-1
-1
-1

3
3
-1
0
0
0
0
0

Где с – означает множество чисел {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Запятая отделяет целую часть от дробной. 0 состояние означает разрешает ввод только числа, далее мы переходим в 1 состояние, в котором допускается ввод следующей части числа, в этом случае м будем оставаться в этом состоянии, до тех пор пока не встретиться символ операции, в этом случае мы закончим считывании числа, и перейдем в состояние 0. Если в 1 состоянии мы встречаем , то переходим в состояние 2, в котором мы должны ввести число, тогда перейдем в состояние 3, где будем считывать дробную часть до тех пор пока не встретим символ операции.

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

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

Те для выражения a + b * c составлялось бинарное дерево вида:









c



b

a

Берется операция стоящая в вершины, и выполняется к значениям стоящий в ветках.

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


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


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

При этом наш конечный автомат проверяет исходный текст на наличие недопустимых символов алфавита. Формируется поток лексем, последовательность которых никак не проверяется.


На четвертом этапе нам необходимо было реализовать автомат с магазинной памятью.


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

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

Грамматика для нашего автомата имеет вид:

Правило: Множество выбора:

P -> D k

P -> I4 v

D ->k I1 k

I1 ->I I2 v

I2 ->, I1 ,

I2 -> έ ; =

I4 -> I3 v

I ->v I3 v

I3 -> = E =

I3 -> έ ,;

E ->T X +-vc(

X ->+ T X +

X -> - T X -

X -> έ ,;)

T -> F Y +-vc(

Y -> * F Y *

Y -> / F Y /

Y -> S

Y -> έ +-),;

S -> S F

S -> έ

F -> + F +

F -> - F -

F -> v v

F -> c c

F ->( E ) (

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

Грамматика вместе со множеством выбора задается в программе.


На пятом этапе нам необходимо было реализовать мп транслятор.


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

Список управляющий символов:
  • Declare - объявить
  • Initialize - инициализировать
  • + - сложить
  • ++ - унарный +
  • - вычесть
  • -- унарный минус
  • * - умножить
  • / - поделить
  • - возвести в степень

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

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

Например когда мы извлекаем из магазина + , то из стека констант выталкиваются два значения, складываются и помещаются обратно: Constants.Push(Constants.Pop() + Constants.Pop()). Операции * выполняются аналогично.

Для операций -, и /, сначала извлекается верхний символ стека, заноситься во временную переменную, далее выталкивается следующая константа, из которого вычитается , делится или возводиться в степень временная константа: tmpConstant = Constants.Pop(); Constants.Push(Constants.Pop() / tmpConstant);

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

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

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

Те если к integer мы прибавим float, то тип возвращаемого значения будет float. Если объявленная переменная имеет тип integer, то при присвоении в нее переменной/числа типа float, оно будет динамически приведено к integer;

События на которые реагирует программа:

Разбор текста на лексемы и запуска мп распознававателя по лексемам.

private void button1_Click(object sender, EventArgs e)

{

itsDFS.Reset();

listView1.Items.Clear();

listView2.Items.Clear();

try

{

for (int i = 0; i < richTextBox1.Text.Length; ++i)

{

itsDFS.setNextSymbol(richTextBox1.Text[i]);

}

}

catch (IncorrectSymbolExeption) { MessageBox.Show("Lexems Parser fail"); }

try

{

MPTranslator.Reset(itsDFS.TEMP);

MPTranslator.Go();

}

catch (ArgumentOutOfRangeException ex) { MessageBox.Show("Something goes wrong"); }

catch (Exception ex) { MessageBox.Show(ex.Message); }

for (int i = 0; i < itsDFS.TEMP.Count; ++i)

listView1.Items.Add(itsDFS.TEMP[i].ToString());

for (int i = 0; i < MPTranslator.Variable.Count; ++i)

{

if (MPTranslator.InitializeTable.ContainsKey(MPTranslator.Variable[i]))

{

listView2.Items.Add(MPTranslator.Variable[i] + ": " + MPTranslator.InitializeTable[MPTranslator.Variable[i]].ToString());

}

else listView2.Items.Add(MPTranslator.Variable[i] + ": null");

}

}

Выход:

private void exitToolStripMenuItem_Click(object sender, EventArgs e)

{

Application.Exit();

}


private void openToolStripMenuItem_Click(object sender, EventArgs e)

{

if (richTextBox1.Text.Length != 0)

richTextBox1.Text = "";

button1.Enabled = false;

OpenFileDialog open = new OpenFileDialog();

open.Filter = "Text files (*.txt)|*.txt";

open.ShowDialog();

if (open.FileName == "")

{

MessageBox.Show("File not selected");

}

else

{

try

{

itsDFS = new pseudoKA(open.FileName);

MPTranslator = new MP();

}

catch (IOException)

{

MessageBox.Show("Incorrect input file");

return;

}

button1.Enabled = true;

}

}

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

private void saveToolStripMenuItem_Click(object sender, EventArgs e)

{

if (itsDFS == null)

{

MessageBox.Show("FM is not loaded !");

return;

}

SaveFileDialog save = new SaveFileDialog();

save.Filter = "Text files (*.txt)|*.txt";

save.ShowDialog();

if (save.FileName == "")

{

MessageBox.Show("File for save not selected !");

return;

}

if (!itsDFS.Save(save.FileName)) MessageBox.Show("File not saved");

}

Класс автомат с магазинной памятью:

class MP

{

private Stack Magazine;

private Stack Constants;

private List Variables;

private List VariablesType;

private Dictionary InitializeVariables;

private string CurrentVariable;

private MyType CurrentValue;

private string CurrentType;


private List ListOfLexems;

private int CurrentLexeme;

public MP()

{

CurrentLexeme = 0;

CurrentValue = new MyType(0f);

Constants = new Stack();

Variables = new List();

VariablesType = new List();

InitializeVariables = new Dictionary();

Magazine = new Stack();

Magazine.Push("P");

}

public void Reset(List ListOfLexems)

{

this.ListOfLexems = ListOfLexems;

CurrentLexeme = 0;

Magazine.Clear();

Magazine.Push("END");

Magazine.Push("P");

VariablesType.Clear();

Constants.Clear();

Variables.Clear();

InitializeVariables.Clear();

}

public void Go()

{

MyType tmpConstant;

while(true)

{

if ((Magazine.Count == 0) && (CurrentLexeme == ListOfLexems.Count)) break;

switch (Magazine.Pop())

{

case "END":

if ((ListOfLexems[CurrentLexeme].Symbol == ';')&

(CurrentLexeme != ListOfLexems.Count - 1))

{

Magazine.Push("END");

Magazine.Push("P");

CurrentLexeme++;

break;

}

if ((ListOfLexems[CurrentLexeme].Symbol == ';') &

(CurrentLexeme == ListOfLexems.Count - 1))

{

CurrentLexeme++;

break;

}

throw new Exception();

break;

//****************

case "P":

if (ListOfLexems[CurrentLexeme].Symbol == 'k')

{

CurrentType = ListOfLexems[CurrentLexeme].ToString();

Magazine.Push("D");

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == 'v')

{


Magazine.Push("I4");

CurrentVariable = ListOfLexems[CurrentLexeme].ToString();

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() +" :type or variable expected");

break;

//****************

case "I4":

if (ListOfLexems[CurrentLexeme].Symbol == 'v')

{

Magazine.Push("I3");

CurrentLexeme++;

break;

}

throw new Exception();

break;

//****************

case "D":

if (ListOfLexems[CurrentLexeme].Symbol == 'k')

{

Magazine.Push("I1");

CurrentLexeme++;

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :type expected");

break;

//***************

case "I1":

if (ListOfLexems[CurrentLexeme].Symbol == 'v')

{

Magazine.Push("I2");

Magazine.Push("I");

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :type expected");

break;

//***************

case "I2":

if (ListOfLexems[CurrentLexeme].Symbol == ',')

{

Magazine.Push("I1");

CurrentLexeme++;

break;

}

if ((ListOfLexems[CurrentLexeme].Symbol == ';') |

(ListOfLexems[CurrentLexeme].Symbol == '='))

{

break;

}

throw new Exception();

break;

//***************

case "I":

if (ListOfLexems[CurrentLexeme].Symbol == 'v')

{

Magazine.Push("I3");

Magazine.Push("Declare");

CurrentVariable = ListOfLexems[CurrentLexeme].ToString();

CurrentLexeme++;

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == 'c')

{

Magazine.Push("E");

CurrentLexeme++;

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :constant or variable expected");

break;

//***************

case "I3":

if (ListOfLexems[CurrentLexeme].Symbol == '=')

{

Magazine.Push("Initialize");

Magazine.Push("E");

CurrentLexeme++;

break;

}

if ((ListOfLexems[CurrentLexeme].Symbol == ';') |

(ListOfLexems[CurrentLexeme].Symbol == ','))

{

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " : = {| ; | ,} expected");

break;

//***************

case "E":

if ((ListOfLexems[CurrentLexeme].Symbol == '+')|

(ListOfLexems[CurrentLexeme].Symbol == '-')|

(ListOfLexems[CurrentLexeme].Symbol == 'c')|

(ListOfLexems[CurrentLexeme].Symbol == 'v')|

(ListOfLexems[CurrentLexeme].Symbol == '(')|

(ListOfLexems[CurrentLexeme].Symbol == ''))

{

Magazine.Push("X");

Magazine.Push("T");

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :{+|-|c|v|(|} expected");

break;

//***************

case "X":

if ((ListOfLexems[CurrentLexeme].Symbol == ';')|

(ListOfLexems[CurrentLexeme].Symbol == ',')|

(ListOfLexems[CurrentLexeme].Symbol == ')')|

(ListOfLexems[CurrentLexeme].Symbol == ''))

{

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == '+')

{

Magazine.Push("X");

Magazine.Push("+");

Magazine.Push("T");

CurrentLexeme++;

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == '-')

{

Magazine.Push("X");

Magazine.Push("-");

Magazine.Push("T");

CurrentLexeme++;

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :{+|-|;|,|)|} expected");

break;

//***************

case "T":

if ((ListOfLexems[CurrentLexeme].Symbol == 'c')|

(ListOfLexems[CurrentLexeme].Symbol == '+')|

(ListOfLexems[CurrentLexeme].Symbol == '-')|

(ListOfLexems[CurrentLexeme].Symbol == 'v')|

(ListOfLexems[CurrentLexeme].Symbol == '(')|

(ListOfLexems[CurrentLexeme].Symbol == ''))

{

Magazine.Push("Y");

Magazine.Push("F");

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :{+|-|c|v|(|} expected");

break;

//***************

case "Y":

if ((ListOfLexems[CurrentLexeme].Symbol == ';')|

(ListOfLexems[CurrentLexeme].Symbol == ',')|

(ListOfLexems[CurrentLexeme].Symbol == '+')|

(ListOfLexems[CurrentLexeme].Symbol == '-'))

{

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == ')')

{

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == '')

{

Magazine.Push("S");

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == '*')

{

Magazine.Push("Y");

Magazine.Push("*");

Magazine.Push("F");

CurrentLexeme++;

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == '/')

{

Magazine.Push("Y");

Magazine.Push("/");

Magazine.Push("F");

CurrentLexeme++;

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :{+|-|/|*|)||;|,} expected");

break;

//***************

case "S":

if (ListOfLexems[CurrentLexeme].Symbol == '')

{

Magazine.Push("S");

Magazine.Push("");

Magazine.Push("F");

CurrentLexeme++;

break;

}

if ((ListOfLexems[CurrentLexeme].Symbol == ';')|

(ListOfLexems[CurrentLexeme].Symbol == ',')|

(ListOfLexems[CurrentLexeme].Symbol == '+')|

(ListOfLexems[CurrentLexeme].Symbol == '-')|

(ListOfLexems[CurrentLexeme].Symbol == ')'))

{

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :{+|-|;|,|)|} expected");

break;

//***************

case "F":

if (ListOfLexems[CurrentLexeme].Symbol == 'c')

{

CurrentValue = ListOfLexems[CurrentLexeme].Number;

Constants.Push(CurrentValue);

CurrentLexeme++;

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == 'v')

{

if (!Variables.Contains(ListOfLexems[CurrentLexeme].ToString())) throw new Exception(ListOfLexems[CurrentLexeme].ToString() + " is not declared");

Constants.Push(new MyType(InitializeVariables[ListOfLexems[CurrentLexeme].ToString()]));

CurrentLexeme++;

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == '+')

{

Magazine.Push("++");

Magazine.Push("F");

CurrentLexeme++;

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == '-')

{

Magazine.Push("--");

Magazine.Push("F");

CurrentLexeme++;

break;

}

if (ListOfLexems[CurrentLexeme].Symbol == '(')

{

Magazine.Push(")");

Magazine.Push("E");

CurrentLexeme++;

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :{ + | - | c | v | ( } expected");

break;

//***************

case ")":

if (ListOfLexems[CurrentLexeme].Symbol == ')')

{

CurrentLexeme++;

break;

}

throw new Exception("Incorrect " + ListOfLexems[CurrentLexeme].ToString() + " :{ ) } expected");

break;

// Rule symbols

//***************

case "Declare":

if (Variables.Contains(CurrentVariable)) throw new Exception("Variable: " + CurrentVariable + " is also declared");

Variables.Add(CurrentVariable);

VariablesType.Add(CurrentType);

break;

//***************

case "Initialize":

tmpConstant = Constants.Pop();

if (!Variables.Contains(CurrentVariable)) throw new Exception("Variable: " + CurrentVariable.ToString() + " is not declared");


if (VariablesType[Variables.IndexOf(CurrentVariable)] == "float") tmpConstant.ToFloat();

else tmpConstant.ToInteger();


if (InitializeVariables.ContainsKey(CurrentVariable))

{

InitializeVariables[CurrentVariable] = tmpConstant;

break;

}

InitializeVariables.Add(CurrentVariable, tmpConstant);

break;

//***************

case "+":

Constants.Push(Constants.Pop() + Constants.Pop());

break;

//***************

case "-":

tmpConstant = Constants.Pop();

Constants.Push(Constants.Pop() - tmpConstant);

break;

//***************

case "++":

break;

//***************

case "--":

tmpConstant = Constants.Pop();

tmpConstant.Inverse();

Constants.Push(tmpConstant);

break;

//***************

case "*":

Constants.Push(Constants.Pop() * Constants.Pop());

break;

//***************

case "/":

tmpConstant = Constants.Pop();

Constants.Push(Constants.Pop() / tmpConstant);

break;

case "":

tmpConstant = Constants.Pop();

Constants.Push(Constants.Pop() tmpConstant);

break;

//***************

default: throw new Exception();

}

}

}

public List Variable

{

get { return Variables; }

}

public Dictionary InitializeTable

{

get { return InitializeVariables; }

}

}

Класс который проходит по тексту и формирует лексемы:

class pseudoKA

{

private int itsCurrentState;

private List itsState;

private List itsSymbols;

private Lexeme itsLexeme;

private int itsOldState;


public pseudoKA(string path)

{

itsState = new List();

itsLexeme = new Lexeme();

ReadAndOptimize tmp = new ReadAndOptimize(path, itsState, itsLexeme);

itsSymbols = new List(tmp.Symbols);

itsCurrentState = 0;

itsOldState = 0;


}


public void Reset()

{

itsCurrentState = 0;

itsOldState = 0;

itsLexeme.ClearLex();

itsLexeme.Reset();

}


public bool Save(string path)

{

try

{

SaveKA save = new SaveKA(path, itsState, itsSymbols);

return true;

}

catch (IOException)

{

return false;

}

}


public void setNextSymbol(char symbol)

{

itsCurrentState = itsState[itsCurrentState].setNextSymbol(symbol);

if (itsCurrentState != itsOldState) itsLexeme.OnStateChange(symbol);

else itsLexeme.setNextSymbol(symbol);

if ((symbol == ';') && (itsState[itsOldState].FiniteState == false)) throw new IncorrectSymbolExeption();

itsOldState = itsCurrentState;

}

public List TEMP

{

get { return itsLexeme.LexemsList; }

}

}

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

class ReadAndOptimize

{

private List itsSymbols;

private List