Проектирование трансляторов

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.Условные инструкции

<инстр1>::=<условие><инстр2>ELSE<инстр3>│<условие><инстр2>

<условие>::=IF<выраж>THEN,


где <выраж> должно иметь тип BOOLEAN.

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

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

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

<инстр2> <инстр2>

(q) BR r (q)

(q+1) <инстр3>

(r)


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

<условие>::=IF<выраж>THEN и имеет следующий вид:


(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 тетрады, в которую позднее надо добавить адрес перехода, который еще не известен


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

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

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

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

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

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

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

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

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

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

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


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

<инстр1>::=<ист.часть><инстр3>

<ист.часть>::=<условие><инстр2>ELSE

<ист.часть>::=<условие><инстр2>ELSE

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

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

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

QUAD(I,2):=NEXTQUAD;


<инстр1>::=<ист.часть><инстр3>

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

QUAD(I,2):=NEXTQUAD; <инстр2> в (BR...)


Выводы:

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

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

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

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

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

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

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

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

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

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

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

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


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


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

<инстр1>::=I:<инстр2>,где

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

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

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


<инстр1>::=<опред.метки><инстр2>

<опред.метки>::=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 Размерность массива


Т.к. правило <инстр1>::=<опред.метки><инстр2> редуцируется

после генерации тетрад <инстр2>, то с ним не связывается никакой

дополнительной семантики ZB: инструкция GOTO в Фортране ис-

пользует подпрограмму просмотра всей ST (LOOKUP) ,т.к. метки ин-

струкций не должны повторяться.


<инстр>::=GOTO I

LOOKUP(I.NAME,P);

IF P=0 THEN

BEGIN INSERT(I.NAME,P);

P.TYPE:=LABEL;

P.DECLARED:=0;

END

ELSE CHECKTYPE(P,LABEL);

ENTER(BRL,P,0,0);


Подпрограмма CHECKTYPE(P,LABEL) сравнивает тип элемента ST,

на который указывает P с LABEL. В случае несовпадения печатается

сообщение об ошибке и ABORT.


3.Переменные и выражения

<пер>::=I|I(<список выр>)

<список выр>::=выр|<списоквыр>,<выр>


<пер>:=I -тетрад не генерирует

LOOKUP(I.NAME,P); поиск идентификатора

IF P=0 THEN ERROR(4);

<пер>.ENTRY:=P; связать с <пер> адрес найденного в ST элемента

В фортране если Р=0 нужно с помощью процедуры INSERT внести

идентифика тор в ST и установить TYPE равнымREAL или INT в зави-

симости от первой буквы идентификатора.

При обработке переменной с индексом I (<список выр>) необхо-

димо:

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

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

тод.

Чтобы вычислить VARPART необходимо преобразовать синтаксис


<инд>::=I(<выр>|<инд>,<выр> <пер>::=<инд>)


Программа для <инд>::=I(<выр> должна найти идентификатор

массива, сгенерировать тетрады для VARPART:=<выр> и связать с

<инд> адрес элемента ST для d1. <инд>::=I(<выр> LOOKUP(I.NAME,P);

-поиск идентификатора IF P=0 OR P.TYPE !=2 -он должен быть в ST и

иметь тип ARRAY.


THEN ERROR(5)

<инд>.COUNT:=P.NUMBER-1;-подсчет количества индексов

<инд>.ARR:=P; -запомнить адрес описателя массива

<инд>.ENTRY:=P+1; -занести в ENTRY адрес элемента ST для d1

GENERATETEMP(P); -генерация временной перем. типа INT для VARPART

P.TYPE:=INTEGER; -запомнить ее адрес

<инд>.ENTRY2:=P; -генерация тетрад для преобразования типа, если

CONVERTRI(<выр>.ENTRY); они нужны

P:=<выр>.ENTRY;

ENTER(:=,P,,<инд>.ENTRY2); -генерация тетрады занесения первого

индекса в VARPART


Подпрограмма GENERATETEMP(P) заносит в ST элемент для вре-

менной переменной, а адрес этого нового элемента возвращает в P.

Подпрограмма CONVERTRI(P)проверяет тип P-го элемента ST. Если тип

- INT, то ничего не делается, если REAL, то с помощью

GENERATETEMP заводится новая временная переменная типа INT и ге-

нерируется CVRI-тетрада для преобразования заданной переменной в

тип INT и занесения результата в новую временную переменную. Ука-

затель на временную переменную в ST остается в P. Если тип тип

Р-го элемента не INT и не REAL, то выдается сообщение об ошибке.

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

<инд>:

1.<инд>.ENTRY -адрес элемента ST для d1(для di,если сгенери-

рован код i-го индексного выражения)

2.<инд>.ENTRY2 -адрес элемента ST для VARPART

3.<инд>.COUNT -[размерность - i], если сгенерирован код для

i-го индексного выражения

4.<инд>.ARR -адрес описателя имени массива в ST

Теперь для правила <инд1>::=<инд2>,<выр> надо сгенерировать

код, реализующий формулу VARPART:=VARPART*d1+<выр>, если это

второе по счету индексное выражение.

<инд1>::=<инд2>,<выр>

<инд1>.COUNT:=<инд2>.COUNT-1; -подсчет индексов

<инд1>.ARR:=<инд2>.ARR; -эапомнить тип элемента

<инд1>.ENTRY:=<инд2>.ENTRY+1;-в <инд1>.ENTRY занесли ук-ль на эл-тST для di

P1:=<инд2>.ENTRY2; -в P1 и в ENTRY2 адреса элемента ST для VARPART

<инд1>.ENTRY2:=P1;

ENTER(*,P1,<инд>.ENTRY,P1); -генерация тетрады VARPART=VARPART*di

P:=<выр>.ENTRY; -генерация тетрад преобразования R->I(если надо)

ENTER(+,P!,P,P!); -генерация тетрады VARPART=VARPART+индекс

Заметим, что мы всегда имеем дело не с самим выражением, а с

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

выражения. Для правила <пер>::=<инд>) надо проверить (при компи-

ляции) количество индексных выражений и построить элемент STс

описанием элемента массива.

<пер>::=<инд>)

IF <инд>.COUNT!=0

THEN ERROR(6);

GENERATETEMP(P); -генерирование временной переменной для описателя

P.TYPE1%=3; элемента массива

P.TYPE:=<инд>.ARR.TYPE; -занести тип1,адресс эл-та ST дляVARPART,

P.ADRESS:=<инд>.ENTRY2; адрес эл-та ST, содержащего имя массива

P.NUMBER:=<инд>.ARR.NUMBER;

Трансляция описаний массивов

1) В польской записи описание массива

ARRAY A [L1:U1,...Ln:Un] можно представить в виде

L1U1...LnUn A ADEC

2) Для тетрад в виде

BOUNDS L1,U1

...

BOUNDS Ln,Un

ADEC A

Операция ADEC выполняет при семантической обработке следу-

щие действия:

-заносит запись о каждом массиве в ST;

-выделяет для каждого массива две ячейки:одну для хранеия

адреса начала массива, другую - для хранения адреса допвектора;

-формирует в обьектной программе (при генерации кода) коман-

ды, обеспечивающие перед входом в блок:

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: