Разбор по леволинейной грамматике. Соглашения: - для описания лексем будем использовать леволинейную автоматную грамматику без пустых правых частей: G = (T, N, P, S) леволинейная, если каждое правило из Р имеет вид A Bt либо A t, где A N, B N, t T. - анализируемая цепочка заканчивается специальным символом - признаком конца цепочки. Алгоритм разбора по леволинейной грамматике: (1) первый символ исходной цепочки a 1 a 2...a n заменяем нетерминалом A, для которого в грамматике есть правило вывода A a 1 (другими словами, производим "свертку" терминала a 1 к нетерминалу A) (2) многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал a i исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B Aa i (i = 2, 3,.., n);

Диаграммы состояний (ДС) Диаграмма состояний (ДС) - неупорядоченный ориентированный помеченный граф, который строится следующим образом: (1) строим вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала - одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных (например, H). Эти вершины называются состояниями. H - начальное состояние. (2) соединяем эти состояния дугами по следующим правилам: a) для каждого правила вида W t соединяем дугой состояния H и W (от H к W) и помечаем дугу символом t; б) для каждого правила вида W Vt соединяем дугой состояния V и W (от V к W) и помечаем дугу символом t; Диаграмма состояний для грамматики G_ex = ( { a, b, }, { S, A, B, C }, P, S ), где P: S C будет выглядеть так: C Ab | Ba A a | Ca B b | Cb L(G) = { ([ab | ba]) n | n >= 1 } Алгоритм разбора по диаграмме состояний: (1) объявляем текущим состояние H; (2) многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом. Состояние, в которое мы при этом попадаем, становится текущим.

Диаграммы состояний для праволинейных грамматик ДС по праволинейной регулярной грамматике строится следующим образом: (1) строим вершины графа, помеченные нетерминалами грамматики, и еще одну вершину, помеченную символом, отличным от нетерминальных (например, F). Эти вершины называются состояниями. S - начальное состояние. F – заключительное состояние. (2) соединяем эти состояния дугами по следующим правилам: a) для каждого правила вида W t соединяем дугой состояния F и W (от W к F) и помечаем дугу символом t; б) для каждого правила вида W tV соединяем дугой состояния V и W (от W к V) и помечаем дугу символом t; Диаграмма состояний для грамматики G_ex2 = ( { 0, 1, }, { S, B, C }, P, S ), где P: S 0Bбудет выглядеть так: B 1B | 1C | C L(G) = { 0 1 n | n >= 0 } Имея ДС, построенную по любой регулярной грамматике, можно по ней восстановить как леволинейную, так и эквивалентную ей праволинейную регулярную грамматику S B C F

Алгоритм построения праволинейной грамматики G right по ДС, построенной по леволинейной грамматике G left. Нетерминалами G right будут все состояния из ДС, кроме S. Если в ДС есть исходящие дуги из S, то вводим в ДС новое заключительное состояние S, в которое из S ведет дуга, помеченная признаком конца. Каждой дуге из состояния V в заключительное состояние S (или S), помеченной символом t ( ) ставится в соответствие правило V t ( V ). Каждой дуге из состояния V в состояние W, помеченной символом t, ставится в соответствие правило V tW. Начальное состояние H объявляется начальным символом грамматики.

Алгоритм построения леволинейной грамматики G rleft по ДС, построенной по праволинейной грамматике G right. Нетерминалами G left будут все состояния из ДС для G right, кроме S. Каждой дуге из состояния S в состояние W, помеченной символом t, ставится в соответствие правило W t. Если в ДС есть входящие дуги в S, то в G left добавляется также и правило W St. Каждой дуге из состояния V в состояние W, помеченной символом t, ставится в соответствие правило W Vt. Заключительное состояние F объявляется начальным символом грамматики.

Соглашения для работы с диаграммами состояний a)Если из одного состояния в другое выходит несколько дуг, помеченных разными символами, то изображается одна дуга, помеченная всеми этими символами. b)Непомеченная никакими символами дуга соответствует переходу при любом символе, кроме тех, которыми помечены другие дуги, выходящие из этого состояния. c)Вводится дополнительное состояние ошибки (ER); переход в это состояние означает, что исходная цепочка языку не принадлежит.

