Операторные грамматики (грамматики простого предшествия)

По-прежнему наша цель - решить задачу анализа входной последовательности и обойтись при этом как можно меньшими затратами на поиск. Метод, о котором пойдет речь далее, основан на понятии приоритета символов анализируемой последовательности.

Пусть дана входная цепочка символов "….RS…". Попробуем сразу определить, какое правило нам будет удобнее выполнить (точнее, над какой частью цепочки сначала производить операции, т.е. с какого символа начинать). Для этого можно использовать понятие приоритета, основываясь на введенной системе отношений между символами, а именно:

для любой цепочки "….RS…" возможны следующие варианты:

Если есть правило, заканчивающееся на R,

U®…R,

тогда можно сказать, что R > S.

Если есть правило, включающее в себя RS,

U®…RS…,

тогда можно сказать, что R = S.

Если же есть правило, начинающееся на S,

U®S… ,

тогда можно сказать, что R < S.

Итак, существуют три варианта отношений между символами:

 

Здесь предполагается, что S - терминал

 

Алгоритм разбора

Нам потребуются два стека: стек операторов OP и стек аргументов ARG. Обозначим через S верхний символ в стеке операторов OP, а через R - входной символ.

Далее циклически выполняем следующие действия:

Если R - идентификатор, то поместить его в ARG и пропустить шаги 2,3.

Если f(S)<g(R), то поместить R в OP и взять следующий символ.

Если f(S)³g(R), то вызвать семантическую процедуру, определяемую символом S. Эта процедура выполняет семантическую обработку, например, исключает из ARG связанные с S аргументы и заносит в ARG результат операции. Это – т.н. редукция сентенциальной формы.

 

Построим матрицу, строки которой будут соответствовать f(S), а столбцы – g(R). Для грамматики

E®E+T | T

T®T*F | F

F®(E) | i

эта матрица будет выглядеть следующим образом:

                                 g(R)

		+	*	(	)	#
	+	>	<	<	>	<
Стек	*	>	>	<	>	<
F(S)	(	<	<	<	=	<
	)	>	>	X	>	<
	#	<	<	<	<	>

 

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

Элементы матрицы 'X' обозначают ошибочную (запрещенную) ситуацию.

Условием нормального окончания работы алгоритма является ситуация, когда в стеке находится единственный символ # (S=#), а значение R есть также #. Во всех остальных случаях считается, что разбираемое выражение построено некорректно.

Рассмотрим пример разбора выражения (a*b/c+d)*e#

S	R	w	Arg	f(S)?g(R)
#		(a*b/c+d)*e#
#	(	a*b/c+d)*e#		<
#(	a	*b/c+d)*e#	A	<
#(	*	b/c+d)*e#	A	<
#(*	b	/c+d)*e#	a, b	<
#(*	/	c+d)*e#	a, b	>
#(	/	c+d)*e#	(a*b)	<
#(/	c	+d)*e#	(a*b), c	<
#(/	+	d)*e#	(a*b), c	>
#(	+	d)*e#	((a*b)/c)	<
#(+	d	)*e#	((a*b)/c), d	<
#(+	)	*e#	((a*b)/c), d	>
#(	)	*e#	(((a*b)/c)+d)	=
#	*	e#	(((a*b)/c)+d)	<
#*	e	#	(((a*b/)c)+d), e	<
#*	#		(((a*b)/c)+d), e	>
#	#		((((a*b/)c)+d)*e)	>

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

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

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

МАТРИЦЫ ПЕРЕХОДОВ

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

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

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

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

инстр::= 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):

…IF U THEN…

Судя по всему, 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:= '<перем >'

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

 

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

IF U ¹ '' THEN ERROR(1);

PUSH(R);

SCAN().

IF U ¹ '' THEN ERROR(2);

POP();

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

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

PUSH('<выр >+')

U:= '';

SCAN().

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

POP();

U:= '<выр >'.

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

STOP().

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

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

U:= '';

SCAN().

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

POP();

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

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

POP();

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

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

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

U:= '';

SCAN().

ERROR(10);

STOP().

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

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

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

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

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