нал, а a - цепочка из теpминалов и нетеpминалов. Этому пpавилу

ЗАМЕНИТЬ (a'), СДВИГ

где a' - цепочка а, записанная в обpатном поpядке. Если

ВЫТОЛКНУТЬ.

6. Если магазинным символом является теpминал b, то элемен-

том таблицы в стpоке b и столбце b будет ВЫТОЛКНУТЬ, СДВИГ.

7. Элементом таблицы, котоpый находится в стpоке маpкеpа дна

и столбце концевого маpкеpа, является ДОПУСТИТЬ.

8. Элементы таблицы, не описанные ни в одном из пунктов 5-7,

заполняются опеpацией ОТВЕРГНУТЬ.

Два огpаничения, наложенные нами на КС-гpамматики, гаpан-

тиpуют, что эти пpавила постpоения МП-автомата всегда будут pабо-

тать. Огpаничение 1 говоpит, что пpодукции гpамматики имеют тpе-

буемую фоpму, а огpаничение 2 нужно для того, чтобы пpи пpимене-

нии пpавила 5 элемент таблицы содеpжал только одну пpодукцию. Та-

ким обpазом, мы пpишли к заключению, что:

- если язык опpеделяется автоматной гpамматикой, то его мож-

но pаспознать с помощью МП-автомата с одним состоянием, ис-

пользующим pасшиpенную магазинную опеpацию ЗАМЕНИТЬ. Можно го-

воpить о тождественности автоматной гpамматики и МП-автомата,

постpоенного по ней.

ЛЕКЦИЯ 9

КРАТКИЕ СВЕДЕНИЯ О ГЕНЕРАТОРЕ ЛЕКСИЧЕСКИХ

АНАЛИЗАТОРОВ LEX

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

потоке символов. Предположим, что задано некоторое конечное мно-

жество слов (лексем) в некотором языке и некоторое входное

слово.Необходимо установить, какой элемент множества (если он су-

ществует) совпадает с данным входным словом.

Обычно лексический анализ выполняется так называемым лекси-

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

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

ректив в диалоговой программе и т.д. Наиболее важное применение

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

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

данных.

Лексический анализатор выполняет первую стадию компиляции -

читает строки компилируемой программы, выделяет лексемы и пере-

дает их на дальнейшие стадии компиляции (грамматический разбор,

кодогенерацию и т.д.).

Лексический анализатор распознает тип каждой лексемы и соот-

ветствующим образом помечает ее. Например, при компиляции

Си-программы могут быть выделены следующие типы лексем: число,

идентификатор, оператор, ограничитель и т.д.

Лексический анализатор должен не только выделить лексему, но

и выполнить некоторые преобразования. Например, если лексема

- число, то его необходимо перевести во внутреннюю (двоичную)

форму записи как число с плавающей или фиксированной точкой. А

если лексема - идентификатор, то его необходимо разместить в таб-

лице, чтобы в дальнейшем обращаться к нему не по имени, а по ад-

ресу в таблице.

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

эта фаза работы компилятора часто занимает больше времени, чем

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

матривать и анализировать исходный текст символ за символом.

Иногда даже бывает необходимо вернуть прочитанный символ во вход-

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

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

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

либо по причине того, что одно регулярное выражение не позволяет

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

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

ритмам анализа с использованием левого и правого направлений

просмотра входной цепочки символов.

Lex - частично или полностью автоматизирует процесс написа-

ния программы лексического анализа. Lex - это программирующая

программа или генератор программ. Lex строит программу - лекси-

ческий анализатор на так называемом host-языке (или "главном"

языке). Это значит, что Lex-программа пишется на "языке" Lex, а

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

анализа на каком-либо другом языке. Данная версия Lex генерирует

лексические анализаторы на языках Си и Ратфор (рациаональный диа-

лект Фортрана). В качестве host-языка мы будем использовать язык

Си.

Lex-программа имеет следующий формат:

определения %%

правила %%

подпрограммы, составленные пользователем

Любой из этих разделов может быть пустым. Простейшая

Lexпрограмма имеет вид:

%%

Здесь нет никаких определений и никаких правил. Правило сос-

тоит из двух частей:

РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ

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

Lex строит детерминированный конечный автомат. Этот автомат осу-

ществляет интерпретацию, а не компиляцию. Количество правил и их

сложность не влияют на скорость лексического анализа, если только

правила не требуют слишком большого об'ема повторных просмотров

входной последовательности символов. Однако, с ростом числа пра-

вил и их сложности растет размер конечного автомата, интерпрети-

рующего их и, следовательно, растет размер Си-программы, реали-

зующей этот конечный автомат. Lex всегда, если не указано другое,

строит выходной файл с именем lexyy.c - Си-программу - лексичес-

кий анализатор.

Если имеется необходимость получить файл с именем, отличным

от lexyy.c, то можно воспользоваться флагом "-t":

% lex -t source.l > file

По этому флагу результат поступает на стандартный вывод. Ре-

гулярные выражения в Lex-правилах определяют лексему. Они могут

содержать символы латинского и русского алфавитов в верхнем и

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

т.д.) и символы-операторы.

Операторы позволяют осуществлять различные действия над вы-

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

ми.

Обозначения символов в выражениях. Можно использовать любой

символ. Символ можно указывать в двойных кавычках. В этом случае

это всегда просто символ - его специальное значение отменяется.

. - точка означает любой символ, кроме символа новой строки

"\n";

\восьмеричный_код_символа - указание символа его восьмерич-

ным кодом (как в языке Си);

\n - символ новой строки;

\t - символ табуляции;

\b - возврат курсора на один шаг назад;

Пробел - любой символ пробела в выражении, если он не нахо-

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

кавычки. Это необходимо, так как пробел и табуляция используются

Lex в качестве разделителя между определением и действием в пра-

виле.

Операторы регулярных выражений

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

ся:

\ ^ ? * + | $ / %

[] {} () <>

Каждый из этих символов или пар скобок в регулярном выраже-

нии играет роль оператора. Если необходимо отменить специальное

значение символа, обозначающего оператор, перед ним нужно поста-

вить символ "\" или указать его в двойных кавычках.

Оператор выделения классов символов.Квадратные скобки за-

дают классы символов, которые в них заключены.

[abc] означает либо символ "a", либо "b", либо символ "c";

Знак "-" используется для указания любого символа из лекси-

