Алгоритм дейкстры

Алгоритм Дейкстры представляет собой менее формализованный вариант метода операторных грамматик. Он интересен нам прежде всего с исторической точки зрения.

Пусть имеется следующая грамматика инфиксных арифметических выражений:

EE+T|E–T

ET

TT*F|T/F

T  F

F  F ^ P

F  P

P  (E)

P  a

Каждой операции ставится в соответствие некоторый приоритет, а именно:

+, - 2 *, / 3 ^ 4

Эти приоритеты отражают старшинство операций умножения и деления по сравнению со сложением и вычитанием и старшинство возведения в степень по сравнению со всеми остальными операциями.

Алгоритм преобразования основан на использовании стека и состоит в следующем:

1. Проверяется очередной символ во входной строке.

2. Если это операнд, то он передается в выходную строку.

3. Если это открывающая скобка, то она заносится в стек с приоритетом нуль.

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

5. Если текущий символ во входной строке является закрывающей скобкой, то операции из стека последовательно переносятся в выходную строку до тех пор, пока на вершине стека не появится открывающая скобка; эта открывающая скобка отбрасывается.

6. Если выражение закончилось, то из стека последовательно переносятся в выходную строку все оставшиеся в нем операции.

Матрицы переходов

Перейдем теперь от анализа арифметических выражений к более сложным объектам – программам. Пусть у нас есть язык, включающий в себя оператор присваивания, а также условный и циклический операторы. Грамматика такого языка в самом упрощенном виде может выглядеть так:

прогр ::= инстр

инстр ::= инстр; инстр

инстр ::= перем := выр

инстр ::= if выр then инстр else инстр end

инстр ::= while выр do инстр end

выр ::= выр перем | перем

перем ::= i

Тогда мы сможем писать программы наподобие следующей:

d := 10;

a := b+c-d;

if a then d := 1 else

while d do

e := e-1

end

end

Как видно, этот язык, несмотря на свою простоту, позволяет создавать весьма нетривиальные условные и циклические конструкции.

Описанные выше способы анализа предложений КС-языков имеют существенный недостаток, связанный с необходимостью реализации процедуры поиска правил или просмотра таблицы для выбора нужной редукции.

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

Для наглядности рассмотрим еще более упрощенный вариант грамматики нашего языка:

<прог> ::= <инстр>

<инстр> ::= IF <выр> THEN <инстр>

<инстр> ::= <перем> := <выр>

<выр> ::= <выр> + <перем> | <перем>

<перем> ::= i

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

Стек необходим нам для хранения правых частей грамматики, заканчивающихся терминалом. Эта часть называется головой правила.

Строки матрицы переходов соответствуют тем головам правых частей правил, которые могут появиться в стеке, а столбцы соотносятся с терминальными символами, включая и ограничитель предложений #. Элементами матрицы будут номера или адреса подпрограмм.

	#	IF	THEN	:=	+	i
#	5	1	0	6	0	1
IF	0	0	9	0	3	1
IF <выр> THEN	7	1	0	6	0	1
<перем> :=	8	0	0	0	3	1
<выр> +	4	0	4	0	4	1
i	2	0	2	2	2	0

Итак, распознаватель использует стек S, переменную R, принимающую значение текущего считываемого символа, а также переменную U, которая либо пуста, либо содержит тот символ, к которому была приведена последняя первичная фраза (иными словами, значением переменной является последняя разобранная синтаксическая категория).

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

# IF <выр> THEN IF <выр> THEN <перем> :=

в стеке будет представлена следующим образом:

<перем> :=

IF <выр> THEN

IF <выр> THEN

#

Итак, в стеке хранятся те последовательности символов, которые должны редуцироваться одновременно.

Распознаватель работает следующим образом. На каждом шаге работы верхний элемент стека соответствует некоторой строке матрицы. По входному терминальному символу (это – столбец) определяется элемент матрицы, являющийся номером подпрограммы, которую нужно выполнить. Эта подпрограмма произведет необходимую редукцию или занесет R в стек и будет сканировать следующий исходный символ. При написании подпрограмм будем считать, что функция PUSH(R) помещает в стек символR, функция SCAN() помещает очередной символ из входной цепочки в R, а функция POP() просто извлекает из стека верхний символ (предполагается, что он нам уже не нужен).

