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

од-

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

фликтные ситуации (раздел 5) из-за неоднозначности выбора нетер-

минала, соответствующего пустой последовательности.

Секция деклараций состоит из последовательности строк двух

видов: строк-директив и строк исходного текста.

Строки исходного текста без изменений копируются в выходной

файл y.tab.c и могут содержать операторы препроцессора и описа-

ние внешних об'ектов. Область действия переменных, описанных в

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

файл, т.е. они доступны как в операторах действий, так и в проце-

дурах, находящихся в секции программ.

Строки-директивы начинаются символом "%" (этот символ в YACC

играет роль своего рода esc-символа). Две специальные директивы

%{ и %} ограничивают с двух сторон группы строк исходного текста.

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

о грамматике.


ДЕКЛАРАЦИЯ ИМЕН ЛЕКСЕМ


%token <список имен лексем>


Пользователь при описании грамматики решает, какие конструк-

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

этапе лексического анализа, и на уровне этих конструкций (лексем)

задает грамматические правила. Все виды лексем, кроме литералов,

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

секции правил. Благодаря декларации имен лексем в директиве

%token YACC отличает имена лексем от имен нетерминальных симво-

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

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

рективу %token напоминанием о необходимости построения лексичес-

кого анализатора и руководствоваться этой директивой при его на-

писании.

Заметим, что ключевые слова описываемого входного языка час-

то бывает удобно считать лексемами. Имена лексем могут совпадать

с этими ключевыми словами, недопустимым является лишь совпадение

имен лексем с зарезервированными словами языка Си.


ДЕКЛАРАЦИЯ ПРИОРИТЕТОВ И АССОЦИАТИВНОСТИ ЛЕКСЕМ


%left <список лексем>

%right <список лексем>

%nonassos <список лексем>


Лексемы в данных директивах задаются литералами или именами.

В последнем случае декларация приоритета заменяет также деклара-

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

является желательным присутствие в списке директивы %token всего

набора имен лексем.

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

приоритета или ассоциативности.

При вызове YACC с флагом -d последовательность операторов

#define помещается также в информационный файл y.tab.h.

Переопределив при необходимости ряд номеров типов лек-

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

пользуемых лексем.


ДЕКЛАРАЦИЯ ИМЕНИ НАЧАЛЬНОГО СИМВОЛА


%start <имя начального символа>


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

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

тическим правилом.

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

генерируемую программу грамматического анализа. Любая из опреде-

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

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

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

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

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

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

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

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

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

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


main() { return (yyparse(); }


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

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


#include

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 имеет вид


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

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

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

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