В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов, страница 7

АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ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, ...