Реферат: Проектирование трансляторов
писании.
Заметим, что ключевые слова описываемого входного языка час-
то бывает удобно считать лексемами. Имена лексем могут совпадать
с этими ключевыми словами, недопустимым является лишь совпадение
имен лексем с зарезервированными словами языка Си.
ДЕКЛАРАЦИЯ ПРИОРИТЕТОВ И АССОЦИАТИВНОСТИ ЛЕКСЕМ
%left <список лексем>
%right <список лексем>
%nonassos <список лексем>
Лексемы в данных директивах задаются литералами или именами.
В последнем случае декларация приоритета заменяет также деклара-
цию имени лексемы, хотя в целях обеспечения наглядности описания
является желательным присутствие в списке директивы %token всего
набора имен лексем.
Использование лексемы само по себе не требует задания ее
приоритета или ассоциативности.
При вызове YACC с флагом -d последовательность операторов
#define помещается также в информационный файл y.tab.h.
Переопределив при необходимости ряд номеров типов лек-
сем,пользователь должен проверить уникальность номеров у всех ис-
пользуемых лексем.
ДЕКЛАРАЦИЯ ИМЕНИ НАЧАЛЬНОГО СИМВОЛА
%start <имя начального символа>
Директива отменяет действующий по умолчанию выбор в качес-
тве начального символа нетериминала, определяемого первым грамма-
тическим правилом.
Секция программ-процедуры, которые должны быть включены в
генерируемую программу грамматического анализа. Любая из опреде-
ляемых пользователем программных компонент может находиться в
секции программ спецификационного файла, либо присоединяться на
этапе вызова Си-компилятора для трансляции файла 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
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
