Question

Я столкнулся с проблемой освобождения кучи, используя free() в моем токенизаторе.Токенайзер является частью калькулятора синтаксического анализа рекурсивного спуска, который в остальном работает безупречно.Но после включения вызова в функцию освобождения, он ведет себя хаотично.Хотя в действительности калькулятор, вероятно, никогда не приблизится к исчерпанию своей кучи, написание программы с утечкой памяти - просто плохая практика.

tokenize.h

#define OPERAND 0
#define OPERATOR 1
#define PARENTHESIS 2
#define TERMINAL 3
#define ADD '+'
#define SUBTRACT '-'
#define MULTIPLY '*'
#define DIVIDE '/'
#define EXPONENT '^'
#define L_PARENTHESIS '('
#define R_PARENTHESIS ')'

typedef struct {
    int id;
    char *value;
} token;

int token_count();
token *tokenize();
void deallocate();

tokenize.c

#include <stdio.h>
#include <stdlib.h>

#include "tokenize.h"

int token_count(char string[]) {
    int i = 0;
    int count = 0;
    while (string[i] != '\0') {
        if (string[i] >= '0' && string[i] <= '9') {
            while (1) {
                i++;
                if (string[i] >= '0' && string[i] <= '9') {
                    continue;
                } else {
                    break;
                }
            }
            count++;
            continue;
        }
        switch (string[i]) {
          case ADD:
          case SUBTRACT:
          case MULTIPLY:
          case DIVIDE:
          case EXPONENT:
          case L_PARENTHESIS:
          case R_PARENTHESIS:
            count++;
            i++;
            continue;
          default:
            return 0;
            break;
        }
    }
    return count;
}

token *tokenize(char string[]) {
    int i = 0;
    token *ret;
    int count = token_count(string);
    if (!count) {
        return ret;
    }
    ret = malloc((count + 1) * sizeof(token));
    ret[count].id = TERMINAL;
    int ret_ind = 0;
    while (string[i] != '\0') {
        if (string[i] >= '0' && string[i] <= '9') {
            ret[ret_ind].id = OPERAND;
            int size = 0;
            int j = i;
            while (1) {
                size++;
                j++;
                if (string[j] >= '0' && string[j] <= '9') {
                    continue;
                } else {
                    break;
                }
            }
            ret[ret_ind].value = malloc(size * sizeof(char) + 1);
            ret[ret_ind].value[size + 1] = '\0';
            for(int k = 0; k < size; k++) {
                ret[ret_ind].value[k] = string[i + k];
            }
            i = j;
            ret_ind++;
            continue;
        }
        switch (string[i]) {
          case ADD:
          case SUBTRACT:
          case MULTIPLY:
          case DIVIDE:
          case EXPONENT:
            ret[ret_ind].id = OPERATOR;
            ret[ret_ind].value = malloc(2 * sizeof(char));
            ret[ret_ind].value[0] = string[i];
            ret[ret_ind].value[1] = '\0';
            ret_ind++;
            i++;
            continue;
          case L_PARENTHESIS:
            ret[ret_ind].id = PARENTHESIS;
            ret[ret_ind].value = malloc(2 * sizeof(char));
            ret[ret_ind].value[0] = L_PARENTHESIS;
            ret[ret_ind].value[1] = '\0';
            ret_ind++;
            i++;
            continue;
          case R_PARENTHESIS:
            ret[ret_ind].id = PARENTHESIS;
            ret[ret_ind].value = malloc(2 * sizeof(char));
            ret[ret_ind].value[0] = R_PARENTHESIS;
            ret[ret_ind].value[1] = '\0';
            ret_ind++;
            i++;
            continue;
          default:
            break;
        }
        break;
    }
    return ret;
}

void deallocate(token *in) {
    int i = 0;
    while (1) {
        free(in[i].value);
        i++;
        if (in[i].id == TERMINAL) {
            break;
        }
    }
    free(in);
    return;
}

chqrlie · Answer 1 · 29 июня 2019

В вашем коде есть несколько проблем:

, если во входной строке нет токенов или синтаксическая ошибка, вы возвращаете ret неинициализированным из tokenize.Вместо этого вы должны вернуть NULL.
ret[ret_ind].value[size + 1] = '\0'; сохраняет нулевой терминатор на один шаг дальше в выделенном массиве.Это должно быть ret[ret_ind].value[size] = '\0';
malloc(size * sizeof(char) + 1) несовместимо: если вы настаиваете на использовании sizeof(char), который по определению равен 1, вы должны написать malloc((size + 1) * sizeof(char)), но использовать * 1017 идиоматично* в C, и вы также можете заменить несколько строк кода на простые ret[ret_ind].value = strndup(string + i, k);
случаи для L_PARENTHESIS и R_PARENTHESIS могут быть объединены в один блок.
цикл освобождения должен прекратиться, когда вы достигнете токена TERMINAL.В текущем коде вы не можете обрабатывать пустой список, который не следует создавать, но лучше сделать функции утилит более устойчивыми к последующим изменениям.
```
void deallocate(token *in) {
    if (in) {
        for (int i = 0; in[i] != TERMINAL; i++)
            free(in[i].value);
        free(in);
    }
}
```
прототипы в token.h должен включать списки типизированных аргументов.

