46023 (665330), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

ся свертка по пустому правилу, сопровождающаяся выполнением ука-

занного действия. При этом независимо от характера действия оче-

редной элемент в стеке значений отводится для хранения значения

неявно присутствующего "пустого" нетерминала. В действии, находя-

щемся в конце правила, соглашение о значениях псевдопеременных

остается прежним, если иметь в виду наличие дополнительных симво-

лов. В приведенном выше правиле в действии 3 для доступа к значе-

ниям элементов B, C, D, K следовало бы использовать соответствен-

но псевдопеременные $1, $2, $4, $6; псевдоперемнные $3, $5 хра-

нят результаты действий 1 и 2. В действиях, находящихся внутри

правила, с помощью псевдоперемнных $i доступны значения располо-

женных левее элементов, а также результаты предшествующих встав-

ленных в тело действий. Результатом внутреннего действия (т.е.

значением неявного нетерминалА) является значение, присвоенное в

этом действии псевдопеременной $$, при отсутствии такого присваи-

вания результат действия не определен. Заметим, что присваивание

значения псевдопеременной $$ во внутренних действиях не вызывает

предварительной установки значения нетерминала, стоящего в левой

части правила: это значение в любом случае устанавливется только

действием в конце правила или считается равным значению $1.

ЛЕКЦИЯ 11

СЕМАНТИЧЕСКИЕ ПРОГРАММЫ

Генерация какого─либо промежуточного кода большей частью

осуществляется одновременно с синтаксическим анализом. С этой

целью включаются действия, вызов которых обеспечивает не только

генерацию кода, но и построение таблиц символов, обращение к ним

и т.д. Свяжем с каждым правилом грамматики семантическую програм-

му, которая должна выполнять соответствующую семантическую обра-

ботку, когда связанное с ней правило вызывает синтаксическую ре-

дукцию. Рассмотрим как осуществить перевод арифметического выра-

жения с данными правилами в различные внутренние формы:

Правила грамматики:

Z ::= E

E ::= T|E+T|E─T|─T

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

F ::= I|(E)

1. Перевод инфиксной записи в польскую. Всякий раз, когда в

сентециальной форме найдена основа Х, редуцируемая к нетерминалу

U, синтаксический распознаватель вызывает программу, связанную с

правилами U ::= X.

Программа осуществляет обработку символов в Х и выдает ту

часть польской цепочки, которая имеет непосредственное отношение

к Х. Так как : (1) основа редуцируется при каждой редукции,то (2)

если в основе встречается нетерминал V, то часть польской цепоч-

ки, включающая подцепочку, которая приводится к V, уже была сге-

нерирована.

Считаем, что генерируемая польская цепочка хранится в од─

номерном массиве Р. Пусть р ─ содержит адрес первого свободно─

го элемента Р (Рнач=1). Вызванная программа имеет доступ к симво-

лам основы s(1),...,s(i), находящимся в синтаксическом стеке рас-

познавателя.

Программа, связанная с правилом Е1 ::= Е2+Т

В момент ее вызова согласно (2) массив Р содержит

...,

т.к. сначала генерируется код для Е (основа ─ самая левая

простая фраза), потом для Т. Справа от Т только терминалы.

Очевидно данная программа должна поместить знак + в поль─

скую цепочку. При этом Е2+Т переводится в запись Е2 Т +. Следо─

вательно семантическая программа имеет вид Р(р):="+";р:=р+1.

Программа для правила F ::= I (I─любой идентификатор)

По правилам польской записи (ЛК10) идентификаторы пред─

шествуют своим операторам и идут в том же порядке, что и в инфик-

сной записи. То есть необходимо лишь занести идентификатор в Р.

Р(р) := s(i); р:=р+1 s(i)─верхний символ стека

Для правила F ::= (E) действия не включаются, т.к. скобок в

польской записи нет, а для Е польская запись уже сгенерирова─

на. Аналогично рассуждая получим:

правило семантическая программа

(1) Z ::= T нет

(2) E ::= T нет

(3) E ::= E+T P(p):='+';p:=p+1

(4) E ::= E─T P(p):='─';p:=p+1

(5) E ::= ─T P(p):='@';p:=p+1

(6) T ::= F нет

(7) T ::= T*F P(p):='*';p:=p+1

(8) T ::= T/F P(p):='/';p:=p+1

(9) F ::= I P(p):=s(i);p:=p+1

(10)F ::= (E) нет

Очевидно для правил 3,4,7,8 можно иметь одну программу:

P(p):=s(i─1); p:=p+1