Конечный автомат (КА) Конечный автомат (КА) - это пятерка (K, T, δ, H, S), где K - конечное множество состояний; T - конечное множество допустимых входных символов; δ - отображение (функция переходов) множества K T K, определяющее поведение автомата; H K - начальное состояние; S K - заключительное состояние (либо конечное множество заключительных состояний, но для грамматик – одно!). δ (A, t) = B означает, что из состояния A по входному символу t происходит переход в состояние B. Конечный автомат допускает цепочку a 1 a 2...a n, если δ(H, a 1 ) = A 1 ; δ(A 1, a 2 ) = A 2 ;... ; δ(A n-2, a n-1 ) = A n-1 ; δ(A n-1,a n ) = S, где a i T, A j K, j = 1, 2,..., n-1; i = 1, 2,..., n; H - начальное состояние, S - одно из заключительных состояний. Множество цепочек, допускаемых конечным автоматом, составляет определяемый им язык.

Анализатор для регулярной грамматики G_ex. char c;bool scan_G ( ) { enum state { H, A, B, C, S, ER }; void gc ( ) { cin >> c; }state CS; // CS - текущее состояние CS = H; do { gc (); switch (CS) { case H: if (c == 'a') { CS = A;} else if (c == 'b') { CS = B;} else CS = ER; break; case A: if (c == 'b') { CS = C;} else CS = ER; break; case B: if (c == 'a') { CS = C;} else CS = ER; break; case C: if (c == 'a') { CS = A;} else if (c == 'b') { CS = B;} else if (c == ' ') CS = S; else CS = ER; break; } } while (CS != S && CS != ER); if (CS == ER) return false; else return true; }

О недетерминированном разборе При анализе по ДС для регулярной грамматики может оказаться, что из одного состояния выходит несколько дуг, ведущих в разные состояния, но помеченных одним и тем же символом. Для леволинейных грамматик эта ситуация возникает, когда в правилах вывода есть совпадающие правые части. Для праволинейных грамматик аналогичная ситуация возникает, когда альтернативы вывода из одного нетерминала грамматики начинаются одинаковыми терминальными символами. Недетерминированный конечный автомат (НКА) – это пятерка ( K, T, δ, H, S ), где K - конечное множество состояний; T - конечное множество допустимых входных символов; δ - отображение множества K T в множество подмножеств K; H K - конечное множество начальных состояний (у нас одно!); S K - конечное множество заключительных состояний (у нас одно!). δ (A,t) = {B1,B2,...,Bn} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний Bi, i = 1, 2,...,n.

Алгоритм построения детерминированного КА по НКА Вход: M = (K, T, δ, H, S) - НКА. Выход: M1 = (K1, T, δ1, H1, S1) - детерминированный КА, допускающий тот же язык, что и автомат М. Метод: 1. Строим отображение δ1 (K1 T K1) по δ, начиная с состояния H. 2. δ1 для Н К1 строим т.о.: - если в НКА переход из Н по какому-то символу был детерминированным, переносим соответствующие отображение в результирующий КА. Состояния, появляющиеся в правой части отображений δ1 принадлежат К1; - если же в НКА переход из Н по какому-то символу t был недетерминированным, то в КА включаем отображения δ1 по правилу: δ1 (H, t) = A1A2...An,где Ai К, и в НКА есть F (H, t) = Ai для всех 1

Пример работы алгоритма преобразования НКА в КА Задан НКА M = ( { H, A, B, S }, { 0, 1 }, δ, { H }, { S } ), где δ (H, 1) = BL = { 1(01) n | n >=1 } δ (A, 1) = B δ (A, 1) = S δ (B, 0) = A, Функции переходов КА, построенные по НКА в соответствии с предложенным алгоритмом. δ1(Н, 1) = B δ1(B, 0) = A δ1(A, 1) = BS δ1(BS, 0) = A Заключительным состоянием построенного детерминированного КА является состояние BS. Таким образом, M1 = ({H, B, A, BS}, {0, 1}, δ1, H, BS).

Задачи лексического анализа 1.выделить в исходном тексте цепочку символов, представляющую лексему, и проверить правильность ее записи; 2.удалить пробельные литеры и комментарии; 3.преобразовать цепочку символов, представляющих лексему, в пару: ( тип_лексемы, указатель_на_информацию_о_ней ); 4.зафиксировать в специальных таблицах для хранения разных типов лексем факт появления соответствующих лексем в анализируемом тексте. Чтобы решить эту задачу, опираясь на способ анализа с помощью ДС, на дугах вводится дополнительные пометки-действия. Теперь каждая дуга в ДС может выглядеть так:

Лексический анализ языков программирования Принято выделять следующие типы лексем: идентификаторы, служебные слова, константы и ограничители. Каждой лексеме сопоставляется пара: ( тип_лексемы, указатель_на_информацию_о_ней ). Таким образом, лексический анализатор - это транслятор, входом которого служит цепочка символов, представляющих исходную программу, а выходом - последовательность лексем. Лексемы перечисленных выше типов можно описать с помощью регулярных грамматик. Например, идентификатор (I): I a | b|...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9 целое без знака (N): N 0 | 1 |...| 9 | N0 | N1 |...| N9

Описание модельного языка P program D1; B D1 var D {, D } D I {, I }: [ int | bool ] B begin S { ; S } end S I := E | if E then S else S | while E do S | B | read (I) | write (E) E E1 [ = | | = | != ] E1 | E1 E1 T { [ + | - | or ] T } T F { [ * | / | and ] F } F I | N | L | not F | (E) L true | false I a | b|...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9 N 0 | 1 |...| 9 | N0 | N1 |...| N9 Замечания: запись вида { } означает итерацию цепочки, т.е. в порождаемой цепочке в этом месте может находиться либо, либо, либо, либо и т.д. запись вида [ | ] означает, что в порождаемой цепочке в этом месте может находиться либо, либо. P - цель грамматики; символ - маркер конца текста программы.

Контекстные условия. Любое имя, используемое в программе, должно быть описано и только один раз. В операторе присваивания типы переменной и выражения должны совпадать. В условном операторе и в операторе цикла в качестве условия возможно только логическое выражение. Операнды операции отношения должны быть целочисленными. Тип выражения и совместимость типов операндов в выражении определяются по обычным правилам; старшинство операций задано синтаксисом. В любом месте программы, кроме идентификаторов, служебных слов и чисел, может находиться произвольное число пробелов и комментариев вида { }. Program, var, int, bool, begin, end, if, then, else, while, do, true, false, read и write - служебные слова (их нельзя переопределять). Используется паскалевское правило о разделителях между идентификаторами, числами и служебными словами.

Представление лексем enum type_of_lex { LEX_NULL, /*0*/ LEX_AND, LEX_BEGIN, … LEX_WRITE, /*18*/ LEX_FIN, /*19*/ LEX_SEMICOLON, LEX_COMMA, … LEX_GEQ, /*35*/ LEX_NUM, /*36*/ LEX_ID, /*37*/ POLIZ_LABEL, /*38*/ POLIZ_ADDRESS, /*39*/ POLIZ_GO, /*40*/ POLIZ_FGO }; /*41*/ Содержательно внутреннее представление лексем - это пара ( тип_лексемы, значение_лексемы ). Значение лексемы - это номер строки в таблице лексем соответствующего класса, содержащей информацию о лексеме, или непосредственное значение, например, в случае целых чисел. Соглашение об используемых таблицах лексем: TW - таблица служебных слов М-языка; TD - таблица ограничителей М-языка; TID - таблица идентификаторов анализируемой программы;

Класс Lex class Lex { type_of_lex t_lex; int v_lex; public: Lex ( type_of_lex t = LEX_NULL, int v = 0) { t_lex = t; v_lex = v; } type_of_lex get_type ( ) { return t_lex; } int get_value ( ) { return v_lex; } friend ostream& operator

Класс Ident class Ident { char *name; bool declare; type_of_lex type; bool assign; int value; public: Ident ( ) { declare = false; assign = false; } char *get_name ( ) { return name; } void put_name ( const char * n ) { name = new char [ strlen ( n ) + 1]; strcpy ( name, n ); } bool get_declare ( ) { return declare; } void put_declare ( ) { declare = true; } type_of_lex get_type ( ) { return type; } void put_type ( kind_of_lex t ) { type = t; } bool get_assign ( ) { return assign; } void put_assign ( ) { assign = true; } int get_value ( ) { return value; } void put_value ( int v ) { value = v; } };

Класс tabl_ident class tabl_ident{ ident *p; int size; int top; public: tabl_ident ( int max_size ) { p = new ident [ size = max_size ]; top = 1; } ~tabl_ident ( ) { delete [ ] p; } ident & operator [ ] ( int k ) { return p [ k ]; } int put (const char * buf); }; int tabl_ident::put(const char * buf) { for (int j = 1; j < top; j++) if ( ! strcmp ( buf,p [ j ].get_name ( ) ) ) return j; p [ top ].put_name ( buf ); top++; return top - 1; }

Класс Scanner class Scanner { enum state { H, IDENT, NUMB, COM, ALE, DELIM, NEQ }; static char* TW [ ]; static type_of_lex words [ ]; static char * TD [ ]; static type_of_lex dlms [ ]; state CS; FILE *fp; char c; char buf [ 80 ]; int buf_top; void clear ( ) ; void add ( ); int look (const char * buf, char * * list); void gc ( ) { c = fgetc ( fp ); } public: Scanner (const char * program); Lex get_lex (); };

Класс Scanner void Scanner::clear ( ) { buf_top = 0; for (int j = 0; j < 80; j++ ) buf [ j ] = '\0'; } void Scanner::add ( ) { buf [ buf_top ++ ] = c; } int Scanner::look (const char * buf, char * * list) { int i = 0; while (list [ i ]) { if ( ! strcmp (buf, list [ i ] ) ) return i; i++; } return 0; } Scanner::Scanner (const char * program) { fp = fopen ( program, "r" ); CS = H; clear(); }

Таблицы лексем для М-языка char * Scanner:: TW [ ] = { NULL,"and","begin","bool","do","else","end", // "if","false","int","not","or","program","read", // "then","true","var","while","write }; // char * Scanner:: TD [ ] = {NULL, ";", ",", ":", ":=", "(", ")", // "="," ", "+", "-", "*", "/", " ="}; // tabl_ident TID (100);

Lex Scanner::get_lex ( ) { int d, j; CS = H; do {gc (); switch(CS) { case H: if ( c == ' ' || c == '\n' || c == '\r' || c == '\t ) else if ( isalpha(c)) { clear(); add(); CS = IDENT; } else if ( isdigit (c) ) { d = c - '0'; CS = NUMB; } else if ( c == '{' ) { CS = COM; } else if ( c == ':' || c == ' ') { clear(); add(); CS = ALE; } else if ( c == return Lex (LEX_FIN); else if ( c == '! ) { clear(); add (); CS = NEQ; } else CS = DELIM; break;

case IDENT: if ( isalpha(c) || isdigit(c) ) { add(); } else if ( j = look (buf, TW) ) return Lex (words[ j ], j); else { j = TID.put (buf); return Lex (LEX_ID, j); } break; case NUMB: if ( isdigit (c) ) { d = d * 10 + (c - '0'); } else return Lex ( LEX_NUM, d); break; case COM: if ( c == '}' ) { CS = H; } else if (c == || c == '{' ) throw c; break;

case ALE: if ( c == '= ) { add(); j = look ( buf, TD ); return Lex ( dlms [ j ], j); } else { j = look (buf, TD); return Lex ( dlms [ j ], j ); } break; case NEQ: if ( c == '= ) { add(); j = look ( buf, TD ); return Lex ( LEX_NEQ, j ); } else throw '!'; break; case DELIM: clear( ); add( ); if ( j = look(buf, TD) ) { return Lex ( dlms [ j ], j );} else throw c; break; } //end switch } while ( true ); }