Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

• > e= I { область };

=e II { область };

<• e III { область }.

Вобоих случаях в матрицах не имеют места два вида отноше­

ний предшествия для любой пары (т. е. нет клетки с символами

2.8.4. Метод Наура

Основная идея разбора заключается в следующем: фраза обра­ батывается терминал за терминалом в одном направлении — слева направо (канонический метод разбора). Для каждого очередного терминала формируется определенное синтаксическое состояние, т. е. предсказывается, какая конструкция может следовать в дан­ ной фразе за этим терминалом. Если следующий терминал удовлет­

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

Логику действия грамматического разбора можно описать таб­ лицей (табл. 2), которая включает: 1) основную строку, где поме­ щены основные символы (терминалы) языка; 2) основной столбец, где перечисляются синтаксические состояния. Столбец является спе­ цифической особенностью данного метода — его можно изобразить:

140

а) либо в общей таблице, где сначала записываются синтаксиче­ ские состояния, и на пересечении с определенным терминалом за­ писан текущий номер состояния; б) либо рассматривать как две синтаксические таблицы, одна из. которых по данному синтаксиче­ скому состоянию определяет «начало», а другая «конец» возмож­ ных конструкций; 3) как рабочую зону, в которой записываются но­ мера новых состояний, полученных из комбинации: элемент столбца «состояние» — элемент строки «терминал».

Поскольку содержимое основной строки и основного столбца в процессе разбора не меняется, то терминалы и синтаксические со­ стояния используются как справочники.

В отличие от них рабочая зона (называемая еще накопитель синтаксических состояний)—это место, где происходит переработ­ ка всех промежуточных результатов. Ее можно сравнить и рассмат­ ривать как неограниченное число стэков. В каждом стэке ввод осу­ ществляется по одному терминалу и только с одного конца зоны. Так что терминал, введенный в стэк последним, вынимается из не­ го первым.

Изложенная идея синтаксического анализа методом Наура име­ ет некоторое сходство с принципом работы машины Тьюринга с тремя лентами.

Вкратце изложим этот принцип. Машина Тьюринга имеет три ленты, ограниченные слева и неограниченные справа: а) входная — на ней расположен словарь языка (основные символы); б) рабо­

типов конструкций, и три головки (по одной на каждой ленте).

На каждом шаге машина работает только на одной ленте, вы­ полняя одно изследующих действий:

1) на входной ленте читается символ за символом, сдвигая го­ ловку на одну ячейку вправо;

2) на рабочей ленте либо пишется символ и головка сдвигает­ ся на одну ячейку вправо, либо на одну ячейку влево и стирается записанный в ней символ, но после такого действия всегда влево от головки остаются непустые ячейки, а вправо — пустые;

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

141

Работа машины начинается при пустых рабочей и выходной лен­ тах. Непустой остается только входная лента, содержащая основ­ ные символы языка. Головки всех лент при этом находятся в край­ не левом положении.

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

Отличие метода Наура от принципа работы машины Тьюринга заключается в следующем:

1)состояния, которые могут встретиться в процессе граммати­ ческого разбора, были явно перечислены, т. е. помещение синтакси­ ческих состояний в стэк всегда непосредственно обусловливается прочтением очередного терминала на рабочую ленту;

2)в машине Тьюринга разрешается писать на рабочей ленте за один шаг только один символ, тогда как при грамматическом раз­ боре иногда читается сразу несколько символов (терминалов).

Синтаксические состояния Наур рассматривает как эквивалент­ ные, при этом каждое состояние характеризуется своим номером. Текущий номер должен давать описание ситуации достаточное для того, чтобы полностью определить действия при выборе следующе­ го терминала на входе, включая определение нового текущего со­ стояния.

Каждый шаг анализа состоит в обработке одного терминала. При этом выполняется: проверка, может ли данный терминал на­ чинать предсказанную синтаксическую конструкцию. Это делается путем сравнения номера терминала с рабочим состоянием >в стэке, т. е. ищется соответствующая пара «терминал-состояние» в общей таблице (если представлены две таблицы в таблице «начало»). Ес­ ли ответ отрицательный, продолжение анализа невозможно. Если ответ положительный, то эта конструкция определена и дальше можно делать одно из двух:

а) в предположении, что начатая конструкция продолжается, выбирается любое другое синтаксическое состояние из состояния рабочего терминала, и помещается в верхнюю часть стэка, после чего осуществляется переход к следующему шагу (т. е. к следую­ щему терминалу);

б) в предположении, что начатая конструкция заканчивается этим рабочим терминалом, в общей таблице отыскивается соответ­ ствующее состояние и тем самым проверяется, может ли данный терминал заканчивать эту конструкцию. Если нет, продолжение анализа невозможно, если да, то это означает конец конструкции, и соответствующее состояние убирается из стэка. Эту операцию можно повторить любое количество раз в зависимости от началь­ ных вариантов.

Далее следует переход к очередному шагу анализа. Анализ счи­ тается законченным, а результат его правильным, если после обра­ ботки последнего терминала фразы стэк оказывается простым.

В некоторых вариантах возможна ситуация, когда на некото­ ром шаге не оказывается ни одного допустимого продолжения, а обработка фразы еще не окончена. Это означает, что либо анали-

142

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

Все рассмотренные методы грамматического разбора (синтак­ сического анализа) зависят от конкретных особенностей языков.

Была высказана идея построения универсальных алгоритмов синтаксического анализа и контроля не зависящих от конкретных

анализа и контроля ТС-М (ориентированного на класс алгоритми­ ческих языков, задаваемых рекурсивно полными грамматиками) разработан в Академии наук Молдавской ССР и реализован на ЭВМ «Минск-22».

Упражнения:

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

методом Эйкеля, Паула, Бауэра, Замелзона.

143

3. Используя метод грамматического разбора Эйкеля, Паула, Бауэра и Замелзона, проконтролировать грамматическую правиль­ ность следующих терминальных цепочек, определяя способ чтения цепочки в процессе построения алгоритма:

а) ххху, хххг при

если схема правил вывода P2G — грамматики, порождающей приве- , денные выше предложения, имеет вид:

Р = {<выражение> : : = < т е р м > | < в ы р а ж е н и е > + + < т е р м > | < в ы р а ж е н и е > — < т е р м >

< т е р м > : : = <множитель> | < т е р м > X < м н о ж и т е л ь > / < т е р м > / < м н о ж и т е л ь > ,

144