МП-автоматы

20. МП-автоматы Основная цель курса - изучение подходов к построению синтаксического анализатора языка программирования высокого уровня. Главное, что делает синтаксический анализатор - построение дерева разбора для подаваемой на вход цепочки символов. А цепочкой этой является текст компилируемой программы. Практически все языки полностью описываются с помощью нотации Бэкуса-Наура, т.е. посредством контекстно-свободной грамматики. Как мы увидим, не любая КС-грамматика годится для того, чтобы на ее основе строить синтаксический анализатор. Тем не менее мы начнем с дальнейшего изучения КС-грамматик в общем виде. На очереди описание КС-языков с помощью автоматов с магазинной памятью (МП-автоматов). Автомат с магазинной памятью (МП-автомат) это структура A = < Q,T, M ,  , s, F> где: Q,T, M – конечные множества (состояний, терминалов, магазинных символов),  : Q (T {})(M {})  P(QM*) – функция, s  Q – начальное состояние, F  Q. – множество заключительных (конечных) состояний,  – символ, обозначающий пустое место. P(S) – множество всех подмножеств множества S, включая пустое. M* - множество слов алфавита M, включая пустое слово. Общая схема МП-автомата представлена на рисунке  – это функция переходов. Если (q,)   (p,a,A), то это понимается как команда, согласно которой: 1) автомат из состояния p переходит в состояние q; 2) если a и a – символ входной цепочки в обозреваемой клетке, то указатель с этой клетки переходит на соседнюю клетку справа (обработка символа a); при a= указатель остается на месте; 3) если A и A - верхний символ стека, то: • при    символ A в вершине стека заменяется символами  - одна буква на одну ячейку стека по очереди справа налево (первая буква  окажется на вершине стека); • при  =  символ A из стека выкидывается; 4) если A=, то: • при    в стек кладется слово  (как в п.3); • при  =  стек не меняется. При изображении управляющего устройства МП-автомата в виде графа описанная выше команда изображается на ребре, идущем из состояния r в состояние p, в виде метки a/A Для изображения меток используем соглашения: вместо /A пишем A; вместо пишем ; вместо  не пишем ничего; Конфигурация – это информация о состоянии автомата, которая полностью определяет возможности его дальнейшего поведения. Конфигурация включает информацию о текущем состояни, о непрочитанном еще содержимом ленты и о содержимом стека. Записывается конфигурация в виде тройки , где p - состояние,  - цепочка терминалов на ленте от текущего указателя (непрочитанная часть),  - содержимое стека (при  =a1a2…an a1– верхний символ стека, a2 - символ под ним и т.д.) Если согласно какому-то (q,)   (p,a,A) автомат из конфигурации может перейти в конфигурацию , то пишем  . Транзитивное замыкание этого отношения обозначаем как *. Начальной или стартовой конфигурацией МП-автомата является конфигурация . Конечной или заключительной называется любая конфигурация вида при условии, что p – одно из заключительных состояний. Говорим, что цепочка  терминалов воспринимается автоматом, если * для некоторой заключительной конфигурации . Множество всех цепочек, воспринимаемых автоматом A, называется языком, который распознает A, и обозначается L(A). Если для языка L существует такой автомат A, что L = L(A), то язык L называется МП-автоматным. Два МП-автомата A1 и A2 называются эквивалентными, если L(A1)= L(A2). 21. Левый разбор в КС-грамматиках Наша ближайшая цель – установить связь между КС-грамматиками и МП-автоматами. Эта связь формулируется просто: язык тогда и только тогда определяется какой-то КС-грамматикой, когда он определяется каким-то МП-автоматом. Для доказательства этого утверждения а также для конкретных приложений языков и автоматов при построении компиляторов нам надо вернуться к понятию вывода в КС-грамматиках и познакомиться с понятием лево-стороннего нисходящего разбора (LL-разбора). Рассмотрим пример грамматики S  AaD A  Bb|a B  CcA C  d D  Ae В грамматике выводима цепочка dcdcabbaae: S  AaD  BbaD  CcAbaD  CcAbaAe  CcAbaae  dcAbaae  dcBbbaae  dcCcAbbaae  dcCcabbaae  dcdcabbaae. Дерево разбора этой цепочки есть Нисходящим левым разбором называется построение этого дерева от вершины и вниз слева направо и параллельный вывод: Соответствующий вывод: S  AaD  BbaD  CcAbaD  dcAbaD  dcBbbaD  dcCcAbbaD  dcdcAbbaD  dcdcabbaD  dcdcabbaAe  dcdcabbaae. Предложение. В выводе цепочки, соответствующем левому разбору, на каждом шаге происходит замена самого левого нетерминала на какую-то цепочку. Понятно, что левый нисходящий разбор строится по дереву разбора единственным образом. Если бы рассматриваемая грамматика была однозначной, то, стало быть, этот разбор дал бы определение некого канонического вывода для всех цепочек. Однозначными являются многие грамматики. Но поиск эффективного метода построения левого нисходящего разбора не для каждой из них может быть успешно осуществлен. 22. МП-автоматы и КС-грамматики Теорема. Класс языков, распознаваемых МП-автоматами, совпадает с классом контекстно-свободных языков. Доказательство. Пусть G – произвольная КС-грамматика. Строим по ней МП-автомат A. Делаем следующее. 1) Множество терминалов T у A и у G общее. 2) Множество состояний Q автомата состоит из трех символов : s, w, f. 3) M – стековые символы – есть множество T N {} терминалов и нетерминалов грамматики вместе с добавочным символом , который будем называть маркером дна стека. 4) Определяем переход из s в w с меткой/S. 5) Каждой продукции A сопоставляем переход из w в w с меткой /A. 6) Каждому терминалу a сопоставляем переход из w в w с меткой a / a.. 7) Определяем переход из w в f с меткой/. 8) Состояние f делаем заключительным. Рисунок схематически изображает устройство A. Докажем, что L(A) = L(G). Для начала проиллюстрируем это примером. Пусть G состоит из правил S ABc, A Aa|b, B aS|Ab. Рассмотрим вывод S ABc  AaSc  AaABcc  AabBcc  babBcc  babAbcc  babbbcc Теперь представим, что слово babbbcc находится на ленте автомата. Начиная работу, он из стартового состояния s может попасть в w. Чтения ленты при этом не происходит, а в стек запишется S: . Далее мы пробуем организовать работу автомата синхронно с выводом. В выводе на первом шаге применяется продукция SABc. Ей соответствует переход автомата с меткой /S ABc, который опять не затрагивает ленту, а только заменяет в стеке верхний символ S на ABc. Получим . Далее произойдет заминка потому, что в выводе заменяется буква B, а автомат с этой B ничего сделать не может. Затруднение будет снято, если перестроить вывод цепочки: рассмотреть дерево разбора и по нему построить соответствующий левому разбору вывод. В результате получим S ABc  bBc  baSc  baABcc  babBcc  babAbcc  babbbcc Теперь на втором шаге первая буква A меняется на b и в автомате есть соответствующий переход с меткой /A b. Это позволит заменить верхнюю букву A в стеке на b: . Как видим до сих пор содержимое стека полностью совпадает с тем, что получается в выводе. Но дальше автомат может применить только правило b/b . Это значит, что с ленты считывается символ b и он же выталкивается из стека: . Дальнейшее содержимое стека меняется так: , , , , , , , , , , Наконец маркер дна выталкивается и автомат переходит в заключительное состояние f. Теперь нетрудно догадаться как строго доказать эквивалентность грамматики и построенного по ней автомата. Допустим, что в грамматике S * . Рассматриваем левый вывод этой цепочки. Доказываем, что если цепочка A1 – одно из слов этого вывода, причем , состоит только из терминалов, A - некоторый нетерминал, то автомат, распознавая цепочку , может прийти к конфигурации <, w, A1>, причем  = . Другими словами, если к считанной части цепочки приписать содержимое стека (без ), то полученное слово есть одна из цепочек вывода. Действительно, первое слово вывода есть S и ему соответствует конфигурация <, w, S> автомата. Далее по индукции, если из A1 на следующем шаге выводится слово с нетерминалом, то это есть результат замены A на некоторую цепочку согласно какой-то продукции вида A abc...B или A abc.... Тогда в автомате есть переход из w в w с такой же меткой и автомат может перейти к конфигурации <, w, abc...B1> или к <,w, abc... 1>. Цепочка  - еще не распознанная часть  - обязана начинаться с abc.... Поэтому серия переходов из w в w с метками a/a , b/b , c/c ,... даст конфигурацию <1, w, B1> или <1, w, 1>, причем  = abc... 1. Это завершает индукционный переход. Следующая картинка иллюстрирует это рассуждение. Пререход Автомат Стек и указатель автомата В момент, когда в выводе исчезает последний нетерминал, в стеке автомата также не останется нетерминалов и серией переходов вида a/a стек избавляется от терминалов, а слово  считывается до конца. Остается применить переход /. Пусть, обратно, автомат воспринимает цепочку . Тогда он на последнем шаге обязан применить /. А перед этим в его стеке кроме маркера дна ничего не может остаться. На предыдущих шагах, на считая очевидного первого, как и раньше, если к считанной части цепочки приписать содержимое стека (без ), то полученное слово выводится из S. Это столь же легко доказывается по индукции. Тем завершено доказательство того, что L(A) = L(G). Теперь для продолжения доказательства теоремы следует по произвольному стековому автомату A построить эквивалентную ему КС-грамматику G. Сначала переделаем A в автомат немного более “приличного” вида. Построим по A автомат A1 следующим образом: 1. Введем три новых состояния s, g, f. Состояние s будет новым стартовым состоянием – из него проводим ребро в прежнее стартовое с меткой / . Здесь  - новый стековый символ, который называем маркером дна согласно предназначенной для него роли. 2. Из всех конечных состояний исходного автомата создаем переходы в g с меткой / . 3. Для каждого стекового символа Z исходного автомата добавляем петлю из g в g с меткой /Z  и добавляем переход из g в f с меткой / . 4. Все конечные состояния исходного автомата выкидываем из множества конечных, а единственным заключительным состоянием делаем состояние f. Лемма 1. Автоматы A и A1 эквивалентны. Доказательство. Очевидно. Кроме того, что у A1 единственное заключительное состояние, этот автомат обладает еще одной важной особенностью. Стартуя в s, он кладет в стек маркер дна и этот маркер остается там до момента перехода в заключительное состояние. В конце работы стек полностью опустошается. По автомату A1 построим A2. Цель – сделать так, что все команды со стеком были только таких двух видов: либо U, либо  U, где U – стековый символ. Для этого: 1. Каждый переход с меткой a/AB1B2... Bn из состояния p в состояние q, где aT или a=, AM или A=, B1,B2,...,BnM, n>1, заменяем цепочкой используя для этого новые состояния. 2. В каждый переход a/AB встраиваем новое состояние с переходами a/A и B. 3. В каждый переход a/, где aT или a=, встраиваем новое промежуточное состояние с переходами a/U и /U для нового магазинного символа U. Лемма 2. Автомат A1 эквивалентен автомату A2. Доказательство. Очевидно. Продолжение доказательства теоремы. Для доказательства теоремы в обратную сторону надо по МП-автомату построить эквивалентную ему грамматику. По лемме 2 существует МП-автомат, эквивалентный данному, с единственным заключительным состоянием, у которого на каждом шаге либо один символ кладется в стек, либо один символ выкидывается из стека. Кроме того этот автомат устроен таким образом, что если он воспринял какую-то цепочку, то в момент остановки его стек становится пустым. По этому автомату КС-грамматика строится так. Для любой пары состояний вводится нетерминал Ap,q. Далее в грамматику заносятся: продукции Ap,p для всех состояний p автомата; продукции Ap,w aAq,r bAv,w для всех состояний p,q,r,v,w автомата, переходов и . и магазинных символов X. Здесь a,b либо терминалы, либо пустые цепочки. Начальным нетерминалом грамматики является символ As,f, где s – начальное состояние автомата, f – конечное. Нетерминалу Ap,q придается такой смысл: он обозначает множество всех терминальных цепочек, которые может прочитать автомат при переходе из состояния p в состояние q при условии, что он начинает с пустого стека и заканчивает пустым стеком. Суть рассуждения, которое мы не будем проводить в деталях, заключается в следующем. Предположим, что автомат совершил путешествие из состояния p в состояние q и по пути распознал цепочку  в указанном выше смысле. Т.к. он начинает с пустого стека, то на первом шаге он кладет в стек какой-то символ X. Это переход . А т.к. автомат заканчивает пустым стеком, этот X должен удалиться на каком-то переходе . На пути от q до r автомат работает, начиная с X в стеке, и так же заканчивает. При этом он прочитывает какую-то терминальную цепочку . Если бы этого X в стеке не было, то поведение автомата на этом участке никак бы не изменилось, т.е. он начиная с пустого стека прочитал бы на этом пути от q до r ту же цепочку и оказался бы в q при пустом стеке. Значит  из тех, совокупность которых обозначает нетерминал Aq,r. Далее автомат выкидывает X из стека, считывая b, и из состояния v как-то добирается до w опять начиная и заканчивая пустым стеком. Значит считанная на этом участке цепочка  лежит в классе Av,w. Теперь понятно, почему  = ab соответствует aAq,r bAv,w.