/*

АНАЛИЗАТОР КС-ГРАММАТИКИ

Фраза -> Глагол, Группа_сущ

Группа_сущ -> Прилагат, Существ

Группа_сущ -> Прилагат, Существ, Предлог, Группа_сущ

Глагол -> ...

Прилагат -> ...

Существ -> ...

Предлог -> ...

*/

goal

FRAZA = ["печатать","первый","символ","в","последний","строка"],

print_list(FRAZA),

s(FRAZA).

clauses

s(A) :- sentence(A), write("\nФРАЗА РАСПОЗНАНА\n").

s(_) :- write("\nОШИБКА: ФРАЗА НЕ РАСПОЗНАНА\n").

% СЛУЖЕБНЫЕ И СЕРВИСНЫЕ ПРЕДИКАТЫ

append([],L,L).

append([H|A],B,[H|C]) :- append(A,B,C).

print_list([]).

print_list([Head|Tail]) :- write(Head,"."), print_list(Tail).

% СИНТАКСИС

sentence(S) :-

append(S1,S2,S),

glagol(S1),

GS(S2),

write("\nГлагол:"), writel(S1),

write("\nГс: "), writel(S2).

GS(S) :-

append(S1,S2,S),

prilagat(S1),

noun(S2),

write("\n*** Разбор ГС-1:"),

write("\nПрилагательное: "),writel(S1),

write("\nСуществительное:"),writel(S2).

GS(S) :-

append(S1,Stmp1,S),

append(S2,Stmp2,Stmp1),

append(S3,S4,Stmp2),

prilagat(S1),

noun(S2),

predlog(S3),

GS(S4),

write("\n*** Разбор ГС-2:"),

write("\nПрилагательное: "), print_list(S1),

write("\nСуществительное:"), print_list(S2),

write("\nПредлог: "), print_list(S2),

write("\nГс: "), print_list(S2).

% СЛОВАРЬ

noun(["символ"]). noun(["строка"]). noun(["страница"]).

glagol(["печатать"]). glagol(["стереть"]).

prilagat(["первый"]). prilagat(["второй"]). prilagat(["последний"]).

predlog(["в"]).

Но это все - "экзотика". Теперь рассмотрим более осмысленный пример - грамматику арифметических выражений. Эта грамматика в различных вариантах нам будет встречаться и далее. Пока же рассмотрим наиболее простой случай, содержащий лишь две бинарные операции с разными приоритетами.

G₀=({E,T,F},{a,+,*,(,)},P,E)

P = {E E+T|T

T T*F|F

F (E)|a}

Анализатор на Прологе будет выглядеть так:

E(L) :- T(L).

E(L) :- a3(L1,["+"],L3,L),

E(L1),

T(L3).

T(L) :- F(L).

T(L) :- a3(L1,["*"],L3,L),

T(L1), F(L3).

F(L) :- L=["a"].

F(L) :- a3(["("],L2,[")"],L),

E(L2).

Здесь предикат a3() разбивает список на три части. Как видно, Пролог-программа повторяет нашу грамматику с точностью до формы записи.

9. Ок-грамматики

Несмотря на кажущуюся общность КСГ, при описании естественно-подобных языков существуют ограничения, связанные с различного рода бесконтекстными согласованиями (рода, падежа, числа и т.п.).

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

Рассмотрим, каким образом может осуществляться согласование родов. Допустим, у нас есть группа существительных (ГС), состоящая из местоимения (Мест), прилагательного (Прил) и существительного (Сущ). Тогда определение ГС, учитывающее согласование родов, может выглядеть так:

Гс Мест(k), Прил(k), Сущ(k), ГС

При этом k является контекстуальным аргументом, отвечающим за согласование родов. Этот аргумент является логической переменной:

Мест(муж) этот

Мест(жен) эта

Прил(муж) второй

Прил(жен) вторая

Сущ(жен) строка

Сущ(муж) пароль

и т.д.

На Прологе введение контекстуального аргумента выглядит так:

mest(“муж”, ”этот”).

pril ("жен", "вторая").

и т.п.

10. Синтаксически управляемый перевод

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

Рассмотрим еще раз грамматику арифметического выражения.

SE

ET

EE+T

TF

TT*F

Fa

F(E)

Где E-выражение,

