Детерминированные МП-автоматы

23. Детерминированные МП-автоматы МП-автомат называется детерминированным, если ни при какой ситуации невозможен переход из данного состояния, при данном содержимом верхней ячейки стека и при данном содержимом текущей клетки на ленте по разным ребрам. Это, скорее интуитивное понятие далее будет сделано точным. Для нужд практического программирования как и для обычных автоматов нужны прежде всего детерминированные автоматы. К сожалению, для стековых автоматов неверна теорема о том, что любой МП-автомат может быть переделан в эквивалентный детерминированный. Поэтому при построении синтаксических анализаторов надо сразу ориентироваться на детерминированные автоматы. Работа детерминированного автомата может быть легко запрограммирована. Однако из технических соображений удобно будет слегка модифицировать понятие МП-автомата – сделать его более гибким. Это сделает соответствие между работой автомата и его программной реализацией только более естественным. Суть модификации в удовлетворении такого пожелания. Мы хотим, чтобы в момент перехода по ребру с меткой a/A указатель ленты можно было оставлять на месте. Саму метку надо как-то модифицировать. Вариант /A не годится, т.к. он может выполняться при любом содержимом текущей клетки. А нам надо, чтобы автомат реагировал только на a, но распознавания (сдвига головки) не происходило! Более того, нам хочется, чтобы, когда автомат прочитает всю входную цепочку и окажется на пустой клетке, он мог бы на это среагировать. Т.е. некоторые переходы с меткой /A выполнять только на пустой клетке. Последнее означает, что функция  переходов должна иметь своей областью определения не множество Q (T { })(M {}), как раньше, а более широкое Q (T { }T{})(M {}) Здесь T – это еще один экземпляр терминального множества T, элементы которого мы будем записывать, как и элементы T, заключая их в квадратик, или снабжая индексом в виде квадратика. Также и  - еще одно обозначение для пустого слова или места. Для терминала a T тот факт, что (q,)  (p,a,A), означает: • переход из состояния p в состояние q; • замену в стеке верхнего символа A на цепочку  ; • отсутствие движения указателя на входной ленте. При этом переход может применяется только тогда, когда текущим входным символом является a. Метка на графе указывается как . В тексте пишем a /A. Заметим, что одновременное наличие меток возможно, но такой автомат, естественно, не детерминированный. Команда только тем отличается от , что она не может выполняться, когда автомат обозревает непустую клетку. Т.е. этот переход можно применить только после считывания входной цепочки. Естественно, движения указателя при этом не происходит. Назовем такие автоматы SМП-автоматами (S – от stand – автомат способен выполнять команду “Стоять”). Теорема 1. Классы языков, распознаваемых МП-автоматами и SМП-автоматами одинаковы. Доказательство. Пусть A – некоторый SМП-автомат. Этот автомат надо переделать в обычный, исключив в нем переходы с квадратиками. 1.Займемся переходами с метками вида a/A., где aT, AM {}, .M*. Идея переделки состоит в следующем. Допустим, что автомату при распознавании некоторой цепочки требуется такой переход (это работа со стеком без считывания ленты, причем при условии, что текущим является терминал a). Надо эту работу перенести в “параллельное пространство”. При переходе символ a прочитывается. Это параллельное пространство представляет собой копию фрагмента исходного автомата, в котором остались только команды работы со стеком, причем вместо a используется . Там, где раньше осуществлялось считывание a, происходит возврат к основному автомату. Переход a/A., с которого все началось, изымается Итак, пусть имеется переход 1.1. Начиная с q выпишем все состояния, в которые можно перейти по ребрам с метками вида a/... или /..., где а T – то самое а. На рисунке ниже они изображены черным цветом. Пока автомат выполняет эти переходы, движения считывающей головки не происходит. Если считывание символа а когда-то происходит, от сети черных состояний должны быть ответвления с метками вида a/.... Они помечены красными кружками. Не запрещается красным кружкам совпадать с черными или с синим, или синему - быть черным. 1.2. Представим состояния и переходы изображенными на горизонтальной плоскости серого цвета. Дублируем часть этой плоскости в голубую плоскость, выбирая только черные кружки, метки вида a/... заменяя a на , а от остальных переходов оставляя только вида /.... Ни один из этих голубых кружков не заносится во множество заключительных состояний. 1.3. В исходном автомате выкидываем переход , и соединяем серую и голубую плоскости: Здесь от синего состояния p в голубое q проведен переход с меткой a/A, и для каждого перехода a/B, где BM{}, M*, из какого-нибудь черного кружка v в какое-нибудь состояние w строим переход из голубого v в w c меткой /B. В полученном автомате на один переход с меткой вида будет a/... меньше и он, как легко проверить, эквивалентен исходному автомату. Повторяя процедуру достаточное число раз мы избавимся от переходов с метками a/... для aT. 2. Остается разобраться с переходами, помеченными как /A., где AM{}, .M*. Напомним, что они могут применяться только после считывания входной цепочки, когда текущая клетка становится пустой. Нужда в таких переходах может возникнуть от желания перевести автомат в конечное состояние, когда распознавание входного слова закончено. Переделка похожа на предыдущий случай. Пусть какой-то переход из состояния p в состояние q помечен меткой /A.. 2.1. Этот переход исключаем из автомата и рассматриваем множество состояний (черные), в которые можно попасть из q с помощью переходов с метками /.... или /..... 2.2. Строим параллельную плоскость (голубую) с копией черных состояний и только с этими переходами. Заключительные состояния в голубой плоскости такие же, как в оригинале. 2.3. Определяем переход из p в голубое q с меткой /A.. Нетрудно доказать, что в результате получится эквивалентный автомат. В нем на один переход вида /A стало меньше. Повторяя процедуру достаточное количество раз получим МП-автомат. Теорема доказана. Далее рассматривается наше основное понятие МП-автомата A = < Q, T, M ,  , s, F> Два перехода (q1,1)   (p,a1,A1) и (q2,2)   (p,a2,A2) называются несовместными переходами из состояния p, если либо a1  a2 и оба символа из T, либо A1  A2 и оба символа из M. Автомат A называется детерминированным, если из каждого его состояния p все переходы из p попарно несовместны. Язык называется детерминированным, если он распознается некоторым детерминированным МП-автоматом. Аналогично определяется понятие детерминированности и для SМП-автомата. Суть та же самая – в любой ситуации автомат не может иметь более одной возможности совершить какой-то переход. Приведем формальное определение. Пусть A – SМП-автомат. Перечислим виды пар несовместных переходов из состояния p: а) (q1,)  (p,a,A) и (q2,)  (p,b,B) при a  b и a, b  T; A, BM{}; б (q1,)  (p,a,A) и (q2,)  (p,b,B) при a  b и a, b  T; A, BM{}; в) (q1,)  (p,a,A) и (q2,)  (p,b,B) при a  b и a, b  T ; A, BM{}; г) (q1,)  (p,a,A) и (q2,)  (p,,B) при a  T ; A, BM{}; д) (q1,)  (p,a,A) и (q2,)  (p,,B) при a  T ; A, BM{}; е) (q1,)  (p,a,A) и (q2,)  (p,b,B) при a, b  T{}T{}; A  B и A, BM; SМП-автомат A называется детерминированным, если для каждого его состояния p все переходы из p попарно несовместны. Теорема 2. Любой детерминированный SМП-автомат эквивалентен некоторому детерминированному МП-автомату. Доказательство. Надо взять конструкцию из доказательства теоремы 1 и проверить, что по детерминированному автомату она дает детерминированный автомат. Замечание. Понятие детерминированного языка, как ни странно, не очень сильно, но зависит от выбора определения автомата. Например, если требовать, чтобы воспринимаемость цепочки всегда сопровождалась опустошением стека, для некоторых языков детерминированный автомат не существует, тогда как в принятом у нас способе такой автомат построить можно. Конкретнее, рассмотрим язык c T={a,b} цепочек L={anbn| n=1,2,…}{an| n=0,1,2,…} Вот детерминированный автомат, распознающий этот язык При распознавании цепочки an в стеке остается информация. Можно доказать, что автомат нельзя переделать так, чтобы при завершении распознавания стек всегда опустошался. Например, попытка сделать “отворотку” от v для опустошения стека приведет к недетерминированности. Однако, если после каждой входной цепочки на входной ленте ставить специальный концевой терминал (часто используют символ $), то проблема исчезнет. Но это уже модификация понятия распознаваемости. Оказывается, что не всякий КС-язык является детерминированным. Например, можно доказать, что язык L={ambnak| m=n или n=k} является контекстно-свободным, но не детерминированным. Иными словами не для всякого МП-автомата существует ему эквивалентный детерминированный МП-автомат. Тем не менее, класс детерминированных языков достаточно широк и в него попадают практически все языки программирования высокого уровня. Для построения эффективного синтаксического анализатора языка используется обычно схема: • Запись языка в нотации Бэкуса-Наура. • Анализ соответствующей КС-грамматики и модифицирование ее к некоторому варианту, по которому легко написать детерминированный МП-автомат. • Реализация работы МП-автомата в виде программы – синтаксического анализатора. При изучении КС-грамматик мы сталкивались с понятием однозначной или неоднозначной грамматики. Неоднозначность означала существование некоторой цепочки языка, у которой имелось два разных дерева разбора. Задачей синтаксического анализатора как раз и является построение дерева разбора. Поэтому стоит обратить внимание на два обстоятельства: 1) МП-автомат должен не просто распознавать цепочки языка – он должен в определенном смысле строить дерево разбора. 2) Если исходная грамматика не однозначная, то вряд ли по ней можно построить подходящий МП-автомат. Действительно, справедлива Теорема. Любой детерминированный КС-язык является однозначным КС-языком. Обратное не верно. Без доказательства. 24. Левый разбор и LL(1)-грамматики Хотя класс детерминированных КС-языков не охватывает даже класса однозначных КС-языков, он достаточно широк для того, чтобы включать подавляющее большинство языков программирования. Важное значение с точки зрения приложений имеет поиск фрагментов этого класса, которые имеют достаточную выразительную силу и могут быть легко распознаны и легко запрограммированы с помощью детерминированных КС-автоматов. К таким языкам относится класс так называемых LL(k)-языков для k=1,2,3,… Для определения этих языков не лишне вспомнить понятие лево-стороннего нисходящего разбора (LL-разбора). Такой разбор выводимой цепочки есть процесс построения дерева разбора от корня вниз, когда на каждом шаге достраиваются ребра, выходящие из самого левого нетерминала построенной к текущему шагу части. Левому разбору соответствует вывод, в котором каждый раз заменяется самый левый нетерминал. Понятно, что левый нисходящий разбор строится по дереву разбора единственным образом. Если бы рассматриваемая грамматика была однозначной, то, стало быть, этот разбор дал бы определение некого канонического вывода для всех цепочек. Однозначными являются многие грамматики. Но поиск эффективного метода построения левого нисходящего разбора не для каждой из них может быть успешно осуществлен. Наша задача – изучить некоторые классы грамматик, для которых это возможно. Схема программирования LL-разбора с использованием стековой памяти. Алгоритм по существу представляет вольное описание работы МП-автомата. Имеется указатель, “считывающий” по очереди символы обрабатываемой цепочки слева направо. Параллельно строится вывод. При этом поддерживается выполнимость условия (инвариант): “Считанная часть в соединении с содержимым стека должна совпадать с выведенной сентенциальной формой”. Шаг 1. Начальный символ грамматики S заносится в стек. Этот же символ – начало вывода. Шаг 2. Цикл с описанным выше логическим инвариантом. Извлекаем верхний символ стека. Возможные случаи. a) Это нетерминал (допустим A). По продолжению входной цепочки (от указателя) подыскивается правило грамматики A так, чтобы  могло бы стать началом этого еще непрочитанного куска. Слово , заносится в стек вместо A, а правило применяется к выводу. b) Это терминал. Он должен совпадать с первым символом непрочитанной части. Символ из стека выкидывается, а указатель сдвигается вправо. Чтобы такой алгоритм работал, надо иметь способы подбора правил A, которые обеспечили бы корректность всей процедуры. И здесь многое зависит от грамматики, задающей язык. s-грамматика – это такая грамматика G, у которой: 1) У любого правила A слово  начинается с терминала. 2) Для любых двух разных правил A и A с одинаковыми левыми нетерминалами слова  и  начинаются с разных терминалов. Очень легко понять, что для s-грамматик описанный выше алгоритм вполне эффективен. Например, для грамматики S aAbB|bBA, A aCA|cB, Bbc|ccCA, C a|c|bABA детерминированный МП-автомат строится так: Важно, что в этом случае не вся левая часть продукции кладется в стек. Первый терминал сразу считывается и в стек попадает только остаток. Это обеспечивает детерминированность автомата. Рассмотрим для примера разбор цепочки bccacbccbc. Ее вывод: SbBA bccCAA  bccaAA bccacBA bccacbcA bccacbccB bccacbccbc. Работа автомата: Полезные для дальнейшего анализа функции First() и Follow(). Пусть G= – произвольная КС – грамматика. Для нетерминала A определим: First(A) = {aT| A* a для некоторой цепочки   (T N)* }. Определим также First() для цепочек: First() = {aT|  * a для некоторой цепочки   (T N)*}. Иными словами First(A) – это множество терминалов, с которых “может начинаться” A (точнее – может начинаться слово, выводимое из A). Аналогично, First(). Перед вычислением First(A) или First() предварительно надо вычислить множество нетерминалов, из которых выводится пустое слово. Назовем такие нетерминалы прозрачными. Их множество легко получить. Множество First(A) вычисляется так. Вычисление надо делать параллельно для всех нетерминалов в несколько итераций. Сначала в First(A) переписываются все терминалы, с которых начинаются  в продукциях вида A с учетом прозрачности начальных нетерминалов. Затем надо рассмотреть нетерминалы B, с которых начинаются такие  (также с учетом прозрачности нетерминалов левее B) и рекурсивно добавить их множества First(B) к First(A). Например для грамматики G1 S  Aс|Bd; A  a|aA; B  b|bB First(S) = {a,b}. Если в грамматике нет –правил, то First() = {a}, если начинается с терминала a, и First() = First(A) , если начинается с нетерминала A. Но при наличии –правил в случае, когда в начале  имеется блок нетерминалов, надо анализировать их на предмет прозрачности. Если для первого нетерминала A имеет место A * , то после добавления к First() множества First(A) надо рассматривать второй нетерминал, допустим B. Добавить First(B) и опять рассмотреть возможность B *  и т.д. Например, для грамматики G2 S  AB|BG ; A  aA|ε ; B  bB|c First(AB) = {a,b,с}, First(BG) = {b,с}. Теперь для произвольной КС-грамматики G= и нетерминала A определим: Follow(A) = {aT | S* Aa для некоторых цепочек ,  (T N)* }. Иными словами Follow(A) – это те терминалы, которые могут встречаться непосредственно после нетерминала A в некоторой цепочке, выводимой из стартового нетерминала S. Множества Follow(A) могут быть вычислены по следующему алгоритму (надо только предварительно выкинуть все бесполезные нетерминалы) . 1) Для всех продукций вида A  B, где (T N)* , (T N)+ добавляем в Follow(В) элементы First(). 2) Для всех продукций вида A  B или вида A  B , где (T N)* , (T N)+ и *  добавляем в Follow(B) все элементы Follow(A). 2) Для всех продукций вида A  B , где (T N)* , N* и *  добавляем в Follow(B) все элементы Follow(A). Пункт 2) выполняется до тех пор, пока происходят изменения. С помощью множеств Follow(A) сделаем обобщение понятия s-грамматики на случай, когда имеются –правила. Предположим, что некоторая грамматика удовлетворяет условиям s-грамматики с тем только исключением, что в ней допускаются продукции вида A. Гарантирует ли это однозначность LL-разбора? Нет. Допустим, что при левостороннем разборе цепочки встретилась ситуация bacA. Дальше надо выбрать одно из правил, у которого левая часть есть A. Предположим, что исходная цепочка имеет вид bacd…. Тогда правила вида A x…, где xd и x – терминал, заведомо не годятся. Альтернатива может возникнуть только для двух правил A и Ad. А неоднозначность может проявиться в том, что после применения правила A из полученного bac через несколько шагов выведется bacd…. Это означает, что  * d…. Значит S * bacAd…. Значит dFollow(A). Неоднозначность будет невозможна, если подобные коллизии запретить. Это и дает определение следующего понятия. q-грамматика - это такая грамматика G, у которой: 1) Для любого правила A либо =, либо слово  начинается с терминала. 2) Если два разных правила имеют вид Aa и Ab , то ab. 3) При наличии двух правил вида A и Aa символ a не может лежать в  Follow(A). Выше приведенное рассуждение показывает, что q-грамматика является однозначной, а при LL-разборе любой цепочки в ситуации, когда надо выбирать между A и Ad, выбирается Ad…. Пример q-грамматики G3. S  aAS|b ; A cAS |ε Вычислим Follow(A) = {a,b}. Т.к. c  Follow(A), то это q-грамматика. Детерминированный МП-автомат для такой грамматики строится не намного сложнее, чем для s-грамматики. Но в нем используются переходы вида a/, которые не сдвигают указатель на входной ленте. Использование этих команд связано с продукцией Aε. Дело в том, что если в вершине стека находится элемент A, а очередным терминалом на ленте является c, то применяется переход c/AAS. Для остальных же терминалов символ A должен просто выталкивается их стека, а терминал не прочитываться. В общем случае для каждого правила вида Aε надо добавить переход ε/A ε, который позволит вытолкнуть из стека оставшиеся там после считывания входной цепочки символы A. В нашем примере это не обязательно, т.к. никакая сентенциальная форма не может заканчиваться буквой A. Для примера рассмотрим вывод цепочки: acbb. Ее вывод: SaAS  acASS  acSS  acbS  acbb. Работа автомата: LL(1)-грамматики. Для натурального числа k=1,2,… LL(k)-грамматикой называют такую однозначную контекстно-свободную грамматику, у которой для построения LL-разбора любой терминальной цепочки информация на входной ленте, в ее k клетках считая от текущей и вправо достаточна для того, чтобы правильно выбрать очередное правило грамматики. Мы будем рассматривать только LL(1)-грамматики. Их класс уже достаточно широк для построения синтаксических анализаторов почти всех языков. Рассмотренные ранее s-грамматики и q-грамматики принадлежат, очевидно, классу LL(1). Еще раз рассмотрим ситуацию выбора правила при LL-разборе. Допустим, что опять выведено xA и возникла необходимость выбора одного из двух правил A и A. Пусть входная цепочка имеет вид xd..., где x – терминальная цепочка, d - терминал. Неоднозначность может возникнуть, если после применения первого правила в дальнейшем выводится xd..., и такое же начало можно получить после применения второго правила. Рассмотрим ситуации когда после применения A может получиться слово вида xd. Случай 1. Слово  не пустое и xA  x * xd . Отсюда dFirst(). Случай 2. Имеет место  * и xA  x * x * xd.; Тогда  * d, откуда xA * xAd . Теперь dFollow(). Для более удобной формализации этой ситуации введем еще одно обозначение. Направляющим множеством продукции A назовем Route(A) = First()Follow(A) при  *  , Route(A) = First() иначе. Теорема. КС-грамматика G= является LL(1)-грамматикой тогда и только тогда, когда для любых ее разных продукций вида A, A множества Route(A) и Route(A) не пересекаются. Для доказательства теоремы требуется более строгое определение LL(k)-грамматики и мы этим заниматься не будем. Однако рассуждения, на основании которых введено понятие направляющих символов достаточно ясно объясняет, что условие теоремы – это и есть то, что можно принять за строгое определение LL(1)-грамматики. Построение детерминированного автомата LL-разбора по LL(1)-грамматике. Понятно, что при построении дерева разбора, когда просматривается очередной терминальный символ d, а очередным нетерминалом является A, вопрос о том, какое из правил вида A применять, заключается в определении, в котором из множеств Route(A) лежит d. Цепочку  надо положить в стек, не передвигая указателя на ленте. Если бы  начиналась с терминала, можно было бы произвести одновременно считывание этого символа, а в стек класть укороченную на одну букву цепочку. Но для однообразия алгоритма мы этого делать не будем. Приведем пример. Грамматика G содержит правила. S  AbB|d A  CAb|B B  cSd|ε C  a|ed Сделаем необходимые вычисления Правая часть Выводимость ε First AbB - a, b, c, e d - d CAb - a,e B + c cSd - c ε + a - a ea - e Нетерминал Выводимость ε First Follow S - a, b, c, d, e d A + a, c, e b B + c b,d C - a, e a, b, c, e Направляющие множества Правило Route S  AbB a, b, c, e S  d d A  CAb a, e A  B b, c B  cSd c B  ε b, d, ε C  a a C  ed e Последняя таблица показывает, что данная грамматика является LL(1)-грамматикой. Автомат: Переход ε/B ε добавлен из-за наличия продукции B  ε. По этой же причине мы занесли ε в список направляющих нетерминалов правила B  ε, пометив его там красным цветом. Это делает построение автомата единообразным. Разбор цепочки: edcddbb . Вывод: SAbBCAbbBedAbbBedBbbBedcSdbbBedcSdbbB edcddbbB edcddbb Работа автомата: Графическое представление МП-автомата обладает наглядностью, но становится неприменим в случае сложных алгоритмов, к которым, как правило, относится синтаксический анализ языков программирования. Поэтому на практике автомат задается в виде таблицы. В общем случае может понадобиться ряд таблиц, т.к. функция переходов по существу имеет трехмерную область определения. При этом можно составлять таблицы трех разных видов. В нашем же случае, когда синтаксический анализатор осуществляет детерминированный LL-разбор, находясь практически всегда в одном состоянии w, можно ограничиться одной таблицей. Так автомат из предыдущего примера можно описать так. Строки таблицы помечены стековыми символами, столбцы – терминальными символами или символом ε. В клетках содержатся действия автомата при переходах из w в w. Стек\Лента a b c d e ε S AbB AbB AbB d AbB Err A CAb B B Err CAb Err B Err  ε cSd  ε Err  ε C a Err Err Err  ed Err a  Err Err Err Err Err b Err  Err Err Err Err c Err Err  Err Err Err d Err Err Err  Err Err e Err Err Err Err  Err  Err Err Err Err Err OK Здесь: • запись  означает замену верхнего символа стека на цепочку  ; • запись  означает выталкивание верхнего символа стека и одновременное движение указателя входной цепочки; • запись Err указывает на ошибку, отвергающую входную цепочку; • запись OK – успех, т.е. цепочка воспринята. Таким образом для реального программирования синтаксического анализатора достаточно: • Сделать лексический анализ. • Описать данный язык на уровне лексем в нотации Бэкуса-Наура. • Получив соответствующую КС-грамматику определить, является ли она LL(1)- грамматикой. Если нет – найти ей эквивалентную LL(1)- грамматику. • По полученной LL(1)- грамматике составить выше указанную таблицу. • Реализовать структуру “Стек”. • С помощью таблицы написать программу, моделирующую работу МП-автомата и выдающую по ходу работы необходимую информацию. LL-разбор считается одним из самых простых и понятных способов построить синтаксический анализатор. Вместе с тем он и наиболее слабый. В настоящее время разработан и с успехом применяется более мощный метод LR-разбора, когда дерево разбора строится не сверху вниз, а снизу вверх.