В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 13
Текст из файла (страница 13)
Если применить алгоритм заполнения таблицык этому автомату, то в результате получим таблицу различимости (табл. 3.4).Т а б л и ц а 3.43 xx 0x x2 x0 x0 x1 0x x x x0 xx x x 0A B C D EПоскольку в результате проверки установлено, что состояния A и 1 эквивалентныи являются начальными у двух заданных автоматов, делаем вывод, что эти ДКАдействительно допускают один и тот же язык.Время заполнения таблицы, а значит, и время проверки эквивалентностидвух состояний, полиномиально относительно числа состояний. Если числосостояний равно n, то количество пар состояний равно Cn2 , или n(n − 1)/2.За один цикл рассматриваются все пары состояний, чтобы определить, является ли одна из пар состояний-преемников различимой. Значит, один циклзанимает время не больше O(n2 ).
Кроме того, если в некотором цикле60Глава 3. Лексический анализне обнаружены новые пары различимых состояний, то алгоритм заканчивается. Следовательно, количество циклов не превышает O(n2 ), а верхняя границавремени заполнения таблицы равна O(n4 ).Однако с помощью более аккуратно построенного алгоритма можно заполнить таблицу за время O(n2 ). С этой целью для каждой пары состояний (r, s)необходимо составить список пар состояний (p, q), «зависящих» от (r, s), т. е.если пара (r, s) различима, то (p, q) также различима. Вначале такие спискисоздаются путем рассмотрения каждой пары состояний (p, q), и для каждоговходного символа (а их число фиксировано) пара (p, q) вносится в списокдля пары состояний-преемников (D(p, a) и D(q , a)).Если обнаруживается, что пара (r, s) различима, то в списке этой парыкаждая пока неразличимая пара отмечается как различимая и помещаетсяв очередь пар, списки которых нужно проверить аналогичным образом.Общее время работы этого алгоритма пропорционально сумме длин списков, так как каждый раз проверяется наличие некоторой пары в списке (когдапроходим по списку пары, признанной различимой).
Так как размер входногоалфавита считается постоянным, то каждая пара состояний попадает в O(1)списков. Поскольку всего пар O(n2 ), суммарное время также O(n2 ).Еще одним важным следствием проверки эквивалентности состоянийявляется возможность минимизации ДКА. Это значит, что для каждогоДКА можно найти эквивалентный ему ДКА с наименьшим числом состояний. Более того, для данного языка существует единственный минимальный(с точностью до обозначения состояний). Основная идея минимизации ДКАсостоит в том, что понятие эквивалентности состояний позволяет объединятьсостояния в блоки следующим образом.1.2.3.4.Все эквивалентные состояния и только они образуют блок.Затем строим ДКА с состояниями — блоками.Переходы определяем естественным образом.Начальным состоянием является блок, содержащий начальное состояние исходного автомата.5.
Заключительным состоянием является блок, содержащий заключительные состояния исходного автомата.Доказательство основано на том, что эквивалентность состояний транзитивна, а кроме того, по определению симметрична и рефлексивна; значит,блоки состояний образуют разбиение.Теорема 3.8. ДКА, полученный в результате применения алгоритмаминимизации, имеет наименьшее возможное число состояний из всехДКА, эквивалентных данному.Д о к а з а т е л ь с т в о . Пусть N — ДКА, эквивалентный исходному M ,но имеющий меньшее число состояний.
Применим алгоритм определения3.5. Связь регулярных множеств, конечных автоматов и регулярных грамматик61эквивалентных неразличимых состояний к объединению M и N . Их начальные состояния эквивалентны (неразличимы). Для любых двух неразличимыхсостояний p и q все их (непосредственные) преемники по любому символунеразличимы, поскольку если бы преемники были различимы, то p и qможно было бы различить.
Таким образом, каждое состояние p автоматаM неотличимо хотя бы от одного состояния q автомата N . В самом деле,существует цепочка a1 , . . . , ak , переводящая M из начального состояния в p.Эта же цепочка переводит N в некоторое q . Это следует из того, что начальные состояния неразличимы, и из предыдущего замечания. Если |M | > |N |,то в M имеются два состояния, неразличимые с некоторым q из M . Но этопротиворечит построению M , в котором все состояния различимы.Следствие.
Между состояниями любых двух минимальных для данногоДКА автоматов можно установить взаимно однозначное соответствие,т. е. эти автоматы эквивалентны с точностью до именования состояний.Д о к а з а т е л ь с т в о . Достаточно применить предыдущее рассуждение в обе стороны.Таким образом, получаем следующий алгоритм минимизации автомата.1. Создать все пары (заключительное состояние, незаключительное состояние) и отметить их как непомеченные.2. Пока есть непомеченная пара:а) пометить ее;б) для каждой пары состояний, ведущей в данную пару по каждому(одному и тому же) символу: если эта пара не обозначена какразличимая, сделать ее различимой и непомеченной;в) построить множества эквивалентных состояний как транзитивноезамыкание, каждое такое множество объявить состоянием;г) множества, состоящие из заключительных состояний, сделать заключительными.Если применить этот алгоритм к автомату, изображенному на рис. 3.16,то получим автомат, изображенный на рис.
3.17, поскольку состояния B и Dэквивалентны. Если применить этот алгоритм одновременно к автоматам,изображенным на рис. 3.16 и 3.17, то получим, что эквивалентными являютсямножества состояний {1, A}, {3, C}, {2, B , D} и {0, E}.3.5.3. Реализация на Java. Программа на Java минимизации ДКАс проверкой эквивалентности двух ДКА приведена в пакете Finite (программное приложение). Функция equivalence() делает следующее.62Глава 3. Лексический анализ1. Сделать автомат всюду определенным.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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
