Карпов - Основы построения трансляторов (2005), страница 11

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

МП-автомат — это конечный автомат, снабженный дополнительным стеком (магазином) для хранения промежуточной информации потенциально бесконечного объема (рис. 2.17). МП-автомат имеет конечное множество внутренних состояний 5 с начальным состоянием лО и подмножеством Е заключительных состояний„конечный алфавит входных сигналов Х и конечный ал- фавит магазина Г' с маркером 1, который обозначает дно стека. Функция переходов о по каждой тройке <~пекуи~ее внул~реннее сосиояние, очередной входной сигнси, верхпий символ магазина- определяет на очередном шаге функционирования следующее состояние и цепочку символов магазинной памяти, записываемых в магазин вместо прочитанного верхнего символа (условимся, что цепочка записывается в стек "хвостом вперед", т.

е. сначала в стек записывается последний символ цепочки„затем предпоследний и т. д.). МП-автомат распознает входную цепочку, если после ее завершения на входе автомат перейдет в одно из заключительных состояний и его магазин будет пустым. Рис. 2.17. Структура МП-автомата ПРИМЕР 2.20.

МП-автомат М=(«5~, «(, )~, «А~, ю, 1. о, ®) рис. 2.18 только с одним состоянием распознает язык правильных скобочных выражений. Вначале стек пуст — в нем находится заключительный маркер 1. По каждой встретившейся на входе открывающей скобке ( автомат добавляет в магазин символ А (который отмечает, что соответствующая закрывающая скобка впоследствии должна встретиться во входной цепочке). Каждая встретившаяся на входе закрывающая скобка приводит к выбрасыванию символа А из магазина. Когда все символы и во входной строке, и в стеке исчерпываются, автомат остается в заключительном состоянии ю. Легко видеть, что любое нарушение структуры входной цепочки — несбалансированность скобок — не может привести к ситуации, когда при пустой входной строке стек автомата останется пустым.

Языки и грамматики Рис. 2.18. МП-автомат, распознающий язык правильных скобочных выражений МП-автомат является недетерминированным, если его функция переходов неоднозначна и/или в нем имеются в-переходы. Недетерминированный МП- автомат распознает входную цепочку, если существует последовательность шагов его работы, приводящая его из начального в одно из заключительных состояний после прочтения всей входной цепочки и пустом магазине. Оказывается, что класс КС-языков совпадает с классом языков, распознаваемых недетерминированными МП-автоматами. Детерминированные МП-автоматы могут распознать лишь более узкий класс КС-языков„который все же более широк, чем класс автоматных языков. В частности, как мы видели, не- автоматный язык правильных скобочных выражений распознается простейшим детерминированным МП-автоматом (рис. 2.18). Покажем, что по каждой КС-грамматике б = (7, Х, Я.

Н) можно построить (не- детерминированный) МП-автомат Л4;, распознающий язык, порождаемый 6. Множество состояний М<; составляют три состояния: начальное юо, рабочее 1 и заключительное су. Множество входных сигналов искомого МП-автомата— это множество терминальных символов грамматики 6. Алфавит магазина Г составляют все нетерминальные символы б и для каждого терминального символа ае 7 грамматики б в него входит символ а', т. е. Г = М ~ 7'. Взаимно- однозначную функцию 7" — +7, сопоставляющую каждому ае 7 элемент а'~:-7, ооозначим ~ Расширим определение функции,~ на множество У не- терминалов грамматики б, определяя ее на этом множестве как тождественную функцию.

Далее будем считать, что эта функция на цепочках символов из 7иХ определяется покомпонентно. Функция переходов о искомого МП-автомата строится так: Ч 5(~о. г., 1) ==(з,.Ю) // в верхушке магазина помещаем начальный нетерми- нал грамматики Й; Ч (~7а~ 7): б(з, а. Яа)) = (ь, а) // если в верхушке магазина — символика), соответствующий очередному входному терминалу а, то автомат переходит к следующему входному символу, выбрасывая из магазина верхний символ; Ч (~АеГ)(~7А — +схем): о(к, е, А) =- (л,Яа)),/ если в верхушке магазина стоит нетерминал, то МП-автомат, не читая очередного входного символа, заме- Глава 2 няет его в магазине одной из альтернатив этого нетерминала из множества продукций грамматики 6; О о(ю, е, 1~) = (О, ~ ) 0 если в магазине больше нет символов„то переходим в заключительное состояние. Легко видеть, что при удачном выборе последовательности выполнения ко- манд построенный так МП-автомат (недетерминированно) моделирует про- цесс левостороннего порождения входной цепочки, если она является цепоч- кой языка, порождаемого грамматикой О.

ПРИМЕР 2.21. Построим МП-автомат М~д, распознающий язык правильных скобочных выражений, формально по двусмысленной грамматике б~. 5-+ — +55 ~ ® ~ я, порождающей этот язык. Множество состояний М~;5 содержит начальное состояние ьо, рабочее состояние ь и заключительное состояние д. Множество его входных сигналов— множество терминалов грамматики 6~. Магазинный алфавит включает символ Я (единственный нетерминал грамматики) и пару символов, (' и )', соответствующих терминалам грамматики: М65 ФО ъ Ч1 1( )1 Р ( ) 1 ЮО -~- б ®).

Функция переходов МП-автомата определится так: б(ьр, е, 1) =(л, К1); 0 в магазин записываем начальный нетерминал грамматики; автомат переходит в состояние ь-, // если терминал входной цепочки и верхушка магазина совпадают, выбрасываем символ из магазина и переходим к следующему входному символу; Алгоритм распознавания языка очень непросто построить по такому неде- терминированному автомату. Обратно, оказывается, что по каждому (недетерминированному) МП-рас- познавателю можно построить КС-грамматику, порождающую распознавае- мый этим автоматом язык. Это доказывается более сложно; доказательство можно найти, например, в [Г701.

Ял, ), )') =(, ~); о(ь, я, 5) = (ь, Я Я; о(.~, ~, Я = (,, (' ~ )'); ~(,5', ~, Я=(Л, Е); Й~' ~ -~) =(ч -~-)' 0 в соответствии с продукцией грамматики; д при пустом магазине входная цепочка распознана, если она кончилась. Языки и грамматики Итак. МП-автомат может быть использован для представления любого языка типа 2. Очевидно также, что по любому МП-автомату может быть построена машина Тьюринга, моделирующая его функционирование. 2.6.4. Конечные автоматы Пусть имеется (недетерминированный) конечный автомат Л = (Л; Х, ло, о, Г).

