Модельный язык программирования (1119466)
Текст из файла
Предмет изучения:системы программирования• Основные определения• Программный продукт и его жизненный цикл• Основные компоненты системпрограммирования• Трансляторы: компиляторы и интерпретаторы• Языки программирования и средства ихформального описания• Объектно-ориентированный подход кпроектированию программных продуктов• Язык программирования Си++1Правила грамматики М-языкаPD1DBS→→→→→EE1TFLINCR→→→→→→→→→program D1; B⊥var D {, D}I {, I}: [ int | bool ]begin S {; S} endI := E | if E then S else Swhile E do S | B | read (I) | write (E)E1 | E1 [ = | < | > | <= | >= |!= ] E1T {[ + | - | or ] T}F {[ * | / | and ] F}I | N | L | not F | (E)true | falseC | IC | IRR | NRa | b | ...
| z | A | B | ... | Z0 | 1 | 2 | ... | 92Правила модельного языка• Запись вида {α} означает итерацию цепочки α(повторение её 0 или более раз): впорождаемой цепочке в этом месте можетнаходиться либо ε, либо α, либо αα, либо ααα,и так далее• Запись вида [α|β] означает, что впорождаемой цепочке этом месте можетнаходиться либо α, либо β• P – цель грамматики• Символ ⊥ – маркер конца текста программы3Контекстные условия в М-языке1. Любое имя, используемое в программе, должно бытьописано, причём только один раз2. В операторе присваивания типы переменной ивыражения должны совпадать3. В условном операторе и в операторе цикла в качествеусловия возможно только логическое выражение4.
Операнды операций отношения должны бытьцелочисленными5. Тип выражения и совместимость типов операндов ввыражении определяются по обычным правилам(нельзя складывать целочисленные и логическиезначения); старшинство операций задано4синтаксисомПримечания в М-языке• В любом месте программы, кромеидентификаторов, служебных слов и чисел,может находиться произвольное числопробелов и примечаний (комментариев) вида{< любые символы, кроме символов } и ⊥ >}• Вложенных комментариев в модельном языкенет5Лексемы модельного языка• Идентификаторы: первым символом любогоимени всегда является строчная или прописнаялатинская буква (строчные и прописные буквыразличаются), следующими символами вименах могут быть любые буквы и любыедесятичные цифры• Целые числа по основанию 10.
В языкевыбрана десятичная система счисления• Односимвольные и двухсимвольные знакиопераций• Служебные (ключевые) слова6План работы анализатора языка1. Ввод очередного набора символов (“лексемы”)Символы текста программы “от пробела допробела”набираются в буфер2. Поиск по таблицам лексемПоиск должен вестись сравнением содержимогонабранного буфера с текстовым представлениемстандартных правильных лексем3. Успешный поиск в таблице означает обнаружениев тексте правильной лексемыПравильными лексемами также считаются любыеимена и десятичные константы7Действия в грамматике М-языкаGetS– ввод очередного символа исходнойпрограммыclear– инициализация ввода символов лексемыadd– добавление символа к буферу лексемget_token – поиск лексем в таблицах служебных слов (TW ),ограничителей и знаков операций (TD )get_object – поиск в таблице имён (TI ) или констант (TC )Ident– создание нового объекта “Идентификатор”Number – создание нового объекта “Константа”put_obj – занесение информации о вновь созданныхобъектах в таблицы констант (TC ) или имён (TI)Token– создание новой лексемы при вводе константыили идентификатора (имени)8Диаграмма состоянийGetSH(State = Error)clear, addцифраadd, GetSget_object/{put_object}Literal⊥Identifier{GetS!цифраclear, add,clear, add, GetSGetSбуква, цифраadd, GetSget_token{get_object/}{put_object}пробелбуква:<>clear, add,GetSGetSComment⊥{NOperator=Error=add, GetS,get_tokenadd, GetS, get_tokenLOperatorclear, add,OperatorGetS clear, add}GetSget_token+–*/;,()=get_token{GetS/Error}9Автомат анализатораclass Scanner { enum State { H,Comment, Noperator,Operator,Identifier, Literal,Error };State FA_State; FILE * fp;char c;buf b;Token Scanner:: get_lex () { Token * res;for (;;) { switch (FA_State) {case H:if (isspace (c)GetS ();else if (isalpha (c)) { b.clear (); b.add (); GetS ();else if (isdigit (c)) { b.clear (); b.add (); GetS ();else if (c== ‘{’ ){GetS ();else if (c== ‘:’ || c== ‘<’ || c== ‘>’){ b.clear (); b.add (); GetS ();else if (c == ‘⊥’) {b.clear (); b.add ();else if (c == ‘!’){ b.clear (); b.add (); GetS ();else{ b.clear (); b.add ();break;/* { */case Comment:if (c == ‘}’){GetS ();else if (c == ‘⊥’) {else if (c == ‘{’){elseGetS ();break;/* … */ };LOperator,/* … *//* … */FA_State = Identifier;FA_State = Literal;FA_State = Comment;}}}FA_State = LOperator;FA_State = Error;return TD.get_token (b);FA_State = NOperator;FA_State = Operator;}}}}FA_State = H;}FA_State = Error; throw c; }throw c; }10Автомат анализатораclass Scanner { enum State { H,Comment,Identifier,State FA_State; FILE * fp;Token Scanner:: get_lex () { Token * res;for (;;) { switch (FA_State) {/* : < > */ case LOperator:if (c == ‘=’)/* ! *//* … */ };Noperator,Literal,char c;{Operator,Error };buf b;b.add (); GetS ();break;case NOperator:if (c == ‘=’){b.add (); GetS ();elsebreak;case Operator:if ((res = TD.get_token (b)) != 0) { GetS ();elsebreak;case Error:break;LOperator,/* … *//* … */FA_State = H;return TD.get_token (b);}FA_State = H;return TD.get_token (b); }throw ‘!’;FA_State = H;return res;throw c;throw c;11}Автомат анализатораclass Scanner { enum State { H,Comment, Noperator,Operator,LOperator,Identifier, Literal,Error };State FA_State; FILE * fp;char c;buf b;/* … */Token Scanner:: get_lex () { Token * res;for (;;) { switch (FA_State) {/* … */case Identifier: if (isalnum(c)) {b.add (); GetS ();}else{FA_State = H;if ((res = TW.get_token (b)) !=0 ) return res;return new Token (LEX_ID, CreateIdentObject (b));}break;case Literal: if (isdigit (c)) {b.add (); GetS ();}else{FA_State = H;return new Token(LEX_NUM,CreateNumberObject(b));}break;} // end switch (FA_State)} // end for};12Обработка ошибок при анализеParser::~Parser (char * program): scan (program) { }Parser::~Parser (){}void Parser:: Analyze () { GetL (); P (); }int main (int argc, char ** argv) { /* ...
*/try { Parser * M = new Parser (“program.txt”);M -> Analyze ();}catch (char c){ cout << “Неверный символ при лексическом”“ анализе: ” << c << endl;/* ... */} /* ... */13}Класс описания лексемclass Token { type_of_lex type;ProgramObject * value;// тип лексемы// значение лексемы:// указатель на объект// Конструктор лексем:public: Token (const type_of_lex t, ProgramObject * v = 0);// Выдать тип лексемы по запросу из-внеtype_of_lex get_type () const;// Выдать указатель на объект лексемыProgramObject * get_value () const;// Установить новый тип лексемыvoid set_type (const type_of_lex t);// Связать лексему с объектомvoid set_value (ProgramObject * v);};14Типы лексемenum type_of_lex { LEX_NULL,LEX_PROGRAM, LEX_VAR,LEX_BOOL, LEX_INT,LEX_FALSE,LEX_TRUE,LEX_BEGIN, LEX_END,LEX_ASSIGN,LEX_IF,LEX_THEN, LEX_ELSE,LEX_WHILE,LEX_DO,LEX_READ, LEX_WRITE,LEX_AND,LEX_NOT,LEX_OR,LEX_LT,LEX_LE,LEX_EQ,LEX_NE,LEX_GE,LEX_GT,LEX_DIV,LEX_PLUS,LEX_MINUS,LEX_MULT,LEX_LPAREN, LEX_RPAREN,LEX_COMMA, LEX_COLON, LEX_SEMICOLON,LEX_ID,LEX_NUM,LEX_FIN}; // Сведения о лексемах берутся из правил языка15Лексемы, определяемые языком• Таблицы служебных слов языка и знаков операций иограничителей:static char * KeyWords [] = {“”,“program”, “begin”,“bool”, “true”,“false”,“do”, “while”,“read”,“and”,“end”,“var”,“int”,“if”,“then”, “else”,“write”, “not”, “or”,0};static char * Delimiters [] = {“”,“⊥”,“,”,“:”,“<”,“<=”,“=”,“!=”,“+”,“-”,“*”,“/”,0};“:=”,“>=”,“(”,“;”,“>”,“)”,16Лексемы, определяемые языком• Типов лексем LKeyWords и LDelimiterstatic type_of_lex LKeyWords [] = {LEX_NULL,LEX_VAR,LEX_FALSE,LEX_DO,LEX_NOT,LEX_PROGRAM,LEX_INT,LEX_IF,LEX_WHILE,LEX_OR,LEX_BEGIN,LEX_BOOL,LEX_THEN,LEX_READ,LEX_AND,static type_of_lex Ldelimiters [] = {LEX_NULL,LEX_ASSIGN,LEX_EQ,LEX_PLUS,LEX_LPAREN,LEX_FIN,LEX_SEMICOLON,LEX_NE,LEX_MINUS,LEX_RPAREN,LEX_COMMA,LEX_LT,LEX_GE,LEX_MULT,LEX_NULL};LEX_END,LEX_TRUE,LEX_ELSE,LEX_WRITE,LEX_NULL};LEX_COLON,LEX_LE,LEX_GT,LEX_DIV,17Класс таблиц лексемclass TokenTable { Token ** p; char ** c; int size;public: TokenTable (int max_size, char * data [],type_of_lex t []);~ TokenTable ();// деструктор таблицыint get_size () const;// доступ к размеру таблицыvoid put_obj (ProgramObject * t, int i);Token * get_token (const buf & b) const;/* ...
*/};TokenTable TW (sizeof ( KeyWords)/sizeof ( KeyWords[0]),KeyWords, LKeyWords);TokenTable TD (sizeof ( Delimiters)/sizeof(Delimiters[0]),Delimiters, LDelimiters);18Буфер для сборки лексемclass buf { char * b;int size;int top;public: buf// указатель на буфер ввода лексем// размер буфера ввода лексем// текущая позиция для ввода в буфер(int max_size = 260) // конструктор буфера{ b = new char [size = max_size]; clear (); }~ buf() { delete b; }// деструктор буфераvoid clear() { memset (b, ‘\0’, size); top = 0; }void add(const char c) { b [top ++] = c; }char * get_string () const; // выдать представление лексемы};Token * TokenTable::get_token (const buf & b) const{ Token ** q = p; char ** s = c; Token * t;while (*q) { t = *q ++; if (! strcmp (b.get_string (), * s ++)) return t; }return 0;}19Класс программных объектов• Лексический анализатор работает с объектами трёх видов:• Имена, введённые программистом (Ident)• Константы, введённые программистом (Number)• Операции, определённые в языке (Operation)• В программе создаётся базовый класс объектов и системапроизводных классов:class ProgramObject { protected: type_of_lex type; int value;public: type_of_lex get_type() const;voidset_type(type_of_lex t);intget_value () const;voidset_value (int v);virtual boolis_object(const buf & b) const = 0;};class Ident:public ProgramObject { /* ...
*/ };class Number:public ProgramObject { /* ... */ };class Operation: public ProgramObject { /* ... */ };20Операционные объектыObjectTable<Operation> TO (20);// Таблица для операционных объектовint size = TW.get_size () - 1; for (int i = 0; i < size; i ++){ Token * T = TW (i); char * Ep = TW [i]; type_of_lex tp = T -> get_type ();switch (tp){ case LEX_AND:TW.put_obj (TO.put_obj (new AndObject(Ep, tp)), i ); break;case LEX_WRITE: TW.put_obj (TO.put_obj (new WriteObject (Ep, tp)), i ); break;/* LEX_TRUELEX_FALSELEX_NOTLEX_ORLEX_READ */}}int size = TD.get_size () - 1; for (i = 0; i < size; i ++){ Token * T = TD (i); char * Ep = TD [i]; type_of_lex tp = T -> get_type ();switch (tp){ case LEX_ASSIGN: TD.put_obj (TO.put_obj (new AssignObject (Ep, tp)), i); break;case LEX_LT:TD.put_obj (TO.put_obj (new LtObject(Ep, tp)), i); break;/* LEX_EQLEX_GTLEX_LELEX_GELEX_NE*//* LEX_PLUSLEX_MINUSLEX_MULTLEX_DIV*/}class TokenTable { Token ** p; char ** c; int size; // дополнительные методы}/* … */Token * TokenTable:: operator () (int k) { return p [k]; }21char * TokenTable:: operator [] (int k) { return c [k]; } };Классы операционных объектовclass TrueObject :public Operation { public: TrueObjectclass FalseObject :public Operation { public: FalseObjectclassNotObject :public Operation { public: NotObjectclassOrObject :public Operation { public:OrObjectclassAndObject :public Operation { public: AndObjectclassEqObject :public Operation { public:EqObjectclassLtObject :public Operation { public:LtObjectclassGtObject :public Operation { public:GtObjectclassLeObject :public Operation { public:LeObjectclassGeObject :public Operation { public:GeObjectclassNeObject :public Operation { public:NeObjectclassPlusObject :public Operation { public: PlusObjectclass MinusObject :public Operation { public: MinusObjectclass MultObject :public Operation { public: MultObjectclassDivObject :public Operation { public:DivObjectclass AssignObject :public Operation { public: AssignObjectclass WriteObject :public Operation { public: WriteObjectclass ReadObject :public Operation { public: ReadObject(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };(char *s, type_of_lex t); };22Таблицы программных объектов• Таблица любых программных объектов(идентификаторов, констант и операций) может иметьтакие элементы данных:• внешнее представление текущего объектаидентификатора или операции (буквы, цифры,знаки операций), который надо найти в таблицеили записать туда• внешнее представление констант в производномклассе констант отсутствует• указатель на свободное место в таблице• общий размер таблицы23Шаблон таблиц объектовtemplate <class Object> class ObjectTable int size; public: Object ** p; int free;public:ObjectTable (int max_size);~ ObjectTable ();Object * operator [] (int k);Object * put_obj (Object * t = 0){ p [free ++] = t; return t; }Object * get_object (const buf & b) const{ Object ** q = p; Object * t;for (int i = 0; i < free; i ++){ t = * q ++;if (t -> is_object (b)) return t; // Виртуальная функция}return 0;}};ObjectTable<Ident>TI(100);ObjectTable<Number>TC(40);24ObjectTable<Operation> TO(20); // Операционные объектыПроизводные классы объектовclass Ident:public ProgramObject { char * name; public: Ident (const buf & b);char * get_name ()const;bool is_object (const buf & b) const; };class Number: public ProgramObject { public: Number (const buf & b);bool is_object (const buf & b) const; };Ident *{Scanner::CreateIdentObject (const buf & b)Ident * I = TI.get_object(b);return I == 0 ? TI.put_obj (new Ident (b)) : I;}Number * Scanner::CreateNumberObject (const buf & b){Number * N = TC.get_object(b);return N == 0 ? TC.put_obj (new Number (b)) : N;}class Operation: public ProgramObject { char * sign;protected: Operation ( char * str, type_of_lex t);public: bool is_object (const buf & b) const; };25Списки в модельном языке• Правила со списками грамматики модельного языка:B → begin S {;S} endD → I {,I}: [ int | bool ]D1 → var D {,D}T → F {[ * | / | and ] F}E1 → T {[ + | - | or ] T}• Вычисление множеств first и follow:follow (List) = {;}⊕D1: first (List) = {,}D: first (List) = {,}follow (List) = {:}⊕B: first (List) = {;}follow (List) = {end}⊕E1: first (List) = {+ – or } follow (List) = {< > <= >= = !=}∪ follow (E) = { ) then do } ∪ follow (S) = { ; end else } ⊕T: first (List) = {* / and} follow (List) = { + – or }∪ follow (E1) = { < > <= >= = != ) ; do else end then }⊕26Списки в модельном языке• Правила для символов S и E терминализируются:S → BE → E1 | E1 [ = | < | > | <= | >= |!= ] E1• Удаление общих начал в правилах для символа E:E → E1 E2E2 → [ = | < | > | <= | >= |!= ] E1 | ε• Вычисление множеств first и follow для символа E2:E2: first (E2) = {< > <= >= = !=}follow (E2) = follow (E) = { ) ; do else end then } ⊕• Метод рекурсивного спуска к модельному языкуприменим27Семантический анализ описаний• Правила грамматики модельного языка, на основе которыхмогут порождаться операторы описания данных:P → program D1;B⊥D1 → var D {,D}D → I {,I}: [ int | bool ]• При компиляции :• имена локальных объектов блоков дополняются именамиблоков (функций, процедур), в которых они описаны• имена внутренних переменных и функций модулейпрограммы дополняются именами самих этих модулей• имена процедур и функций дополняются именами классовили объемлющих процедур• имена методов классов и перегруженных функцийдополняются именами, строящимися в зависимости от числа28и типов их формальных параметровОператор присваивания• Оператор присваивания являетсядвухместным:I := E• Оператор присваивания в ПОЛИЗ:или&I E := ;I E := ;• Операнды двухместной операцииприсваивания ‘:=’• адрес переменной I(обозначается как &I или I) и• ПОЛИЗ выражения E (обозначается как Е)• Операция ‘;’ удаляет ненужный результат29Операторы ввода/вывода• Операторы ввода/вывода являютсяодноместными:read (I)write (E)• Представление операторов ввода/вывода вПОЛИЗ:&I Read и E Write• Запись &I означает, что операндом операцииявляется адрес переменной I, а не её значение• Двойное подчёркивание означаетиспользование ПОЛИЗ подчёркнутого элемента• Образ составного оператора естьпоследовательность образов составляющихоператоров30Классы объектной модели•••••••••class bufclass TokenTableclass Tokentemplate<class Object> class ObjectTableclass ProgramObject• class Address: public ProgramObject• class Ident: public ProgramObject• class Label: public ProgramObject• class Number: public ProgramObject• class Operation: public ProgramObject• class TrueObject: public Operation …• class ReadObject: public Operationclass Scannerclass Parserclass Simulatortemplate <class T, int max_size> class StackTD, TWTA, TC, TI, TL, TO, PLZNames, Types, Values31Обработка ошибок при анализе• Возбуждение исключительных ситуаций осуществляется внутриметодов Analyze () и P ():Parser::~Parser (char * program): scan (program) {}Parser::~Parser (){}void Parser:: Analyze () { GetL (); P (); } // запуск анализатораint main (int argc, char ** argv){ /* ...
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
