Пояснительная записка

Автоматная реализация алгоритма разбора

Содержание пояснительной записки

• Порядок выполнения работы
• Постановка задачи
• Текстовое описание реализованного автомата разбора
• Пример реализации
• Таблица 1. Обозначения символов
• Таблица 2. Функции выходов
• Таблица 3. Таблица переходов
• Рисунок 1
• Приложение 1
• Приложение 2
• Список литературы
• Порядок выполнения работы
• Постановка задачи
• Составление таблиц переходов, выходов, и/или графа автомата

Разработка алгоритма работы реализуемого автомата

Программная реализация автомата

Написание пояснительной записки

Постановка задачи

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

Текстовое описание реализованного автомата разбора

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

Любой ЦА описывается следующем кортежем: М = {X, Y, S, д, л, s0}, где X, Y, S - соответственно множества входных, выходных значений ЦА и внутренних состояний.

X = {x1, x2, x3, …..xn}

Y = {y1, y2, y3, …..ym}

S = {s1, s2, s3, ……sk} где m, n, k - конечные значения.

Если m, n, k конечны, то автомат называют конечным.

Состояние ЦА определяется состоянием элементов памяти д, л - соответственно характеристические функции перехода из одного состояния в другое (д) и функция выхода ЦА (л). s0 - начальное состояние ЦА.

По закону функционирования или по виду выходной функции ЦА делятся на: автоматы 1-го рода (автоматы Мили) и автоматы 2-го рода (автоматы Мура).

Закон функционирования ЦА первого рода (автомата Мили) есть:

s (t)= ? (s (t-1), x (t)), y (t)= ? (s (t-1), x (t)), где

s (t) - состояние автомата в настоящий момент;

s (t-1)- состояние автомата в предыдущий момент. Если t=0, то s(t-1)=s0;

x (t) - входной сигнал в текущий момент;

? - оператор формирования данного состояния s;

? - оператор формирования данного выходного сигнала y.

Т.е., закон функционирования представляет собой совокупность двух функций: функции перехода ? и функции выхода ?, а также, что данное состояние s (t) зависит от предыдущего состояния s (t-1) и входного сигнала в данный момент времени, что выходной сигнал в данный момент времени так же определяется предыдущим состоянием и входным сигналом в данный момент времени.

Функция выхода ЦА 2-го рода отличается от такой функции ЦА 1-го рода тем, что используется состояние в данный момент времени s (t). Таким образом, закон функционирования ЦА 2-го рода есть:

S (t) = ? (s (t-1), x (t)), y (t) = ? (s (t), x (t)).

У ЦА Мили выходной сигнал имеется только тогда, когда есть входной сигнал, а у ЦА Мура выходной сигнал имеется всегда.

Пример реализации:

Задание.

Pascal. Преобразование цикла FOR в LABEL/GOTO

Таблица 1. Обозначения символов

Таблица 2. Функции выходов

На Рисунке 1 представлен граф распознающего автомата. Рисунок графа распознающего автомата выполнен в графическом редакторе CorelDraw.

Текстовое описание автомата.

Распознающий автомат A = {Q, У, F, X, Y, д, л}

Множество состояний автомата Q = {q0, q1, …. , q18}

Начальное состояние q0

Допускающим состоянием является состояние q16

Множество входящих сигналов {x1, x2, … , x12, y1, y2, …, y10}

Множество выходных сигналов {w0, w1, … , w6}

Таблица 3. Таблица переходов

Рисунок 1.

Приложение 1.

Файл ConsoleApplication1.cpp

Приложение 2.

Текст программы:

#include "pch.h"

#include <iostream>

#include <conio.h>

#include <stdio.h>

#include <string.h>

#include <fstream>

int main()

