close

Вход

Забыли?

вход по аккаунту

?

Курсовая работа по ТФГ Герасимов НВ Мочалов МС гр 4308 2013г

код для вставкиСкачать
Министерство образования и науки Российской Федерации
Государственное образовательное учреждение
Казанский национальный исследовательский технический университет им. А.Н.Туполева
Кафедра автоматизированных систем обработки информации и управления
Курсовая работа
по дисциплине "Теория формальных грамматик"
РУКОВОДИТЕЛЬ: доцент кафедры АСОИУ Д.Г.Хохлов
ИСПОЛНИТЕЛИ: Мочалов М.С. студент группы 4308 Оценка__________ Принял_________
Дата __.__.2013 г. Герасимов Н.В. студент группы 4308 Оценка__________ Принял_________
Дата __.__.2013г. Казань 2013
СПИСОК ИСПОЛНИТЕЛЕЙ
Мочалов М.С. студент группы 4308 -
разделы: 1, 2, 3, 5.1, Приложения: 1, 3, 5,6;
программы: Form1.cs, STAutomat.cs;
Герасимов Н.В. студент группы 4308 -
разделы: 1, 2, 4, 5.2, Приложения: 2, 4,5,7;
программы: Form1.cs, MPAutomat.cs;
ОГЛАВЛЕНИЕ
1. Задание ......................... .............................. .................................3 2. Описание языка..............................................................................3
3. Лексический разбор.......................................... ..............................3
3.1 Построение конечного автомата для лексики..............................4
4. Синтаксический разбор................................................................4
4.1. Автомат с магазинной памятью.............................................5
5 . Разработка программы на С#...........................................................6
5.1. Программа лексического анализатора ......................................6
5.2. Программа синтаксического анализатора ................................7
Приложение 1. Граф переходов...... ............................................................8
Приложение 2 Матрица операторного предшествования..................................9
Приложение 3 Пример работы программы..........................................10
Приложение 4 Тестирование программы............................................11
Приложение 5 Текст формы.................................................................................12
Приложение 6 Текст программы лексического анализатора....................14
Приложение 7 Текст программы синтаксического анализатора.................18
Литература.............................................................................................................22
1. Задание
Составить программу, которая проводит лексический и синтаксический разборы данного языка. Построить автоматы для получившихся регулярных и контекстно-свободных грамматик. Разработать программу грамматического разбора данного языка. Входной язык содержит операторы условия типа if ... then ... else и if ... then, разделенные символом ; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, шестнадцатеричные числа, знак присвоения(:=).
2. Описание языка
Для полного понимания сути задачи приведём несколько примеров различных правильно составленных предложений языка.
1) if x>3A then
x:=2E1
else
x:=3F0;
2) if x<3A then
if x>1A then
x:=2E1;
else
x:=3F0;
3. Лексический разбор
Основная задача лексического разбора - разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Лексика входного языка на метаязыке МБНФ:
знак-сравнения ::= <|>|=
имя ::= буква
имя ::= имя [буква]
буква ::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|
шестнадцатеричное-число ::= шестнадцетеричная-цифра
шестнадцатеричное-число ::= шестнадцатеричное-число [шестнадцетеричная-цифра]
шестнадцетеричная-цифра::=0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F
3.1. Построение конечного автомата для лексики
Конечный автомат - абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Существуют различные способы задания конечного автомата. В нашем случае автомат задан в виде упорядоченной пятерки: , где
* - входной алфавит (конечное множество входных символов), из которого формируются входные цепочки, допускаемые конечным автоматом;
* - множество состояний;
* - начальное состояние ;
* - множество заключительных состояний ;
* - функция переходов;
Конечный автомат начинает работу в состоянии q0, считывая по одному символу входной цепочки. Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов. Читая входную цепочку x и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии q'. Если это состояние является заключительным, то говорят, что автомат допустил цепочку x.
4. Синтаксический разбор
Синтаксический разбор - это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. Опираясь на приведённые в разделе 2 примеры, в которых присутствуют все возможные варианты написания предложений, соответствующих описанию заданного языка, комплексно рассмотрим грамматику языка и составим её формальное описание на мета языке МБНФ :
выражение ::= оператор...
оператор ::= if условие then оператор;| if условие then оператор else оператор;
оператор ::= присвоение
присвоение ::= имя := число
условие ::= число знак_сравнения имя|имя знак_сравнения число
условие ::= имя знак_сравнения имя
4.1. Распознаватель на основе алгоритма "Сдвиг-свертка"
Для построения автомата с магазинной памятью для синтаксического анализатора используем распознаватель на основе алгоритма "Сдвиг - свертка". Данный автомат, представлен "Приложением 2", (подробнее о нем можно прочитать в книге Молчанова А.Ю. "СПО лабораторный практикум") прошёл все теоретические и практические тесты (вручную). На основе данного автомата написана программа синтаксического анализатора.
5. Разработка программы на С#
Коды лексем представлены в табл. 5.
Таблица 5. Коды лексем
:=VDifthen12345else<=>;678910 Служебные слова: if; then; else;
Разделители: '<'; '>'; '='; ':='; ';'
Идентификаторы: 'V'
Константы 'D'
5.1. Программа лексического анализатора
Программу лексического разбора входного предложения должна работать таким образом, чтобы в результате получилась последовательность лексем входного текста. Для этого будем использовать коды лексем (см. табл. 5).
Данная программа просматривает символы входного текста. Если данный символ является либо буквой, либо цифрой, либо пробелом, то мы просматриваем следующий символ без вывода кода лексемы на экран. Иначе, мы определяем, было введено имя или цифра, или какой-либо другой символ. Таким образом, мы сокращаем запись входного предложения и приводим к виду, который легко использовать в дальнейшей обработке.
Текст программы смотрите в "Приложение №6".
Таким образом, результаты обработки примеров, приведённых при описании языка в (раздел 2), будут иметь вид:
Входное предложение
if x>03A then
x:=02E1
else
x:=03F0;
Коды лексем представлены на рис. 5.1.
Рис. 5.1. Результат работы лексического анализатора.
Результатом данной программы является список кодов лексем и их описание . Данный список кодов лексем будет являться входными данными для программы синтаксического анализатора.
5.2. Программа синтаксического анализатора
Программа синтаксического анализатора получает на вход список кодов лексем. В ходе синтаксического анализа исходный список кодов лексем преобразуется в структуру данных - в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки. Опираясь на автомат с магазинной памятью (см. пункт 4.1) напишем программу для синтаксического анализатора. Входными данными будут являться список кодов лексем, полученный после работы лексического анализатора.
Данная программа будет проверять правильность нашего предложения, опираясь на правила грамматики (имя не должно начинаться с цифры и т.п.). Текст программы представлен в Приложении 7.
Результатом данной программы является вкладка, с деревом, в котором представлен обработанный код входной строки.
Приложение 1.
Граф переходов, заданный матрицей инцидентности.
ifthenls;<>=:_A0{}G1*HI1VT1VE1VVVZO1O1O1G1HVDCERVDERCCCCCCCCCCCCCCCCCCC1CCCC1HHHHHHHHHHHHHHHHHHHHHG1ERERERERERERERERERERERGERERERERERERERERERGHHHHHHHHERERERERERHHHHERHHERVVVVVVVVVZHHHHHVVHERVVERDERDERERDERERERZHHHHHDDHERERDERI1VI2VVVVVVZHHHHHVVHERVVERI2VVVVVVVVERERERERERHVVHERVVERT1VVVT2VVVVZHHHHHVVHERVVERT2VVVVT3VVVZHHHHHVVHERVVERT3VVVVVT4VVZHHHHHVVHERVVERT4VVVVVVVVZERERERERHVVHERVVERE1VVVVVVE2VZHHHHHVVHERVVERE2VVVVVVVE3ZHHHHHVVHERVVERE3VVVVE4VVVZHHHHHVVHERVVERE4VVVVVVVVZERERERERHVVHERVVERO1HHHHHHHHERERERERERHHHHRTHHERZI1VT1VE1VVVZERERERERHHHHERHERERERERERERERERERERERERERERERERHERERERERERERER
Приложение 2.
Матрица операторного предшествования
0;ifthenelsea:=<=>Lk; >if = < <<< then>< =< else>< >< > a> >> = >> :=> >>< < > < = > < > > < Ln<< < Приложение 3. Пример работы программы.
Рис.1.
Рис. 2.
Рис. 3.
Приложение 4. Тестирование программы
Тест 1
Входное предложение:
if x=5 then
if x<y then
x:=1
else x:=3;
Результатом работы является дерево разбора, которое представлено на рис.5.
Рис. 5.
Тест 2
Входное предложение:
if then a:=a;
Результатом работы является сообщение:
"ошибка, входная строка не принимается"
Приложение 5
Код формы. Файл Form1.cs
// Интерфейс лексического и синтаксического анализаторов. // Исполнители: Герасимов Н.В., Мочалов М.С.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
/*Входной язык содержит операторы условия типа if...then..else и if...then, разделенные символом; (точка с запятой).
//Операторы условия содержат идентификаторы, знаки сравнения <,>,=, шестнадцатеричные числа, знак присваивания (:=).*/
namespace LexSynParser
{
public partial class Form1 : Form
{
STAutomat StA;
MPAutomat MpA;
string[,] inputstr = new string[100,2];
public Form1()
{
InitializeComponent();
dataGridView1.ColumnCount = 4;
dataGridView1.ColumnHeadersVisible = true;
DataGridViewCellStyle columnHeaderStyle = new DataGridViewCellStyle();
columnHeaderStyle.BackColor = Color.Beige;
columnHeaderStyle.Font = new Font("Verdana", 10, FontStyle.Bold);
dataGridView1.ColumnHeadersDefaultCellStyle = columnHeaderStyle;
dataGridView1.Columns[0].Name = "№ п/п";
dataGridView1.Columns[0].Width = tabControl1.Width/9;
dataGridView1.Columns[1].Name = "Лексема";
dataGridView1.Columns[1].Width = tabControl1.Width / 3;
dataGridView1.Columns[2].Name = "Код лексемы";
dataGridView1.Columns[2].Width = tabControl1.Width / 4;
dataGridView1.Columns[3].Name = "Значение";
dataGridView1.Columns[3].Width = tabControl1.Width - tabControl1.Width / 9 - tabControl1.Width / 3 - tabControl1.Width / 4 - 65; this.Icon = LexSynParser.Properties.Resources.parsing;
StA = new STAutomat();
MpA = new MPAutomat();
}
private void Form1_SizeChanged(object sender, EventArgs e)
{
tabControl1.Width = this.Width - 40;
tabControl1.Height = this.Height - 60;
treeView1.Width = tabControl1.Width - 40;
treeView1.Height = tabControl1.Height - 60;
dataGridView1.Width = tabControl1.Width - 40;
dataGridView1.Height = tabControl1.Height - 60;
btnClearList.Location = new Point(tabControl1.Width - 130, tabControl1.Height - 75);
dataGridView1.Columns[0].Width = tabControl1.Width / 9;
dataGridView1.Columns[1].Width = tabControl1.Width / 3;
dataGridView1.Columns[2].Width = tabControl1.Width / 4;
dataGridView1.Columns[3].Width = tabControl1.Width - tabControl1.Width / 9 - tabControl1.Width / 3 - tabControl1.Width / 4 - 85;
}
private void btnGetTable_Click(object sender, EventArgs e)
{
//try
//{
lexanaliz();
syntaxanaliz();
//}
//catch { }
}
private void lexanaliz()
{
dataGridView1.Rows.Clear();
StA.count = 0;
int a=-1;
StA.state = "H";
StA.leksema = "";
for (int i = 0; i < listBox1.Items.Count; i++)
{
for (int j = 0; j < listBox1.Items[i].ToString().Length; j++)
{
a = StA.ReadChar(listBox1.Items[i].ToString()[j]);
if (a == 2)
{
MessageBox.Show("Ошибка во входной строке");
return;
}
else
if (a == 1)
j--;
}
StA.ReadChar(' ');
}
for (int i = 0; i < StA.datagrid.GetLength(0); i++)
{
if (StA.datagrid[i, 0] != null)
{
dataGridView1.Rows.Add(StA.datagrid[i, 0], StA.datagrid[i, 1], StA.datagrid[i, 2], StA.datagrid[i, 3]);
MpA.inputstr[i] = Convert.ToInt32(StA.datagrid[i, 2]);
if (StA.datagrid[i, 2] == "3" || StA.datagrid[i, 2] == "2")
{
MpA.ukazlex++;
MpA.znachlex[MpA.ukazlex] = StA.datagrid[i, 1];
}
}
else
break;
}
StA = new STAutomat();
}
private void syntaxanaliz()
{
treeView1.Nodes.Clear();
MpA.Parser();
MpA.ukaz--;
treeView1.Nodes.Add(MpA.settn(MpA.iprav[MpA.ukaz], "E"));
for (int i = 0; i < MpA.iprav.Length; i++)
{
MpA.iprav[i] = 0;
MpA.ukaz = 0;
}
MpA = new MPAutomat();
}
private void btnClearList_Click(object sender, EventArgs e)
{
listBox1.Items.Clear();
}
private void btnAddString_Click(object sender, EventArgs e)
{
listBox1.Items.Add(textBox1.Text);
}
private void btnOpen_Click(object sender, EventArgs e)
{
try
{
string str;
listBox1.Items.Clear();
openFileDialog1.ShowDialog();
System.IO.StreamReader file = new System.IO.StreamReader(@openFileDialog1.FileName);
while ((str = file.ReadLine()) != null)
{
listBox1.Items.Add(str);
}
file.Close();
}
catch { }
}
}
}
Приложение 6
Лексический анализатора. Файл STAutomat.cs
// Исполнитель: Мочалов М.С.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LexSynParser
{
class STAutomat
{
public int count;
public string state; //состояние автомата
public string leksema; //добавляемая лексема в таблицу лексем
public string[,] statesA; // Граф переходов состояния автомата
public string[] statesP; //Состояния автомата, при которых происходит запись
// лексемы в таблицу лексем
public string[,] oplexp; // Описание записываемых лексем
public string[,] datagrid;
public int datagr;
public STAutomat()
{
datagrid = new string[100,4];
datagr = 0;
count = 0;
state = "H";
//Граф переходов автомата
statesA = new string[21, 22] {
// A - символы A - F
// G - символы G - Z
// 0 - символ 0
// 1 - символы от 1 до 9
// * - все остальные символы ASCII кода
//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
{"0", "i", "f", "t", "h", "e", "n", "l", "s", ";", "<", ">", "=", ":", " ", "A", "0", "{", "}", "G", "1", "*"},
{"H", "I1", "V", "T1", "V", "E1", "V", "V", "V", "Z", "O1", "O1", "O1", "G1", "H", "V", "D", "C", "ER","V", "D", "ER"}, //Начальное состояние
{"C", "C", "C", "C", "C", "C", "C", "C", "C", "C", "C", "C", "C", "C", "C", "C", "C", "C", "C1","C", "C", "C"},//Комментарии
{"C1", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H"},//Комментарии
{"G1", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "G", "ER", "ER", "ER", "ER","ER","ER","ER","ER", "ER"},
{"G", "H", "H", "H", "H", "H", "H", "H", "H", "ER", "ER", "ER", "ER", "ER", "H", "H", "H", "H", "ER","H", "H", "ER"},//Знак присваивания
{"V", "V", "V", "V", "V", "V", "V", "V", "V", "Z", "H", "H", "H", "H", "H", "V", "V", "H", "ER","V", "V", "ER"},//Переменная (идентификатор)
{"D", "ER", "D", "ER", "ER", "D", "ER", "ER", "ER", "Z", "H", "H", "H", "H", "H", "D", "D", "H", "ER","ER","D", "ER"},//Константа
{"I1", "V", "I2", "V", "V", "V", "V", "V", "V", "Z", "H", "H", "H", "H", "H", "V", "V", "H", "ER","V", "V", "ER"}, //IF
{"I2", "V", "V", "V", "V", "V", "V", "V", "V", "ER", "ER", "ER", "ER", "ER", "H", "V", "V", "H", "ER","V", "V", "ER"},//IF
{"T1", "V", "V", "V", "T2", "V", "V", "V", "V", "Z", "H", "H", "H", "H", "H", "V", "V", "H", "ER","V", "V", "ER"},
{"T2", "V", "V", "V", "V", "T3", "V", "V", "V", "Z", "H", "H", "H", "H", "H", "V", "V", "H", "ER","V", "V", "ER"},
{"T3", "V", "V", "V", "V", "V", "T4", "V", "V", "Z", "H", "H", "H", "H", "H", "V", "V", "H", "ER","V", "V", "ER"},
{"T4", "V", "V", "V", "V", "V", "V", "V", "V", "Z", "ER", "ER", "ER", "ER", "H", "V", "V", "H", "ER","V", "V", "ER"},
{"E1", "V", "V", "V", "V", "V", "V", "E2", "V", "Z", "H", "H", "H", "H", "H", "V", "V", "H", "ER","V", "V", "ER"},
{"E2", "V", "V", "V", "V", "V", "V", "V", "E3", "Z", "H", "H", "H", "H", "H", "V", "V", "H", "ER","V", "V", "ER"},
{"E3", "V", "V", "V", "V", "E4", "V", "V", "V", "Z", "H", "H", "H", "H", "H", "V", "V", "H", "ER","V", "V", "ER"},
{"E4", "V", "V", "V", "V", "V", "V", "V", "V", "Z", "ER", "ER", "ER", "ER", "H", "V", "V", "H", "ER","V", "V", "ER"},
{"O1", "H", "H", "H", "H", "H", "H", "H", "H", "ER", "ER", "ER", "ER", "ER", "H", "H", "H", "H", "ER","H", "H", "ER"},//операция с 1 знаком
{"Z", "I1", "V", "T1", "V", "E1", "V", "V", "V", "Z", "ER", "ER", "ER", "ER", "H", "H", "H", "H", "ER","H", "ER", "ER"},//Точка с запятой
{"ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "ER", "H", "ER", "ER","ER","ER","ER","ER", "ER"}};//ошибка
statesP = new string[2] { "H", "Z" };
oplexp = new string[10, 2] {
/**/{"C1","Комментарии"},
/*1*/{"G","Знак присваивания"}, //
/*2*/{"V","Идентификатор"},
/*3*/{"D","Число(Константа)"},
/*4*/{"I2","Служебное слово"},
/*5*/{"T4","Служебное слово"},
/*6*/{"E4","Служебное слово"},
/*7*/{"O1","Операция"},
/*8*/{"Z","Точка с запятой"},
/*9*/{"ER","Нераспознанная лексема"}};
}
//Считываем символы из ListBox'a
public int ReadChar(char c)
{
int endtoken = 0;
endtoken = GoToState(c);
if (endtoken == 1) { return 1;}
if (endtoken == 2) {return 2;}
return 0;// если 1, то ошибка, если 0, то ошибки нет
}
//Функция перехода из одного состояния в другое
public int GoToState(char c)
{
int indi = 0, indj = 0; // индексы в матрице переходов автомата
int endtoken = 0;
for (int j = 1; j < 22; j++)
{
if (c == statesA[0, j][0])
{
indj = j;
break;
}
if (j == 15 || j == 19 || j == 16)
{
if (c >= 'A' && c <= 'F' || c >= 'a' && c <= 'f') { indj = 15; break; }
if (c >= 'G' && c <= 'Z' || c >= 'g' && c <= 'z') { indj = 19; break; }
if (c >= '0' && c <= '9') { indj = 16; break; }
}
if (j == 21) { indj = 21; }
}
for (int i = 1; i < 21; i++)
{
if (state == statesA[i, 0])
{
indi = i;
break;
}
}
string prevstate = state; // предыдущее состояние автомата
state = statesA[indi, indj];
if (statesA[indi, indj] == "ER")
{
endtoken = 2;
}
else
{
if (state != prevstate)
{
for (int i = 0; i < statesP.Length; i++)//Условия добавления лексемы в таблицу лексем
{
if (state == statesP[i])
{
AddLex(leksema, prevstate);
leksema = System.String.Empty;
endtoken = 1;
break;
}
}
}
}
if (endtoken == 0 && c != ' ') { leksema += c; }
return endtoken;
}
//Добавление лексемы в таблицу лексем
public void AddLex(string lex, string stateP)
{
int pozition = 0;
bool flag = false;
count++;
for (int i = 0; i < 10; i++)
{
if (stateP == oplexp[i, 0])
{
pozition = i;
flag = true;
break;
}
}
int a = pozition;
switch (lex)
{
case "<": a = 7;
break;
case "=": a = 8;
break;
case ">": a = 9;
break;
case ";": a = 10;
break;
default: break;
}
if (stateP != "C1" && stateP != "ER" && flag)// исключаем комментарии
{
datagrid[datagr, 0] = count.ToString();
datagrid[datagr, 1] = lex;
datagrid[datagr, 2] = a.ToString();
datagrid[datagr, 3] = oplexp[pozition, 1];
datagr++;
}
else
{ count--; }
}
}
}
Приложение 7
Синтаксический анализатор. Файл MPAutomat.cs
// Исполнитель: Герасимов Н.В.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace LexSynParser
{
class MPAutomat
{
public int[,] matr; //Матрица операторного предшествования
public int[,] stekAut; //Стек автомата
public int[,] prav; //правила грамматики
public string[,] prav1; //разобранные правила грамматики для treeview
public int ind; //указатель стека
public int[] inputstr;
public int[] iprav; // Массив правил
public int ukaz = 0; // Указатель в массиве правил
public string[] znachlex; //значения свертнутых лексем
public int ukazlex; //указатель в массиве значений лексем
public MPAutomat()
{
znachlex = new string[100];
ukazlex = -1;
ind = 0; // В стеке есть 1 значение iprav = new int[50];
//матрица операторного предшествования
matr = new int[11, 11] {
//0 1 2 3 4 5 6 7 8 9 10
//0*/{"0", ";", "if", "then", "else", "a", ":=", <, =, >, "Lk"},
/*0*/{0, 10, 4, 5, 6, 2, 1, 7, 8, 9, 11},
/*1*/{10, 20, 20, 20, 20, 20, 20, 20, 20, 20, 23},
/*2*/{4, 20, 20, 22, 20, 21, 20, 21, 21, 21, 20},
/*3*/{5, 23, 21, 20, 22, 21, 20, 20, 20, 20, 20},
/*4*/{6, 23, 21, 20, 23, 21, 20, 20, 20, 20, 20},
/*5*/{2, 23, 20, 23, 23, 20, 22, 23, 23, 23, 20},
/*6*/{1, 23, 20, 23, 23, 21, 20, 20, 20, 20, 20},
/*7*/{7, 20, 20, 23, 20, 21, 20, 20, 20, 20, 20},
/*8*/{8, 20, 20, 23, 20, 21, 20, 20, 20, 20, 20},
/*9*/{9, 20, 20, 23, 20, 21, 20, 20, 20, 20, 20},
/*10*/{12, 21, 21, 20, 20, 21, 20, 20, 20, 20, 20}};
stekAut = new int[100, 2];
stekAut[0, 0] = 12;
stekAut[0, 1] = 21;
prav = new int[8,6] {
{10,13,0,0,0,0}, // 0
{13,6,13,5,13,4}, // 1
{13,5,13,4,0,0}, // 2
{13,1,2,0,0,0}, // 3
{13,7,13,0,0,0}, // 4
{13,8,13,0,0,0}, // 5
{13,9,13,0,0,0}, // 6
{2,0,0,0,0,0}, // 7
};
prav1 = new string[8, 6] {
{"E",";","","","","",},
{"if", "E", "then", "E", "else", "E"},
{"if", "E", "then", "E", "", ""},
{"a", ":=", "E", "","",""},
{"E", "<", "E", "", "", ""},
{"E", "=", "E", "", "", ""},
{"E", ">", "E", "", "", ""},
{"a","","","","",""}};
inputstr = new int[100];
}
// Добавление лексемы в стек
private void push(int lex, int c) // строка с лексемой и строка с символом(<,>,=)
{
if (ind < stekAut.GetLength(0))
{
ind++;
stekAut[ind, 0] = lex;
stekAut[ind, 1] = c;
}
else
MessageBox.Show("Стек переполнен");
}
//выталкивание лексемы из стека
private int[] pop()
{
int[] sstr = new int[2];
if (ind >= 0)
{
sstr[0] = stekAut[ind, 0];
sstr[1] = stekAut[ind, 1];
ind--;
}
else
MessageBox.Show("Стек пуст");
return sstr;
}
//Преобразование входных лексем(замена индентификатров и констант на а)
private int[] zamena(int[] mstr)
{
for (int i = 0; i < mstr.GetLength(0); i++)
{
if (mstr[i] == 3)
{
mstr[i] = 2;
}
if (mstr[i] == 0)
{
mstr[i] = 11;
break;
}
}
return mstr;
}
// Свертка символов в стеке
public int svertka()
{
int[] rstr = new int[2]; //Вытолкнутая лексема из стека
int[] rezstr = new int[6]; // Строка, которую необходимо свернуть
int i = 5;
int numprav;
numprav = -1;
do
{
rstr = pop();
rezstr[i] = rstr[0];
i--;
}
while (rstr[1] == 22 || rstr[1] == 23 || rstr[0] == 13);
rstr = pop();
if (rstr[0] == 13)
rezstr[i] = rstr[0];
else
push(rstr[0], rstr[1]);
int flag = 0;
for (int j = 0; j < 8; j++) //Ищем правила для светрки
{
int n = 5;
for (int k = 0; k < 6; k++)
{
if (rezstr[n] != prav[j, k])
{
flag = 0;
break;
}
else
flag = 1;
n--;
}
if (flag == 1)
{
numprav = j;
push(13, 20);
break;
}
}
return numprav;
}
//Функция синтаксического анализатора
public void Parser()
{
int[] mstr;
int astr, sstr;
int poz1, poz2; // индексы матрицы операторного предшествования
int index = 0; // индекс во входной строке
poz1 = 0;
poz2 = 0;
ind = 0;
mstr = zamena(inputstr);
astr = mstr[index];
sstr = stekAut[ind, 0];
while (sstr != 12 || astr != 11)
{
for (int i = 0; i < matr.GetLength(0); i++)// число строк/столбцов
{
if (matr[i, 0] == sstr)
{
poz1 = i;
}
if (matr[0, i] == astr)
{
poz2 = i;
}
}
if (matr[poz1, poz2] == 20)
{
MessageBox.Show("Ошибка, входная строка не принимается");
break;
}
else
{
if (matr[poz1, poz2] == 21 || matr[poz1, poz2] == 22)
{
push(astr, matr[poz1, poz2]);
}
else
{
int a;
a = svertka();
if (a != -1)
{
iprav[ukaz] = a;
ukaz++;
index--;
}
else
{
MessageBox.Show("Ошибка, входная строка не принимается");
break;
}
}
}
index++;
astr = mstr[index];
for (int i = ind; i > -1; i--)
if (stekAut[i, 0] != 13)
{
sstr = stekAut[i, 0];
break;
}
}
}
public TreeNode settn(int num, string strname)
{
TreeNode tr = new TreeNode(strname);
ukaz--;
for (int i = 0; i < prav1.GetLength(1) && prav1[num, i] != ""; i++)
if (prav1[num, i] == "E")
tr.Nodes.Add(new TreeNode("E"));
else
{
if (prav1[num, i] == "a")
{
tr.Nodes.Add(new TreeNode(znachlex[ukazlex]));
ukazlex--;
}
else
tr.Nodes.Add(new TreeNode(prav1[num, i]));
}
for (int j = tr.Nodes.Count - 1; j >= 0; j--)
if (tr.Nodes[j].Text == "E")
tr.Nodes[j] = settn(iprav[ukaz], "E");
return tr;
}
}
}
СПИСОК ЛИТЕРАТУРЫ
1. Липский В.Л. . Комбинаторика для программистов. М.:Мир,1988.
2. Свердлов С.З. "Языки программирования и методы трансляции", М.:Мир, 2007 г
3. Хохлов Д.Г. Системное программное обеспечение: Учебное пособие. - Казань, Мастер Лайн, 2009, 178 с.
4. Хохлов Д.Г., Захарова З.Х. Введение в системное программирование: Учебное пособие. - Казань, Изд-во Казан. технич. ун-та, 2005, 163 с.
5. Хохлов Д.Г. Программирование на языке высокого уровня. Часть 2: Методы программирования: Учебник. - Казань: Мастер Лайн, 2009. - 270 с. (разделы 7 - 9, приложения).
6. Хохлов Д.Г. Основы технологии модульного программирования. Учебное пособие.- Казань: Изд-во Казан. технич. ун-та, 2005. - 63 с.
7. Хохлов Д.Г. Лабораторный практикум по методам трансляции: Методические указания.- Казань: Изд-во Казанского техн. ун-та, 2008. - 71 с. 8. Хохлов Д.Г., Захарова З.Х. Операционные системы: Учебное пособие. - Казань: : Мастер Лайн, 2010. - 154 с. (разделы 1, 5, приложения). 9. Хохлов Д.Г. Методические указания к курсовой работе по программированию на языке высокого уровня для направления Т28 "Информатика и вычислительная техника". Казань: Изд-во Казан. гос. тех. ун-та,2003
10. Хохлов Д.Г. Структуры данных и комбинаторные алгоритмы: Учебное пособие. Казань: Изд-во Казан. гос. тех. ун-та,2005.
7
Документ
Категория
Рефераты
Просмотров
60
Размер файла
136 Кб
Теги
тфг, мочалов, 4308, герасимов, работа, курсовая, 2013г
1/--страниц
Пожаловаться на содержимое документа