Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Алгоритм построения детерминированного КА по НКАВход: M = (K, VT, F, H, S) - недетерминированный конечный автомат. Выход: M’ = (K’, VT, F’, H’, S’) - детерминированный конечный автомат, допускающий тот же язык, что и автомат М. Метод: 1. Множество состояний К’ состоит из всех подмножеств множества К. Каждое состояние из К’ будем обозначать [A1A2...An], где Ai Î K. 2. Отображение F’ определим как F’ ([A1A2...An], t) = [B1B2...Bm], где для каждого 1 <= j <= m F(Ai, t) = Bj для каких-либо 1 <= i <= n. 3. Пусть H = {H1, H2, ..., Hk}, тогда H’ = [H1, H2, ..., Hk]. 4. Пусть S = {S1, S2, ..., Sp}, тогда S’ - все состояния из K’, имеющие вид [...Si...], .Si Î S для какого-либо 1 <= i <= p.
Замечание:в множестве K’ могут оказаться состояния, которые недостижимы из начального состояния, их можно исключить.
Проиллюстрируем работу алгоритма на примере. Пусть задан НКА M = ({H, A, B, S}, {0, 1}, F, {H}, {S}), где F(H, 1) = B F(B, 0) = A F(A, 1) = B F(A, 1) = S , тогда соответствующий детерминированный конечный автомат будет таким: K’ = {[H], [A], [B], [S], [HA], [HB], [HS], [AB], [AS], [BS], [HAB], [HAS], [ABS], [HBS], [HABS]}
F’([A], 1) = [BS] F’([H], 1) = [B] F’([B], 0) = [A] F’([HA], 1) = [BS] F’([HB], 1) = [B] F’([HB], 0) = [A] F’([HS], 1) = [B] F’([AB], 1) = [BS] F’([AB], 0) = [A] F’([AS], 1) = [BS] F’([BS], 0) = [A] F’([HAB], 0) = [A] F’([HAB], 1) = [BS] F’([HAS], 1) = [BS] F’([ABS], 1) = [BS] F’([ABS], 0) = [A] F’([HBS], 1) = [B] F’([HBS], 0) = [A] F’([HABS], 1) = [BS] F’([HABS], 0) = [A]
S’ = {[S], [HS], [AS], [BS], [HAS], [ABS], [HBS], [HABS]} Достижимыми состояниями в получившемся КА являются [H], [B], [A] и [BS], поэтому остальные состояния удаляются. Таким образом, M’ = ({[H], [B], [A], [BS]}, {0, 1}, F’, H, {[BS]}), где F’([A], 1) = [BS] F’([H], 1) = [B] F’([B], 0) = [A] F’([BS], 0) = [A]
Задачи лексического анализа
Лексический анализ (ЛА) - это первый этап процесса компиляции. На этом этапе символы, составляющие исходную программу, группируются в отдельные лексические элементы, называемые лексемами.
Лексический анализ важен для процесса компиляции по нескольким причинам:
a) замена в программе идентификаторов, констант, ограничителей и служебных слов лексемами делает представление программы более удобным для дальнейшей обработки; b) лексический анализ уменьшает длину программы, устраняя из ее исходного представления несущественные пробелы и комментарии; c) если будет изменена кодировка в исходном представлении программы, то это отразится только на лексическом анализаторе.
Выбор конструкций, которые будут выделяться как отдельные лексемы, зависит от языка и от точки зрения разработчиков компилятора. Обычно принято выделять следующие типы лексем: идентификаторы, служебные слова, константы и ограничители. Каждой лексеме сопоставляется пара (тип_лексемы, указатель_на_информацию_о_ней). Соглашение: эту пару тоже будем называть лексемой, если это не будет вызывать недоразумений. Таким образом, лексический анализатор - это транслятор, входом которого служит цепочка символов, представляющих исходную программу, а выходом - последовательность лексем.
Очевидно, что лексемы перечисленных выше типов можно описать с помощью регулярных грамматик. Например, идентификатор (I): I ® a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9 целое без знака (N): N® 0 | 1 |...| 9 | N0 | N1 |...| N9 и т.д. Для грамматик этого класса, как мы уже видели, существует простой и эффективный алгоритм анализа того, принадлежит ли заданная цепочка языку, порождаемому этой грамматикой. Однако перед лексическим анализатором стоит более сложная задача: он должен сам выделить в исходном тексте цепочку символов, представляющую лексему, а также преобразовать ее в пару (тип_лексемы, указатель_на_информацию_о_ней). Для того, чтобы решить эту задачу, опираясь на способ анализа с помощью диаграммы состояний, введем на дугах дополнительный вид пометок - пометки-действия. Теперь каждая дуга в ДС может выглядеть так:
Смысл ti прежний - если в состоянии A очередной анализируемый символ совпадает с ti для какого-либо i = 1, 2 ,... n, то осуществляется переход в состояние B; при этом необходимо выполнить действия D1, D2, ... ,Dm.
Лексический анализатор для М-языка
Вход лексического анализатора - символы исходной программы на М-языке; результат работы - исходная программа в виде последовательности лексем (их внутреннего представления). Лексический анализатор для модельного языка будем писать в два этапа: сначала построим диаграмму состояний с действиями для распознавания и формирования внутреннего представления лексем, а затем по ней напишем программу анализатора. Первый этап: разработка ДС.
Представление лексем: все лексемы М-языка разделим на несколько классов; классы перенумеруем: à служебные слова - 1, à ограничители - 2, à константы (целые числа) - 3, à идентификаторы - 4. Внутреннее представление лексем - это пара (номер_класса, номер_в_классе). Номер_в_классе - это номер строки в таблице лексем соответствующего класса.
Соглашениеоб используемых переменных, типах и функциях: 1) пусть есть переменные: buf - буфер для накопления символов лексемы; c - очередной входной символ; d - переменная для формирования числового значения константы; TW - таблица служебных слов М-языка; TD - таблица ограничителей М-языка; TID - таблица идентификаторов анализируемой программы; TNUM - таблица чисел-констант, используемых в программе. Таблицы TW и TD заполнены заранее, т.к. их содержимое не зависит от исходной программы; TID и TNUM будут формироваться в процессе анализа; для простоты будем считать, что все таблицы одного типа; пусть tabl - имя типа этих таблиц, ptabl - указатель на tabl.
2) пусть есть функции: void clear (void); - очистка буфера buf; void add (void); - добавление символа с в конец буфера buf; int look (ptabl Т); - поиск в таблице Т лексемы из буфера buf; результат: номер строки таблицы с информацией о лексеме либо 0, если такой лексемы в таблице Т нет; int putl (ptabl Т); - запись в таблицу Т лексемы из буфера buf, если ее там не было; результат: номер строки таблицы с информацией о лексеме; int putnum (); - запись в TNUM константы из d, если ее там не было; результат: номер строки таблицы TNUM с информацией о константе-лексеме; void makelex (int k, int i); - формирование и вывод внутреннего представления лексемы; k - номер класса, i - номер в классе; void gc (void) - функция, читающая из входного потока очередной символ исходной программы и заносящая его в переменную с; void id_or_word (void); - функция, определяющая является слово в буфере buf идентификатором или служебным словом и формирующая лексему соответствующего класса; void is_dlm (void); - если символ в буфере buf является разделителем, то формирует соответствующую лексему, иначе производится переход в состояние ER.
Диаграмма состояний для лексического анализатора приведена на следующей странице.
Замечания: 1) Символом Nx в диаграмме (и в тексте программы) обозначен номер лексемы x в ее классе. 2) По нашей диаграмме знак "!=" представлен двумя лексемами, хотя нужно сделать одну лексему, по аналогии с ":=". Соответствующие изменения надо сделать и в синтаксическом анализаторе. |
|
Последнее изменение этой страницы: 2016-08-11 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |