Лекции (18) (Презентации лекций (PDF)), страница 2

Например,идентификатор (I):I → a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9целое без знака (N):N → 0 | 1 |...| 9 | N0 | N1 |...| N9Описание модельного языкаP →D1 →D →B →S →E →E1 →T →F →L →I →N →program D1; Bvar D { , D }I { , I }: [ int | bool ]begin S { ; S } endI := E | if E then S else S | while E do S | B | read (I) | write (E)E1 [ = | < | > | <= | >= | != ] E1 | E1T { [ + | - | or ] T }F { [ * | / | and ] F }I | N | L | not F | (E)true | falsea | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I90 | 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 - таблица идентификаторов анализируемой программы;Класс Lexclass 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 << (ostream & s, Lex l ) {s << '(' << l.t_lex << ',' << l.v_lex << ");" ;return s;}};Класс Identclass 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_identclass 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;}Класс Scannerclass 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 ();};Класс Scannervoid 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",//123456"if","false","int","not","or","program","read",// 78910111213"then","true","var","while","write“ };//1415161718char * Scanner:: TD [ ] = {NULL, ";", "@", ",", ":", ":=", "(", ")",//123 456 7"=","<", ">", "+", "-", "*", "/", "<=", ">="};//8 9 10 11 12 13 14 1516tabl_ident TID (100);gc();‘‘Hadd();gc();буква,цифрабукваclear(); add(); gc();IDENTj=look(buf,TW);Lex(words[j], j);илиj=TID.put(buf); Lex(LEX_ID, j);d=d*10+(c-’0’); gc();цифрацифраd=c-’0’; gc();NUMBLex(LEX_NUM, d)gc();{}COMgc();gc();ER:, <, >ALEclear(); add(); gc();=j=look(buf,TD); Lex(dlms[j],j)add(); gc(); j=look(buf,TD); Lex(dlms[j],j);lex(2,N:=)!Lex (LEX_FIN)=NEQgc();gc(); Lex (LEX_NEQ)ERDELIM+, - , *, /, ; , , , (, ), =clear(); add(); gc(); j=look(buf,TD); Lex(dlms[j], j);ERLex Scanner::get_lex ( ) {int d, j;CS = H;do {gc ();switch(CS) {case H:if ( c == ' ' || c == '\n' || c == '\r' || c == '\t‘ )elseif ( isalpha(c)) { clear(); add(); CS = IDENT; }elseif ( isdigit (c) ) { d = c - '0'; CS = NUMB; }elseif ( c == '{' ) { CS = COM; }elseif ( c == ':' || c == '<' || c == '>') {clear(); add(); CS = ALE; }elseif ( c == '@') return Lex (LEX_FIN);elseif ( c == '!‘ ) { clear(); add (); CS = NEQ; }else CS = DELIM;break;case IDENT:if ( isalpha(c) || isdigit(c) ) {add(); }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'); }elsereturn Lex ( LEX_NUM, d);break;case COM:if ( c == '}' ) { CS = H; }elseif (c == '@' || c == '{' ) throw c;break;case ALE:if ( c == '=‘ ) {}else {add();j = look ( buf, TD );return Lex ( dlms [ j ], j);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 );}}.