Вот упрощенная версия:

#include <stdio.h>
#include <stdlib.h>

#include "tokenize.h"

int token_count(const char *string) {
    int count = 0;
    int i = 0;
    while (string[i] != '\0') {
        switch (string[i++]) {
          case ' ':
            continue;
          case '0': case '1': case '2': case '3': case '4':
          case '5': case '6': case '7': case '8': case '9':
            i += strspn(string + i, "0123456789");
            continue;
          case ADD:
          case SUBTRACT:
          case MULTIPLY:
          case DIVIDE:
          case EXPONENT:
          case L_PARENTHESIS:
          case R_PARENTHESIS:
            count++;
            continue;
          default:
            return -1;
        }
    }
    return count;
}

token *tokenize(const char *string) {
    int count = token_count(string);
    if (count <= 0)
        return NULL;

    token *ret = malloc((count + 1) * sizeof(token));
    int i = 0;
    int ret_ind = 0;
    while (string[i] != '\0') {
        if (string[i] >= '0' && string[i] <= '9') {
            int size = strspn(string + i, "0123456789");
            ret[ret_ind].id = OPERAND;
            ret[ret_ind].value = strndup(string + i, size);
            ret_ind++;
            i += size;
            continue;
        }
        switch (string[i]) {
          case ' ':
            i++;
            continue;
          case ADD:
          case SUBTRACT:
          case MULTIPLY:
          case DIVIDE:
          case EXPONENT:
            ret[ret_ind].id = OPERATOR;
            ret[ret_ind].value = malloc(2);
            ret[ret_ind].value[0] = string[i];
            ret[ret_ind].value[1] = '\0';
            ret_ind++;
            i++;
            continue;
          case L_PARENTHESIS:
          case R_PARENTHESIS:
            ret[ret_ind].id = PARENTHESIS;
            ret[ret_ind].value = malloc(2);
            ret[ret_ind].value[0] = string[i];
            ret[ret_ind].value[1] = '\0';
            ret_ind++;
            i++;
            continue;
          default:
            break;
        }
        break;
    }
    ret[ret_ind].id = TERMINAL;
    return ret;
}

void deallocate(token *in) {
    if (in) {
        for (int i = 0; in[i] != TERMINAL; i++)
            free(in[i].value);
        free(in);
    }
}

Вот дополнительные замечания для остальныхкод:

зачем очищать экран при входе и выходе?
вы должны проверить конец файла в основном цикле:
```
if (!fgets(user_in, 1024, stdin))
    break;
```
Вы должны эффективно удалить новую строку:
```
#include <string.h>

user_in[strcspn(user_in, "\n")] = '\0';
```
, тогда вы можете упростить тест для выхода:
```
if (!strcmp(user_in, "exit"))
    break;
```
нет необходимости очищать user_in после solve()
вы можете упростить тестирование, решив аргументы командной строки:
```
for (int i = 1; i < argc; i++)
    solve(argv[i]);
```
Вы должны игнорировать пробелы и принимать пустые строки
Вы должны использовать "%.17g вместо %lf.Обратите внимание, что l является обязательным для scanf() для типа double, но игнорируется для printf, поскольку аргументы float преобразуются в double при передаче в функции vararg, такие как printf.
вы должны использовать контекстную структуру и передавать указатель на нее в parse и его вспомогательные функции, чтобы избежать глобальных переменных
, как вы можете видеть вtry_add_sub и try_mul_div, это упростит переключение для унификации типов токенов и позволит избежать классификации OPERATOR.
синтаксический анализатор слишком сложен: вы должны использовать рекурсивное снижение более непосредственно: try_add_sub должен сначала вызвать try_mul_div и перебрать аддитивные операторы, вызывая try_mul_div для каждого последующего операнда.Точно так же, try_mul_div должен сначала вызвать try_exp, а try_exp вызовет try_primitive, который будет обрабатывать скобки и константы.
этот подход потребляет один токен за раз, что можетбыть прочитанным из источника выражений на лету, минуя необходимость токенизации всей строки.
вы должны принять синтаксис полного числа для констант, что легко с strtod().

Вот упрощенная версия по этим направлениям:

//---- tokenize.h ----

#define TERMINAL 0
#define OPERAND 1
#define ERROR 2
#define ADD '+'
#define SUBTRACT '-'
#define MULTIPLY '*'
#define DIVIDE '/'
#define EXPONENT '^'
#define L_PARENTHESIS '('
#define R_PARENTHESIS ')'

#define SYNTAX_ERROR 1
#define PAREN_ERROR 2

typedef struct context {
    char *p;
    char *nextp;
    int parenthesis_balance;
    int error_code;
    double value;
} context;

int this_token(context *cp);
void skip_token(context *cp);

