О рекурсивном спуске (1114930)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Учебные материалы для 2 курсаГлавная страницаЗанятия по языку СиЗанятия попрограммированию вUnixМатериалы длядополнительного чтенияКонспекты занятий поязыку Си++Опции компилятора насервере (C)Опции компилятора насервере (C++)Стиль форматированияпрограммО вещественных числахО рекурсивном спускеО написании MakefileЗадание намоделирование кешаДокументация по STLСсылкиПамятка по работе в UnixЛекции по ОС для КазФМГУО рекурсивном спускеПредположим, что необходимо провести анализ выражения, записанного в строке,и построить дерево разбора. В выражении допускаются бинарные операции +, *,числа и скобки.Такие выражения описываются следующей грамматикой:expr0 : expr1 { '+' expr1 } ;expr1 : expr2 { '*' expr2 } ;expr2 : '(' expr0 ')' | NUM ;Здесь символы :, |, ;, {, } — специальные символы, используемые для записиграмматики.Определим константы, перечисляющие возможные виды лексических единиц(лексем):enum{OP_EOF,OP_NUM,OP_PLUS,OP_STAR,OP_LBR,OP_RBR};// конец строки// число// знак '+'// знак '*'// знак '('// знак ')'Определим тип узла дерева, который будет использоваться как для передачиинформации от лексического анализатора к синтаксическому, так и дляпостроения дерева.typedef struct Tree{int opcode;struct Tree *left;struct Tree *right;int num;} Tree;// код лексемы (см.

выше)// левое поддерево// правое поддерево// значение числаДля хранения текущего состояния анализатора будем использовать глобальныепеременные.static const unsigned char *parse_str; // анализируемая строкаstatic int parse_pos;// текущая позиция в строкеstatic Tree *parse_token;// текущая лексемаРабота лексического анализатора заключается в создании узла типа Tree длялексемы в текущей позиции текста и продвижении текущей позиции вперед построке.Фрагмент лексического анализатора приведен ниже:Tree *get_token(){if (!parse_str[parse_pos]) {// достигли конца строкиreturn tree_create_token(OP_EOF);}// проверим, что в текущей позиции находится знак операцииint opcode = OP_EOF;switch (parse_str[parse_pos]) {case '+':}opcode = OP_PLUS;break;case '(':opcode = OP_LBR;break;// прочие символы операций...}if (opcode) {parse_pos++;return tree_create_token(opcode);}if (isdigit(parse_str[parse_pos])) {// создание лексемы для числа}Работа синтаксического анализатора заключается в инициализации переменныхсостояния и запуска рекурсивной функции разбора. После завершения разборанужно проверить, что вся входная строка прочитана.Tree *parse_expr(const unsigned char *str){parse_str = str;// задать строку для разбораparse_pos = 0;// установить позицию в строкеparse_token = get_token();// считать первую лексемуTree *t = parse_expr0();// разобрать строкуif (parse_token->opcode != OP_EOF) { // проверить, что дошли до концаtree_free(t);t = 0;}tree_free(parse_token);return t;}Функция, разбирающая выражения на слагаемые, может выглядеть примерно так:Tree *parse_expr0(void){Tree *t1 = parse_expr1();if (!t1) return 0;while (parse_token->opcode == OP_PLUS) {Tree *t2 = parse_token;parse_token = get_token();Tree *t3 = parse_expr1();if (!t3) {tree_free(t1);tree_free(t2);return 0;}t2->left = t1;t2->right = t3;t1 = t2;}return t1;}Функция для анализа одного множителя (то есть либо числа, либо выражения вскобках) может выглядеть следующим образом:Tree *parse_expr2(void){if (parse_token->opcode == OP_NUM) {Tree *t = parse_token;parse_token = get_token();return t;} else if (parse_token->opcode == OP_LBR) {tree_free(parse_token);parse_token = get_token();Tree *t = parse_expr0();if (t == NULL) {return NULL;}if (parse_token->opcode != OP_RBR) {tree_free(t);return NULL;}}parse_token = get_token();return t;} else {return NULL;}Last modified: Friday, 21­Jun­2013 16:47:49 MSK Alexander Chernov.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги