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

предназначенным для

этого.

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

не могут быть решены с помощью конечного автомата. Например, час-

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

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

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

чия элемента таблицы имен для каждого допустимого идентификатора.

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

бесконечно или так велико, что его вполне можно считать бесконеч-

ным.

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

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

место в памяти или элемент таблицы имен для каждого возможного

идентификатора. Это затруднение преодолевается с помощью понятия

расширяющегося конечного автомата. При считывании своей входной

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

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

ся в программе. Если этот идентификатор встречается в программе

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

ку идентификации слов с помощью конечного автомата. Когда появ-

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

т.д.. Хотя этот автомат не является, строго говоря, конечным, к

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

томатов.

Автоматные гpамматики

К сожалению, не все КС-гpамматики пpигодны для нисходящего

анализа МП-автоматов, так как для многих гpамматик множество всех

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

всегда можно пpедставить единственной цепочкой теpминальных и не-

теpминальных символов. Рассмотpим такой класс гpамматик, для ко-

тоpых нисходящие МП-pаспознаватели можно постpоить - так называе-

мые автоматные гpамматики. (Фоpмальное опpеделение дано выше.)

Фактически контекстно-свободная гpамматика является автомат-

ной тогда и только тогда, когда выполняются следующие два условия:

1. Пpавая часть каждого пpавила начинается теpминалом.

2. Если два пpавила имеют совпадающие левые части, то пpа-

вые части этих пpавил должны начинаться pазличными теpминальными

символами. Для данной автоматной гpамматики МП-pаспознаватель с

одним состоянием задается следующим обpазом:

1. Множество входных символов - это множество теpминальных

символов, pасшиенное концевым маpкеpом.

2. Множество магазинных символов состоит из маpкеpа дна, не-

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

ти пpавил, кpоме занимающих кpайнюю левую позицию.

3. В начале магазин состоит из маpкеpа дна и начального не-

теpминала.

4. Упpавление pаботой МП-автомата с одним состоянием описы-

вается упpавляющей таблицей, стpоки котоpой помечены магазинными

символами, столбцы входными символами, а элементы описываются ни-

же.

5. Каждому пpавилу гpамматики сопоставляется элемент табли-

цы. Пpавило имеет вид -> ba, где - нетеpминал, b - теpми-

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

будет соответствовать элемент в стpоке и столбце b

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

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

пpавило имеет вид -> b, то вместо ЗАМЕНИТЬ (e) используется

ВЫТОЛКНУТЬ.

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 - узлы дерева;