В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 6
Текст из файла (страница 6)
Результат применения алгоритма 3.3 для регулярного выражения (a|b)∗ abb приведен на рис. 3.14.ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ36EDD^`ED^`DE^`E^`Рис. 3.14:3.3.4Построение детерминированного конечногоавтомата с минимальным числом состоянийРассмотрим теперь алгоритм построения ДКА с минимальным числомсостояний, эквивалентного данному ДКА [10].Пусть M = (Q, T, D, q0 , F ) – ДКА. Будем называть M всюду определенным, если D(q, a) 6= ∅ для всех q ∈ Q и a ∈ T .Лемма.
Пусть M = (Q, T, D, q0 , F ) – ДКА, не являющийся всюду определенным. Существует всюду определенный ДКА M 0 , такой что L(M ) =L(M 0 ).Доказательство. Рассмотрим автомат M 0 = (Q∪{q 0 }, T, D0 , q0 , F ), где q 0 ∈/Q – некоторое новое состояние, а функция D0 определяется следующимобразом:(1) Для всех q ∈ Q и a ∈ T , таких что D(q, a) 6= ∅, определить D0 (q, a) =D(q, a).(2) Для всех q ∈ Q и a ∈ T , таких что D(q, a) = ∅, определить D0 (q, a) =q0 .(3) Для всех a ∈ T определить D0 (q 0 , a) = q 0 .Легко показать, что автомат M 0 допускает тот же язык, что и M .Приведенный ниже алгоритм получает на входе всюду определенный автомат.
Если автомат не является всюду определенным, его можносделать таковым на основании только что приведенной леммы.Алгоритм 3.4. Построение ДКА с минимальным числом состояний.Вход. Всюду определенный ДКА M = (Q, T, D, q0 , F ).Выход. ДКА M 0 = (Q0 , T, D0 , q00 , F 0 ), такой что L(M ) = L(M 0 ) и M 0содержит наименьшее возможное число состояний.Метод. Выполнить шаги 1-5:3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ37(1) Построить начальное разбиение Π множества состояний из двухгрупп: заключительные состояния Q и остальные Q−F , т.е. Π = {F, Q−F }.(2) Применить к Π следующую процедуру и получить новое разбиениеΠnew :for (каждой группы G в Π){разбить G на подгруппы так, чтобысостояния s и t из G оказалисьв одной подгруппе тогда и только тогда,когда для каждого входного символа aсостояния s и t имеют переходы по aв состояния из одной и той же группы в Π;заменить G в Πnew на множество всехполученных подгрупп;}(3) Если Πnew = Π, полагаем Πres = Π и переходим к шагу 4, иначеповторяем шаг 2 с Π := Πnew .(4) Пусть Πres = {G1 , ...
, Gn }. Определим:Q0 = {G1 , ... , Gn };q00 = G, где группа G ∈ Q0 такова, что q0 ∈ G;F 0 = {G|G ∈ Q0 и G ∩ F 6= ∅};D0 (p0 , a) = q 0 , если D(p, a) = q, где p ∈ p0 и q ∈ q 0 .Таким образом, каждая группа в Πres становится состоянием нового автомата M 0 . Если группа содержит начальное состояние автомата M , эта группа становится начальным состоянием автомата M 0 . Если группа содержит заключительное состояние M , онастановится заключительным состоянием M 0 . Отметим, что каждаягруппа Πres либо состоит только из состояний из F , либо не имеетсостояний из F . Переходы определяются очевидным образом.(5) Если M 0 имеет “мертвое” состояние, т.е. состояние, которое не является допускающим и из которого нет путей в допускающие, удалить его и связанные с ним переходы из M 0 . Удалить из M 0 такжевсе состояния, недостижимые из начального.Пример 3.10.
Результат применения алгоритма 3.4 приведен на рис. 3.15.ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ38EDEEEDDDED^`ED^`ED^`DEEРис. 3.15:3.4Регулярные множества и их представленияВ разделе 3.3.3 приведен алгоритм построения детерминированного конечного автомата по регулярному выражению. Рассмотрим теперь какпо описанию конечного автомата построить регулярное множество, совпадающее с языком, допускаемым конечным автоматом.Теорема 3.1. Язык, допускаемый детерминированным конечным автоматом, является регулярным множеством.Доказательство.
Пусть L – язык допускаемый детерминированнымконечным автоматом M = ({q1 , ... , qn }, T, D, q1 , F ). Введем De – расширенную функцию переходов автомата M : De (q, w) = p, где w ∈ T ∗ , тогдаи только тогда, когда (q, w) `∗ (p, e).kОбозначим Rijмножество всех слов x таких, что De (qi , x) = qj и еслиeD (qi , y) = qs для любой цепочки y – префикса x, отличного от x и e, тоs 6 k.kесть множество всех слов, которые переводятИными словами, Rijконечный автомат из состояния qi в состояние qj , не проходя ни черезкакое состояние qs для s > k. Однако, i и j могут быть больше k.kRijможет быть определено рекурсивно следующим образом:0Rij= {a|a ∈ T, D(qi , a) = qj },k−1 S k−1k−1 ∗ k−1kRik (Rkk= Rij) Rkj , где 1 6 k 6 n.Rijkозначает, что для входной цепочкиТаким образом, определение Rijw, переводящей M из qi в qj без перехода через состояния с номерами,большими k, справедливо ровно одно из следующих двух утверждений:k−1, т.е.
при анализе цепочки w автомат1. Цепочка w принадлежит Rijникогда не достигает состояний с номерами, большими или равными k.3.4. РЕГУЛЯРНЫЕ МНОЖЕСТВА И ИХ ПРЕДСТАВЛЕНИЯ392. Цепочка w может быть представлена в виде w = w1 w2 w3 ,k−1где w1 ∈ Rik(подцепочка w1 переводит M сначала в qk ),k−1 ∗w2 ∈ (Rkk ) (подцепочка w2 переводит M из qk обратно в qk , непроходя через состояния с номерами, большими или равными k),k−1(подцепочка w3 переводит M из состояния qk в qj ) –и w3 ∈ Rkjрис. 3.16.TNTLT V V N TMРис. 3.16:Тогда L =SnR1j. Индукцией по k можно показать, что это множе-qj ∈Fство является регулярным.Таким образом, для всякого регулярного множества имеется конечный автомат, допускающий в точности это регулярное множество, и наоборот – язык, допускаемый конечным автоматом есть регулярное множество.Рассмотрим теперь соотношение между языками, порождаемыми праволинейными грамматиками и допускаемыми конечными автоматами.Праволинейная грамматика G = (N, T, P, S) называется регулярной,если(1) каждое ее правило, кроме S → e, имеет вид либо A → aB, либоA → a, где A, B ∈ N , a ∈ T ;(2) в том случае, когда S → e ∈ P , начальный символ S не встречаетсяв правых частях правил.Лемма.
Пусть G – праволинейная грамматика. Существует регулярная грамматика G0 такая, что L(G) = L(G0 ).Доказательство. Предоставляется читателю в качестве упражнения.Теорема 3.2. Пусть G = (N, T, P, S) – праволинейная грамматика. Тогда существует конечный автомат M = (Q, T, D, q0 , F ) для которого L(M ) = L(G).40ГЛАВА 3.
ЛЕКСИЧЕСКИЙ АНАЛИЗДоказательство. На основании приведенной выше леммы, без ограничения общности можно считать, что G – регулярная грамматика.Построим недетерминированный конечный автомат M следующимобразом:1. состояниями M будут нетерминалы G плюс новое состояние R, непринадлежащее N . Так что Q = N ∪ {R};2. в качестве начального состояния M примем S, т.е. q0 = S;3. если P содержит правило S → e, то F = {S, R}, иначе F = {R}.Напомним, что S не встречается в правых частях правил, если S →e ∈ P;4. состояние R ∈ D(A, a), если A → a ∈ P .
Кроме того, D(A, a) содержит все B такие, что A → aB ∈ P . D(R, a) = ∅ для каждого a ∈ T .M , читая вход w, моделирует вывод w в грамматике G. Покажем, чтоL(M ) = L(G). Пусть w = a1 a2 ... an ∈ L(G), n > 1. ТогдаS ⇒ a1 A1 ⇒ ... ⇒ a1 a2 ... an−1 An−1 ⇒ a1 a2 ... an−1 anдля некоторой последовательности нетерминалов A1 , A2 , ... , An−1 . По определению, D(S, a1 ) содержит A1 , D(A1 , a2 ) содержит A2 , и т.д., D(An−1 , an )содержит R. Так что w ∈ L(M ), поскольку De (S, w) содержит R, а R ∈ F .Если e ∈ L(G), то S ∈ F , так что e ∈ L(M ).Аналогично, если w = a1 a2 ...
an ∈ L(M ), n > 1, то существует последовательность состояний S, A1 , A2 , ... , An−1 , R такая, что D(S, a1 ) содержит A1 , D(A1 , a2 ) содержит A2 , и т.д. ПоэтомуS ⇒ a1 A1 ⇒ a1 a2 A2 ⇒ ... ⇒ a1 a2 ... an−1 An−1 ⇒ a1 a2 ... an−1 an– вывод в G и x ∈ L(G). Если e ∈ L(M ), то S ∈ F , так что S → e ∈ P иe ∈ L(G).Теорема 3.3. Для каждого конечного автомата M = (Q, T, D, q0 , F ) существует праволинейная грамматика G = (N, T, P, S) такая, чтоL(G) = L(M ).Доказательство. Без потери общности можно считать, что автомат M– детерминированный. Определим грамматику G следующим образом:1.
нетерминалами грамматики G будут состояния автомата M . Такчто N = Q;2. в качестве начального символа грамматики G примем q0 ,т.е. S = q0 ;3. A → aB ∈ P , если D(A, a) = B;3.5. ПРОГРАММИРОВАНИЕ ЛЕКСИЧЕСКОГОАНАЛИЗА414. A → a ∈ P , если D(A, a) = B и B ∈ F ;5. S → e ∈ P , если q0 ∈ F .Доказательство того, что S ⇒∗ w тогда и только тогда, когдаD (q0 , w) ∈ F , аналогично доказательству теоремы 3.2.e3.5Программирование лексическогоанализаКак уже отмечалось ранее, лексический анализатор (ЛА) может бытьоформлен как подпрограмма.
При обращении к ЛА, вырабатываютсякак минимум два результата: тип выбранной лексемы и ее значение (если оно есть).Если ЛА сам формирует таблицы объектов, он выдает тип лексемы иуказатель на соответствующий вход в таблице объектов. Если же ЛА неработает с таблицами объектов, он выдает тип лексемы, а ее значениепередается, например, через некоторую глобальную переменную. Помимо значения лексемы, эта глобальная переменная может содержатьнекоторую дополнительную информацию: номер текущей строки, номер символа в строке и т.д. Эта информация может использоваться вразличных целях, например, для диагностики.В основе ЛА лежит диаграмма переходов соответствующего конечного автомата.
Отдельная проблема здесь – анализ ключевых слов. Какправило, ключевые слова – это выделенные идентификаторы. Поэтому возможны два основных способа распознавания ключевых слов: либо очередная лексема сначала диагностируется на совпадение с какимлибо ключевым словом и в случае неуспеха делается попытка выделитьлексему из какого-либо класса, либо, наоборот, после выборки лексемы идентификатора происходит обращение к таблице ключевых словна предмет сравнения.
Подробнее о механизмах поиска в таблицах будет сказано ниже (гл. 7), здесь отметим только, что поиск ключевыхслов может вестись либо в основной таблице имен и в этом случае в неедо начала работы ЛА загружаются ключевые слова, либо в отдельнойтаблице. При первом способе все ключевые слова непосредственно встраиваются в конечный автомат лексического анализатора, во втором конечный автомат содержит только разбор идентификаторов.В некоторых языках (например, ПЛ/1 или Фортран) ключевые слова могут использоваться в качестве обычных идентификаторов. В этомслучае работа ЛА не может идти независимо от работы синтаксическогоанализатора. В Фортране возможны, например, следующие строки:DO 10 I=1,25DO 10 I=1.25ГЛАВА 3.
ЛЕКСИЧЕСКИЙ АНАЛИЗ42В первом случае строка – это заголовок цикла DO, во втором – оператор присваивания. Поэтому, прежде чем можно будет выделить лексему, лексический анализатор должен заглянуть довольно далеко.Еще сложнее дело в ПЛ/1. Здесь возможны такие операторы:IF ELSE THEN ELSE = THEN; ELSE THEN = ELSE;илиDECLARE (A1, A2, ... , AN)и только в зависимости от того, что стоит после “)”, можно определить,является ли DECLARE ключевым словом или идентификатором.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
