Вопросы для самопроверки

1. С чем связана способность МП – автомата проводить нисходящий разбор?

2. С чем связана способность МП – автомата проводить восходящий разбор?

3. Как можно сформулировать проблему разбора входной цепочки моделированием МП – автомата?

Синтаксический анализ «сверху вниз»

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

При решении задачи синтаксического разбора строки вида х= =а1,а2…аnЄL(G)используют, как правило, один из двух основных методов. Первый из них заключается в построении дерева вывода, корень которого помечен символом S, а листьями являются узлы, помеченные символами а1,а2…аn.

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

Нисходящий разбор

Пусть p = 1,2,3,… k – левый разбор цепочки W Î L(G). Зная p, можно построить дерево разбора. Начинают с корня, помеченного начальным символом.

Пусть 1-е правило имеет вид S = x₁,…,x_k. Нужно присоединить k потомков к вершине S. Если x_i – первый слева – нетерминал, то 2-е правило будет иметь вид x_i = y₁…y_e. По этому принципу строим все дерево.

Простая СУ – схема: Т=íN, S, D, R, Sý отображает разбор в левом или правом выводе.

Правила из R, которые имеют вид А:=a, b, представим в виде

A:= a, ia^’ , где i – номер правила.

a^’:= b\T (в цепочке b удалим все терминальные символы) .

Нисходящий преобразователь (распознаватель)

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

В простейшей форме метод рекурсивного спуска предоставляет удобную возможность построения лексического анализатора (распознавателя символов) языка, порожденного LL(1)-грамматикой G=(N, S, P, S). Такой лексический анализатор каждому символу из множества N S ставит в соответствие единственную процедуру, с помощью которой для любой строки языка можно однозначно определить, выводима она из этого символа или нет.

Пусть имеем грамматику G(N, S, P, S), в которой правила занумерованы от 1 до р.

А также недетерминированный нисходящий распознаватель М1. Тогда его называют левым анализатором. То есть он моделирует левый вывод в грамматике G по правилу:

d (q, e, A) = (q, a, i) A:= a. (i – номер правила, записывается в выходную цепочку).

Анализатор каждый раз развертывает нетерминал, распознанный наверху магазина, в соответствии с некоторым правилом из Р, а также одновременно выдает номер этого правила.

Если наверху магазина находится терминальный символ, то М1 по правилу:

d (q, а, а) = (q1, е, е) проверяет, совпадает ли он с соответствующим символом во входной цепочке.

М_L {(q₀,q₂), (*,+,(,),i), (N T $), (1,…,6), (d, q₀, $, q₁)};

(*,+,(,),i) – входной алфавит;

(N T $) – алфавит магазинных символов;

(1,…,6) – номера правил на выходе;

q₀ – начальный символ автомата;

$ - начальный символ магазина;

Q*E*Г -> Q*Г^**D^*.

1. (q₀, e, E) = (q₀, E+T, 1);

2. (q₀, e, E) = (q₀, T, 2);

3. (q₀, e, T) = (q₀, T*F, 3);

4. (q₀, e, T) = (q₀, F, 4);

5. (q₀, e, F) = (q₀, (E), 5);

6. (q₀, e, F) = (q₀, i, 6);

7. (q₀, a, a) = (q₀, e, e);

8. (q₀, e, $) = (q₀, e, p) p - левый разбор цепочки.

(q₀, i*(i+i), E, e) |¾ (q₀, i*(i+i), T, 2) |¾

(q₀, i*(i+i), T*F, 23) |¾ (q₀, i*(i+i), F*F, 234) |¾

(q₀, i*(i+i), i*F, 2346) |¾ (q₀, *(i+i), *F, 2346) |¾

(q₀, (i+i), F, 2346) |¾ (q₀, (i+i), (E), 23465) |¾

(q₀, i+i), E), 23465) |¾ (q₀, i+i), E+T), 234651) |¾

(q₀, i+i), T+T), 2346512) |¾ (q₀, i+i), F+T), 23465124)|¾

(q₀, i+i), i+T), 234651246) |¾ (q₀, i), T), 234651246) |¾

(q₀, i), F), 2346512464) |¾ (q₀, i), i), 23465124646) |¾

(q₀, e, e, 23465124646) |¾ (q₁, e, e, 23465124646)

Левый анализатор – недетерминированная процедура. Чтобы ею пользоваться, необходимо уметь моделировать ее детерминированно. Существует класс грамматик (L,L), для которых левый разбор можно делать детерминированным. Для этого анализатору необходимо предоставить возможность, которая при считывании входной (исследуемой) цепочки позволяла бы заглядывать на k символов вперед, и очередной шаг делался бы после анализа полученной информации.

L, L – означает, что читается слева направо, и выдается левый разбор.

L, R - означает, что читается слева направо, и выдается правый разбор.

Левые и правые разборы используются в зависимости от той или иной грамматики.