OP1 -+x OP2--Примеры четверок: -a = 4 a + b = 7 6 + 3 = 11

Выражение

(-a + b)*(c + d)

будет соответствовать такой последовательности четверок: -a=4

1 + b=2 c + d=3

2 * 3=4

Целые числа с левой стороны от знаков равенства относятся к другим четверкам. Из сформированных четверок нетрудно генерировать машинный код, а многие компиляторы на основании четверок осуществляют трансляцию в промежуточный код. Цель настоящего раздела - показать, как включать в грамматику выражений действия для генерирования соответствующих четверок. Действия заключаются в угловые скобки <,> и обозначаются как Al, А2... . В данном случае требуются четыре различнтх действия. Алгоритм пользуется стеком, а номера четверок размещаются с помощью целочисленной переменной. Перечислим эти действия:

А1 - поместить элемент в стек;

А2 - взять три элемента из стека, напечатать их с последующим знаком «=» и номером следующей размещаемой четверки и поместить полученное целое число в стек;

A3 - взять два элемента из стека, напечатать их с последующим знаком «=» и номером следующей размещаемой четверки и поместить полученное целое число в стек;

А4 - взять один элемент из стека.

Грамматика с учетом этих добавленных действий примет вид S -EXP<A4> EXP-TERM

ЕХР + <А1>ТЕRМ<А2> TERM-FACT

TERM *<A1>FACT<A2> FACT --<A1>FACT<A3>

ID<A1>

(EXP)

ID-abcde

Действие Al используется для помещения в стек всех идентификаторов и операторов, а действия А2 и A3 - для получения бинарнтх и унарнтх четверок соответственно. Можно написать код для этих действий на Алголе 68, допуская следующие описания:

[1 : 20] union (int, char) stack;

intptr : =0, quadno : = 0;

char in

Считается, что in принимает значение последней считанной литеры (или символа).

Покажем действия А1-А4:

<A1>

stack [ptr plusab 1]:= in

<A2>

begin

for i from ptr - 2 to ptr

do print stack [i]

print ((" = ", quadno plusab 1, newline));

stack [ptr minusab 2]: = quadno

<A3>

begin

for i from ptr - 1 to ptr

do print slack [i]

print ((" = ", quadno plusab 1, newline) );

stack [ptr minusab 1] : = quadno

<A4>

ptr minusab 1

В качестве примера проследим за преобразованием выражения

( - a + b) * (c + d)

в четверки. Действие A1 выполняется после распознавания каждого идентификатора и оператора, действие А2 - после второго операнд;: каждого знака бинарной операции, а действие A3 - после первого (и единственного) операнда каждого знака унарной операции. Действие же А4 выполняется только один раз после считывания всего выражения.

Следует заметить, что:

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

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

3. приведенная выше грамматика рекурсивна влево, так как правила вида

TERM-FACT x TERM подразумевают иной порядок вычисления: например, (А*(В*С)), а не ((А*В)*С). Тем не менее мы можем преобразовать леворекурсивные правила в праворекурсивные с помощью включения действий в соответствующие места путем введения новтх нетерминалов.

(минус)

А1, поместить в стек « - » А1, поместить в стек а A3, удалить из стека 2 Элементы, поместить в стек «1» А1, поместить в стек «+» A1, поместить в стек b А2, удалить из стека 3 Элементы, поместить в стек «2»

A1, поместить в стек «X»

A1, поместить в стек c

-а = 1

1+b=2

A1, поместить в стек «+ » A1, поместить в стек d

А2, удалить из стека 3 C+d =3

) Элементы, поместить в стек "3"

А2, удалить из стека 3 2*3 = 4

Элементы, поместить в стек «4» А4, удалить из стека 1 Элемент Так, правила TERM-FACT

TERM - TERM x<A1>FACT<A2> эквивалентны правилам

TERM-FACT

NEW-e

X<A1>FACT<A2>NEW

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

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

Объем «кода» в вышеприведенном примере весьма невелики, как мы увидим из других примеров, иллюстрирующих тот же метод, труднее всего определить, где в грамматике должны появляться действия, а не писать код для этих действий.

6.2. РАБОТА С ТАБЛИЦЕЙ СИМВОЛОВ

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

Когда описывается идентификатор, например