О рекурсивном спуске (Мини-учебник с ejudge = Чернокнижка)

Учебные материалы для 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.