T-терм,

F-формула,

a-идентификатор.

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

Например, пусть дана фраза: a+a*a. Воспользовавшись данной грамматикой, получим следующую цепочку вывода:

SEE+TE+T*FT+T*FF+F*Fa+a*a

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

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

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

Судя по определению постфиксной формы записи, правилу EE+T соответствует элемент перевода E=ET+ (Выражению E+T в польской форме соответствует запись ET+). Строго говоря, элемент перевода E=ET+ означает, что перевод, порождаемый символом E, стоящим в левой части правила, получается из перевода, порождаемого символом E, стоящим в правой части правила, за которым идут перевод, порожденный символом T, и знак +. Рассуждая подобным образом, получим в результате следующую схему перевода:

Правило	Элемент перевода
EE+T	E = ET+
ET	E = T
TT*F	T = TF*
TF	T = F
F(E)	F = E
Fa	F = a

Определим выход, соответствующий входу a+a*a. Для этого сначала по правилам схемы перевода найдем левый вывод цепочки a+a*a из S. Затем вычислим соответствующую последовательность выводимых пар цепочек. При этом будем дописывать справа от полученной последовательности результат применения соответствующего элемента перевода:

(E,E) (E+T, ET+)

(T+T, TF+)

(F+T, FT+)

(a+T, aT+)

(a+T*F, aTF*+)

(a+F*F, aFF*+)

(a+a*F, aaF*+)

(a+a*a, aaa*+).

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

Перевод инфиксной формы записи в польскую

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

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

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

Z ::= E

E ::= T | E+T | E-T | -T

T ::= F | T*F | T/F

F ::= a | (E)

Запишем схему перевода в следующем виде:

№	Правило	Семантическая программа
1	Z ::= E	нет(*)
2	E ::= T	нет(**)
3	E ::= E+T	Push('+')(**)
4	E ::= E-T	Push('-')(**)
5	E ::= -T	Push('@')
6	T ::= F	Нет
7	T ::= T*F	Push('*')
8	T ::= T/F	Push('/')
9	F ::= a	Push(a)
10	F ::= (E)	Нет

Это - явно более приближенный к практическому воплощению вариант. Здесь семантическая процедура Push(X) добавляет в конец выходной цепочки символ X. При этом надо сделать следующие замечания:

Правило (1) применимо, если R=# (символ # означает конец анализируемой последовательности); правила (2), (3), (4) применимы, если в R содержится '+', '-', '#' или ')'.

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

Алгоритм СУ-перевода выглядит так: сначала в стек S заносится символ #. Далее к содержимому стека мы пробуем применить какое-либо правило из списка. Если ни одно из правил не срабатывает, то в стек заносится очередной символ анализируемой входной последовательности.

Проще всего изобразить процедуру разбора на конкретном примере, а сам процесс изобразить в виде некоторой таблицы (в столбце _k... мы будем записывать остаток входной цепочки символов). Рассмотрим разбор выражения "a*(b+c)#":

Стек S	R	k...	Номер правила	Польская цепочка
#	a	*(b+c)#
#a	*	(b+c)#	9	a
#F	*	(b+c)#	6	a
#T	*	(b+c)#		a
#T*	(	b+c)#		a
#T*(	b	+c)#		a
#T*(b	+	c)#	9	ab
#T*(F	+	c)#	6	ab
#T*(T	+	c)#	2	ab
#T*(E	+	c)#		ab
#T*(E+	c	)#		ab
#T*(E+c	)	#	9	abc
#T*(E+F	)	#	6	abc
#T*(E+T	)	#	3	abc+
#T*(E	)	#		abc+
#T*(E)	#		10	abc+
#T*F	#		7	abc+*
#T	#		2	abc+*
#E	#		1	abc+*
#Z	#		STOP	abc+*