//---- tokenize.c ----

#include <stdlib.h>

//#include "tokenize.h"

int this_token(context *cp) {
    char *p = cp->p;
    for (;;) {
        switch (*p) {
        case '\0':
            cp->nextp = p;
            return TERMINAL;
        case ' ':
        case '\t':
        case '\n':
            /* ignore white space */
            p++;
            continue;
        case ADD:
        case SUBTRACT:
        case MULTIPLY:
        case DIVIDE:
        case EXPONENT:
        case L_PARENTHESIS:
        case R_PARENTHESIS:
            /* single character operators */
            cp->nextp = p + 1;
            return *p;
        default:
            /* try and parse as a number constant */
            cp->value = strtod(p, &cp->nextp);
            if (cp->nextp > p)
                return OPERAND;
            return ERROR;
        }
    }
}

void skip_token(context *cp) {
    cp->p = cp->nextp;
}

//---- parse.h ----

int parse(char expression[], double *result);
void solve(char expression[]);

//---- parse.c ----

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//#include "tokenize.h"
//#include "parse.h"

/* expression parsers return non zero upon error */
int try_add_sub(context *cp, double *result);
int try_mul_div(context *cp, double *result);
int try_exp(context *cp, double *result);
int try_primary(context *cp, double *result);

int try_add_sub(context *cp, double *result) {
    if (try_mul_div(cp, result))
        return 1;
    for (;;) {
        double operand;
        switch (this_token(cp)) {
        case ADD:
            skip_token(cp);
            if (try_mul_div(cp, &operand))
                return 1;
            *result += operand;
            continue;
        case SUBTRACT:
            skip_token(cp);
            if (try_mul_div(cp, &operand))
                return 1;
            *result -= operand;
            continue;
        }
        return 0;
    }
}

int try_mul_div(context *cp, double *result) {
    if (try_exp(cp, result))
        return 1;
    for (;;) {
        double operand;
        switch (this_token(cp)) {
        case MULTIPLY:
            skip_token(cp);
            if (try_exp(cp, &operand))
                return 1;
            *result *= operand;
            continue;
        case DIVIDE:
            skip_token(cp);
            if (try_exp(cp, &operand))
                return 1;
            *result /= operand;
            continue;
        }
        return 0;
    }
}

int try_exp(context *cp, double *result) {
    if (try_primary(cp, result))
        return 1;
    if (this_token(cp) == EXPONENT) {
        double operand;
        skip_token(cp);
        if (try_exp(cp, &operand))
            return 1;
        *result = pow(*result, operand);
    }
    return 0;
}

int try_primary(context *cp, double *result) {
    switch (this_token(cp)) {
    case OPERAND:
        skip_token(cp);
        *result = cp->value;
        return 0;
    case L_PARENTHESIS:
        skip_token(cp);
        cp->parenthesis_balance++;
        if (try_add_sub(cp, result))
            return 1;
        cp->parenthesis_balance--;
        if (this_token(cp) != R_PARENTHESIS) {
            cp->error_code = PAREN_ERROR;
            return 1;
        }
        skip_token(cp);
        return 0;
    }
    cp->error_code = SYNTAX_ERROR;
    return 1;
}

/* parse and evaluate an expression, return error code, update result */
int parse(char expression[], double *result) {
    context cc;
    cc.nextp = cc.p = expression;
    cc.parenthesis_balance = 0;
    cc.error_code = 0;
    cc.value = 0;
    if (try_add_sub(&cc, result))
        return cc.error_code;
    if (this_token(&cc) != TERMINAL)
        return SYNTAX_ERROR;
    return 0;
}

void solve(char expression[]) {
    double result = 0;

    switch (parse(expression, &result)) {
    case 0:
        printf("   %.17g\n", result);
        break;
    case SYNTAX_ERROR:
        printf("ERROR: Syntax\n");
        break;
    case PAREN_ERROR:
        printf("ERROR: Unbalanced parenthesis\n");
        break;
    }
}

//---- calculator.c ----

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//#include "parse.h"

int main(int argc, char **argv) {
    for (int i = 1; i < argc; i++)
        solve(argv[i]);
    if (argc == 1) {
        char user_in[1024];
        char *p;
        printf("Terminal Calculator\n");
        printf("Type 'exit' to terminate\n\n");

        for (;;) {
            printf("=> ");
            if (!fgets(user_in, sizeof user_in, stdin)) {
                printf("\n");
                break;
            }
            /* strip trailing newline */
            user_in[strcspn(user_in, "\n")] = '\0';
            /* skip initial white space */
            p = user_in + strspn(user_in, " \t");
            /* ignore empty and comment lines */
            if (*p == '\0' || *p == '#')
                continue;
            /* trap exit command */
            if (!strcmp(p, "exit"))
                break;
            solve(p);
        }
    }
    return 0;
}

Как использовать free для освобождения выделений кучи, выполненных с помощью malloc?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Как использовать free для освобождения выделений кучи, выполненных с помощью malloc?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы