И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции. (1114901), страница 2
Текст из файла (страница 2)
. . ; F(An-2,an-1) = An-1; F(An-1,an) = S, где ai ⊂VT, Aj ⊂ K, j = 1, 2 , ... ,n-1; i = 1, 2, ... ,n; H - начальное состояние, S одно из заключительных состояний.Определение: множество цепочек, допускаемых конечным автоматом,составляет определяемый им язык.Для более удобной работы с диаграммами состояний введем несколькосоглашений:1. если из одного состояния в другое выходит несколько дуг,помеченных разными символами, то будем изображать одну дугу,помеченную всеми этими символами;2.
непомеченная дуга будет соответствовать переходу при любомсимволе, кроме тех, которыми помечены другие дуги, выходящиеиз этого состояния.3. введем состояние ошибки (ER); переход в это состояние будетозначать, что исходная цепочка языку не принадлежит.По диаграмме состояний легко написать анализатор для регулярнойграмматики.Например, для грамматики G = ({a,b, ⊥}, {S,A,B,C}, P, S), гдеS → C⊥P:С → Ab | BaA → a | CaB → b | Cbанализатор будет таким:#include <stdio.h>int scan_G(){enum state {H, A, B, C, S, ER}; /* множество состояний */state CS; /* CS - текущее состояние */FILE *fp; /* указатель на файл, в котором находится анализируемая цепочка */int c;CS=H;fp = fopen ("data","r");c = fgetc (fp);do {switch (CS) {case H: if (c == 'a') {c = fgetc(fp); CS = A;}else if (c == 'b') {c = fgetc(fp); CS = B;}else CS = ER;break;case A: if (c == 'b') {c = fgetc(fp); CS = C;}else CS = ER;break;case B: if (c == 'a') {c = fgetc(fp); CS = C;}else CS = ER;break;case C: if (c =='a') {c = fgetc(fp); CS = A;}else if (c == 'b') {c = fgetc(fp); CS = B;}else if (c == '⊥') CS = S;else CS = ER;break;}} while (CS != S && CS != ER);if (CS == ER) return -1; else return 0;}О недетерминированном разбореПри анализе по регулярной грамматике может оказаться, что нескольконетерминалов имеют одинаковые правые части, и поэтому неясно, ккакому из них делать свертку (см.
ситуацию 4 в описании алгоритма). Втерминах диаграммы состояний это означает, что из одного состояниявыходит несколько дуг, ведущих в разные состояния, но помеченныходним и тем же символом.Например, для грамматики G = ({a,b, ⊥}, {S,A,B}, P, S), гдеP:S → A⊥A → a | BbB → b | Bbразбор будет недетерминированным (т.к. у нетерминалов A и B естьодинаковые правые части - Bb).Такойграмматикебудетсоответствоватьнедетерминированныйконечный автомат.Определение: недетерминированный конечный автомат (НКА) - этопятерка (K, VT, F, H, S), гдеK - конечное множество состояний;VT - конечное множество допустимых входных символов;F - отображение множества K × VT в множество подмножеств K;H K - конечное множество начальных состояний;S K - конечное множество заключительных состояний.F(A,t) = {B1,B2,...,Bn} означает, что из состояния A по входному символуt можно осуществить переход в любое из состояний Bi, i = 1, 2, ...
,n.В этом случае можно предложить алгоритм, который будет перебиратьвсе возможные варианты сверток (переходов) один за другим; еслицепочка принадлежит языку, то будет найден путь, ведущий к успеху;если будут просмотрены все варианты, и каждый из них будетзавершаться неудачей, то цепочка языку не принадлежит. Однако такойалгоритм практически неприемлем, поскольку при переборе вариантовмы, скорее всего, снова окажемся перед проблемой выбора и,следовательно, будем иметь "дерево отложенных вариантов".Один из наиболее важных результатов теории конечныхавтоматов состоит в том, что класс языков, определяемыхнедетерминированными конечными автоматами, совпадает с классомязыков, определяемых детерминированными конечными автоматами.Это означает, что для любого НКА всегда можно построитьдетерминированный КА, определяющий тот же язык.Алгоритм построения детерминированного КА по НКАВход: M = (K, VT, F, H, S) - недетерминированный конечный автомат.Выход: M’ = (K’, VT, F’, H’, S’) - детерминированный конечный автомат,допускающий тот же язык, что и автомат М.Метод:1.
Множество состояний К’ состоит из всех подмножеств множества К.Каждое состояние из К’ будем обозначать [A1A2...An], где AiK.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...], .SiS для какого-либо 1 ≤ i ≤ p.Замечание: в множестве K’ могут оказаться состояния, которыенедостижимы из начального состояния, их можно исключить.Проиллюстрируем работу алгоритма на примере.Пусть задан НКА M = ({H, A, B, S}, {0, 1}, F, {H}, {S}), гдеF(H, 1) = B F(B, 0) = AF(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.1.
пусть есть функции: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) - функция, читающая из входного потока очереднойсимвол исходной программы и заносящая его в переменную с.Тогда диаграмма состояний для лексического анализатора:Замечание: символом Nx в диаграмме (и в тексте программы) обозначен номер лексемы x в ееклассе.Второй этап: по ДС пишем программу#include <stdio.h>#include <ctype.h>#define BUFSIZE 80typedef struct tabl * ptabl;extern ptabl TW, TID, TD, TNUM;char buf[BUFSIZE]; /* для накопления символов лексемы */int c; /* очередной символ */int d; /* для формирования числового значенияконстанты */void clear(void); /* очистка буфера buf */void add(void); /* добавление символа с в конец буфераbuf*/int look(ptabl); /* поиск в таблице лексемы из buf;результат: номер строки таблицы либо 0 */int putl(ptabl); /* запись в таблицу лексемы из buf,если ее там не было; результат:номер строки таблицы */int putnum();/* запись в TNUM константы из d, если еетам не было; результат: номер строкитаблицы TNUM */int j;/* номер строки в таблице, где находитсялексема, найденная функцией look */void makelex(int,int); /* формирование и вывод внутреннегопредставления лексемы */void scan (void){enum state {H,ID,NUM,COM,ASS,DLM,ER,FIN};state TC; /* текущее состояние */FILE* fp;TC = H;fp = fopen("prog","r"); /* в файле "prog" находитсятекст исходной программы */c = fgetc(fp);do {switch (TC) {case H:if (c == ' ') c = fgetc(fp);else if (isalpha(c)){clear(); add(); c = fgetc(fp); TC = ID;}else if (isdigit (c)){d = c - '0'; c = fgetc(fp); TC = NUM;}else if (c=='{') {c=fgetc(fp); TC = COM;}else if (c == ':'){c = fgetc(fp); TC = ASS;}else if (c == '⊥'){makelex(2, N⊥); TC = FIN;}else TC = DLM;break;case ID:if (isalpha(c) || isdigit(c)) {add(); c=fgetc(fp);}else {if (j = look (TW)) makelex (1,j);else {j = putl (TID); makelex (4,j);};TC = H;};break;case NUM:if (isdigit(c)) {d=d*10+(c - '0'); c=fgetc (fp);}else {makelex (3, putnum()); TC = H;}break;/* ...........*/} /* конец switch */} /* конец тела цикла */while (TC != FIN && TC != ER);if (TC == ER) printf("ERROR !!!");else printf("O.K.!!!");}Задачи.33.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