Признак нормального окончания работы алгоритма: когда в стеке остался единственный символ Z, а текущим символом является `#'- символ конца входной последовательности, то мы считаем, что процедура синтаксического анализа завершена успешно. В противном случае (если в стеке есть другие символы) фраза построена неверно.

Основной недостаток синтаксически-управляемого перевода (как, впрочем, и всех механизмов, основанных на применении грамматик в явном виде) заключается в том, что фактически мы имеем дело с полным перебором всех возможных вариантов применений правил грамматики. Избежать этого перебора позволяют лишь введенные весьма искусственные соглашения относительно условий применимости тех или иных правил в различных ситуациях (см. те же правила (1), (2), (3) и (4)). Более того, поиск как таковой и в схеме СУ-перевода, и в МП-автоматах, о которых мы будем говорить ниже, категорически недопустим. Вот если бы мы работали с Прологом, то тогда нам не пришлось бы вводить эти правила-ограничители поиска - внутренний механизм Пролога сам перебрал бы все возможные варианты применения правил. Здесь же нам нужно "стопроцентное" попадание в нужное правило.

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

…

T-F

T!F

…

Т.е. действие унарного оператора (`-' или `!') будет направлено на F (F(E), Fa). Если же поместить унарный оператор в правило

E-T (или E!T),

то оператор будет действовать уже на терм, а это означает, что в выражении "!a*b" сначала будет вычислено произведение a*b, а затем только будет взято его отрицание.

11. Автоматы с магазинной памятью

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

G = { {a , +, * , /, - , . , ) , ( } , {E, T, F,}P, E }

P = { ET, EE + T, EE - T,

TF, TT*F, TT/ F,

Fa, F (E) }

создать конечный распознающий автомат уже невозможно.

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

Определение. Автомат с магазинной памятью (МП-автомат или стековый автомат) - это семерка

МП = (, Q, Г, q₀, z₀, T, P), где

- конечный входной алфавит (входной словарь);

Q - конечное множество состояний;

Г - конечный алфавит магазинных символов;

q₀ - начальное состояние управляющего устройства (q₀Q);

z₀ - символ, находящийся в магазине в начальный момент времени (начальный символ), z ₀Г;

T - множество терминальных (заключительных) состояний, TQ;

P - отображение множества Q({e})Г в множество конечных подмножеств множества QГ^*:

P: Q({e})Г QГ^*

Условно МП-автомат можно изобразить так:

Конфигурацией МП-автомата называется тройка (q,,)Q^*Г^*, где

q - текущее состояние устройства;

- неиспользованная часть входной цепочки; первый символ цепочки находится под входной головкой; если = e, то считается, что вся входная лента прочитана;

- содержимое магазина; самый левый символ цепочки a считается верхним символом магазина; если a=e, то магазин считается пустым.

Такт работы МП-автомата

