Построение детерминированного конечного автомата

 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования
«Гомельский государственный технический университет имени П.О. Сухого»

Факультет автоматизированных и информационных систем

Кафедра «Информационные технологии»

Специальность 1-40 04 01 «Информатика и технологии программирования»

Отчет
по лабораторной работе №7
по теме: «Построение детерминированного конечного автомата»
по дисциплине: «Методы трансляции»

Составил: студент гр. ИП-31                 Доктренко Д.И.

(подпись, дата)

Принял: доцент кафедры ИТ                 Кравченко О.А.

(должность)

Гомель 2023

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

Задание

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

1) составить ДКА, который анализирует синтаксическую правильность заданной конструкции, т. е. соответствие структуры конструкции общему описанию;

2) разработать программу (на одном из изученных языков программирования), которая моделирует работу ДКА;

3) проверить работу программы при анализе правильной и неправильной конструкции.

Вариант индивидуального задания

Вариант 16

Описание функции языка программирования имеет следующую структуру:

function имя_функции(список_параметров_функции) begin оператор_присваивания; оператор_присваивания; оператор_присваивания; end;

Оператор присваивания имеет одну из следующих структур:

переменная := выражение

переменная := алгебраическое_сложение выражение

переменная := выражение алгебраическое_сложение выражение

В левой части оператора присваивания в качестве переменной может использоваться имя функции.

Алгебраическое сложение – это одна из операций + или -.

Выражение – это переменная или число.

Список параметров функции разделяется символом «;». Количество параметров – от одного до трех. В качестве параметра функции может использоваться только переменная.

Пробелы могут стоять в конструкции в любом месте. Каждое служебное слово должно быть выделено пробелами.

Алфавит языка после лексического анализа:

Служебные слова: function, begin, end.

Знаки: ;, +, -, (, ), пробел.

Имена функций: f1, f2, f3, f4.

Переменные: a1, a2, a3, a4, a5, a6.

Числа: r1, r2, r3, r4, r5, r6.

Пример правильной конструкции:

function f1(a2; a5; а1) begin a3:= r1-a2-a5; a4:= r1+a2; f1:=-a4; end;

Пример неправильной конструкции:

function f1(a2, a5) begin a3:= r1-a2; a4:= r1+a2; f1:=-a4; end;

Модель ДКА:

[pic 1]

Таблица состояний:

Код программы:

using System;

using System.Collections.Generic;