formal_languages_translation_theory (Формальные грамматики), страница 9

| z | A | B | ... | Z0 | 1 | 2 | ... | 9Замечания к грамматике модельного языка:а) запись вида {} означает итерацию цепочки , т. е. в порождаемой цепочке вэтом месте может находиться либо , либо , либо , либо  и т. д.;б) запись вида [ | ] означает, что в порождаемой цепочке в этом месте можетнаходиться либо , либо ;в) P — цель грамматики; символ  — маркер конца текста программы.Контекстные условия:1. Любое имя, используемое в программе, должно быть описано и только один раз.2. В операторе присваивания типы переменной и выражения должны совпадать.3.

В условном операторе и в операторе цикла в качестве условия возможно толькологическое выражение.4. Операнды операции отношения должны быть целочисленными.5. Тип выражения и совместимость типов операндов в выражении определяются пообычным правилам; старшинство операций задано синтаксисом.В любом месте программы, кроме идентификаторов, служебных слов и чисел, можетнаходиться произвольное число пробелов и комментариев в фигурных скобках вида { любые символы, кроме «}» и «»  }.true, false, read и write — служебные слова (в М-языке их нельзя переопределять в отличие от аналогичных стандартных идентификаторов в Паскале).Разделители между идентификаторами, числами и служебными словами употребляются так же, как в Паскале.37Элементы теории трансляции / Задачи лексического анализаПерейдем к построению лексического анализатора.Вход лексического анализатора — символы исходной программы на М-языке; результат работы — исходная программа в виде последовательности лексем (их внутреннего представления).

В нашем случае лексический анализатор будет вызываться, когда потребуетсяочередная лексема исходной программы, поэтому результатом работы лексического анализатора будет очередная лексема анализируемой программы на М-языке.Лексический анализатор для модельного языка будем создавать поэтапно: сначалаопишем на языке Си   классы объектов, которые будут использоваться при ЛА, затем построим ДС с действиями для распознавания и формирования внутреннего представлениялексем, а затем по ДС напишем программу ЛА. Отметим, что мы будем рассматривать одиниз возможных способов проектирования и реализации программы ЛА на Си  , быть может, не самый лучший.Проектирование классовой структуры лексического анализатораПредставление лексем: выделим следующие типы лексем, введя следующий перечислимый тип данных:enum type_of_lex{LEX_NULL,LEX_AND, LEX_BEGIN, … LEX_WRITE,LEX_FIN,LEX_SEMICOLON, LEX_COMMA, … LEX_GEQ,LEX_NUM,LEX_ID,POLIZ_LABEL,POLIZ_ADDRESS,POLIZ_GO,POLIZ_FGO};////////////////////0181935363738394041Содержательно внутреннее представление лексем — это пара (тип_лексемы, значение_лексемы).