Схема рассуждений при формировании подпрограмм выглядит так (рассмотрим, для примера, подпрограмму 9): сначала мы выписываем содержимое верхнего элемента стека (для нашей подпрограммы это будет IF). Далее записываем значение считанного терминала (этоTHEN) и смотрим, что может находиться между ними (т.е. какая синтаксическая категория U):

…IFUTHEN…

Судя по всему, U должно быть равно <выр>. Значит, первая процедура нашей подпрограммы – это проверка вида

if U<выр> then error()

Затем смотрим, не получилось ли у нас разобранной синтаксической категории. Ничего путного пока у нас не вышло, поэтому присвоим переменной U пустое значение (U := ''), а в стек занесем полученную голову правила (PUSH('IF <выр> THEN')). Далее надо будет считать следующий входной символ. Итак, подпрограмма номер 9 будет выглядеть так:

9: IF U'<выр>' AND U'<перем>' THEN ERROR();

PUSH('IF <выр> THEN')

U := '';

SCAN().

Еще пример. В самом начале в стеке находится символ # и U пусто. В соответствии с нашей грамматикой входным символом должен быть либо IF, либо i. Поскольку с них начинаются правые части, необходимо занести их в стек и продолжить работу. Тогда первой подпрограммой будет такая:

1: IF U '' THEN ERROR(); PUSH(R); SCAN().

Предположим, что i – верхний элемент стека. Определим теперь, какие символы из тех, которые могут оказаться в R, считаются допустимыми. За i могут следовать символы: #, THEN, := или +. В любом из этих случаев необходимо заменить i на <перем>, т.е. выполнить редукцию

...<перем>... => ...i...

В подпрограмме 2 именно это и делается:

2: IF U'' THEN ERROR(); POP(); U := '<перем>'

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

Приведем все подпрограммы, соответствующие нашей матрице переходов:

1. IF U'' THEN ERROR(1);

PUSH(R);

SCAN().

2. IF U'' THEN ERROR(2);

POP();

U := '<перем>'.

3. IF U'<выр>' AND U'<перем>' THEN ERROR(3);

PUSH('<выр>+')

U := '';

SCAN().

4. IF U'<перем>' THEN ERROR(4);

POP();

U := '<выр>'.

5. IF U'<прог>' AND U'<инстр>' THEN ERROR(5);

STOP().

6. IF U'<перем>' THEN ERROR(6);

PUSH('<перем>:=')

U := '';

SCAN().

7. IF U'<инстр>' THEN ERROR(7);

POP();

U := '<инстр>'.

8. IF U'<выр>' AND U'<перем>' THEN ERROR(8);

POP();

U := '<инстр>'.

9. IF U'<выр>' AND U'<перем>' THEN ERROR(9);

PUSH('IF <выр> THEN')

U := '';

SCAN().

0. ERROR(10);

STOP().

На самом деле мы поступили не совсем корректно, определяя подпрограммы с одинаковыми номерами. Все подпрограммы должны быть уникальными. Дело в том, что каждаяподпрограмма выдает свою собственную диагностику ошибок. А это очень важный фактор.

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

Способ матриц переходов – это очень быстрый метод обработки, т.к. в нем полностью исключается поиск. Во-вторых, очень эффективна нейтрализация ошибок: каждый нуль в матрице соответствует определенной синтаксической ошибке. Так как нулей, соответствующих частным случаям ошибок, в матрице обычно много, то диагностика получается достаточно полной. По меньшей мере, метод матриц переходов – это наиболее эффективный с точки зрения нейтрализации ошибок способ обработки. Кроме того, матрица переходов достаточно легко может быть отредактирована и/или дополнена новыми элементами по ходу развития представлений разработчика об устройстве создаваемого языка. Вдобавок ко всему, по имеющейся грамматике языка матрица переходов может быть сформирована автоматически.

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

На этом мы закончим рассмотрение методов синтаксического анализа. Разберемся теперь с тем, как могут быть представлены результаты этого анализа.