Построенный автомат является недетерминированным.

Начальную конфигурацию с цепочкой a + a*a запишем так: (s₀ , a+a*a , h₀E).

Последовательность тактов работы построенного автомата, показывающая, что заданная цепочка допустима, имеет вид:

(s₀ , a+a*a , h₀E) ├ (s₀ , a+a*a , h₀T+E) ├ (s₀ , a+a*a , h₀T+T) ├ (s₀ , a+a*a , h₀T+F) ├

(s₀ , a+a*a , h₀T+a) ├ (s₀ , +a*a , h₀T+) ├ (s₀ , a*a , h₀T) ├ (s₀ , a*a , h₀F*T) ├

(s₀ , a*a , h₀F*F) ├ (s₀ , a*a , h₀F*a) ├ (s₀ , *a , h₀F* ) ├ (s₀ , a , h₀F) ├

(s₀ , a , h₀a) ├ (s₀ ,  , h₀) ├ (s₀ ,  , ).

Отметим, что последовательность правил, используемая построенным автоматом, соответствует левому выводу входной цепочки:

E  E+T  T+T  F+T  a+T  a+T*F  a+F*F  a+a*F  a+a*a.

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

Т акой способ построения дерева по заданной цепочке называется нисходящим.

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

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

Задание на лабораторную работу

Написать программу, реализующую работу недетерминированного магазинного автомата.

Входные данные:

1. Текстовый файл с описанием грамматики, для которой строится магазинный автомат.

Каждая строка в файле может задавать несколько правил грамматики с одинаковой левой частью. В этом случае правила отделяются друг от друга символом ‘|’.

Для отделения левой части правила от правой используется символ ‘>’. В одной строке может быть несколько символов ‘>’. В этом случае первый из них трактуется, как символ, отделяющий правую и левую части продукции, все последующие – как терминальный символ.

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

Все символы, не описанные выше, являются терминальными символами.

Правил в грамматике (а значит и во входном файле) – неограниченное количество.

Рекомендуется считать пробельные символы в файле незначащими, а для терминала «пробел» использовать какой-нибудь другой символ (например, ~, либо заключать пробел в апострофы).

Пример входного файла

E > E + T | T

T > T * F | F

F > ( E ) | a | ~

2. Строка символов, которую нужно проанализировать с помощью построенного автомата и дать заключение о допустимости (или недопустимости) автоматом данной цепочки символов.

Выходные данные

1. На оценку «удовлетворительно»: заключение о допустимости (или недопустимости) автоматом цепочки символов.

2. На оценку «отлично»: значение множеств P, Z и т.д.; список команд (1) – (4) (см раздел «Построение магазинного автомата»); цепочка конфигураций магазинного автомата, полученная в процессе его работы; заключение о допустимости (или недопустимости) автоматом цепочки символов.

Литература

При подготовка данной лабораторной работы были использованы материалы сайта http://mf.grsu.by/.

Copyright © 2005 – 2010 Voldem@r