Значение лексемы — это номер строки в таблице лексем соответствующегокласса, содержащей информацию о лексеме, или непосредственное значение, например, вслучае целых чисел.Соглашение об используемых таблицах лексем:TW — таблица служебных слов М-языка;TD — таблица ограничителей М-языка;TID — таблица идентификаторов анализируемой программы;Таблицы TW и TD заполняются заранее, т. к. их содержимое не зависит от исходнойпрограммы; TID формируется в процессе анализа.Необходимые таблицы можно представить в виде объектов, конкретный вид которыхмы рассмотрим чуть позже, или в виде массивов строк, например, для служебных слов.Класс Lex:38Элементы теории трансляции / Задачи лексического анализаclass Lex{type_of_lex t_lex;intv_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 << ( ostream &s, Lex l ){s << '(' << l.t_lex << ',' << l.v_lex << ");";return s;}};Класс Ident:class Ident{char*booltype_of_lexboolintpublic:Ident (){declareassign}name;declare;type;assign;value;= false;= 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;}39Элементы теории трансляции / Задачи лексического анализа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;intsize;inttop;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 ){40Элементы теории трансляции / Задачи лексического анализа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{enumstate { H, IDENT, NUMB, COM, ALE, DELIM, NEQ };static char* TW[];static type_of_lexwords[];static char* TD[];static type_of_lexdlms[];stateCS;FILE* fp;charc;charbuf[80];intbuf_top;void clear (){buf_top = 0;for ( int j = 0; j < 80; ++j )buf[j] = '\0';}void add (){buf [ buf_top ++ ] = c;}int look ( const char *buf, char **list ){int i = 0;while ( list[i] ){if ( !strcmp(buf, list[i]) )return i;++i;}return 0;}void gc (){c = fgetc (fp);}public:41Элементы теории трансляции / Задачи лексического анализаLex get_lex ();Scanner ( const char * program ){fp = fopen ( program, "r" );CS = H;clear();gc();}};Таблицы лексем М-языка можно описать на Си  , например, таким образом:char * Scanner::TW[] ={""// 0 позиция 0 не используется"and",// 1"begin",// 2"bool",// 3"do",// 4"else",// 5"end",// 6"if",// 7"false",// 8"int",// 9"not",// 10"or",// 11"program",// 12"read",// 13"then",// 14"true",// 15"var",// 16"while",// 17"write",// 18NULL};char * Scanner::{"""@",";",",",":",":=","(",")","=","<",">","+","-","*","/","<=",42TD[] =////////////////////////////////0 позиция 0 не используется123456789101112131415Элементы теории трансляции / Задачи лексического анализа"!=",">=",NULL// 16// 17};tabl_ident TID(100);type_of_lex Scanner::words[] ={LEX_NULL,LEX_AND,LEX_BEGIN,LEX_BOOL,LEX_DO,LEX_ELSE,LEX_END,LEX_IF,LEX_FALSE,LEX_INT,LEX_NOT,LEX_OR,LEX_PROGRAM,LEX_READ,LEX_THEN,LEX_TRUE,LEX_VAR,LEX_WHILE,LEX_WRITE,LEX_NULL};type_of_lex Scanner::dlms[] ={LEX_NULL,LEX_FIN,LEX_SEMICOLON,LEX_COMMA,LEX_COLON,LEX_ASSIGN,LEX_LPAREN,LEX_RPAREN,LEX_EQ,LEX_LSS,LEX_GTR,LEX_PLUS,LEX_MINUS,LEX_TIMES,LEX_SLASH,LEX_LEQ,LEX_NEQ,LEX_GEQ,LEX_NULL};43Элементы теории трансляции / Задачи лексического анализаgc();’_’Hadd(); gc();буква,цифрабукваclear(); add(); gc();цифраd  c´0´; gc();IDENTj  look(buf, TW); Lex(words[j], j);или j  TID.put(buf); Lex(LEX_ID, j);d  d*10  ( c –´0´); gc( );цифраNUMBLex(LEX_NUM, d);gc( );{}COMgc();gc();:,,ERALEclear(); add(); gc();jlook(buf, TD); Lex(dlms[j], j);add( ); gc( ); jlook(buf, TD); Lex(dlms[j], j);Lex(LEX_FIN);!gc();NEQgc() ; Lex(LEX_NEQ);ER,,,/,,,;,(,),DELIMclear( ); add( ); gc( );jlook(buf, TD); Lex(dlms[j], j);Рис.

9. ДС для модельного языка.44Элементы теории трансляции / Задачи лексического анализаНа рис. 9 приведена диаграмма состояний для модельного языка. Лексический анализможет проводиться независимо от последующих этапов трансляции. В этом случае исходныйфайл с текстом программы преобразуется в последовательность лексем во внутреннем представлении согласно построенной ДС; затем эта последовательность подается на вход синтаксическому анализатору.Мы реализуем другой подход: лексический анализатор выдает очередную лексему потребованию синтаксического анализатора и затем «замирает», пока к нему не обратятся заследующей лексемой.

При таком подходе действие Lex(k, l); в ДС означает return Lex(k, l);.Кроме того, вместо перехода в состояние ошибки ER генерируется исключение с указаниемсимвола, который привел к ошибочной ситуации. Перехватываться и обрабатываться исключения будут не в лексическом анализаторе, а в основной программе, содержащей анализатор. Обработка исключения состоит в выводе сообщения об ошибке и корректном завершении программы.Непосредственно реализует ЛА по ДС функция get_lex():Lex Scanner::get_lex (){int d, j;CS = H;do{switch ( CS ){case H:if ( c ==' ' || c =='\n' || c=='\r' || c =='\t' )gc ();else if ( isalpha(c) ){clear ();add ();gc ();CS = IDENT;}else if ( isdigit(c) ){d = c - '0';gc ();CS = NUMB;}else if ( c== '{' ){gc ();CS = COM;}else if ( c== ':' || c== '<' || c== '>'){clear ();add ();gc ();CS = ALE;}else if ( c == '@' )return Lex(LEX_FIN);45Элементы теории трансляции / Задачи лексического анализаelse if ( c == '!' ){clear ();add ();gc ();CS = NEQ;}elseCS = DELIM;break;case IDENT:if ( isalpha(c) || isdigit(c) ){add ();gc ();}elseif ( 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');gc();}elsereturn Lex ( LEX_NUM, d );break;case COM:if ( c == '}' ){gc ();CS = H;}else if (c == '@' || c == '{' )throw c;elsegc ();break;case ALE:if ( c == '=' ){add ();gc ();j = look ( buf, TD );return Lex ( dlms[j], j );}else{46Элементы теории трансляции / Синтаксический анализj = look (buf, TD);return Lex ( dlms[j], j );}break;case NEQ:if ( c == '=' ){add ();gc ();j = look ( buf, TD );return Lex ( LEX_NEQ, j );}elsethrow '!';break;case DELIM:clear ();add ();if ( j = look(buf, TD) ){gc ();return Lex ( dlms[j], j );}elsethrow c;break;}// end switch}while ( true );}Можно упростить реализацию метода get_lex(), вынеся обращение к gc() из телаswitch и вставив его непосредственно перед оператором switch.Синтаксический анализНа этапе синтаксического анализа нужно:1) установить, имеет ли цепочка лексем структуру, заданную синтаксисом языка, и2) зафиксировать эту структуру.Следовательно, снова надо решать задачу разбора: дана цепочка лексем, и надо определить, выводима ли она в грамматике, определяющей синтаксис языка.

Если да, то построить вывод этой цепочки или дерево вывода. Однако структура таких конструкций как выражение, описание, оператор и т.п., более сложная, чем структура идентификаторов и чисел.Поэтому для описания синтаксиса языков программирования нужны более мощные грамматики, чем регулярные. Обычно для этого используют КС-грамматики, правила которых име*ют вид A → , где A  N,   (T  N ) .