Смекни!
smekni.com

Проектирование трансляторов (стр. 17 из 31)

секции программ спецификационного файла, либо присоединяться на

этапе вызова Си-компилятора для трансляции файла y.tab.c и компо-

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

этих способов должны быть заданы:

- лексический анализатор - функция с именем yylex();

- все процедуры, вызовы которых содержатся в действиях, свя-

занных с грамматическими правилами;

- главная процедура main() при необходимости заменить ее

стандартный библиотечный вариант, который имеет вид:

main() { return (yyparse(); }

- процедура обработки ошибок yyerror() - также для замены

библиотечного варианта (его текст приводится ниже).

#include <stdio.h>

yyerror(s)char *s; { fprintf(stderr, "%s0, s);}

Для обеспечения корректной работы грамматического анализато-

ра функция лексического анализа yylex должна быть согласована с

конкретной спецификацией грамматики и удовлетворять определенным

требованиям. Основная задача функции yylex состоит во вводе из

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

соответствующей одной из лексем, и возвращении номера типа этой

лексемы. Для нелитеральных лексем номером типа может служить

об'явленное в секции деклараций имя лексемы (с помощью механизма

#define YACC обеспечивает замену его нужным номером), в случае

литералов номером типа является числовое значение символа (если

оно не было переопределено). Алгоритм поиска должен заключаться в

попытке нахождения сначала более сложных (нелитеральных) лексем и

лишь при несовпадении ни с одной из них текущих элементов ввода

возвращать номер типа литеральной лексемы (любой однозначный сим-

вол, не начинающий ни одну из возможных лексем, сам образует лек-

сему).

Действия с использованием псевдопеременных.Для обеспечения

связи между действиями, а также между действиями и лексическим

анализатором создаваемые YACC грамматические анализаторы поддер-

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

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

в стек после ее распознавания лексическим анализатором (напомним,

что им считается текущее значение переменной yylval). После каж-

дой свертки вычисляется значение нетерминала, заместившего свер-

нутую строку, и помещается в вершину стека; значения элементов

правой части примененного правила перед этим выталкиваются из

стека. Заметим, что таким образом к моменту свертки любого прави-

ла все значения нетериналов в правой части оказываются вычислен-

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

ла будет рассмотрен ниже.

Описанный механизм не требует вмешательства пользователя и

предоставляет ему следующие возможности:

- Использовать в действиях, осуществляемых после свертки по

правилу, значение любого элемента его правой части. Доступ к этим

значениям обеспечивается набором так называемых ПСЕВДОПЕРЕМЕННЫХ

с именами $1,$2,..., где $i соответствует значению i-го элемента;

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

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

- Формировать в действиях значение, образованного в ре-

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

псевдопеременной с именем $$. Eсли в действии не определяется

значение переменной $$ (а также если действие отсутствует), зна-

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

ние первого элемента правой части, т.е. неявно выполняется прис-

ваивание.

Несколько иная ситуация в отношении использования псевдопе-

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

вой части. На самом деле YACC интерпретирует правило вида

A: B C {действие 1} D {действие 2} K

как

A: B C EMPTY1 D EMPTY2 K;

EMPTY1: {действие 1}

EMPTY2: {действие 2}

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

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

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

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

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

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

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

лов. В приведенном выше правиле в действии 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+Т переводится в запись Е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