(q,a,Z) (q', ,)

Если a=e, то этот такт называется e-тактом. В e-такте входной символ не принимается во внимание и входная головка не сдвигается. Если =e, то верхний символ удаляется из магазина (магазинный список сокращается).

Начальная конфигурация МП-автомата - это тройка

(q₀, , Z₀), ^*

Говорят, что цепочка допускается МП-автоматом, если

(q₀, , Z₀) ^*(q, e, ) для некоторых qT и Г^*

На практике более полезным и универсальным является т.н. расширенный МП-автомат

МП_r = (, Q, Г, q₀, Z₀, T, P_r), где

P_r - отображение множества Q({e})Г^* в множество конечных подмножеств множества QГ^*, а все остальные символы имеют тот же смысл, что и в определении МП-автомата.

В отличие от МП-автомата расширенный МП-автомат обладает способностью продолжать работу и тогда, когда магазин пуст.

Теорема. Пусть G = (N,,P,S) - КС-грамматика. По грамматике G можно построить такой МП-автомат R, что L_e(R)=L(G).

В качестве примера рассмотрим расширенный МП-автомат R, распознающий грамматику G₀

G₀=({E,T,F},{a,+,*,(,),#},P,E)

P = {E E+T|T

T T*F|F

F (E)|a}

Здесь '#' - символ конца входной последовательности.

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

R = (, Q, Г, q₀, Z₀, T, P), где

Q = {q, r},

Г={E, T, F, $}

q₀ = q,

Z₀ = $,

T = {r},

P:

(1)(q,e,E+T) (q,E)(*)

(2)(q,e,T) (q,E)(*)

(3)(q,e,T*F) (q,T)

(4)(q,e,F) (q,T)

(5)(q,e,(E)) (q,F)

(6)(q,e,a) (q,F)

(7)(q,#,$E) (r,e)

(8)(q,b,e) (q,b) для всех b{a,+,*,(,)};

Замечание 1. Правила, отмеченные (*), применимы, если следующим символом входной цепочки является '+', или '-', ')' или входная цепочка пуста.

Замечание 2. Приоритет выполнения правил определяется содержимым стека.

Пусть на входе распознавателя цепочка "a+a*a". Тогда процесс ее распознавания будет выглядеть так:

(q,a+a*a#,$) (q, +a*a#, $a)

(q, +a*a#, $F)

(q, +a*a#, $T)

(q, +a*a#, $E)

(q, a*a#, $E+)

(q, *a#, $E+a)

(q, *a#, $E+F)

(q, *a#, $E+T)

(q, a#, $E+T*)

(q, e, $E+T*a)

(q, e, $E+T*F)

(q, e, $E+T)

(q, #, $E)

(r, #, e)

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

Более того, МП-автомат можно считать просто более формальным изложением алгоритма СУ-перевода. Например, алгоритм в СУ-перевода гласит: если ни одно из правил не применимо к содержимому стека, то следует поместить в стек очередной символ входной последовательности. В МП-автомате вместо этого используется правило (8). А условие завершения СУ-перевода формулируется правилом (7). Более того, если говорить о конкретной программной реализации обоих методов, то и в том, и в другом случае нам придется пользоваться практически эквивалентными структурами.

12. Операторные грамматики

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

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

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

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

U…R,

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

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

U…RS…,

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

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

US…,

тогда можно сказать, что 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). Для грамматики

EE+T | T

TT*F | F

F(E) | i

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

g(R)

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

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

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

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

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

S	R		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 мы получим польскую форму записи разбираемого выражения.

13. Алгоритм Дейкстры

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

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

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. Если выражение закончилось, то из стека последовательно переносятся в выходную строку все оставшиеся в нем операции.

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

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

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

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

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

инстр ::= 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 получает значение. К этому моменту нам известно, какие инструкции подлежат редукции и обработке.

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

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

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

15. Внутренние формы представления программы

Мы уже говорили о том, что внутренняя форма - это промежуточная форма представления исходной программы, пригодная (1) для простой машинной обработки (операторы располагаются в том же порядке, в котором они и будут исполняться); (2) для интерпретации. Рассмотрим, как представимы во внутренней форме некоторые наиболее употребительные операторы. Начнем с польской формы.

15.1 Польская форма

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

Если R является идентификатором или константой, то его значение заносится в стек и осуществляется считывание следующего символа (правило "<операнд>::=идентификатор").

Если R - бинарный оператор, то он применяется к двум верхним операндам в стеке, и затем они меняются на полученный результат (правило "<операнд>::=<операнд><операнд><оператор>").

Если R - унарный оператор, то он применяется к верхнему символу в стеке, который затем заменяется на полученный результат (правило "<операнд>::=<операнд><оператор>").

Упрощенно алгоритм вычисления польской формы (ПФ) выглядит так:

R := getchar

while R != # do

case R of

'идентификатор':push(R)

'бин.оператор':pop(B), pop(A), Tmp := R(A,B), push(Tmp)

'унарн.оператор':pop(A), Tmp := R(A), push(Tmp)

endcase

R := getchar

endwhile

Замечание. Следует помнить, что существуют операторы, которые не заносят в стек результаты своей работы. Таким оператором является, к примеру, оператор присваивания языка Паскаль. Однако в языке Си (Си++) оператор присваивания возвращает значение.

Польскую форму легко расширять. Рассмотрим включение в ПФ других, отличных от арифметических, операторов и конструкций. Символом $ мы будем предварять имена операторов, чтобы не спутать их с аргументами.

Безусловные переходы

Безусловный переход на метку (аналог GOTO L)

L $BRL (Branch to label)

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

Безусловный переход на символ

C $BR

Под символом здесь понимается номер позиции (индекс) в массиве, содержащем польскую форму.

Условные переходы

<операнд1> <операнд2> $BRxZ|$BRM|$BRP|$BRMZ|$BRPZ|

<операнд1> - значение арифметического выражения,

<операнд2> - номер или место символа в польской цепочке (адрес).

$BRx - код оператора. При этом можно ввести самые разнообразные условия перехода. Например:

$BRZ - переход по значению 0,

$BRM - переход по значению <0,

$BRP - переход по значению >0,

$BRMZ - переход по значению <=0,

$BRPZ - переход по значению >=0,

и т.п.

При выполнении условия перехода в качестве следующего символа берется тот символ, адрес которого определяется вторым операндом. В противном случае работа продолжается как обычно.

Условные конструкции

IF <выражение> THEN <инстр1> ELSE <инстр2>

В ПФ мы имеем:

<выражение> <c₁> $BRZ <инстр₁> <c₂> $BR <инстр₂>

Предполагается, что для любого выражения 0 означает "ложь", а неравенство нулю - "истина". Здесь

<c₁> - номер символа, с которого начинается <инстр₂>,

<c₂> - номер символа, следующего за <инстр₂>,

$BR - оператор безусловного перехода на символ,

$BRZ - оператор перехода на символ c₁, если значение <выражение> равно нулю).

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

Понятно, что применение ПФ для условной конструкции в виде

<выр> <инстр1> <инстр2> $IF

неприемлемо, ибо к моменту выполнения оператора $IF все три операнда должны быть уже вычислены или выполнены, что, разумеется, неверно.

Описание массивов

Пусть дано описание массива

ARRAY A[L1..U1,...,Lk..Uk]

в ПФ оно представляется в виде

L1 U1 ... Lk Uk A $ADEC,

где $ADEC - оператор объявления массива. Оператор $ADEC имеет переменное количество аргументов, зависящее от числа индексов. Операнд A - адрес в таблице символов. При вычислении $ADEC из этого элемента таблицы извлекается информация о размерности массива A и, следовательно, о количестве операндов $ADEC. Отсюда понятно, почему операнд A должен располагаться непосредственно перед оператором $ADEC.

Обращение к элементу массива и вызовы подпрограмм

Конструкция A[<выр>,..,<выр>] записывается в виде

<выр> .. <выр> A $SUBS

Оператор $SUBS, используя элемент A таблицы символов и индексные выражения, вычисляет адрес элемента массива. Затем операнды исключаются из стека и на их место заносится новый операнд, специфицирующий тип элемента массива и его адрес.

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

x₁ x₂ f $CALL,

где x₁ и x₁ - аргументы, f - имя функции, $CALL - команда передачи управления по адресу, определяемому именем функции. При этом предполагается, что мы заранее занесли в таблицу имен информацию о том, сколько и каких аргументов у функции f, а также ее адрес - индекс начала кода подпрограммы в массиве польской формы.

Не случайно поэтому в подавляющем количестве языков программирования имена функций ассоциируются с их адресами.

Циклы

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

FOR I=N1 TO N2 DO Operator

может быть сконструирован на исходном языке:

I := N1;

L1:IF I>N2 THEN GOTO L2;

Operator;

I:=I+1;

GOTO L1;

L2:

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

Рассмотрим фрагмент программы:

BEGIN

INTEGER K;

ARRAY A[1..I-J];

K := 0;

L:IF I>J THEN

K := K+A[I-J]*6

ELSE

BEGIN

I := I+1;

I := I+1;

GOTO L;

END

END.

Добавим еще два оператора без операндов - $BLOCK ("начало блока") и $BLOCKEND ("конец блока"). Эти операторы иногда очень важны - в некоторых языках программирования с их помощью можно вводить локальные, "внутриблоковые" переменные, вызывать автоматически деструкторы и т.п. Кроме того, нам понадобится оператор присваивания ":=", который ничего не заносит обратно в стек. Польская форма нашего фрагмента будет выглядеть так:

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

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

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

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

15.2 Тетрады

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

$BLOCK(10) + K, T4, T5

- I, J, T1(11) := T5,, K

$BOUNDS 1, T1(12) $BR 18

$ADEC A(13) + I, 1, T6

:= 0,, K(14) := T6,, I

- I, J, T2(15) + I, 1, T7

$BMZ 13, T2(16) := T7,, I

- I, J, T3(17) $BRL L

* A[T3], 6, T4(18) $BLOCKEND

Здесь используются следующие операторы:

Оператор	Операнды	Описание
$BR	i	переход на i-ю тетраду
$BZ (BP,BM)	i, P	переход на i-ю тетраду, если P=0 (P>0,P<0)
$BG (BL,BE)	i, P1, P2	переход на i-ю тетраду, если P1>P2 (P1<P2,P1=P2)
$BRL	P	переход на тетраду, номер которой задан в P-м элементе таблицы символов
$BOUNDS	P1, P2	P1 и P2 описывают граничную пару массива
$ADEC	P	Массив описан в P. Если размерность массива равна n, то этой тетраде должны предшествовать n операторов $BOUNDS, задающих n граничных пар

С тетрадой номер 9 могут возникнуть определенные проблемы. Трудности связаны с использованием аргумента в виде переменной с индексом. Решение может заключаться в использовании той же методики, что и в случае описания массивов.

Введем пару операторов типа

$AINDX I

$AGET A, R

Здесь $AINDX заносит аргумент I (индекс массива) в специальный стек - стек индексов. Это необходимо для того, чтобы команда $AGET смогла вычислить адрес элемента массива A, используя содержимое стека индексов, и занести значение этого элемента в R. В этот же момент может происходить и очистка стека (по мере извлечения необходимого количества аргументов)

Например, выражение "A[1,2]+B[J]" будет представлено в виде

$AINDX 1

$AINDX 2

$AGET A, T1

$AINDX J

$AGET B, T2

+ T1, T2, T3

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

15.3 Об операторах и выражениях

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

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

void main(void)

{ int a,b;

3-4*b;

1+2;

for(2+a;1;)

b+1;

}

Не менее важными являются вопросы вида: что такое пустой оператор? как сделать так, чтоб была возможность ставить или не ставить разделитель операторов (`;') перед закрывающей операторной скобкой? и т.д.

16. Оптимизация программ

Оптимизация программ - это очень объемная тема, на которую написаны (и пишутся до сих пор) многочисленные труды. Здесь мы лишь вкратце затронем этот вопрос.

Различают два основных вида оптимизации - машинно-зависимую (МЗО) и машинно-независимую (МНЗО):

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

В отличие от МЗО, МНЗО - отдельная фаза компилятора, предшествующая генерации кода. Она включается на этапе генерации промежуточного кода - внутренней формы представления программы.

Оптимизации подлежат:

время выполнения;

емкостные ресурсы (память).

Существуют 4 основных типа машинно-независимой оптимизации МНЗО.

I. Исключение общих подвыражений (оптимизация линейных участков)

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

представить выражение в форме, пригодной для обнаружения общих подвыражений;

определить эквивалентность двух и более подвыражений;

исключить повторяющиеся;

изменить команды так, чтобы учесть это исключение.

Например, пусть выражение A = c*d*(d*c+b) записано в виде тетрад:

* c d T1

* d c T2

+ T2 b T3

* T1 T3 T4

= A T4

Упорядочим операнды в алфавитном порядке (там, где это возможно):

* c d T1

* c d T2

+ T2 b T3

* T1 T3 T4

= A T4

Далее определим границы операторов и найдем общие подвыражения (это (1) и (2)) и затем исключим подвыражение (2). После чего заменим далее везде T2 на T1:

* c d T1

+ T1 b T3

* T1 T3 T4

= A T4

Этот прием неудобен тем, что возможны варианты, когда либо не представляется возможным отыскать сразу общие выражения, либо в тех случаях, когда b, c, d - функции, имеющие побочный эффект; в этом случае мы можем поломать всю логику вычислений.

II. Вычисления на этапе компиляции

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

A := 1.5 * 2/3

III. Оптимизация булевых выражений

Метод основан на использовании свойств булевых выражений. Например, вместо

if (a and b and c) then <операторы> endif

надо сгенерировать команды таким образом, чтобы исключались лишние проверки. Суть метода состоит в том, что мы строим разветвление условия оператора if. Таким образом, вместо "if (a and b and c) then <операторы> endif" получим:

if not a then goto Label

if not b then goto Label

if not c then goto Label

<операторы>

Label://метка перехода

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

IV. Вынесение инвариантных вычислений за пределы цикла

Это - один из наиболее эффективных методов оптимизации, дающий весьма ощутимые результаты.

Для реализации метода необходимо:

распознать инвариант;

определить место переноса;

перенести инвариант.

Неудобства метода:

отследить инвариант нелегко, т.к. аргументы могут косвенно зависеть от переменной цикла;

не учитываются побочные эффекты, если аргументы инва...