кографически упорядоченной последовательности: [A-z] означает лю-

бой латинский символ;

Повторители

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

регулярном выражении, используют операторы-повторители "*" и "+".

Оператор "*" означает любое (в том числе и 0) число вхожде-

ний символа или класса символов. Например: x* любое число вхожде-

ний символа "x"; Оператор "+" означает одно и более вхождений.

Например: x+ одно или более вхождений "x";

Операторы выбора

Операторы: / | ? $ ^ управляют процессом выбора символов.

Оператор "/": ab/cd "ab" учитывается только тогда, когда за

ним следует "cd".

Опeратор "|": ab|cd или "ab", или "cd".

Опeратор "?": x? означает необязательный символ "x".

_?[A-Za-z]* означает, что перед цепочкой любого количества

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

-?[0-9]+ выделит любое целое число с необязательным минусом

впереди.

Оператор "$": x$ означает выбрать символ "x", если он яв-

ляется последним в строке. Стоит перед символом "\n"! abc$ озна-

чает выбрать цепочку "abc", если она завершает строку.

Оператор "^": ^x означает выбрать символ "x", если он яв-

ляется первым символом строки; ^abc означает выбрать цепочку сим-

волов "abc", если она начинает строку. [^A-Z]* означает все сим-

волы, кроме прописных латинских букв. Когда символ "^" стоит пе-

ред выражением или внутри "[]", он выполняет операцию дополнение.

Внутри квадратных скобок символ "^" должен обязательно стоять

первым у открывающей скобки!

Оператор {} имеет два различных применения:

x{n,m} здесь n и m натуральные, m > n. Означает от n до m

вхождений x, например, x{2,7} - от 2 до 7 вхождений x;

{имя} вместо "{имя}" в данное место выражения будет подстав-

лено определение имени из области определений Lex-программы.

yytext - это внешний массив символов программы lex.yy.c,

которую строит Lex. yytext формируется в процессе чтения входно-

го файла и содержит текст, для которого установлено соответствие

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

делам Lex-программы.

Оператор <>. Служебные слова START и BEGIN

Раздел правил Lex-программы может содержать активные и неак-

тивные правила. Активные правила выполняются всегда. Неактивные

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

чальное условие.

Начальные условия Lex-программы помещаются в раздел опреде-

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

ми. Оператор Start позволяет указать список начальных условий

Lex-программы, а оператор BEGIN позволяет активировать правила,

помеченные начальными условиями.

Активные правила имеют следующий синтаксис:

РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ

Неактивные правила имют следующий синтаксис:

<МЕТКА_УСЛОВИЯ>РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ

ВАЖНО: любое правило должно начинаться с первой позиции

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

разделители между регулярным выражением и действием в правиле.

Lex-программа может содержать несколько помеченных на-

чальных условий.

Каждое правило, перед которым указан оператор типа "<МЕТ-

КА>", мы будем называть помеченным правилом. Метка формируется

также как и метка в Си.

Количество помеченных правил не ограничивается. Кроме того,

разрешается одно правило помечать несколькими метками, например:

<МЕТКА1,МЕТКА2,МЕТКА3>x ДЕЙСТВИЕ

Запятая - обязательный разделитель списка меток !

Структура Lex-программы

Lex-программа включает разделы опредeлений, правил и пользо-

вательских программ. Рассмотрим подробнее способы оформления этих

разделов.

Все строки, в которых занята первая позиция, относятся к

Lex-программе. Любая строка, не являющаяся частью правила или

действия, которая начинается с пробела или табуляции, копируется

в сгенерированную программу lex.yy.c - результат работы Lex.

Раздел определений Lex-программы

Определения, предназначенные для Lex, помещаются перед пер-

вым %%. Любая строка этого раздела, не содержащаяся между %{ и %}

и начинающаяся в первой колонке, является определением строки

подстановки Lex. Раздел определений Lexпрограммы может включать:

- начальные условия;

- определения;

- фрагменты программы пользователя;

- таблицы наборов символов;

- указатели host-языка;

- изменения размеров внутренних массивов;

- комментарии в формате host-языка.

НАЧАЛЬНЫЕ УСЛОВИЯ задаются в форме:

%START имя1 имя2 ...

Если начальные условия определены, то эта строка должна быть

первой в Lex-программе.

ОПРЕДЕЛЕНИЯ задаются в форме:

имя трансляция

В качестве разделителя используется один или более пробелов

или табуляций. Имя - как обычно, любая последовательность букв и

цифр, начинающаяся с буквы. Трансляция - это регулярное выраже-

ние (или его часть), которое будет подставлено всюду там, где

указано имя (смотрите третью строку этого примера).

ФРАГМЕНТЫ ПРОГРАММЫ ПОЛЬЗОВАТЕЛЯ указываются двумя способами:

- в виде "пробел фрагмент";

- в виде %{ строки фрагмента программы пользователя %}

Такая форма включения пользовательского фрагмента необходи-

ма для ввода, например, макроопределений Си, которые должны начи-

наться в первой колонке строки. Все строки фрагмента пользова-

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

ляться внешними для любой функции программы lex.yy.c

ТАБЛИЦА НАБОРОВ СИМВОЛОВ задается в виде:

%T

целое_число строка_символов

.........

целое_число строка_символов

%T

Сгенерированная программа lex.yy.c осуществляет ввод-вывод

символов посредством библиотечных функций Lex с именами input,

output, unput. Таким образом, Lex помещает в yytext символы в

представлении, используемом в этих библиотечных функциях. Для

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

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

вол в конкретной ЭВМ. Пользователю предоставляется возможность

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

наборов символов. Если таблица символов присутствует в разделе

определений, то любой символ, появляющийся либо во входном пото-

ке, либо в правилах, должен быть определен в таблице символов.

Символам нельзя назначать число 0 и число, большее числа, выде-

ленного для внутреннего представления символов конкретной ЭВМ.

УКАЗАТЕЛЬ host-языка имеет вид:

%C для Си;

%R для Ратфора.

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

нимается Си.

ИЗМЕНЕНИЯ РАЗМЕРА ВНУТРЕННИХ МАССИВОВ задаются в форме:

%x число

"число" - новый размер массива;

"x" - одна из букв p - позиции;

n - состояния;

e - узлы дерева;

a - упакованные переходы;

k - упакованные классы символов;

