Магазинные автоматы. Как магазинные автоматы воспринимают языки программирования

Теперь опишем работу этого  автомата.

Допустим входная строка содержит N символов A , за которыми следует N символов B.

Считывание символов А , приводит к тому что в стеке оказывается N элементов А( и больше ничего). Первый символ В переводит автомат в допускающее состояние , но потребуется еще N-1  считываний b , чтобы очистить стек. Таким образом, любая строка, содержащая иную конфигурацию символов, не будет допущена.

Замечание. Иногда возникает необходимость проверить стек на пустоту. Для такой операции никакой особой возможности не предусмотрено но можно поступить следующим образом. В пустой стек можно положить элемент который будет служить признаком дна стека. А потом проверять вершину на равенство с добавленным нами элементом.

6. Детерминированные и недетерминированные автоматы.

Детерминированным называется такой  автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое  автомат может перейти из текущего.

Детерминированный автомат завершает  работу лишь тогда, когда достигает  конечного состояния.

Недетерминированные автоматы являются обобщением детерминированного автомата.

От недетерминированного автомата можно перейти к детерминированному .

Для недетерминированных автоматов (в отличие от детерминированных) существует два эквивалентных критерия завершения работы:

1.пустой магазин

2.достижение конечного  состояния

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

С помощью любого недетерминированного автомата можно описать любой  контекстно-свободный язык, в то время как с помощью детерминированного магазинного автомата лишь некоторые  контекстно-свободные языки( хотя и регулярные).

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

7.Автоматное программирование.

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

 

Существуют различные модели для  описания конечных автоматов. Однако их представление в виде графов переходов (диаграмм состояний) наиболее удобно для человека.

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

В начале покажем как это можно  реализовать в привычном нам  стиле на языке С:

Здесь getchar  считывает следующий символ из подаваемого нами входного потока, puthchar используем для вывода .

 

Теперь посмотрим как изменится программа если  написать программу автоматным стилем. Заметим, что разбор строки разделяется на три фазы: пропуск пробелов, печать слова и пропуск символов остатка строки. Назовём эти три фазы состояниями before, inside и after. Программа теперь может выглядеть, например, так:

Код стал длиннее , но чтение у нас производится теперь только один раз, вместо четырёх циклов остался только один,  для перехода от одного состояния к другому мы воспользовались оператором switch.

Программа реализует работу конечного  автомата. Буквой N на диаграмме обозначен  символ конца строки, буквой S — символ пробела, буквой A — все остальные  символы. За один шаг автомат делает ровно один переход в зависимости  от текущего состояния и прочитанного символа. Некоторые переходы сопровождаются печатью прочитанного символа; такие  переходы на диаграмме обозначены звёздочками.

 

 

8.Необходимость магазинных  автоматов

Теперь я хочу показать на примере  неэффективность конечных автоматов  и необходимость введения автоматов  с магазинной памятью.

Синтаксический разбор осуществляется с применением более сложных  грамматик, обеспечивающих иерархическое  определение одних правил через  другие. Поэтому, для построения распознавателей, мощности конечных автоматов, используемых при лексическом анализе, уже  не хватает. Необходим более мощный и универсальный автомат, поддерживающий построение дерева разбора и выстраивающий  его как сверху вниз, так и снизу  вверх. Поэтому для контекстно-свободных грамматик вводят автоматы с магазинной памятью(АМП).

Давайте предположим нам  необходимо построить распознаватель правильной вложенности круглых скобок. Такая вложенность скобок часто встречается в различных языках программирования при построении арифметических выражений. Для решения данной задачи необходимо:

1. определять равенство скобок, то есть количество открывающихся и закрывающихся скобок должно быть равным;
2. следить за правильностью их вложения, то есть, чтобы любой закрывающейся скобке предшествовала соответствующая открывающаяся.

Невозможность использования конечного  автомата подтверждается и тем, что  грамматику, порождающую рассматриваемые  цепочки, нельзя свести к праволинейной (тому виду, который, по классификации Хомского, эквивалентен конечному автомату).

 Ее также нельзя представить  итеративными диаграммами Вирта,  непосредственно соответствующими  конечному автомату. Это определяется  наличием в грамматике правил  с рекурсией в середине. А такая  рекурсия не может быть сведена  к итерации. Грамматика G может быть определена следующим образом:

 G = ({A, S}, { (, ) }, P, S) ,

Где P определяется как:

1)S → (A ) A

2) A → S и 3) A→ε

Проблему можно решить следующим  образом, можно сделать счетчик, который в начальный момент времени  будет иметь значение 0, с каждой открывающейся скобкой, значения счетчика будет увеличиваться, а с каждой закрывающейся- уменьшатся, так же мы должны помнить что во время работы счетчик не должен принимать отрицательные значения. Раз мы ввели счетчик, значит мы затратили память, а следовательно использование стека не усложняет нашу задачу. А экономить ячейки памяти мы давно уже разучились. Кроме того, в реальной ситуации могут быть более сложные зависимости. Например, может быть несколько видов скобок со своими правилами вложенности и их взаимным расположением. Значит, необходим универсальный подход, обеспечивающий преодоление различных ситуаций. Таким универсальным подходом и является использование автомата с магазинной памятью.

9.Описание и  команды магазинного автомата. Примеры.

Автомат с магазинной памятью  определяется следующими пятью объектами:

1)Конечным множеством входных символов, включающим концевой маркер ( ).

2)Конечным множеством магазинных символов, включающим маркер дна ( ).

3)Конечным множеством состояний, включающим начальное состояние.

4)Устройством управления (УУ), которое каждой комбинации входного символа, магазинного символа и состояния ставит в соответствие выход или переход. Переход, в отличие от выхода, заключается в выполнении операций над магазином, состоянием и входом. Операции, запрашивающие входной символ после концевого маркера или выталкивания из магазина после маркера дна, а также операция вталкивания маркера дна, исключаются.

5) Начальным содержимым магазина, содержащим маркер дна и, возможно пустую, цепочку магазинных символов.

 Я хочу продемонстрировать  программу работы автомата с  магазинной памятью со скобками (проверка правильности расстановки скобок).

Проанализируем для начала нашу задачу.

Давайте опишем операции автомата :

1. "Вытолкнуть" - выталкивает из стека верхний символ( в дальнейшем будем использовать этот символ ↑)
2. "Втолкнуть А" - вталкивает в стек магазинный символ А( ↓А)
3. ''Заменить XYZ'' – необходимо вытолкнуть верхний символ и втолкнуть вместо него несколько других.
4. Переход АМП из одного состояния в другое указывается явно операцией "Состояние t", где t - новое состояние автомата (будем сокращать текст данной операции до "[t]").