езультат обработки контрольного примера
остановка задачи
Реализовать детерминированный конечный автомат указанного типа для разбора и преобразования циклов, написанных на языке, соответствующих требованию варианта задания.
Тип автомата — Мили.
Вариант — № 21; преобразование цикла do {…} while (…)
в циклwhile (…) do {…}.
екстовое описание
Данный автомат реализуется на языке C++. Для обозначения состояний и переходов по ним используется оператор выбора switch-case.
Идеальный проход по автомату осуществляется так:
· найти ключевое слово } while(
· вывести l:
· выводить данные в файл без изменения пока не встретится закрывающая скобка }
· найти ключевое слово } do(
· вывести if (
· выводить пока не встретится закрывающая скобка )
· если найдено ещё одно ключевое слово do {, перейти к п.2, иначе — продолжить считывать код;
тображение автомата в виде графа
аблица обозначения входных символов
| Входной символ | Значение |
| Zd | Символ ‘d’ |
| Zo | Символ ‘o’ |
| Zbr | Символ ‘{’ |
| Zsp | Пробел |
| Zbrs | Символ ‘}’ |
| Zbrc | Символ ‘(’ |
| Zbrck | Символ ‘)’ |
| Zi | Символ ‘i’ |
| Zf | Символ ‘f’ |
| Ztz | Символ ‘;’ |
| Znsn | Символ ‘/’ |
| Znd | Любой символ, кроме ‘d’ |
| Zno | Любой символ, кроме ‘0’ |
| Znbrck | Любой символ, кроме ‘)’ |
| Znnsn | Любой символ, кроме ‘/’ |
| Znn | Любой символ, кроме ‘/’ и ‘}’ |
| Znsp | Любой символ, кроме пробела |
аблица обозначений функций выходов
| Функция | Значение |
| W0 | Нет вывода |
| W1 | Вывод входного символа |
| W2 | Вывод “d”, далее – входного символа |
| W4 | Вывод “do”, далее – входного символа |
| W5 | Вывод “l:” |
| W6 | Вывод “if (” |
| W7 | Вывод “{\n goto l;\n}” |
онтрольный пример
Входной файл cycle.cpp:
езультат обработки контрольного примера
Выходной файл cycleout.cpp:
ЗАКЛЮЧЕНИЕ
В данном курсовом проекте мы реализовали автомат для разбора и преобразования циклов, написанных на языке, соответствующих требованию варианта задания. Вариант работы подразумевал также типы входного и выходного циклов. Мы обработали один цикл, в случае множественных или вложенных циклов во входных данных.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Горбатов В.А. Теория автоматов: учебник для вузов. - М.: АСТ: Астрель, 2008. - (Высшая школа). - 559с.
2. Карпов Ю.Г. Теория автоматов: Учебник для вузов. - СПб.: Питер, 2003. - (Учебник для вузов). - 206с.
3. Кузнецов О.П. Дискретная математика для инженера: учебник. - 6-е изд., стер. - СПб. [и др. ]: Лань, 2009. - 395 с.: ил.
4. Ахо А., Лам М., Сети Р., Ульман Дж.Д Компиляторы: принципы, технологии и инструментарий, 2 изд.: Пер. с англ. – М.: ООО «И.Д.Вильямс», 2011. – 1184 с.
ПРИЛОЖЕНИЕ
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace CSSample
{
class Program
{
private static string code;
private static int pos = 0;
/// Получение следующего символ из входного потока данных автомата
/// <returns>Символ</returns>
private static char Next()
{
if (pos >= code.Length - 1)
return ' ';
//Символ с кодом 255 означает конец последовательности символов
return code.ToCharArray()[pos++];
}
static void Main(string[] args)
{
//Прочитаем содержимое файла, указанного параметром к командной строке
StreamReader F = new System.IO.StreamReader(args[0]);
code = F.ReadToEnd().ToUpperInvariant();
F.Close(); //закрываем файл
StreamWriter Fw = new System.IO.StreamWriter(args[1]); //Создаём выходной файл
string ident = ""; //Идентификатор цикла
string fromval = ""; //Значение «ОТ»
string toval = ""; //Значение «ДО»
string stepval = ""; //Значение шага
string nident = ""; //Идентификатор, встреченный после NEXT
int identpos = 0; //Позиция в идентификаторе
char c; //Обрабатываемый символ
s0:
c = Next();
if (c == 'F') goto s1;
//Если символ во входном потоке F - может быть, начало слова FOR?
Fw.Write(c);
goto s0;
s1:
c = Next();
if (c == 'O') goto s2;
//Если символы во входном потоке FO - может быть, начало слова FOR?
Fw.Write("F" + c);
goto s0;
s2:
c = Next();
if (c == 'R')
goto s3; //Если символы во входном потоке FOR - может быть, начало слова FOR?
Fw.Write("FO" + c);
goto s0;
s3:
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r')) goto s4; // FOR и пробел - определённо, FOR!
Fw.Write("FOR" + c);//А если нет - что-то другое, продолжаем дальше
goto s0;
s4:
c = Next(); //Пропускаем пробелы
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s4;
else
goto s5;
s5: //Сохраняем в память идентификатор
ident += c;
c = Next();
if (c == '=')
goto s6;
else
goto s5;
s6: //Опять пробелы
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s6;
else
goto s7;
s7: //Сохраняем начальное значение переменной
fromval += c;
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s8;
else
goto s7;
s8: //Начинаем поиски фразы TO
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s8;
else
if (c == 'T')
goto s9;
s9:
c = Next();
if (c == 'O')
goto s10;
s10:
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s10;
else
goto s11;
s11:
toval += c;
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s12;
else
goto s11;
s12: //Ищем слово STEP
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s12;
else
if (c == 'S') goto s13;
//Переходим к телу цикла, если STEP отсутствует
//Запись заголовка цикла
Fw.WriteLine(ident.Trim() + " = " + fromval + "\r\nDO WHILE " + ident.Trim() + " <= " + toval + "\r\n");
goto s19;
s13:
c = Next();
if (c == 'T')
goto s14;
s14:
c = Next();
if (c == 'E')
goto s15;
s15:
c = Next();
if (c == 'P')
goto s16;
s16:
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s16;
goto s17;
s17:
stepval += c;
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
{
//Запись заголовка цикла
Fw.WriteLine(ident.Trim() + " = " + fromval + "\r\nDO WHILE " + ident.Trim() + " <= " + toval + "\r\n");
goto s19;
}
else
goto s17;
s19: //Запись тела цикла и поиск слова NEXT
Fw.Write(c);
c = Next();
if (c == 'N') goto s20;
goto s19;
s20:
c = Next();
if (c == 'E') goto s21;
Fw.Write("N");
goto s19;
s21:
c = Next();
if (c == 'X') goto s22;
Fw.Write("NE");
goto s19;
s22:
c = Next();
if (c == 'T') goto s23;
Fw.Write("NEX");
goto s19;
s23:
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s24;
Fw.Write("NEXT");
goto s19;
s24:
c = Next();
if ((c == ' ') || (c == '\n') || (c == '\r'))
goto s24;
goto s25;
s25:
//Если идентификатор другой, это NEXT от вложенного цикла
if (c != ident.Trim().ToCharArray()[identpos])
{
Fw.Write("NEXT " + nident);
identpos = 0;
nident = "";
goto s19;
}
else
{
//И даже если его начало совпадает с идентификатором из нужного цикла, но он длиннее
if (identpos >= ident.Trim().Length)
{
Fw.Write("NEXT " + nident);
nident = "";
identpos = 0;
goto s19;
}
identpos++;
}
nident += c;
c = Next();
if ((c == ' ') || (c == '\r') || (c == '\n'))
{
if (stepval == "")
Fw.WriteLine(ident + " = " + ident + " + 1");
else
Fw.WriteLine(ident + " = " + ident + " + " + stepval);
Fw.WriteLine("Loop");
goto s26;
}
goto s25;
s26:
Fw.Write(c);
c = Next();
if (c != ' ') //Символ с кодом 255 - конец входного потока
goto s26;
goto s27;
s27:
Fw.Close();
}
}
}