{

FILE *fin;

FILE *fout;

fopen_s(&fin, "D:\\Temp\\in.txt", "rt");

fopen_s(&fout, "D:\\Temp\\output.txt", "wt");

while (!feof(fin))

{

char str[255] = "";

char str2[255] = "";

fgets(str, 254, fin);

for (int i = 0; str[i] != 0; i++)

{

if ((str[i] == 'f') || (str[i] == 'F'))

{

if ((str[i+1] == 'o') || (str[i+1] == 'O'))

{

if ((str[i + 2] == 'r') || (str[i + 2] == 'R'))

{

fprintf(fout, "label Pr, Res; \n");

fprintf(fout, "var\n");

fprintf(fout, "i: integer;\n");

fprintf(fout, "begin\n");

fprintf(fout, "i:=0;\n");

fprintf(fout, "Pr:\n");

fprintf(fout, "if i=2 then goto\n");

fprintf(fout, "Result;\n");

fprintf(fout, "write ('YES');\n");

fprintf(fout, "i:=i+1;\n");

fprintf(fout, "goto Pr;\n");

fprintf(fout, "Res:\n");

fprintf(fout, "end.\n");

}

}

}

}

}

fclose(fin);

fclose(fout);

_getch();

return 0;

}

Примечание

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

digraph G {

ranksep=.3;

node [shape = doublecircle , fontsize = 14];

edge[color="darkgreen",fontcolor="black",fontsize=12];

subgraph a {

q0->q0 [ label = "Y1/W1" ];

node [shape = circle , fontsize = 14];

rankdir = TB;

q0->q1 [ label = "X1/W0" ];

q1->q0 [ label = "Y1/W2" ];

q1->q2 [ label = "X2/W0" ];

q2->q0 [ label = "Y2/W3" ];

q2->q3 [ label = "X3/W0" ];

q3->q0 [ label = "Y3/W4" ];

q3->q4 [ label = "X4/W0" ];

q4->q4 [ label = "X4/W0" ];

q4->q5 [ label = "X5/W0" ];

q5->q5 [ label = "Y5/W0" ];

q5->q6 [ label = "X6/W0" ];

q6->q6 [ label = "Y6/W0" ];

q6->q7 [ label = "X4/W0" ];

q7->q7 [ label = "X4/W0" ];

q7->q8 [ label = "X7/W0" ];

q8->q8 [ label = "Y7/W0" ];

q8->q9 [ label = "X8/W0" ];

q9->q9 [ label = "Y8/W0" ];

q9->q10 [ label = "X2/W0" ];

q10->q10 [ label = "Y2/W0" ];

q10->q11 [ label = "X4/W0" ];}

q11->q11 [ label = "Y4/W0" ];

q11->q12 [ label = "X7/W0" ];

q12->q12 [ label = "Y7/W0" ];

q12->q13 [ label = "X4/W0" ];

q13->q13 [ label = "Y4/W0" ];

q13->q14 [ label = "X9/W0" ];

q14->q14 [ label = "Y9/W0" ];

q14->q15 [ label = "X2/W0" ];

q15->q15 [ label = "Y2/W0" ];

q15->q16 [ label = "X11/W5" ];

q16->q8 [ label = "Y10/W6" ];

q16->q17 [ label = "X10p/W6" ];

q17->q18 [ label = "X12/W0" ];

q18 [shape = doublecircle , fontsize = 14,style="filled",fillcolor="grey"]; }

}

граф визуализация программный graphviz

Список литературы

Горбатов В.А. Теория автоматов: учебник для вузов. - М.: АСТ: Астрель, 2008. - (Высшая школа). - 559с.

Карпов Ю.Г. Теория автоматов: Учебник для вузов. - СПб.: Питер, 2003. - (Учебник для вузов). - 206с.

Кузнецов О.П. Дискретная математика для инженера: учебник. - 6-е изд., стер. - СПб. [и др. ]: Лань, 2009. - 395 с.: ил.

Ахо А., Лам М., Сети Р., Ульман Дж.Д Компиляторы: принципы, технологии и инструментарий, 2 изд.: Пер. с англ. - М.: ООО «И.Д.Вильямс», 2011. - 1184 с.