Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 4
Текст из файла (страница 4)
Пусть s - представитель.Предположим, что на входе a в M существует переход из s в t. Пусть r представитель группы t. Тогда М' имеет переход из s в r по a. Пустьначальное состояние М' - представитель группы, содержащей начальноесостояние s0 исходного M, и пусть заключительные состояния М' представители в F. Отметим, что каждая группа Пres либо состоит толькоиз состояний из F, либо не имеет состояний из F.Шаг 5. Если М' имеет мертвое состояние, т.е.
состояние d, которое не30является допускающим и которое имеет переходы в себя по любомусимволу, удалим его из М'. Удалим также все состояния, не достижимыеиз начального.На рис. 2.13 приведен пример применения алгоритма.2.6. Программирование лексических анализаторовЛексический анализатор, как правило, вызывается как подпрограмма. Приобращении к ЛА вырабатываются как минимум два результата: типвыбранной лексемы и значение (или указатель на значение) для классовлексем (идентификаторов, чисел, строк и т.д.).
Само значение передается,если ЛА не работает с таблицей имен. Если же ЛА сам формирует таблицуимен, то он выдает указатель на имя. Обычно ЛА оформляется какпроцедура-функция, вырабатывающая тип лексемы и заносящая внекоторую глобальную переменную значение лексемы, если этонеобходимо. Помимо значения лексемы, эта глобальная переменная можетсодержать некоторую дополнительную информацию: номер текущейстроки, номер символа в строке и другую. Эта информация можетиспользоваться в различных целях, например, для диагностики.ТелоЛАпредставляетсобойдиаграммупереходовсоответствующего конечного автомата. Отдельная проблема - анализключевых слов.
Как правило, ключевые слова - это выделенныеидентификаторы. Поэтому возможны два основных способа выделенияключевых слов: либо очередная лексема сначала диагностируется насовпадение с каким-либо ключевым словом и в случае неуспеха делаетсяпопытка выделить лексему из какого-либо класса, либо, наоборот, послевыборки лексемы идентификатора требуется заглянуть в таблицуключевых слов на предмет сравнения. Подробнее о механизмах поиска втаблицах будет сказано ниже (гл.
7), здесь отметим только, что поискключевых слов может вестись либо в основной таблице имен и в этомслучае в нее до начала работы ЛА загружаются ключевые слова, либо вотдельной таблице. При первом способе все ключевые слованепосредственно встраиваются в конечный автомат лексическогоанализатора, во втором конечный автомат содержит только разборидентификаторов.В некоторых языках (например, ПЛ/1 или Фортран) ключевые словамогут использоваться в качестве обычных идентификаторов. В этомслучае работа ЛА не может идти независимо от работы синтаксическогоанализатора.
В Фортране возможны, например, следующие строки:31DO 10 I=1,25 иDO 10 I=1.25В первом случае строка - это заголовок цикла DO, во втором - операторприсваивания. Поэтому, прежде чем можно будет выделить лексему,лексический анализатор должен заглянуть довольно далеко.Еще сложнее дело в ПЛ/1.
Здесь возможны такие операторы:IF THEN THEN THEN = ELSE; ELSE ELSE = THEN илиDECLARE (ARG1, ARG2, ...., ARGn) ...и только в зависимости от того, что стоит после ")", можно определить,является ли DECLARE именем подпрограммы или объявлением. Длинатакой строки может быть сколь угодно большой и уже невозможноотделить фазу синтаксического анализа от фазы лексического анализа.Рассмотрим несколько подробнее вопросы программирования ЛА.Основная операция лексического анализатора, на которую уходит большаячасть времени его работы, - это взятие очередного символа и проверка напринадлежность его некоторому диапазону.
Например, основной цикл привыборке числа в простейшем случае может выглядеть следующимобразом:while (Insym<='9' && Insym>='0'){}Программу можно значительно улучшить следующим образом [2]. ПустьLETTER, DIGIT, BLANK, SLESS - элементы перечислимого типа. Введеммассив MAP, входами которого будут символы, значениями - типысимволов. Инициализируем массив MAP следующим образом:MAP['A']:=LETTER;........MAP['z']:=LETTER;MAP['0']:=DIGIT;........MAP['9']:=DIGITMAP[' ']:=BLANK;MAP['<']:=SLESS;........Тогда приведенный выше цикл примет следующую форму:while (Map[Insym]==Digit){}32Выделение ключевых слов может осуществляться после выделенияидентификаторов. ЛА работает быстрее, если ключевые слова выделяютсянепосредственно.fНе буква и не цифраiКлючевое слово ifБуква или цифраИдентификаторnНе ttНе f и не nБуква или цифраНе буква и не цифраКлючевое слово intРис.
2.14Для этого строится конечный автомат, описывающий множествоключевых слов. На рис. 2.14 приведен фрагмент такого автомата.Рассмотрим пример программирования этого конечного автомата на языкеСи, приведенный в [3]:case 'i':if (cp[0]=='f' &&!(map[cp[1]] & (digit | letter))){cp++; return IF;}if (cp[0]=='n' && cp[1]=='t'&&!(map[cp[2]] & (digit | letter))){cp+=2; return INT;}Здесь cp - указатель текущего символа. В массиве map классы символовкодируются битами.Поскольку ЛА анализирует каждый символ входного потока, егоскорость существенно зависит от скорости выборки очередного символавходного потока. В свою очередь, эта скорость во многом определяетсясхемой буферизации.
Рассмотрим несколько возможных эффективныхсхем буферизации.В первой схеме используется буфер, размер которого - двойнаядлина блока обмена N (рис. 2.15).33NN##ПродвижениеПродвижениеНачалоНачалоРис. 2.15Рис. 2.16Чтобы не читать каждый символ отдельно, в каждую из половин буфераодной командой чтения считывается N символов. Если на входе осталосьменьше N символов, в буфер помещается специальный символ (eof).
Набуфер указывают два указателя: продвижение и начало. Междууказателями размещается текущая лексема. Вначале они оба указывают напервый символ выделяемой лексемы. Один из них, продвижение,продвигается вперед, пока не будет выделена лексема, и устанавливаетсяна ее конец. После обработки лексемы оба указателя устанавливаются насимвол, следующий за лексемой. Если указатель продвижение переходитсередину буфера, правая половина заполняется новыми N символами. Еслиуказатель продвижение переходит правую границу буфера, левая половиназаполняется N символами и указатель продвижение устанавливается наначало буфера.При каждом продвижении указателя необходимо проверять, недостигли ли мы границы одной из половин буфера. Для всех символов,кроме лежащих в конце половин буфера, требуются две проверки.
Числопроверок можно свести к одной, если в конце каждой половины поместитьдополнительный 'сторожевой' символ '#' (рис. 2.16).В этом случае почти для всех символов делается единственнаяпроверка на совпадение с '#' и только в случае совпадения нужнопроверить, достигли ли мы середины или правого конца.В третьей схеме используются три указателя (рис.
2.17).Непросмотренная часть буфера заключена между текущим и границей(граница - это указатель на последний элемент буфера). Анализ очереднойлексемы начинается после сканирования незначащих пробелов. Если послеэтого текущий указывает на '#' в конце буфера, делается перезагрузкабуфера (предполагается, что '#' не может входить в состав лексемы).Барьер выбирается таким образом, чтобы между барьером и границейвсегда помещалась любая лексема.
Если начало очередной лексемыоказывается правее барьера, то часть буфера от текущего до границы34переписывается левее буфера и буфер перезагужается. Тем самым началолексемы конкатенируется с ее концом. Так обрабатывается ситуация, когдаграница буфера прошла через лексему.NN\n#ГраницаГраницаБарьерБарьерТекущийа) Пока текущийТекущийбарьерб) после чтенияРис. 2.17В результате большинство входных символов обрабатываютсянепосредственно в буфере.
Копируются только идентификаторы истроковые константы в соответствующие таблицы.2.7. Конструктор лексических анализаторов LEXДля автоматизации разработки лексических анализаторов былоразработано довольно много средств. Как правило, входным языком дляних служат либо КС (автоматные) грамматики, либо язык регулярныхвыражений. Одной из наиболее распространенных систем является LEX,входным языком которого являются регулярные выражения. LEXпрограмма состоит из трех частей:%START список состоянийОбъявления%%Правила трансляции%%Вспомогательные процедурыСекция START содержит перечисление состояний в которых можетнаходиться анализатор.
Секция может остутствовать.Секция объявлений включает объявления переменных, констант и35определения регулярных выражений. При определении регулярныхвыражений могут использоваться следующие конструкции:[abc]- либо a, либо b, либо c;[a-z]диапазон символов;R*любое число (включая 0) повторений регулярного выражения R;R+не равное 0 число повторений регулярного выражения R;R1/R2R1, если за ним следует R2;R1|R2либо R1, либо R2;R?если есть R, выбрать его;R$выбрать R, если оно последнее в строке;^Rвыбрать R, если оно первое в строке;[^R]дополнение к R;R{n,m} повторить R от n до m раз;{имя}использовать именованное выше регулярное выражение;(R)группировка.Правила трансляции LEX программ имеют видp1 { действие_1 }p2 { действие_2 }...............pn { действие_n }где каждое pi - регулярное выражение, возможно помеченное именемсостояния, а каждое действие_i - фрагмент программы, описывающий,какое действие должен сделать лексический анализатор, когда образец p iсопоставляется лексеме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
