Реферат: Проектирование трансляторов
лице, чтобы в дальнейшем обращаться к нему не по имени, а по ад-
ресу в таблице.
Хотя лексический анализ по своей идее прост, тем не менее
эта фаза работы компилятора часто занимает больше времени, чем
любая другая. Частично это происходит из-за необходимости прос-
матривать и анализировать исходный текст символ за символом.
Иногда даже бывает необходимо вернуть прочитанный символ во вход-
ной поток с тем, чтобы повторить просмотр и анализ. Происходит
это потому, что часто бывает трудно определить, где проходят гра-
ницы лексемы. В тех случаях, когда выделение лексемы затруднено
либо по причине того, что одно регулярное выражение не позволяет
ее однозначно определить, либо из-за того, что лексема является
частью другой, приходится прибегать к контекстно-зависимым алго-
ритмам анализа с использованием левого и правого направлений
просмотра входной цепочки символов.
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-программы
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
