1 Необходимость использования автоматов с магазинной памятью
Синтаксический разбор осуществляется с применением более сложных грамматик, обеспечивающих иерархическое определение одних правил через другие. Поэтому, для построения распознавателей, мощности конечных автоматов, используемых при лексическом анализе, уже не хватает. Необходим более мощный и универсальный автомат, поддерживающий построение дерева разбора и выстраивающий его как сверху вниз, так и снизу вверх. Из предыдущих тем известно, что конечный автомат можно расширить дополнительной рабочей памятью, чтобы обеспечить распознавание цепочек, порождаемых практически любыми грамматиками. Организация и поведение такого автомата определяется классом грамматик. Как определено в классификации Хомского, контекстно-свободным грамматикам можно поставить в соответствие автомат с магазинной памятью (АМП).
То, что даже простые цепочки проблематично распознать с использованием конечного автомата, можно проиллюстрировать решением следующей элементарной задачи: необходимо построить распознаватель правильной вложенности круглых скобок. Такая вложенность скобок часто встречается в различных языках программирования при построении арифметических выражений. Для решения данной задачи необходимо:
Определять равенство скобок, то есть количество открывающихся и закрывающихся скобок должно быть равным;
Следить за правильностью их вложения, то есть, чтобы любой закрывающейся скобке предшествовала соответствующая открывающаяся.
Невозможность использования конечного автомата подтверждается и тем, что грамматику, порождающую рассматриваемые цепочки, нельзя свести к праволинейной (тому виду, который, по классификации Хомского, эквивалентен конечному автомату). Ее также нельзя представить только итеративными диаграммами Вирта, непосредственно соответствующими конечному автомату. Это определяется наличием в грамматике правил с рекурсией в середине. А такая рекурсия не может быть сведена к итерации. Грамматика G7.1 Может быть определена следующим образом: G7.1 = ({A, S}, { (, ) }, P, S) ,
Где P определяется как:
1. S (A ) A
2. A S
3. A
Одним из путей решения задачи является добавление счетчика скобок, который, при просмотре цепочки увеличивается на 1, если встретится открывающаяся скобка. Закрывающаяся скобка уменьшает значения счетчика на единицу. Начальное состояние счетчика (перед просмотром цепочки) равно 0. По завершении просмотра цепочки значение счетчика должно быть равным 0. При этом, в ходе просмотра цепочки счетчик не может принимать отрицательные значения. Подход обеспечивает решение поставленной задачи. Однако, наличие счетчика уже определяет автомат с дополнительно рабочей памятью, которому также необходимо наличие арифметического устройства. Поэтому, использование стека вряд ли будет сложнее. Кроме того, в реальной ситуации могут быть более сложные зависимости. Например, может быть несколько видов скобок со своими правилами вложенности и их взаимным расположением. Значит, необходим универсальный подход, обеспечивающий преодоление различных ситуаций. Таким универсальным подходом и является использование автомата с магазинной памятью.
2 Организация автомата с магазинной памятью
АМП в качестве рабочей памяти использует стек, называемый также магазином. Данная память поддерживает только ограниченные операции доступа, в то же время достаточные для решения сложных задач, включая и задачи распознавания цепочек. Автомат с магазинной памятью определяется следующими пятью объектами:
Конечным множеством входных символов, включающим концевой маркер ().
Конечным множеством магазинных символов, включающим маркер дна ().
Конечным множеством состояний, включающим начальное состояние.
Устройством управления (УУ), которое каждой комбинации входного символа, магазинного символа и состояния ставит в соответствие выход или переход. Переход, в отличие от выхода, заключается в выполнении операций над магазином, состоянием и входом. Операции, запрашивающие входной символ после концевого маркера или выталкивания из магазина после маркера дна, а также операция вталкивания маркера дна, исключаются.
Начальным содержимым магазина, содержащим маркер дна и, возможно пустую, цепочку магазинных символов. Автомат с магазинной памятью называется распознавателем, если у него 2 выхода: "Допустить" и "Отвергнуть".
Существуют следующие операции автомата:
Динамическое поведение АМП описывается через его операциями над входной цепочкой и стеком, а также переходами из одного состояния в другое. К операциям над стеком относятся:
"Вытолкнуть" - выталкивает из стека верхний символ (будем также использовать сокращенное обозначение "").
"Втолкнуть А" - вталкивает в стек магазинный символ А (будем также использовать сокращенное обозначение "А").
"Заменить XYZ" - используется для сокращения записи, когда необходимо вытолкнуть верхний символ и вместо него втолкнуть несколько других (конкретно в данном случае, где мы имеем X, Y, Z). Запись эквивалентна:
XYZ (сокращенно обозначим: XYZ).
Переход АМП из одного состояния в другое указывается явно операцией "Состояние t", где t - новое состояние автомата (будем сокращать текст данной операции до "[t]").
Сдвиг входной головки на один символ вправо относительно входной ленты задается операцией "Сдвиг" (сократим до ""). После ее выполнения текущим символом становится следующий символ на входной ленте. Другой операцией над входной головкой является "Держать", которая не изменяет положение входной головки до следующего шага (можно просто не писать, если нет сдвига).
Переход или шаг автомата - это выполнение операций над стеком и входной головкой, а также изменение состояния. При этом необязательно, чтобы за один шаг происходили все изменения. Возможно: или входная головка останется на месте, или не произойдет операции над стеком, или не изменится состояние.
3 Распознаватель скобочных выражений
Рассмотрим одну из возможных реализация АМП, для задачи проверки корректности вложенности круглых скобок. Кратко опишем общий принцип работы автомата. Если входная головка читает "(", то в магазин заталкивается символ А. Если входная головка читает ")", то из магазина выталкивается содержащийся там символ. Цепочка отвергается, если:
На входе остаются правые скобки, а магазин пуст.
Входная цепочка прочитана до конца, а в магазине остаются символы А, соответствующие левым скобкам, для которых не нашлось пары
Определим данный АМП следующим образом:
Множество входных символов: { (, ), }.
Множество магазинных символов: { A, }
Множество состояний: t, где t является также и начальным состоянием автомата, раз оно единственное.
Переходы:
(, A, S А, S,
(, , S А, S,
), A, S , S,
), , S Отвергнуть
, A, S Отвергнуть
, , S Допустить
В начальном состоянии магазин содержит только маркер дна ().
Из представленного описания видно, что поведение автомата имитирует ранее рассмотренный метод распознавания с использованием счетчика. Только вместо счетчика используются "палочки". Эти палочки могут записываться в стек и стираться из него, отражая разность между прочитанными открывающимися и закрывающимися скобками. Работу данного АМП можно рассмотреть на примере распознавания нескольких цепочек. Пусть, первая цепочка будет иметь следующий вид: ( ( ) ( ) ). Тогда осуществляемые автоматом переходы можно представить в виде следующей последовательности текущих состояний его устройств (таблица 1)
Номер шага Содержимое
стека Состояние
автомата Остаток
входной цепочки Номер
применяемого
правила
1
[t] ( ( ) ( ) )
2
2 A
[t] ( ) ( ) )
1
3 A A
[t] ) ( ) )
3
4 A
[t] ( ) )
1
5 A A
[t] ) )
3
6 A
[t] )
3
7
[t]
Допустить
Таблица 1. Последовательности текущих состояний устройств
В приведенном примере цепочка оказалась распознанной. Следующий пример раскрывает поведение автомата при распознавании цепочки, содержащей большее число правых круглых скобок чем левых: ( ) ) )
Таблица переходов и состояний в этом случае будет выглядеть следующим образом (таблица 2):
Номер шага Содержимое стека Состояние автомата Остаток входной цепочки Номер
применяемого
правила
1
[t] ( ) ) )
2
2 A
[t] ) ) )
3
3
[t] ) )
Отвергнуть
Таблица 2. Таблица переходов и состояний
Такая таблица является типичной формой представления одного внутреннего состояния для любого АМП. Если у автомата имеется несколько внутренних состояний, то для каждого из них строится такая таблица переходов. В большинстве реальных случаев АМП имеют только одно состояние.
Методы, используемые при нисходящем разборе, достаточно универсальны и разнообразны. Применение восходящего разбора позволяет использовать более мощные KC(1) грамматики, в том числе и грамматики с левой рекурсией, которые при нисходящем разборе использовать невозможно. Возникают проблемы преобразования таких грамматик в грамматики с правой рекурсией, ориентированные на нисходящий разбор. Такое преобразование не всегда очевидно. Однако, применение диаграмм Вирта для представления синтаксиса языков программирования позволяет легко заменить все левые рекурсии на итерации и использовать полученные правила для нисходящего разбора. Поэтому, при практической разработке трансляторов, не имеет особого смысла использовать восходящий разбор.