2.Преобразование инфиксной записи в тетрады

Будем генерировать теперь для А*(В+С) тетрады:

+В,С,Т1

*А,Т1,Т2

Первую тетраду попытаемся сгенерировать при редукции по прави─

лу Е ::= Е+Т. К этому моменту синтаксическое дерево будет иметь

вид (а).

Е,Т1

Е │

│ ┌──┴──┐

T T T │ │

│ │ │ E,B │

F F F │ │

│ │ │ T,A T,B T,C

A * (B + C) │ │ │

F,A F,B F,C

(a) │ │ │ (б)

A * ( B + C )

На следущем шаге приведения Е+Т к Е семантическая программа

должна выдать тетраду, однако сентенциальная форма {Т*(Е+Т)}не

содержит информации об именах Е и Т. При получении польской

записи имена В и С заносились в выходную цепочку при выполне─

нии редукций F ::= B и F ::= C.

Очевидно, что нам также необходимо в момент редукций F ::=I где─то запомнить информацию об именах редуцируемых

идентификаторов до момента их использования. Заметим, что ска─

нер для каждого идентификатора выдает пары вида (I,B),(I,C),.., причем символ I связан с синтаксической инфор─

мацией, В или С (имя) ─ с семантикой символа.

Привяжем к каждому нетерминалу U (узлу дерева) семанти─

ческую информацию U.SEM. Кроме того, будем генерировать имена

Т1,Т2,.. для обозначения подвыражений, используя для этого

счетчик i. В начале i=0. Операция генерации нового идентифика─

тора и его привязка к U имеет вид

i:=i+1; U.SEM:=Ti

Для генерации тетрады используем процедуру с 4 палитрами:

ENTER(W,X,Y,Z). Тогда получим:

правило семантическая программа

(1) Z ::= Е Z.SEM:=E.SEM

(2) E ::= T E.SEM:=T.SEM

(3) E1 ::= E2+T i:=i+1 E1.SEM:=Ti

ENTER('+',E2.SEM,T.SEM,E1.SEM)

(4) E1 ::= E2─T i:=i+1 E1.SEM:=Ti

ENTER('─',E2.SEM,T.SEM,E1.SEM)

(5) E ::= ─T i:=i+1 E.SEM:=Ti P(p):='@';p:=p+1

ENTER('@',0,T.SEM,E.SEM)

(6) T ::= F T.SEM:=F.SEM

(7) T ::= T*F

(8) T ::= T/F

(9) F ::= I

(10)F ::= (E) F.SEM:=E.SEM

Реализация семантических программ и семантических стеков

Для привязки семантических атрибутов к нетерминалам ис-

пользуются семантические стеки для каждого атрибута (или один

стек с отдельными полями для хранения синтаксического символа и

его семантических атрибутов). Эти стеки должны хранить семанти-

ческую информацию, которая связана с нетерминалами, входящими в

текущую сентенциальную форму. Эти стеки работают параллельно с

синтаксическим стеком S (т.е. удаление и занесение в них синхро-

низировано). Семантическая программа имеет доступ ко всем стекам.

┌───┬────────┬──────┬───────┬────┐

│ E │ │ REAL │ │ 20 │

├───┼────────┼──────┼───────┼────┤

│ + │ │ │ │ │

├───┼────────┼──────┼───────┼────┤

│ T │ │ INT │ │ 40 │

├───┼────────┼──────┼───────┼────┤

│ . │ │ . │ │ . │

│ . │ │ . │ │ . │

│ . │ │ . │ │ . │

└───┴────────┴──────┴───────┴────┘

В действительности не имеет значения, сколько используется

стеков.

Рассмотрим несколько алгоритмов семантической обработки

для языка типа АЛГОЛ.

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

::=ELSE│

::=IFTHEN,

где должно иметь тип BOOLEAN.

Необходимо сгенерировать тетрады одного из двух видов: (1)

тетрады для Т::= (1) тетрады для Т::= (p) BZ

q+1,T,0 (p) BZ q,T,0

(q) BR r (q)

(q+1)

(r)

Программа генерации (Р)тетрады связана с правилом:

::=IFTHEN и имеет следующий вид:

(1) Р:=,ENTRY;─занести в Р адрес элемента TS для

(2) CHECKTYPE(P,BOOLEAN); ─проверить, что тип BOOLEAN

(3) ,JUMP:=NEXTQUAD; ─запомнить номер следущей тетрады

(4) ENTER(BZ,0,P,0); ─генерация BZ─тетрады

