c语言 - 如何使用 free 来释放使用 malloc 进行的堆分配?

Question

我在分词器中使用free()遇到了堆释放的问题。 分词器是递归下降解析计算器的一部分，否则可以完美运行。 但是在合并对释放函数的调用时，它的行为会不稳定。虽然实际上，计算器可能永远不会耗尽其堆，但编写具有内存泄漏的程序只是糟糕的做法。

标记化.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] != '') {
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] != '') {
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] = '';
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] = '';
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] = '';
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] = '';
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;
}

Answer 1

代码中存在多个问题：

• 如果输入行没有标记或语法错误，则从tokenize返回未初始化的ret。您应该改为返回NULL。
• ret[ret_ind].value[size + 1] = '';将空终止符在分配的数组中存储得太远一步。应该是ret[ret_ind].value[size] = '';
• malloc(size * sizeof(char) + 1)不一致：如果你坚持使用sizeof(char)，这是1定义的，你应该写malloc((size + 1) * sizeof(char))，但在C中使用malloc(size + 1)是惯用的，你也可以用一个简单的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] != '') {
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] != '') {
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] = '';
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] = '';
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")] = '';
  

• 然后，您可以简化退出测试：

  if (!strcmp(user_in, "exit"))
  break;
  

• solve()后无需清除user_in

• 您可以通过解决命令行参数来简化测试：

  for (int i = 1; i < argc; i++)
  solve(argv[i]);
  

• 您应该忽略空格并接受空行

• 您应该使用"%.17g而不是%lf。请注意，l是强制性的 对于double类型scanf()，但对于printf忽略，因为float参数在传递给 vararg 时转换为double像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 '':
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("   %.17gn", result);
break;
case SYNTAX_ERROR:
printf("ERROR: Syntaxn");
break;
case PAREN_ERROR:
printf("ERROR: Unbalanced parenthesisn");
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 Calculatorn");
printf("Type 'exit' to terminatenn");
for (;;) {
printf("=> ");
if (!fgets(user_in, sizeof user_in, stdin)) {
printf("n");
break;
}
/* strip trailing newline */
user_in[strcspn(user_in, "n")] = '';
/* skip initial white space */
p = user_in + strspn(user_in, " t");
/* ignore empty and comment lines */
if (*p == '' || *p == '#')
continue;
/* trap exit command */
if (!strcmp(p, "exit"))
break;
solve(p);
}
}
return 0;
}