4

C でバイナリ ツリーをトラバースしようとしています。ツリーには AST ノード (コンパイラの抽象構文ツリー ノード) が含まれています。ASTnode は、指定されたノードのタイプを指定する nodetype を予約します (つまり、INT OP または CHAR と TYPE は他のタイプに関係する必要はありません)。他のメンバーは左右のポインターであり、最後に保存します。

トラバースのコードは次のとおりです。

    void traverse(struct ASTNode *root)
    {
        if(root->nodeType == OP){
            printf("OP \n");
            if(root->left != NULL){
              printf("left - ");
              traverse(root->left);
            }
            if(root->right != NULL){
              printf("right - ");
              traverse(root->right);
            }
            return;
        }
        else{
            if(root != NULL && root->nodeType == INT)
            {
              printf("INT - ");
              printf("INT: %d\n",root->value);
            }
            if(root != NULL && root->nodeType == CHAR)
            {
              printf("CHAR - ");
              printf("CHAR: %c\n",root->chValue);
            }
            return;
        }
    }

また、AST では定数値に余分な値が含まれないため、CONSTANT ノードに左または右の値を割り当てることはできません。

更新しました：

問題は私のメインコールにあります:

    int main()
    {
        struct ASTNode *node1 = makeCharNode('a');
        struct ASTNode *node2 = makeCharNode('b');
        struct ASTNode *node10 = makeCharNode('c');
        struct ASTNode *node3 = makeINTNode(19);

        struct decl *d = (struct decl*) malloc(sizeof(struct decl*));
        struct decl *d2 = (struct decl*) malloc(sizeof(struct decl*));

        struct ASTNode *node4 = makeNode(3,d,node3,node2);
        struct ASTNode *node5 = makeNode(3,d2,node4,node1); !!
        traverse(node4);
    }

ノード 5 (!! でマークされている) を削除すると、コードは非常にうまく機能します。そうしないと、セグメンテーション エラーが発生します。

で動作する関数makenode:

    struct ASTNode *makeNode(int opType,struct decl *resultType,struct ASTNode *left,struct ASTNode *right)
    {
        struct ASTNode *node= (struct ASTNode *) malloc(sizeof(struct ASTNode *));
        node->nodeType = opType;
        node->resultType = resultType;
        node->left = left;
        node->right = right;
        return node;
    }

    struct ASTNode *makeINTNode(int value)
    {
        struct ASTNode *intnode= (struct ASTNode *) malloc(sizeof(struct ASTNode *));
        intnode->nodeType = INT;
        intnode->value = value;
        return intnode;
    }

    struct ASTNode *makeCharNode(char chValue)
    {
        struct ASTNode *charNode = (struct ASTNode *) malloc(sizeof(struct ASTNode *));
        charNode->nodeType = CHAR;
        charNode->chValue = chValue;
        return charNode;
    }
4

6 に答える 6

11

あなたのmallocは間違っています

 struct decl *d = (struct decl*) malloc(sizeof(struct decl*));
 struct decl *d2 = (struct decl*) malloc(sizeof(struct decl*));

する必要があります

 struct decl *d = (struct decl*) malloc(sizeof(struct decl));
 struct decl *d2 = (struct decl*) malloc(sizeof(struct decl));

（またはsizeof（struct decl）の代わりにsizeof * dを使用します）。Cでは、mallocの戻り値をキャストする必要はありません。

また、メンバーにアクセスする前に、メンバーをNULLまたは別のデフォルト値に設定していることを確認してください。mallocはそれらを0/NULLに設定しません。

于 2009-12-26T16:24:10.253 に答える
1

makeNode関数は、構造体のすべてのメンバーを初期化する必要があります。おそらく、左/右ポインタの1つをNULLに設定していませんか？malloc（）呼び出しは、メモリをゼロにしません。

Ack-私は盲目です。nosによる答えは正しいものです。不正なmalloc呼び出し。私はただノイズを追加していました。

于 2009-12-26T16:20:14.583 に答える
1