Построим грамматику б,~ =(Х. Л', .~о, А~), порождающую язык, распознаваемый автоматом А. Множество продукций грамматики строится по функции переходов автомата А и множеству Е заключительных состояний. Для любого перехода о (~, а) =р автомата включим в А.~ продукцию л — +ар, и для каждого ~~еГ включим в Л,~ продукцию д-+г. Очевидно, что грамматика С'А автоматная, она порождает язык, который распознается автоматом А. Действительно, каждому выводу в 6~ соответствует путь в Л из начального в одно из заключительных состояний, и обратно — каждому такому пути соответствует вывод цепочки в бл.

Обратное тоже верно: для любой автоматной грамматики. порождающей язык Л, суще твует конечный автомат, допускающий Л, который может быть построен непосредственно по продукциям грамматики. Особенностью конечных автоматов является то, что по любому недетерминированному конечному автомату легко строится эквивалентный ему детерминированный конечный автомат. Поэтому построенный по автоматной грамматике 6 недетерминированный конечный автомат может быть преобразован в детерминированный конечный автомат, который осуществляет распознавание цепочек языка, порождаемого 6. В этой роли он может быть использован как основа транслятора автоматного языка, заданного грамматикой 6.

Этот вопрос рассматривается в главе 5. Таким образом, между автоматными порождающими грамматиками Хомского и конечными автоматами существует тесная связь, а именно для любой автоматнои грамматики, порождающеи язык Х, существует детерминирован" ный конечный автомат, распознающий Е, и наоборот. Из-за такой связи язы- Глава 2 лентными с точки зрения порождающих возможностей. Кроме этих двух форм в этом разделе мы рассмотрим и некоторые другие формализмы задания языков, не эквивалентные грамматикам Хомского. 2.7Л. Нотация Бэкуса — Наура Очевидно, что для формального задания грамматик формальных языков также необходим язык.