Общее правило для доступа к семантическим стекам: Если осно-

ва х рассматриваемой сентенциальной формы должна быть приведена с

помощью правила U::=x к U, то для работы с семантикой символов

используется программа, которая:

1) заносит информацию в TS или проверяет ее;

2) проверяет семантическую информацию, связанную с х;

3) генерирует тетрады;

4) связывает семантическую информацию с U;

Для обращения в стеки за семантической информацией SEM, свя-

занной с U, применяем обозначение U.SEM. 1.I.NAME ─ указатель,

используется для доступа к имени идентификатора

2.ENTRY ─ выдает указатель на элемент таблицы символов для переменной

3.ENTRY ─ указатель на значение (уже выполненного) выражения

4.JUMP ─ содержит номер BZ тетрады, в которую позднее надо добавить адрес перехода, который еще не известен

Следущая редукция будет связана с правилом: ::=<ус-

ловие> I:=.JUMP Занести номер следущей тетрады

во вторую QU- AD(I,2):=NEXTQUAD компоненту тетрады с помощью I,

т.е. получить (BZq+1,p,0)

Операнды во внутренней форме будем представлять указателем Р

на соответствующий элемент таблицы символов. Ссылка на его атри-

бут будет иметь вид: Р.TYPE,P.TYPE1. Очевидно, если инструкция

содержит ELSE, то между и нужно как бы вста-

вить команду BR. Но при таком синтаксисе конструкция с

ELSE будет распознана лишь после разбора и .

Т.е. будет специфицирована цепочка команд для и .

Преобразуем синтаксис в соответствии с желаемой семантикой:

::=

::=ELSE

::=ELSE

.JUMP:=NEXTQUAD; ─ запомнить номер следущей тетрады

ENTER(BR,0,0,0); в стеке

I:=.JUMP; ─ занести в BZ переход через

QUAD(I,2):=NEXTQUAD;

::=

I:=.JUMP; - вставить адрес перехода через

QUAD(I,2):=NEXTQUAD; в (BR...)

Выводы:

1. Когда редуцируется основа XY..Z, тетрады для всех нетер-

миналов, которые есть в основе, уже сгенерированы. Чтобы вста-

вить между ними дополнительные тетрады, следует изменить синтак-

сис в соответствии с требуемой семантикой.

2. Показано, как используется семантика, связанная с симво-

лом, для запоминания информации, которая потребуется позже. Оче-

видно, что можно допустить любое количество вложенных друг в дру-

га условных операторов, если на некоторых стадиях разбора иметь

произвольное число символов . С каждым из них будет свя-

зано свое .JUMP значение в семантическом стеке. Стеко-

вый механизм обеспечивает автоматическое сохранение каждой такой

компоненты отдельно.

Метки и переходы

Метка I определяется следущим образом:

::=I:,где

I - нетерминал, обозначающий идентификатор.

Метке I нужно присвоить адрес начала . Чтобы это

можно было сделать, изменим синтаксис таким образом:

::=

::=I:

Имея ввиду, что в программе ссылаться на метку можно раньше,

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

::=I;

LOOKUPDEC(I.NAME,P);- поиск описания метки с именем NAME среди иден-

IF P=0 THEN тификаторов. Если его нет(возвращается Р=0),то

BEGIN занести новый элемент с именем NAME в ST.

INSERT(I.NAME,P); Присвоить ему тип LABEL.

P.TYPE:=LABEL;

END

ELSE BEGIN

CHECKTYPE(P,LABEL); Cравнивает тип в ST (P.TYPE) с типом LABEL

IF P.DECLARED=1 THEN Проверяет не повторное ли это определение

ERROR (3) Печать ошибки

END

P.DECLARED:=1; Если нет, то установить признак метка опре-

P.ADRESS:=NEXTQUAD; делена и занести значение в поле ADRESS

Замечание:

1.сли Р-указатель на элемент ST, то для ссылки на его атрибуты

достаточно написать P.ADRESS и т.д. 2.Используем следущие атри-

буты(поля ST):

-TYPE (0=UNSIGNED;1=REAL;2=INT;3=BOOLEAN;4=LABEL)

-TYPE1 (1=простая перем.,2=имя массива,3=перем. с индексом)

-TEMPORARY (1=временная перем.,0-нет)

-DECLARED (0=неопределена,1=определена)

-ADBEWS Номер помеченной тетрады или адрес другого элемента ST

-NUMBER Размерность массива

Т.к. правило ::= редуцируется

Характеристики

Список файлов реферата