コードは、traverse（）に渡された最初のNULLノードでセグメンテーション違反を起こします。

root != NULLelseブロック内をチェックするように注意しますが、それまでにすでに参照を解除しています。NULLポインターを逆参照しようとすると、セグメンテーション違反が発生します。

追加してみてください

if (!root) return;

あなたの最初の行として。

于 2009-12-26T16:20:35.363 に答える
1

root->value私が見ることができるのは、printfに渡す前に他をチェックしたいと思うかもしれないということだけです。

また、これによってバグが発生することはありませんが、変更することをお勧めします

if(root != NULL && root->nodeType == CHAR)

に

else if(root != NULL && root->nodeType == CHAR)

編集：待ってください、ここに何かがあります-root->leftトラバースに渡すとき、それは値自体ですか、それともポインタですか？この関数はポインターを必要とします。

于 2009-12-26T16:16:30.643 に答える
1

最初の「if」ブロックで「root」がNULLかどうかを確認していません。一番簡単なのはラップすることだと思います

if(root != NULL)

INTノードとCHARノードを出力するときに、全体（最終的な戻り値を除く）を回避し、個別の「root！=NULL」チェックを取り除きます。

共有してお楽しみください。

編集：これが私が意味することです：

void traverse(struct ASTNode *root) 
  { 
  if(root != NULL)
    {
    switch(root->nodeType)
      {
      case OP:
        printf("OP \n"); 

        if(root->left != NULL)
          { 
          printf("left - "); 
          traverse(root->left); 
          } 

        if(root->right != NULL)
          { 
          printf("right - "); 
          traverse(root->right); 
          } 
        break;

      case INT:
        printf("INT - "); 
        printf("INT: %d\n",root->value);
        break;

      case CHAR:
        printf("CHAR - "); 
        printf("CHAR: %c\n",root->chValue); 
      }
    } 
  }

また、ifの束の代わりにスイッチを使用するように変更されました。

構文エラーを許してください。これは私の頭から離れており、コンパイラーは便利ではありません。

于 2009-12-26T16:19:39.093 に答える
1

struct decl' ' ポインターを割り当てるコードを示します。それらを初期化するコードは表示しません。makeNode() が 2 番目の引数を初期化する理由、またはどのように初期化するかは明らかではありません。また、3 が何を意味するのかは明らかではありません。また、「 」がどのようstruct declに AST ノードに統合されるかも明らかではありません。

例外的なケースを早期に処理することで、traverse() を単純化できます。

void traverse(struct ASTNode *root)
{
  if (root == NULL)  // Or: assert(root != NULL);
    return;
  if (root->nodeType == OP)
  {
    printf("OP \n");
    if (root->left != NULL)
    {
      printf("left - ");
      traverse(root->left);
    }
    if (root->right != NULL)
    {
      printf("right - ");
      traverse(root->right);
    }
  }
  else if (root->nodeType == INT)
  {
    printf("INT - ");
    printf("INT: %d\n", root->value);    
  }
  else if (root->nodeType == CHAR)
  {   
    printf("CHAR - ");
    printf("CHAR: %c\n", root->chValue);
  }
  else
    assert("Unrecognized nodeType" == 0);
}

これは、不可能なケース (認識されないノード タイプ) にも対処します。また、null ポインターが渡された場合でも、クラッシュしたり燃えたりしません。

ただし、これでは、追加の ASTnode に応じてコードがクラッシュする理由とクラッシュしない理由をまだ説明できません...なぜそれが発生するのかを確認するのに十分なコードがあるとは確信していません。すべてのノード (node1、node2、node3、node10) をトラバースしてみましたか? makeCharNode() および makeINTNode() 関数が正常に機能する場合、これらは問題ないはずですが、このような初歩的なチェックで問題を解決できます。makeNode() 関数が何をするかを確認すると役立つ場合があります。ノードのすべての部分が適切に初期化されていることを確認しますか。

于 2009-12-26T16:41:55.333 に答える