Синтаксический анализ с использованием автомата с магазинной памятью

Программирование Технология и методы программирования Спортивное программирование Теория трансляторов Синтаксический анализ с использованием автомата с магазинной памятью

Помечено: 

  • В этой теме 0 ответов, 1 участник, последнее обновление 1 неделя, 5 дней назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6292
      @admin

      Наличие у конечного автомата внутренних состояний позволяет ему запоминать историю поступающих входных воздействий. На один и тот же входной символ автомат может по-разному реагировать, поскольку его реакция определяется не только этим входным символом, но и тем, в каком внутреннем состоянии автомат находится в данный момент. Поэтому конечные автоматы называют ещё последовательностными схемами, так как по внутреннему состоянию автомата можно судить о том, какова была последовательность символов, поступившая на его вход. Однако, конечной автомат не запоминает историю переходов между внутренними состояниями. И поэтому, как уже было сказано ранее, не любой язык, как множество последовательностей символов (строк), под силу распознавать конечному автомату. Если синтаксис предложений языка невозможно описать регулярными выражениями, то и невозможно сконструировать конечный автомат, способный понимать эти предложения. Одним из простейших примеров такого языка является бесконечное множество предложений типа:

      $$
      \underbrace{x…x}_{n} \; \underbrace{y…y}_{n}, \; где\;n=1,2,…
      $$

      Синтаксис этого языка можно описать правилами КС-грамматики:

      S ::= x y |x S y

      По этим правилам можно сконструировать автомат магазинного типа, принимающий такой язык, в соответствии со схемой:

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

      В общем случае, принимающим для КС-языка является недетерминированый автомат магазинного типа. Ограничимся рассмотрением двух частных случаев КС-языков, для которых возможно построение детерминированных распознавателей: LR(k)-языки и LL(k)-языки. Такие наименования типы этих языков, естественно, получили от типов грамматик, которыми они описываются. Буквой k здесь обозначено целое число, указывающее количество символов исходного текста, которые автомат может считать текущим входным воздействием. Другими словами, k — это длина заголовка каждого столбца управляющей таблицы. Практическую ценность представляют такие грамматики, у которых k = 1. О них в дальнейшем и пойдёт речь:

      1. LR(1)-разбор;
      2. LL(1)-разбор.

      LR(1)-разбор

      Автоматом, построенным на основе LR(1)-грамматики, реализуется алгоритм разбора, относящийся к классу восходящих, так же, как и алгоритм разбора, реализуемый конечным автоматом. В стеке всегда находится некоторое количество имён внутренних состояний автомата. Имя, находящееся в вершине стека, — это имя текущего внутреннего состояния. Координаты ячейки управляющей таблицы, откуда должна быть выбрана очередная команда, определяются так же, как и в случае конечного автомата: внутреннее состояние определяет координату строки, текущий сканируемый символ исходного текста – координату столбца.

      Сконструируем автомат магазинного типа, принимающий язык строк символов x и y, упомянутый выше. Первыми символами предложения языка могут быть только символы x. Принимая их в качестве входного воздействия, автомат должен сохранять некое внутреннее состояние, но при этом запоминать, сколько на его вход поступает символов x, заставляющих его переходить из текущего внутреннего состояния в него же. Запоминание необходимо для того, чтобы в дальнейшем можно было проконтролировать равенство количеств символов x и y, а реализуется запоминание стеком, в который помещается имя одного и того же внутреннего состояния с каждым новым поступлением символа x. Назовем это состояние, например, "учёт x". Приход символа y должен перевести автомат из состояния «учёт x» в состояние «учёт y». И теперь каждое новое поступление на вход автомата символа y должно удерживать его в состоянии "учёт y", но при этом сопровождаться возвратом по истории смены состояний на 2 шага назад, то есть удалением двух записей из стека. Одна из удаляемых записей это — "учёт y", а вторая — "учёт x". Если анализируемый текст синтаксически верен, то есть для каждого y найдется парный ему x, и наоборот: для каждого x найдется парный ему y, то по окончании сканирования исходного текста в стеке должна остаться одна пара состояний «учёт y»-«учёт x» и начальное состояние. Имеет смысл удалить из стека и эту пару записей, и, таким образом, заключительной конфигурацией автомата, соответствующей успешному окончанию распознавания исходного текста, можно считать следующую: текст полностью прочитан, в стеке — начальное состояние.

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

      Словом «допуск» в таблице обозначена команда успешного окончания разбора исходного текста, а пустые ячейки таблицы считаются содержащими команду «ошибка» — неуспешного окончания разбора.

      Распознавание, например, строки xxyy будет выполнено за 5 шагов:

      При этом неявно выстраивается в направлении снизу вверх такое дерево:

      Каждая инструкция удаления из стека двух записей, можно сказать, предписывает построение очередного уровня дерева. Две записи, удаленные первыми из стека, соответствуют правой части правила S::= x y, состоящей из двух символов. Шаг восходящего разбора заменяет правую часть правила на левую, и все последующие удаления из стека — это применения правила S := x S y, длина правой части которого равна трём. Но поскольку символ S явно в стек не помещался, на последующих шагах разбора также удаляется по две записи.

      Та же самая процедура восходящего разбора строки xxyy может быть изображена последовательностью получаемых сентенциальных форм:

      Строка xxyy исходного текста, в конечном итоге, свернулась в аксиому S, что свидетельствует о синтаксической правильности этой строки.

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

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

      Пусть, в отличие от предыдущего варианта автомата, внутренние состояния будут поименованы не длинными идентификаторами (несущими, правда, в себе некий смысл, приписанный внутренним состояниям), а просто числами натурального ряда. Тогда первое правило рассматриваемой грамматики можно разметить так:

      $$
      S ::= \;_1 x_2 S_3 y_4
      $$

      Состояние, имя которого находится в начальной позиции правила для аксиомы, в дальнейшем будет считаться начальным. В нашем случае имя начального состояния — 1. Для детерминированного автомата, естественно, начальные позиции всех правил для аксиомы должны быть отмечены именем начального состояния. Поэтому 1 попадёт и в начальную позицию второго правила рассматриваемой грамматики:
      $$
      S ::= \;_1 x y.
      $$
      Нетрудно догадаться, что по бокам символа в размеченном правиле находятся имена внутренних состояний, между которыми возможен переход. При этом сам символ должен рассматриваться как входное воздействие, из-за которого выполняется переход, слева от символа — имя исходного состояния, справа — имя состояния перехода. Так из разметки первого правила следует, что из состояния 1 под воздействием символа x автомат переходит в состояние 2. И поскольку детерминированный автомат из состояния 1 под воздействием символа x не имеет права переходить ни в какое другое состояние, кроме уже обнаруженного состояния 2, во втором правиле, где уже слева от x появилось 1, справа от x следует поместить 2.

      Обобщая эту ситуацию, можно сказать, что если в нескольких правилах слева от одного и того же символа оказалось имя одного и того же состояния, то и справа от этого символа следует поместить одинаковые имена (метки) состояний. Таким образом, второе правило рассматриваемой грамматики теперь будет размечено так:
      $$
      S ::= \;_1 x_2 y_5
      $$

      Конфигурации
      $$
      \;_2S_3
      $$
      , получившаяся при разметке первого правила, предполагает имитацию чтения символа S из исходного текста (в исходном тексте не может быть нетерминальных символов), в результате которой осуществляется переход из состояния 2 в состояние 3. Необходимость такой манипуляции вытекает из необходимости провести автомат по всей правой части правила слева направо (в данном случае — от состояния 1 до состояния 4 в первом правиле, или от состояния 1 до состояния 5 во втором правиле) и прийти к заключению, что правая часть правила в сентенциальной форме может быть заменена на левую, то-есть может быть выполнен очередной шаг восходящего разбора. Эта замена сопровождается удалением из стека истории прохождения автомата по данному правилу и последующей имитацией чтения нетерминала левой части правила из исходного текста. Удаление из стека фактически возвращает автомат в состояние, из которого он начинал проход по этому правилу, поскольку имя именно этого состояния после удаления оказывается в вершине стека. Следовательно, при разметке необходимо позаботиться о том, чтобы имя состояния, стоящего перед нетерминалом, распространилось на начальные позиции всех правил для этого нетерминала (тех правил, где он является левой частью). В рассматриваемых правилах это относится только к имени 2, стоящему перед S.

      Окончательно разметка грамматики получается такой:

      $$
      S ::= \;_{1,2} x_2 S_3 y_4 |_{1,2} x_2 y_5 .
      $$

      В управляющую таблицу заносятся команды двух типов (не считая команды завершения разбора): перехода (сдвига) и свёртки (приведения). О местах размещения в таблице команд перехода уже было сказано достаточно. Команды свёртки (замены правой части правила на левую) изобразим для начала правилами, по которым выполняется свёртка, хотя для исполнения такой команды нужно знать только длину правой части правила и нетерминал левой части. Длина правой части правила определяет количество записей, которые следуют удалить из стека, нетерминал левой части — имитируемое впоследствии входное воздействие. Место в таблице для команды свертки определяется следующими соображениями. Свёртка должна выполняться тогда, когда автомат оказался в состоянии, соответствующем последней (крайней справа) позиции правила. В рассматриваемом примере это — состояния 4 и 5. При этом допустимыми входными воздействиями являются те символы, которые в какой-либо сентенциальной форме могут оказаться непосредственно справа от нетерминала, к которому сворачивается правая часть правила. (Такие символы называются символами-следователями). Справа от нетерминала S, единственного нетерминала в рассматриваемом примере, может находиться символ y (это явно видно в первом правиле грамматики). Кроме того, для аксиомы всегда символом-следователем, в числе возможных прочих, считается маркер правого конца строки. Поскольку маркер присутствует в первоначальной для восходящего разбора сентенциальной форме (на конце строки исходного текста), очевидно, что он сохранится и в заключительной сентенциальной форме (после аксиомы, в которую свернётся строка исходного текста). С учётом этого замечания схему последовательности сентенциальных форм, приведённую выше, можно дополнить маркером $:

      Таким образом, выполненной разметке грамматики соответствует следующая управляющая таблица:

      Её размер оказался несколько большим размера первоначальной таблицы для такой грамматики из-за учёта дополнительных действий имитации чтения нетерминального символа. Распознавание всё той же строки xxyy$ теперь выполняется за 8 шагов:

      В этой схеме ещё раз обратим внимание на выполнение команд свёртки. В момент чтения второго символа y автомат находится в состоянии 5. По координатам (5,y) из таблицы выбирается команда S ::=x y с длиной правой части правила, равной 2. Поэтому, исполняя эту команду, из стека следует удалить 2 записи и перейти к имитации чтения символа S. Аналогично выполняется команда S ::= x S y, выбранная по координатам (4, $). Но в этом случае из стека следует удалить 3 записи, поскольку длина правой части применяемого правила равна 3.

      LL(1)-разбор

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

      Для рассматриваемого языка строк из x и y предложение xxyy может быть выведено за 2 шага:

      S => x S y => xxyy

      На каждом шаге нисходящего разбора приходится решать 2 вопроса: какой нетерминал в текущей сентенциальной форме подлежит замене на правую часть правила, и правую часть какого правила следует выбрать для такой замены, если для нетерминала в грамматике есть несколько правил. LL(1)-разбор на первый из этих вопросов отвечает так: замене подлежит самый левый нетерминал текущей сентенциальной формы. Ответ на второй вопрос определяется единственным сканируемым символом исходного текста (в случае LL(k)-разбора — k сканируемыми символами исходного текста): из нескольких правых частей правил выбирается та, для которой сканируемый символ является терминальным префиксом всех выводимых из нее строк. Для того, чтобы такой выбор был однозначным, необходимо, чтобы эти альтернативные правые части правил имели различные терминальные префиксы выводимых из них строк.

      В рассматриваемом примере это требование, предъявляемое к грамматике, не выполняется: строки, выводимые из x S y, и строки, выводимые из x y, имеют один и тот же терминальный префикс — символ x. Эта грамматика не может быть использована алгоритмом LL(1)- разбора. Другими словами, она не обладает свойством LL(1).

      Однако существует другая грамматика, описывающая тот же язык и обладающая свойством LL(1).Чтобы получить её из исходной грамматики, следует два конфликтующих правила для нетерминала S объединить в одно: S ::= xZ. При этом новый нетерминал Z определяется двумя правилами, полученными из «остатков» правил для S после вынесения из них префикса x: Z ::=S y|y. Альтернативные правые части правила для Z имеют различные терминальные префиксы выводимых из них строк. Префиксом строк, выводимых из S y, является x. А символ y сам является префиксом и строкой, выводимой из второго правила для Z.

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

      Управляющая таблица для LL(1)-разбора, построенная на базе LL(1)-грамматики языка строк из x и y, выглядит так:

      Выполнение команд, представленных правилами, заключается в вышеупомянутой подстановке правых частей этих правил вместо левых частей. Команда «выброс» выполняется в ситуации совпадения символа в вершине стека с символом, читаемым в исходным тексте. Её выполнение заключается в удалении символа из вершины стека и перемещении по исходному тексту для чтения следующего справа символа.

      Команды «допуск» и «ошибка»( как и ранее, считаем, что пустые ячейки таблицы содержат команду «ошибка»), прекращают разбор с, соответственно, успешным или неуспешным результатом.

      В начальной конфигурации алгоритма на дне стека находятся 2 записи: маркер дна и аксиома.

      Разбор строки xxyy$ выполняется за 9 шагов:

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.