Реферат: Проектирование трансляторов
занного действия. При этом независимо от характера действия оче-
редной элемент в стеке значений отводится для хранения значения
неявно присутствующего "пустого" нетерминала. В действии, находя-
щемся в конце правила, соглашение о значениях псевдопеременных
остается прежним, если иметь в виду наличие дополнительных симво-
лов. В приведенном выше правиле в действии 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
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, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
