В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 13
Текст из файла (страница 13)
Сделать автомат всюду определенным.2. Для каждого состояния определить, из какого состояния по каждомусимволу есть переход.3. Для каждой пары состояний (p, q) и каждого входного символа aсформировать множество таких пар состояний (r, s), что D(r, a) = p,D(s, a) = q .4. Сформировать список пар различимых состояний:а) если есть пара (p, q) ∈ (Q\F × F ), то занести ее в список непомеченных пар;б) пока список непомеченных пар непуст, выбрать пару (p, q), пометитьее как различимую и удалить из списка непомеченных пар; еслипара (r, s) такова, что D(r, a) = p, D(s, a) = q , ее нет в списке различимых пар и нет в списке непомеченных пар, то внести ее в списокнепомеченных пар.5.
Построить множество L = {(Q × Q)\список различимых пар} :6. Построить разбиение множества L на классы эквивалентности:а) выбрать пару (p, q) из этого множества;б) построить множество Si = {p, q};в) пока в Si есть такой элемент s, что во множестве L есть пара (r, s)или (s, r), добавить r к этому множеству и исключить пару (r, s)(или (s, r)) из L.7. Каждое множество Si становится новым состоянием; все состоянияиз Q\{Si } остаются одиночными состояниями.8. Множества Si , состоящие из заключительных состояний, становятсязаключительными состояниями; все заключительные состояния, не вошедшие в {Si }, остаются заключительными состояниями.3.6. Программирование лексического анализаКак уже отмечалось ранее, лексический анализатор (ЛА) может бытьоформлен как подпрограмма.
При обращении к ЛА вырабатываются какминимум два результата: тип выбранной лексемы и ее значение (если оноесть).Если ЛА сам формирует таблицы объектов, то он выдает тип лексемыи указатель на соответствующий вход в таблице объектов. Если же ЛАне работает с таблицами объектов, то он выдает тип лексемы, а ее значениепередается, например, через некоторую глобальную переменную. Помимозначения лексемы, эта глобальная переменная может содержать некоторую3.6. Программирование лексического анализа63дополнительную информацию: номер текущей строки, номер символа в строкеи т.
п. Эта информация может использоваться в различных целях, например,для диагностики.В основе ЛА лежит диаграмма переходов соответствующего конечногоавтомата. Отдельная проблема здесь — анализ ключевых слов. Как правило,ключевые слова — это выделенные идентификаторы. Поэтому возможныдва основных способа распознавания ключевых слов: либо очередная лексема сначала диагностируется на совпадение с каким-либо ключевым словоми в случае неуспеха делается попытка выделить лексему из какого-либокласса, либо, наоборот, после выборки лексемы идентификатора происходит обращение к таблице ключевых слов на предмет сравнения.
Подробнеео механизмах поиска в таблицах будет сказано ниже (гл. 7), здесь отметимтолько, что поиск ключевых слов может вестись либо в основной таблицеимен (и в этом случае в нее до начала работы ЛА загружаются ключевыеслова), либо в отдельной таблице. При первом способе все ключевые слованепосредственно встраиваются в конечный автомат ЛА, при втором — конечный автомат содержит только разбор идентификаторов.В некоторых языках (например, ПЛ/1 или Фортран) ключевые словамогут использоваться в качестве обычных идентификаторов. В этом случаеработа ЛА не может идти независимо от работы синтаксического анализатора.В Фортране возможны, например, следующие строки:DO 10 I=1,25DO 10 I=1.25В первом случае строка — это заголовок цикла DO, во втором — операторприсваивания.
Поэтому, прежде чем можно будет выделить лексему, ЛАдолжен заглянуть довольно далеко.Еще сложнее дело в ПЛ/1. Здесь возможны такие операторы:IF ELSE THEN ELSE = THEN; ELSE THEN = ELSE;илиDECLARE (A1, A2, ... , AN)и только в зависимости от того, что́ стоит после «)», можно определить,является ли DECLARE ключевым словом или идентификатором. Длина такойстроки может быть сколь угодно большой, и уже невозможно отделить фазусинтаксического анализа от фазы лексического анализа.Рассмотрим несколько подробнее вопросы программирования ЛА. Основная операция ЛА, на которую уходит бо́льшая часть времени его работы —это взятие очередного символа и проверка на принадлежность его некоторомудиапазону.
Например, основной цикл при выборке числа в простейшем случаеможет выглядеть следующим образом:while (Insym<=’9’ && Insym>=’0’){ ... }64Глава 3. Лексический анализПрограмму можно значительно улучшить следующим образом [5]. ПустьLETTER, DIGIT, BLANK — элементы перечислимого типа.
Введем массивmap, входами которого будут символы, значениями — типы символов. Инициализируем массив map следующим образом:map[’a’]=LETTER;........map[’z’]=LETTER;map[’0’]=DIGIT;........map[’9’]=DIGIT;map[’ ’]=BLANK;........Тогда приведенный цикл примет следующую форму:while (map[Insym]==DIGIT){ ... }Выделение ключевых слов может осуществляться после выделения идентификаторов. ЛА работает быстрее, если ключевые слова выделяются непосредственно.Для этого строится конечный автомат, описывающий множество ключевых слов.
На рис. 3.18 приведен фрагмент такого автомата.Рассмотрим пример программирования этого конечного автомата на языкеСи, приведенный в [22]:Рис. 3.18........case ’i’:if (cp[0]==’f’ &&!(map[cp[2]] & (DIGIT | LETTER))){cp++; return IF;}if (cp[0]==’n’ && cp[1]==’t’&&!(map[cp] & (DIGIT | LETTER)))3.6. Программирование лексического анализа65{cp+=2; return INT;}{ обработка идентификатора }........Здесь cp — указатель текущего символа. В массиве map классы символовкодируются битами.Поскольку ЛА анализирует каждый символ входного потока, его скоростьсущественно зависит от скорости выборки очередного символа входного потока.
В свою очередь, эта скорость во многом определяется схемой буферизации. Рассмотрим возможные эффективные схемы буферизации.Рис. 3.19Будем использовать буфер, состоящий из двух одинаковых частей длинойN (рис. 3.19, а), где N — размер блока обмена (например, 1024, 2048 и т. п.).Чтобы не читать каждый символ отдельно, в каждую из половин буферапоочередно одной командой чтения считывается N символов. Если на входеосталось меньше N символов, то в буфер помещается специальный символeof. Буфер снабжен двумя указателями: продвижение и начало.
Между указателями размещается текущая лексема. Вначале они оба указывают на первый символ выделяемой лексемы. Один из них, продвижение, продвигаетсявперед, пока не будет выделена лексема, и устанавливается на ее конец.После обработки лексемы оба указателя устанавливаются на символ, следующий за лексемой.
Если указатель продвижение переходит середину буфера,то правая половина заполняется новыми N символами. Если указатель продвижение переходит правую границу буфера, то левая половина заполняетсяN символами и указатель продвижение устанавливается на начало буфера.При каждом продвижении указателя необходимо проверять, не достиглили мы границы одной из половин буфера.
Для всех символов, кроме лежащихв концах половин буфера, требуются две проверки. Число проверок можносвести к одной, если в конце каждой половины поместить дополнительный«сторожевой» символ, в качестве которого логично взять eof (рис. 3.19, б).В этом случае почти для всех символов делается единственная проверкана совпадение с eof, и только при совпадении нужно дополнительно проверить, достигли ли мы середины или правого конца.3 В.А. Серебряков66Глава 3. Лексический анализ3.7. Конструктор лексических анализаторов LEXДля автоматизации разработки ЛА было создано довольно много средств.Как правило, входными языками для них служат или праволинейные грамматики, или языки регулярных выражений.
Одной из наиболее распространенных систем является LEX, работающий с расширенными регулярнымивыражениями. LEX-программа состоит из трех частей:Объявления%%Правила трансляции%%Вспомогательные подпрограммыСекция объявлений включает объявления переменных, констант и определения регулярных выражений. При определении регулярных выражениймогут использоваться следующие конструкции:[abc][a-z]R*R+R1/R2R1|R2R?R$^R[^R]R{n,m}{имя}(R)—————————————либо a, либо b, либо c;диапазон символов;0 или более повторений регулярного выражения R;1 или более повторений регулярного выражения R;R1 , если за ним следует R2 ;либо R1 , либо R2 ;если есть R, выбрать его;выбрать R, если оно последнее в строке;выбрать R, если оно первое в строке;дополнение к R;повторение R от n до m раз;именованное регулярное выражение;группировка.Правила трансляции LEX-программ имеют следующий вид:p_1 { действие_1 }p_2 { действие_2 }................p_n { действие_n }где p_i — регулярное выражение, а действие_i — фрагмент программы,описывающий, какое действие должен сделать ЛА, когда образец p_i сопоставляется лексеме.
В LEX действия записываются на Си.Третья секция содержит вспомогательные процедуры, необходимые длядействий. Эти процедуры могут транслироваться раздельно и загружатьсяс ЛА.3.7. Конструктор лексических анализаторов LEX67ЛА, сгенерированный LEX, взаимодействует с синтаксическим анализатором следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