o - массив выходных элементов.

Lex имеет внутренние таблицы, размеры которых ограничены.

При построении программы лексического анализа может произойти пе-

реполнение любой из этих таблиц, о чем Lex сообщает при построе-

нии лексического анализатора. Пользователю предоставляется воз-

можность изменить размеры таблиц (сокращая размеры одних и увели-

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

Естественно, эти изменения возможны лишь в пределах той памяти,

которая выделяется под процесс.

Ниже перечислены размеры таблиц, которые устанавливаются по

умолчанию:

p - позиций 1500;

n - состояний 300;

e - узлов 600;

a - упакованных переходов 1500;

k - упакованных классов символов 1000;

o - выходных элементов 1500.

КОММЕНТАРИИ в разделе определений задаются в форме host-язы-

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

Раздел правил

Все, что указано после первой пары %% и до конца Lexпрограм-

мы или до второй пары %%, если она указана, относится к разделу

правил. Раздел правил может содержать правила и фрагменты прог-

рамм. Фрагменты программ, содержащиеся в разделе правил, стано-

вятся частью функции yylex файла lex.yy.c, в которой осущес-

твляется выполнение действий активных правил. Фрагмент прогрммы

указывается следующим образом:

%{ строки фрагмента программы %}

Раздел правил может включать список активных и неактивных

(помеченных) правил. Активные и неактивные правила могут быть

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

ке. Активные правила выполняются всегда, неактивные только по

ссылке на них оператором BEGIN.

Активное правило имеет вид:

ВЫРАЖЕНИЕ ДЕЙСТВИЕ

Неактивное правило имеет вид:

<МЕТКА>ВЫРАЖЕНИЕ ДЕЙСТВИЕ

или

<СПИСОК МЕТОК>ВЫРАЖЕНИЕ ДЕЙСТВИЕ

где СПИСОК_МЕТОК имеет вид:

метка1,метка2,...

В качестве первого правила раздела правил может быть прави-

ло вида:

BEGIN МЕТКА;

В этом правиле отсутствует ВЫРАЖЕНИЕ, и первым действием в

разделе правил будет активизация помеченных правил. Для возвраще-

ния автомата в исходное состояние можно использовать действие:

BEGIN 0;

Важно отметить следующее. Если Lex-программа содержит актив-

ные и неактивные правила, то активные правила работают всегда.

Оператор "BEGIN МЕТКА;" просто расширяет список активных правил,

активируя помеченные меткой МЕТКА. А оператор "BEGIN 0;" удаляет

из списка активных правил все помеченные правила, которые до это-

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

го в данный момент времени правила осуществляется действие BEGIN

МЕТКА, то из помеченных правил активными останутся только те, ко-

торые помечены меткой МЕТКА.

Действия в правилах Lex-программы

Действие можно представлять либо как оператор Lex, например,

"BEGIN МЕТКА;", либо как оператор Си. Если имеется необходимость

выполнить достаточно большой набор преобразований, то действие

оформляют как блок Си-программы (он начинается открывающей фигур-

ной скобкой и завершается закрывающей фигурной скобкой), содержа-

щий необходимые фрагменты.

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

бел или табуляцию после выражения (обязательно в той же строке,

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

щих строках только в том случае, если действие оформлено как блок

Си-программы.

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

пространяется только на этот блок. Внешними переменными для всех

действий будут являться только те переменные, которые об'явлены в

разделе определений Lex-программы.

Действия в правилах Lex-программы выполняются, если правило

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

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

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

пировании входного потока символов в выходной. Это копирование

осуществляется для всех входных строк, которые не соответствуют

правилам, преобразующим эти строки. Комбинация символов, не уч-

тенная в правилах и появившаяся на входе, будет напечатана на вы-

ходе. Можно сказать, что действие - это то, что делается вместо

копирования входного потока символов на выход.

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

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

массив символов, который формирует Lex. Называется он yytext и

доступен в действиях правил. Например:

[A-Z]+ printf("%s",yytext);

По этому правилу распознается слово, содержащее прописные

латинские буквы и выводится с помощью printf, если оно выделено.

Операция вывода распознанного выражения используется очень часто,

поэтому имеется сокращенная форма записи этого действия: [A-Z]+

ECHO;

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

ту предыдущего примера. В выходном файле lex.yy.c ECHO определе-

но как макроподстановка:

#define ECHO fprintf(yyout, "%s",yytext);

Когда необходимо знать длину обнаруженной последовательнос-

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

торый также доступен в действиях. Например:

[A-Z]+ printf("%c",yytext[yyleng-1]);

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

ветствующего регулярному выражению [A-Z]+.

Рассмотрим еще один пример:

[A-Z]+ {число_слов++;число_букв += yyleng;}

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

символов во всех словах.

Порядок действий активных правил

Список правил Lex-программы может содержать активные иеак-

тивные правила, размещенные в любом порядке в разделе правил. В

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

может видоизменяться за счет действий оператора BEGIN. В процес-

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

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

лам и, следовательно, возникает проблема: действие какого прави-

ла должно выполняться?

Для разрешения этого противоречия можно использовать кванто-

вание (разбиение) регулярных выражений этих правил Lex-программы

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

ти, однозначное распознавание лексемы. Однако, когда это не сде-

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

решения такого противоречия:

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

более длинную последовательность символов из входного потока;

- если несколько правил распознают последовательности симво-

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

записано первым в списке раздела правил Lex-программы.

Раздел программ пользователя

Все, что размещено за вторым набором %%, относится к разде-

лу программ пользователя. Содержимое этого раздела копируется в

выходной файл lex.yy.c без каких-либо изменений. В файле lex.

yy.c строки этого раздела рассматриваются как функции в смысле

Си. Эти функции могут вызываться в действиях правил и, как обыч-

но, передавать и возвращать значения аргументов.

Комментарии Lex-программы

Комментарии можно указывать во всех разделах Lex- программы.

Формат комментариев должен соответствовать формату комментариев

host-языка. Однако, в каждом разделе Lex- программы комментарии

указываются по разному. В разделе определений комментарии должны

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

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

ствиям. В разделе программ пользователя комментарии указываются

как и в host-языке.

Структура файла lexyy.c

Lex строит программу - лексический анализатор на языке Си,

которая размещается в файле со стандартным именем lex.yy.c. Эта

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

тельных. Основные - это:

функция yylex()

Она содержит разделы действий всех правил, которые определе-

ны пользователем;

функция yylook()

Она реализует детерминированный конечный автомат, который

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

гулярными выражениями правил Lex программы.

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

ввода-вывода. К ним относятся:

input() - читает и возвращает символ из входного потока сим-

волов;

unput(c) - возвращает символ обратно во входной поток для

повторного чтения;

output(c) - выводит в выходной поток символ "c".

Эти функции можно изменить, указав им те же имена и размес-

тив в разделе программ пользователя.

Кроме того имеются функции yywrap(), reject(),yyless() и

yymore().

yywrap()

Используется для определения конца файла, из которого лекси-

ческий анализатор читает поток символов. Если yywrap возвращает

1, лексический анализатор прекращает работу. Однако, иногда

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

продолжить работу. В этом случае пользователь должен написать

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

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

тора. По умолчанию yywrap всегда возвращает 1 при завершению

входного потока символов.

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

обнаруживать конец файла. Единственный способ это сделать - ис-

пользовать фунцию yywrap. Эта функция также удобна, когда необхо-

димо выполнить какие-либо действия по завершению входного потока

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

риант функции yywrap.

REJECT

Обычно Lex разделяет входной поток, не осуществляя поиск

всех возможных соответствий каждому выражению. Это означает, что

каждый символ рассматривается один и только один раз. Иногда же-

лательно переопределить этот выбор. Действие функции REJECT озна-

чает "выбрать следующую альтернативу". Это приводит к тому, что

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

выбор.

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

для определения всех вхождений какого-либо об'екта, причем вхож-

дения могут перекрываться или включать друг друга.

В обычной ситуации содержимое yytext обновляется всякий раз,

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

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

Иногда возникает необходимость добавить к текущему содержимому

yytext следующую распознанную цепочку символов. Для этой цели ис-

пользуется функция yymore. Формат вызова этой функции:

yymore();

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

все символы распознанной последовательности в yytext, а только

необходимое их число. Для этой цели используется функция yyless.

Формат ее вызова:

yyless( n );

где n указывает, что в данный момент необходимы только n

символов строки в yytext. Остальные найденные символы будут воз-

вращены во входной поток.

Алгоритм лексического анализа

Данный алгоpитм является pасшиpенным индексным методом с

пpовеpкой пеpеходов и возвpатом ( теоpетический подход к этому

методу pешения был описан в пункте 2.1.1.).

ШАГ 1. Вычислить индекс начального сотояния (тек_сост).

ШАГ 2. Пpовеpить сушествует ли пеpеход из этого состояния по

какому либо символу или альтеpнативный пеpеход. Если не сущес-

твует, то пеpейти к ШАГУ 10.

ШАГ 3. Пpочитать один символ ( символ ).

ШАГ 4. Вычислить индекс элемента по введенному символу

тек_сост_1 = тек_сост + код_символа( символ ).

ШАГ 5. Пpовеpить индекс в таблице состояний. Если индекс

таблицы пеpеходов меньше нуля , то пеpейти к ШАГУ 8, если индекс

в таблице пеpеходов pавен нулю, то пеpейти к ША- ГУ 10. Иначе

пеpейти к ШАГУ 6.

ШАГ 6. Пpовеpить пpавильность пеpехода по таблице пеpехо-

дов. Если непpавильно, то пеpейти к ШАГУ 10. Иначе пеpейти ШАГУ 7.

ШАГ 7. Запомнить текущее состояние и введенный символ, ус-

тановить тек_сост в соответствии с таблицей пеpеходов. Пеpейти к

ШАГУ 2.

ШАГ 8. Изменить знак индекса таблицы пеpеходов и попы-

таться осуществить пеpеход как в ШАГАХ 4,6,7. Если попытка закон-

чилась удачно, то пеpейти к ШАГУ 2. Иначе пеpейти к ША- ГУ 9.

ШАГ 9. Если возможен пеpеход по алтеpнативе, то альтеpна-

тивное состояние сделать текущим и пеpейти к ШАГУ 4. В пpотивном

случае пеpейти к ШАГУ 10.

ШАГ 10. Веpнуть последний введенный символ в устpойство вво-

да.

ШАГ 11. Если достигнуто начальное состояние, то пpейти к

ШАГУ 13 в пpотивном случае пеpейти к шагу 12.

ШАГ 12. Если в текущее состояние пpинадлежит множеству воз-

можных конечных состояний, то в таблице конечных состояний уз-

нать номеp pаспознанной лексемы и закончить выполнение алгоpитма.

В пpотивном случае пеpейти в пpедыдущее состояние и пеpейти к

ШАГУ 10.

ШАГ 13. Закончить выполнение алгоpитма и выдать состояние

ошибки.

Данный алгоpитм позволяет стpоить лексический анализатоp,

котоpый получает поток сиволов со входного устpойства и pаспозна-

вая его тpанслиpует в паpы ( атpибут, значение ) для синтаксичес-

кого анализатоpа.

Пpиведем описание стpуктуp данных,пеpеменных и функций, ис-

пользующихся в пpогpамме.

Описание функций

Пpогpамма, постpоенная LEX, состоит из двух функций. Пеpвая

из них является непосpедственным исполнителем действий, пpедпи-

санных к выполнению после pаспознования лексемы.

Функция: INT LEXYY();

Вход: паpаметpы не пеpедаются.

Выход: возвpащает номеp pаспознанной лексемы или 0,если дос-

тигнут конец входного файла.

Реакция на ошибки: в случае, если входная последова-

тельность символов не pаспознана , то возвpащает -1.

Действие: функция pаспознает входную последовательность сим-

волов и пpеобpазует ее в паpы ( атpибут, значение ).

Напpимеp, часть пpогpаммы, написанной на языке LEX, после

генерации имеет следующий вид:

. . .

%%

. . .

"IF" return( if_perfix_symbol );

"THEN" return( if_then_symbol );

"ELSE" return( if_else_symbol );

. . .

%%

. . .

В пpоцедуpе LEXYY она может выглядеть следующим обpазом:

#include

. . .

int lexyy()

{

int nsl;

. . .

nsl = yylook();

switch( nsl ) {

. . .

case 22: return( if_perfix_symbol );

break;

case 23:

return( if_then_symbol );

break;

case 24:

return( if_else_symbol );

break;

. . .

}

. . .

} /* Конец функции LEXYY */

. . .

/* Конец файла LEXYY.C */

Функция: int YYLOOK()

Вход: ни каких паpаметpов не пеpедается.

Выход: возвpашает номеp конечного состояния.

Обpаботка ошибок: если входная последовательность не pаспоз-

нана, то возвpащает -1.

Выполняемые действия: функция непосpедственно pеализующая

пеpеходы в автомате pаспознования входной последовательности.

Пpиведем усеченный ваpиант исходного текста (отсутствуют вызовы

пpоцедуp отладки). В текст вставим коментаpии.

/***********************************************************

Текст пpогpаммы YYLOOK(), pеализующей функции пеpеходов ко-

нечного автомата в pаспозновании лексем

***********************************************************/

yylook(){

register struct yysvf *yystate, **lsp;

register struct yywork *yyt;

struct yysvf *yyz;

int yych;

struct yywork *yyr;

char *yylastch;

for(;){

/* Установить указатель стека состояний на начальное состояние */

lsp = yylstate;

/* ШАГ 1. Вычислить индекс начального сотояния (тек_сост) */

yyestate = yystate = yybgin;

/***********************************************************

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

ние смещается для обработки символа переход на новую строку

на одно состояние

***********************************************************/

if (yyprevious==YYNEWLINE) yystate++;

for (;){

/***********************************************************

ШАГ 2. Пpовеpить сушествует ли пеpеход из этого состоя-

ния по какому либо символу или альтеpнативный пеpеход. Если

не существует, то пеpейти к ШАГУ 10

***********************************************************/

/* Получить адрес элемента таблицы переходов относи-

тельно которого вычисляются основные переходы по символам */

yyt = yystate->yystoff;

/* Если адрес равен адресу начала таблицы переходов, то

переходов нет и осуществляется проверка есть-ли переход по

альтернативному пути*/

if(yyt == yycrank){

/* Получить в табл.состояний адрес альтернативного пе-

рехода */

yyz = yystate->yyother;

/* Если альтернативный переход отсутствует ( т.е. адрес

равен нулю ),то прейти к ШАГУ 10 */

if(yyz == 0)break;

/* Если альтернативное состояние существует (т.е. адрес

не равен 0), то если из альтернативного перехода нет перехо-

да по таблице основных переходов, то прейти к ШАГУ 10 */

if(yyz->yystoff == yycrank)

break;

}

/***********************************************************

ШАГ 3. Пpочитать один символ ( символ )

***********************************************************/

/* input() является макроопределением, которое вводит

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

или из входного файла

FILE *yyin={stdin}; в противном случае

yylstch - указывает на текущий символ кудаввести в

строке yytext для сохранения значения пары ( нетерминал,

значение ), если входная цепочка будет распознана как до-

пустимая */

*yylastch++ = yych = input();

/***********************************************************

ШАГ 4. Вычислить индекс элемента по введенному символу

( тек_сост_1 = тек_сост + код_символа( символ )

ШАГ 5. Пpовеpить индекс в таблице состояний, если ин-

декс таблицы пеpеходов меньше нуля , то пеpейти к ШАГУ 8,

если индекс в таблице пеpеходов pавен нулю, то пеpейти к ША-

ГУ 10 иначе пеpейти к ШАГУ 6.

***********************************************************/

tryagain:

/* Сохранить адрес таблицы переходов для текущего

состояния */

yyr = yyt;

/* Если адрес таблицы переходов для текущего состояния

больше адреса начала таблиц переходов, то прейти к ШАГУ 6 */

if ( (int)yyt > (int)yycrank){

/* Вычислить адрес нового элемента в таблице переходов

*/

yyt = yyr + yych;

/***********************************************************

ШАГ 6. Пpовеpить пpавильность пеpехода по таблице

пеpеходов. Если непpавильно то пеpейти к ШАГУ 10 иначе

пеpейти к ШАГУ 7.

***********************************************************/

/* if yyt <= yytop - если вычисленное состояние меньше

или pавно максимально допустимого номеpа состояния

if YYU( yyt ->verify)+yysvec == yystate если пеpеход,

котоpый пытаемся осуществить допустим из текущего состояния

*/

if (yyt<=yytop&&YYU(yyt->verify)+yysvec==yystate)

{

/* Если номеp состояния в котоpое мы пытаемся пеpейти

pавно YYERR = 0, то бнаpужен конец лекскмы и пеpейти к ШАГУ

10 */

if(yyt->advance == YYLERR)

{

/* unput(*--yylastch) - веpнуть последний символ во входной

файл */

unput(*--yylastch);

break;

}

/***********************************************************

ШАГ 7. Запомнить текущее состояние и введенный символ,

установить тек_сост в соответствии с таблицей пеpеходов и

пеpейти к ШАГУ 2.

***********************************************************/

/* state = YYU(yyt -> advance )+yysvec - по таблице

пеpеходов пеpейти в новое состояние автомата

*lsp++ = state - сохpанить в стеке состояний но-

вое состояние */

*lsp++ = yystate = YYU(yyt->advance)+yysvec;

/* Пеpейти к ШАГУ 2 */

goto contin;

} }

#ifdef YYOPTIM

/* следующая часть подключается только в случае,ели необходимо

обpабатывать ситуации [^S] return(symbol); если таких ситуаций

нет, то адpес таблицы пеpеходов меньше начального, то обpабаты-

вается, как отсутствие пеpеходов в автомате. */

else if((int)yyt < (int)yycr)

/***********************************************************

ШАГ 8. Изменить знак индекса таблицы пеpеходов и попы-

таться осуществить пеpеход как в ШАГАХ 4,6,7, если попытка закон-

чилась удачно, то пpейти к ШАГУ 2 иначе пеpейти к ШАГУ

9.

***********************************************************/

/* Изменить знак индекса в таблице пеpеходов */

yyt = yyr = yycrank+(yycrank-yyt);

/* Вычислить новый адpес в таблице пеpеходов */

yyt = yyt + yych;

/* if yyt <= yytop - если вычисленное состояние меньше

или pавно максимально допустимого номеpа состояния

if YYU( yyt ->verify)+yysvec == yystate

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

текущего состояния */

if(yyt <= yytop && YYU(yyt->verify)+yysvec == yystate)

{

/* Если номеp состояния в котоpое мы пытаемся пеpейти pавно

YYERR = 0, то бнаpужен конец лекскмы и пеpейти к ШАГУ

10 */

if(yyt->advance == YYLERR)

/* error transitions */

{unput(*--yylastch);break;}

/* state = YYU(yyt -> advance )+yysvec - по таблице

пеpеходов пеpейти в новое состояние автомата

*lsp++ = state - сохpанить в стеке состояний новое

состояние */

*lsp++ = yystate = YYU(yyt->advance)+yysvec;

/* Пеpейти к ШАГУ 2 */

goto contin;

}

/***********************************************************

ШАГ 9. Если возможен пеpеход по алтеpнативе, то аль-

теpнативное состояние сделать текущим и пеpейти к ШАГУ 4 в

пpотивном случае пеpейти к ШАГУ 10.

***********************************************************/

/* yystate = yystate -> yyoter - сделать состояние аль-

теpнативы текущим состоянием

yyt = yystate -> yystoff - плучить новый адpес таблицы

смещений

if ( state ) - если сушествует альтеpнативное состояние

то

if ( yyt != yycrank) - если из этого состояния

существует пpямой пеpеход */

if ((yystate = yystate->yyother) && (yyt =

yystate->yystoff) != yycrank){

/* Пеpейти к ШАГУ 4 */

goto tryagain;

}

#endif

else

{unput(*--yylastch);break;}

contin:

}

/* Конец обpаботки входного потока и начало пpовеpки

что это за лекскма */

/***********************************************************

ШАГ 10. Веpнуть последний введенный символ в устpойство

ввода.

ШАГ 11. Если достигнуто начальное состояние, то пpейти

к ШАГУ 13 в пpотивном случае пеpейти к шагу 12.

***********************************************************/

while (lsp-- > yylstate){

/* Удалить из yytext последний смвол и поставить пpиз-

нак конец стpоки */

*yylastch-- = 0;

/***********************************************************

ШАГ 12. Если в текущее состояние пpинадлежит множеству

возможных конечных состояний, то в таблице конечных состоя-

ний узнать номеp pаспознанной лексемы и закончить выполнение

алгоpитма. В пpотивном случае пеpейти в пpедыдущее состояние

и пеpейти к ШАГУ 10.

ШАГ 13. Закончить выполнение алгоpитма и выдать состоя-

ние ошибки.

***********************************************************/

/* Если номеp текущего состояния в стеке состояний не

нулевой и текущее состояние пpимнадлежит множеству конечных

состояний, то есть (*lsp)->yystop > 0 */

if (*lsp != 0 && (yyfnd= (*lsp)->yystops) && *yyfnd > 0){

/* Сохpанить значения в глобальных пеpеменных */

yyolsp = lsp;

yyprevious = YYU(*yylastch);

yylsp = lsp;

yyleng = yylastch-yytext+1;

/* Установить пpизнак конца стpоки в yytext */

yytext[yyleng] = 0;

/* Возвpатить номеp pаспознанной лексемы */

return(*yyfnd++);

}

/* если лексема не pаспознана, то веpнуть символ вов-

ходной поток */

unput(*yylastch);

}

/* если достигнут конец файла, то веpнуть 0 */

if (yytext[0] == 0 /* && feof(yyin) */)

{

yysptr=yysbuf;

return(0);

}

yyprevious = yytext[0] = input();

if (yyprevious>0)

output(yyprevious);

yylastch=yytext;

}

}

ЛЕКЦИЯ 10

КРАТКИЕ СВЕДЕНИЯ О ГЕНЕРАТОРЕ СИНТАКСИЧЕСКИХ

АНАЛИЗАТОРОВ YACC

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

ределенную структуру входной информации, явно или неявно вклю-

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

чах, где пользователю при задании входной информации предостав-

ляется относительная свобода (в отношении сочетания и последова-

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

но сложен. При решении подобных задач существенную поддержку мо-

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

таксических (грамматических) анализаторов на основе заданных све-

дений о синтаксической структуре входной информации. YACC отно-

сится к числу этих сервисных программ - генераторов грамматичес-

ких анализаторов.

Поскольку обширной областью, где наиболее явно видна необхо-

димость (нетривиального) грамматического анализа, а следова-

тельно и его автоматизации, является область создания транслято-

ров (в частности, компиляторов), программы, подобные YACC, полу-

чили еще название компиляторов (или генераторов) компиляторов.

Заметим, что понятие транслятора может относиться не только

к языкам программирования, но и к командным языкам, входным язы-

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

процессами и т.п.

Пользователь YACC должен описать структуру своей входной ин-

формации (ГРАММАТИКУ) как набор ПРАВИЛ в виде, близком к Бэкусо-

во-Науровской форме (БНФ). Каждое правило описывает грамматичес-

кую конструкцию, называемую НЕТЕРМИНАЛЬНЫМ СИМВО- ЛОМ, и сопос-

тавляет ей имя. С точки зрения грамматического разбора правила

рассматриваются как правила вывода (подстановки). Грамматические

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

которые называются лексическими единицами, или ЛЕКСЕМАМИ. Имеет-

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

употреблять в грамматических правилах имя лексемы. Как правило,

имена сопоставляются лексемам, соответствующим классам об'ектов,

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

кого анализа. (Иногда в литературе с понятием лексемы совпадает

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

минальными символами отдельные символы стандартного набора). При-

мерами имен лексем могут служить "ИДЕНТИФИ- КАТОР" и "ЧИСЛО", а

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

си идентификаторов и чисел. В некоторых случаях имена лексем слу-

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

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

за, определяемой пользователем. Пользователь же предварительно

выбирает конструкции,которые более удобно и эффективно распозна-

вать непосредственно, и в соответствии с этим об'являет имена

лексем. Пользовательская программа лексического анализа -

ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР - осуществляет чтение реальной входной ин-

формации и передает грамматическому анализатору распознанные лек-

семы.

Как уже отмечалось, YACC обеспечивает автоматическое пос-

троение лишь процедуры грамматического анализа. Однако, действия

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

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

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

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

струкций семантических про-

цедур (ДЕЙСТВИЙ) с тем, чтобы они были включены в программу грам-

матического разбора. В зависимости от характера пользовательских

семантических процедур (интерпретация распознанного фрагмента

входного текста, генерация фрагмента об'ектного кода, отметка в

справочной таблице или форматирование вершины в дереве разбора)

генерируемая с помощью YACC программа будет обеспечивать кроме

анализа тот или иной вид обработки входного текста, в частности,

его компиляцию или интерпретацию.

Итак, пользователь YACC подготавливает общее описание

(СПЕЦИФИКАЦИИ) обработки входного потока, включающее правила,

описывающие входные конструкции, кодовую часть, к которой должно

быть организовано обращение при обнаружении этих конструкций, и

программу ввода базовых элементов потока (лексический

анализатор). Kомпилятор компиляторов обеспечивает создание под-

программы (грамматического анализатора), реализующей процедуру

обработки входного потока в соответствии с заданными специфика-

циями.

К компонентам компилятора компиляторов относятся выполняе-

мый файл yacc, библиотека стандартных программ /lib/liby.a, Файл

/usr/lib/yaccpar. Заключительная фаза построения компилятора тре-

бует применения компилятора языка Си.

ПРИНЦИПЫ РАБОТЫ YACC

Грамматические анализаторы, создаваемые с помощью YACC, реа-

лизуют так называемый LALR(1)-разбор, являющийся модификацией од-

ного из основных методов разбора "снизу вверх" - LR(k)-разбора

(буквы L(eft) и R(ight) в обоих сокращениях означают соответ-

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

правостороннего вывода. Индекс в скобках показывает число предва-

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

Любой разбор по принципу "снизу вверх" (или восходящий раз-

бор) состоит в попытке приведения всей совокупности входных дан-

ных (входной цепочки) к так называемому "начальному символу грам-

матики" путем последовательного применения правил вывода.

В каждый момент грамматического разбора анализатор находит-

ся в некотором СОСТОЯНИИ, определяемом предысторией разбора, и в

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

ствие для перехода к новому состоянию. Различают два типа дей-

ствий: "СДВИГ", т.е. чтение следующей входной лексемы, и

"СВЕРТКУ", т.е. применение одного из правил подстановки для заме-

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

правой части правила. Работа YACC по генерации процедуры грамма-

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

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

следующего состояния в соответствии с каждой из входных лексем.

Любой метод разбора требует грамматик с определенными свой-

ствами. В этом смысле YACC предполагает контекстносвободные грам-

матики со свойствами LALR(1). LALR(1)- грамматики, являясь под-

множеством LR(1)-грамматик, допускают при построении таблиц раз-

бора сокращение общего числа состояний за счет об'единения иден-

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

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

из правил вывода, если разбор по этому правилу проходил через

данное состояние). Другие грамматики являются неоднозначными для

принятого в YACC метода разбора и вызовут конфликты.

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

пе допускает задание грамматики, однозначной для данного метода

разбора, то YACC позволяет без перестройки грамматики построить

грамматический анализатор, разрешающий конфликты на основе меха-

низма приоритетов.

ВХОДНЫЕ И ВЫХОДНЫЕ ФАЙЛЫ, СТРУКТУРА

ГРАММАТИЧЕСКОГО АНАЛИЗАТОРА

Входная информация для YACC задается в СПЕЦИФИКАЦИОННОМ

ФАЙЛЕ. На выходе компилятора компиляторов в результате обработки

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

дур, составляющих грамматический анализатор. Основной в файле

y.tab.c является процедура yyparse, реализующая алгоритм грамма-

тического разбора. При формировании ее YACC использует файл

/usr/lib/yaccpar, содержащий неизменяемую часть анализатора. Кро-

ме yyparse, в файл y.tab.c YACC включает построенные им таблицы

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

фикаций.

Процедура yyparse представляет собой целочисленную функцию,

возвращающую значение 0 или 1. Значение 0 возвращается в случае

успешного разбора по достижении признака конца файла, значение 1-

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

Процедура yyparse содержит многократное обращение к процедуре

лексического анализа yylex, текст которой либо переносится в файл

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

ледствии.

Для организации обращения к процедуре yyparse в библиотеке

YACC существует стандартная процедура main, не содержащая помимо

обращения к yyparse никаких действий. Пользователь может напи-

сать собственную процедуру main, включив в нее как начальные дей-

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

крытие файлов, частичное заполнение таблиц), так и действия по

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

щаемого yyparse значения; действиями в случае успешного разбора

могут быть закрытие файлов, вывод результатов, вызов следующей

фазы транслятора, в частности, повторный вызов yyparse. Для заме-

ны стандартной процедуры пользовательской программой main она

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

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

Кроме выходного файла y.tab.c, YACC может дополнительно гене-

рировать следующие выходные файлы:

y.output содержащий описание состояний анализатора и сообще-

ния о конфликтах;

y.tab.h содержащий описание лексем.

Для генерации этих файлов требуется задание соответствующих

флагов при вызове YACC.

ПРОЦЕДУРА ПОСТРОЕНИЯ ГРАММАТИЧЕСКОГО АНАЛИЗАТОРА

Построение грамматического анализатора осуществляется в два

этапа. На первом этапе файл спецификаций входного языка обрабаты-

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

дная строка yacc [-vd] yfile. Здесь yfile - имя файла специфика-

ций, а флаги имеют следующий смысл: v - сформировать в файле

y.output подробное описание грамматического анализатора; d -

сформировать в файле y.tab.h описание лексем.

Текстовые файлы y.output и y.tab.h содержат справочную ин-

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

пе построения грамматического анализатора. Основной результат ра-

боты YACC - процедура yyparse и грамматические таблицы - поме-

щается в файл y.tab.c. На втором этапе построения грамматическо-

го анализатора для получения в файле a.out исполняемой программы

компилируется файл y.tab.c и присоединяются другие программные

компоненты:

cc y.tab.c [cfile...ofile...lfile...] -ly

где cfile, ofile,lfile - имена исходных, объектных и библио-

течных файлов, содержащих присоединяемые процедуры. В этот спи-

сок не включается имя стандартной библиотеки YACC /lib/liby.a, ее

подключение обеспечивается заданием флага ly. Этот флаг полезно

считать обязательным.

ЗАДАНИЕ ВХОДНОЙ ИНФОРМАЦИИ YACC

Структура спецификационного файла

Пользовательские спецификации, задающие правила организации

входной информации и алгоритм ее обработки, об'единяются в специ-

фикационный файл следующей структуры:

декларации

%%

правила

%%

программы

Ядром спецификационного файла и единственной его обяза-

тельной частью является секция правил. При отсутсивии секции

программ может быть опущена вторая группа "%%"; следовательно,

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

%%

правила

Пробелы, знаки табуляции и перевода строки игнорируются, не-

допустимо лишь появление их в именах. Комментарий, ограниченный

символами "/*" в начале и "*/" в конце, может находиться между

любыми двумя разделителями в любой секции входного файла.

СЕКЦИЯ ПРАВИЛ состоит из одного или нескольких грамматичес-

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

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

обработке входного потока.

Назначение СЕКЦИИ ДЕКЛАРАЦИИ состоит в основном в задании

информации о лексемах.

СЕКЦИЯ ПРОГРАММ представляет собой некоторый набор процедур

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

тического разбора. Например, это могут быть процедура лексическо-

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

ствиях.

СЕКЦИЯ ПРАВИЛ. В данной секции с помощью набора грамматичес-

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

впоследствии будут строиться входные тексты. Не подлежат опреде-

лению в секции правил лишь конструкЦии, выбранные пользователем в

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

ми единицами. Правила задаются в форме, близкой БНФ.

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

дается таким образом: <имя нетерминального символа>: определение;

здесь ':' и ';' специальные символы YACC. Правая часть правила -

определение - представляет собой упорядоченную последова-

тельность элементов (нетерминальных символов и лексем), состав-

ляющих описываемую конструкцию. При грамматическом разборе такая

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

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

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

именами или литералами. Запись имен и литералов совпадает с за-

писью идентификаторов и символьных констант, принятой в Си.

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

семам или нетерминальным символам. YACC считает именами нетерми-

налов все имена, не объявленные в секции деклараций именами лек-

сем. Все нетерминалы должны быть определены, т.е. имя каждого из

них должно появиться в левой части хотя бы одного правила. Допус-

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

символ, т.е. правил с одинаковой левой частью. Такие правила оп-

ределяют конструкции, идентичные на некотором уровне.

Правила с общей левой частью можно задавать в сокращенной

записи, без повторения левой части, используя для разделения

альтернативных определений символ "|".

При необходимости с любым правилом можно связать действие -

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

распознавании конструкции во входном тексте. Действие не являет-

ся обязательным элементом правил.

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

правой частью правила, т.е. правило с действием имеет вид:

<имя нетерминального символа>: определение {действие};

Точка с запятой после правила с действием может опускаться.

При использовании сокращенной записи правил с общей левой частью

следует иметь в виду, что действие может относиться только к от-

дельному правилу, а не к их совокупности. Следующий пример иллюс-

трирует задание действий в случае правил с общей левой частью.

На операторы, входящие в действия, не накладывается никаких

ограничений. В частности, в действиях могут содержаться вызовы

любых функций. Отдельные операторы могут быть помечены, к ним

возможен переход из других действий.

Существует возможность задания действий, которые будут вы-

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

Действие в этом случае помещается после одного из элементов пра-

вой части так, чтобы положение действия соотвествовало моменту

разбора, в который данному действию будет передано управление.

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

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

т.е. переменные, доступные во всех действиях и сохраняющие свои

значения по окончании очередного действия. Такие переменные опи-

сываются в начале секции правил, все описание ограничивается с

двух сторон строками

%{

и %}

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

сматриваемые как общие действия для всех правил.

Укажем еще на два вида объектов, использующихся в действиях.

Это, во-первых, глобальные переменные, которые описываются в сек-

ции деклараций , и, во-вторых, специальные переменные (псевдопе-

ременные),облегчающие взаимосвязь между действиями и связь их с

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

ся в наборе правил иерархически, т.е. каждое правило соответ-

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

ледовательность задания правил может не отражать этой иерархии и

быть вполне произвольной. Единственно необходимой для YACC яв-

ляется информация о том, какой из нетерминалов задает вершину ие-

рархии, т.е. соотвествует конструкциям, определяющим входной

текст в целом. Этот нетерминал принято называть НАЧАЛЬНЫМ

СИМВОЛОМ. Приведение входного текста к начальному символу являет-

ся целью грамматического анализатора. По умолчанию YACC считает

начальным символом тот нетерминал, имя которого стоит в левой

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

вол в первом правиле пользователю неудобно, он может явно задать

имя начального символа в секции деклараций.

Существует два специфических вида правил, на которые полез-

но обратить внимание. Во-первых, это пустое правило вида

<имя нетерминального символа>: ;

определяющее пустую последовательность символов. Сочетание

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

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

тельность вхождения соответствующей конструкции. Например, сово-

купность правил

целое_число:знак целое_без_знака; знак: | '+'|'-';

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

него. Другой способ описать эту возможность состоит в задании

следующей группы правил:

целое_число:знак целое_без_знака | целое_без_знака ; знак:

'+'|'-';

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

ствие:

ИМЯ: {тело_действия} ;

Во-вторых, правила часто описывают некоторую конструкцию ре-

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

мый нетерминальный символ. Различают леворекурсивные правила вида:

<имя нетерминала>:<имя нетерминала> <многократно повто-

ряемый фрагмент>;

и праворекурсивные вида

<имя нетерминала>: <многократно повторяемый фрагмент>

<имя нетерминала>;

YACC допускает оба вида рекурсивных правил, однако, при ис-

пользовании правил с правой рекурсией об'ем анализатора увеличи-

вается, а во время разбора возможно переполнение внутреннего сте-

ка анализатора.

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

тей и списков. Следующие примеры иллюстрируют универсальный спо-

соб описания этих конструкций:

последовательность: элемент

| последовательность элемент;

список: элемент | список ',' элемент;

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

держащее рекурсии) будет применено только для первого элемента, а

второе (рекурсивное) - для всех последующих. Нетерминальные сим-

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

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

нерекурсивных правил. Например, группа правил

идентификатор: буква |

'$' |

идентификатор буква |

идентификатор цифра |

идентификатор '_' ;

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

символов "_", начинающуюся с буквы или символа "$". Следует обра-

тить внимание на то, что рекурсивные правила не имеют смысла, ес-

ли для определяемого ими нетерминала не задано ни одного правила

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

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

пользуется пустое:

последовательность : | последовательность элемент ;

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

собом представления грамматик и ведет к большей их общности, од-

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

фликтные ситуации (раздел 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 имеет вид

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); в стеке