印刷抽象语法树，无限递归问题 [英] Printing Abstract Syntax Tree, infinite recursion issue

问题描述

有关在我的C编程类项目的最后，我们正在实施一个逆波兰式计算器，它可以评估的正确性一名前pression，返回相应的缀前pression，或打印出模拟装配$ C $℃。要做到这一点，我们要同时实现栈和抽象语法树。

For the final project in my C programming class, we are implementing a reverse polish notation calculator which can either evaluate an expression for correctness, return the corresponding infix expression, or print out mock assembly code. To do so, we are to implement both a stack and a Abstract Syntax Tree.

struct snode /*stack data structure */
{
  int datum;
  struct snode* bottom;
};

struct tnode /*tree data structure */
{
  int datum;
  struct tnode* left;
  struct tnode* right;
};

目前，我设计我的程序从标准输入读取，并把元素入栈，然后使用该协议栈来创建一个抽象语法树稍后可用于评估前pression。对于现在，我还没有把任何检查呢，我只是想先建立一个AST。

Currently, I've designed my program to read from stdin and put the elements onto a stack, then to use that stack to create a Abstract Syntax Tree which can later be used to evaluate the expression. For right now, I haven't put in any checks yet, I'm just trying to build a AST first.

下面是我的大部分主要功能。对于现在，还没有检查，以确保给定的公式是正确的。

Below is the majority of my main function. For right now, there are no checks to ensure that the given equation is correct.

int i = 1;


struct snode *stack;
stack = push(stack, -999); /* Here I set what will be the "empty" value of my stack. There's better ways to do it, but this is how I did it for a previous lab and it tended to cause less issues for me when I check if my stack is empty at the end */

struct tnode *AST;
AST = (struct tnode*)malloc(sizeof(struct tnode));
AST->datum = -7062; /*same thing as with stack, this is just a place holder that will be over written. */
AST->right = NULL;
AST -> left = NULL;

struct tnode* tmp;
tmp = (struct tnode*)malloc(sizeof(struct tnode));
tmp -> datum = -7062;
tmp -> right = NULL;
tmp -> left = NULL;

/*Operators are given as letters instead of +,-, etc. */
char *addition = "A"
char *subtraction = "S";
char *multiplication = "X";
char *division = "D"
char *mod = "M";

while(argv[i] !=NULL){
    if(isdigit(unsignedchar)argv[i][0])){
      stack = push(stack, atol(argv[i]));
   }else{ /* In the final code, a strcmp will check to see if argv[i] is one of the above A,S,X,D, or M arguments. For right now, it just fires if it's not a digit for my testing. */
       if(AST->datum == -7062){ /*if this is the first time we're running it*/
         AST->datum = atol(argv[i]);
         AST->right = create_node(stack->datum);
         stack = pop(stack);
         AST -> left = create_node(stack->datum);
         stack = pop(stack); /* I pop the top off the stack twice to get the 2 integers it stores. I know it will for the current testing, checks will be in place later */
       }else{ /* if AST already has elements in it. */
         tmp = AST;
         tmp -> left = tmp-> right = NULL;
         AST->datum = atol(argv[i]);
         AST->right = create_node(stack->datum);
         stack = pop(stack);
         AST->left = tmp; /*This puts the new operator as the root of the tree, the old tree as the left child of that root, and the right child as the integer stored on stack.*/
         }
     }
  i++;
  }

print_table(AST); /*Should print the AST */
}

create_node分配空间和存储什么的给它。

create_node allocates space and stores what's given to it.

struct tnode*
create_node(int x){
  struct tnode* tmp;
  tmp = (struct tnode*)malloc(sizeof(struct tnode))
  tmp->datum = x;
  tmp->right = NULL;
  tmp->left = NULL;
  return tmp;
}

PRINT_TABLE递归地打印出抽象语法树。

print_table recursively prints the Abstract Syntax Tree.

void
print_table(struct tnode *AST){
    if(AST !=NULL){
        print_table(AST->left);
        printf("%d ", AST->datum);
        print_table(AST->right);
      }
  }

现在目前，如果下面给出：/ rpcalc 5 4一
然后程序将返回5 0 4，我明白为什么一个正在恢复为0，所以这部分工作如预期。
然而，当我试着给该程序/ rpcalc 5 4 3×，这是（5 + 4）* 3，冻结了一会儿，然后返回分段错误。

Now currently, if the following is given: /rpcalc 5 4 A Then the program will return 5 0 4. I understand why the A is returning as a 0, so this part is working as intended. However, when I try to give the program /rpcalc 5 4 A 3 X, which is (5+4)*3, it freezes for a moment and then returns a Segmentation Fault.

使用多个printf的语句，我已经分离出的问题倒在PRINT_TABLE函数的递归。出于某种原因，AST->左不似乎到达NULL指针终止程序，使其无限运行，直到程序崩溃。我不知道是什么导致这，不幸的是，直到我解决这个问题我真的不能继续往前走与我的项目。

Using several printf statements, I have isolated the issue down to the recursion in the print_table function. For some reason, the AST->left does not appear to be reaching the NULL pointer to terminate the program, causing it to run infinitely until the program crashes. I'm not sure what's causing this, and unfortunately until I fix it I can't really continue any farther with my project..

推荐答案

让我们开始正中：

       }else{ /* if AST already has elements in it. */
         tmp = AST;
         tmp -> left = tmp-> right = NULL;
         AST->datum = atol(argv[i]);
         AST->right = create_node(stack->datum);
         stack = pop(stack);
         AST->left = tmp; /*This puts the new operator as the root of the tree, the old tree as the left child of that root, and the right child as the integer stored on stack.*/
         }
     }
  i++;
  }

这是不好的。您可以设置 TMP = AST ，那么 tmp-＆GT;左和 tmp-＆GT;右到 NULL ，但也的套 AST-＆GT;左和 AST-＆GT;右到 NULL ，因为它们指向同一个东西！后来，您可以设置 AST-＆GT;左= TMP ，它创建了一个循环，因为再次， AST 和 TMP 指向同一个东西，所以它相当于 AST-＆GT;左= AST 。递归到 AST-方式＆gt;左因此，无限的血统，又名堆栈溢出

This is bad. You set tmp = AST, then tmp->left and tmp->right to NULL, but that also sets AST->left and AST->right to NULL, since they point to the same thing! Later on, you set AST->left = tmp, which creates a cycle, since again, AST and tmp point to the same thing, so it is equivalent to AST->left = AST. Recursing into AST->left is therefore infinite descent, AKA stack overflow.

这篇关于印刷抽象语法树，无限递归问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！