c - Bison 和 Flex 计算器未正确分配值

Question

我正在按照 Bison 文档示例编写 Bison-Flex 计算器。当我尝试为变量赋值时，当该值不包含其他变量时，它可以正常工作。例如，计算器在此操作后为变量 a 分配正确的值: a = 2 + 3 + 5 。但是，如果我尝试将 a 的值赋给另一个变量 b，例如 b = a + 1，计算器会将 a+1 的值存储在变量 a 中。如果我尝试在 Bison 代码中的赋值规则中打印 $1 的名称，我会在上一个示例中得到，程序将变量 a 获取为 $1，而不是 b。我还尝试启用调试选项，看起来 Bison 正在正确应用规则和减少。

Bison 文件 calculadora_bison.y:

%{
#include <math.h>
#include <stdio.h>
#include <string.h>
#include "TablaSimbolos.h"
int yylex (void);
int yyerror (char *s);
%}

%union {
  float valor;
  NodoArbol * tptr;
};

%token <valor> NUM
%token <tptr> VAR FNCT 
%type <valor> exp

%right '='
%left '-' '+'
%left '*' '/'
%left NEG
%right '^'

%%
input: /* vac´ıo */
    | input line
;
line: '\n'
    | exp '\n' { printf ("\t%.10g\n", $1); }
    | exp ';' '\n' {  }
    | error '\n' { yyerrok; }
;
exp: NUM { $$ = $1;}
    | VAR { $$ = $1->valor.val;}
    | VAR '=' exp { $$ = $3; ActualizaNodoFloat($1->nombre, $3);}
    | FNCT '(' exp ')' { $$ = (*($1->valor.fnctptr))($3);}
    | exp '+' exp { $$ = $1 + $3; }
    | exp '-' exp { $$ = $1 - $3; }
    | exp '*' exp { $$ = $1 * $3; }
    | exp '/' exp { $$ = $1 / $3; }
    | '-' exp %prec NEG { $$ = -$2; }
    | exp '^' exp { $$ = pow ($1, $3); }
    | '(' exp ')' { $$ = $2; }
;
%%

struct init{
    char *fname;
    double (*fnct)();
};

struct init arith_fncts[] =
{
  { "atan", atan },
  { "cos",  cos  },
  { "exp",  exp  },
  { "ln",   log  },
  { "sin",  sin  },
  { "sqrt", sqrt },
  { 0, 0 },
};

int init_table(){
    int i;

    CrearArbol();

    for (i = 0; arith_fncts[i].fname != 0; i++){
        InsertarNodoFuncion(FNCT, arith_fncts[i].fname, arith_fncts[i].fnct);
    }

    return 0;
}

int main (){
    init_table ();
    yyparse ();
    return 0;
}

int yyerror (char *s){
    printf ("%s\n", s);
    return 0;
}

我的 Flex 代码，calculatora_flex.l:

%{
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "TablaSimbolos.h"
#include "calculadora_bison.tab.h"    

%}

ALNUM  [a-zA-Z][a-zA-Z0-9]*
DIGITO [0-9]*
FLOAT {DIGITO}*\.{DIGITO}*
OPERADORES [-+()=*^/\n;]

%%

{ALNUM} {
        NodoArbol s;
        s = buscaTS(yytext);                
        yylval.tptr = &s;
        return s.tipo;
        }

{FLOAT} {
        yylval.valor = atof(yytext);
        return NUM;
        }

{DIGITO} {      
        yylval.valor = atoi(yytext);
        return NUM;
        }

{OPERADORES} {          
            return (int)yytext[0];
            }


. { };

%%

对于符号表，我在 C 中使用 BST。头文件是这样的:

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

typedef struct NodoArbolType{
        int tipo; //Componente léxico
        char * nombre; // Lexema
        union {
            float val; 
            double (*fnctptr)();
        } valor;
        struct NodoArbolType *izda; //Nodos hijo
        struct NodoArbolType *dcha;
    }NodoArbol;

void ActualizaNodoFloat(char * nombrenodo, float valor);

void CrearArbol();

NodoArbol BuscarArbol(char * nombre);

NodoArbol buscaTS(char * nombre);

int InsertarNodoEntero(NodoArbol *newNode);

NodoArbol InsertarNodo(int Key, char * cA);

int InsertarNodoFloat(int Key, char * cA, float val);

int InsertarNodoFuncion(int Key, char * cA, double (*fnct)());

void EliminarArbol();

void ImprimirArbol90grados();

void ImprimirArbolConValores();

int EliminarNodo(char * nombre);

.c 文件:

#include "TablaSimbolos.h"
#include "calculadora_bison.tab.h"
//Declaramos el nodo como estático para que solo pueda ser accedido desde aquí
static NodoArbol *raiz;

/**
 * Función que limpia recursivamente a partir de un nodo
 */
static void LimpiarArbol(NodoArbol *T){
    if(T==NULL) return; 
    if(T->izda != NULL) LimpiarArbol(T->izda); //Si sus hijos no son NULL, también
                                               //se limpian
    if(T->dcha != NULL) LimpiarArbol(T->dcha); 
    free(T); //Libera la memoria del puntero al nodo
    return;
}


/*
 * Función que crea un árbol a partir del nodo raíz
 */
void CrearArbol(){
    LimpiarArbol(raiz); //Primero libera el nodo raíz por si existía un árbol previo
    raiz = NULL;
    return;
}

/**
 * Función que determina si un árbol no tiene ningún nodo 
 */
int esVacio(){
    return(raiz==NULL);
}

/*
 * Función que busca en un árbol un nodo a partir de un string que correspondería
 * al campo nombre de los nodos
 */
NodoArbol BuscarArbol(char * nombre){
    NodoArbol *temp;

    temp = raiz; //Puntero auxiliar

    //Mientras temp no sea NULL (haya llegado al final del árbol) o no se 
    //encuentre el string nombre
    while((temp != NULL) && (strcmp(nombre, temp->nombre)!=0)){        
        if(strcmp(nombre, temp->nombre)<0) //Si el string es "menor" que el 
                                        //nombre del nodo a examinar (por ejemplo
                                        // function<while), sigue examinando por
                                        //el nodo hijo izquierdo
            temp = temp->izda;  
        else if(strcmp(nombre, temp->nombre)>0) //Análogamente al caso anterior
                                        //pero cuando sea mayor
            temp = temp->dcha;        
    }
    if(temp == NULL){ //Si el nombre no se ha encontrado, devuelve error
        temp = (NodoArbol *)malloc(sizeof(NodoArbol));
        temp->tipo = -1;
    }
    return(*temp);
}

/**
 * Función que inserta un NodoArbol en el árbol
 */
int InsertarNodoEntero(NodoArbol *nuevoNodo){
    NodoArbol *temp;
    NodoArbol *anterior;

    temp = raiz;
    anterior = NULL;

    //Busca la posición en la que se insertará el nodo
    while((temp != NULL) && (strcmp(nuevoNodo->nombre, temp->nombre)!=0)){
        anterior = temp;
        if(strcmp(nuevoNodo->nombre, temp->nombre)<0)
            temp = temp->izda;
        else if(strcmp(nuevoNodo->nombre, temp->nombre)>0)
            temp = temp->dcha;
    }

    //Añadimos el nodo al árbol
    if(anterior == NULL) //Si anterior==NULL, el nodo es el primero en introducirse
        raiz = nuevoNodo;

    else {
        //Si el nombre de nuevoNodo < anterior->nombre, lo introducimos a la izquierda
        if(strcmp(nuevoNodo->nombre, anterior->nombre)<0)
            anterior->izda = nuevoNodo;
        //En el caso contrario, lo introducimos a la izquierda
        else if(strcmp(nuevoNodo->nombre, anterior->nombre)>0)
            anterior->dcha = nuevoNodo;
    }
   return(nuevoNodo->tipo);
}

/**
 * Función que inserta un nodo en el árbol a partir de su valor y su nombre
 */
NodoArbol InsertarNodo(int valor, char *cA){
    NodoArbol *nuevoNodo;

    nuevoNodo = (NodoArbol *)malloc(sizeof(NodoArbol));
    nuevoNodo->tipo = valor;    
    nuevoNodo->nombre = (char*)malloc(sizeof(char) * strlen(cA));    
    strcpy(nuevoNodo->nombre, cA);
    nuevoNodo->valor.val=0;
    nuevoNodo->izda = nuevoNodo->dcha = NULL;
    InsertarNodoEntero(nuevoNodo);
    return(*nuevoNodo);
}

int InsertarNodoFloat(int Key, char * cA, float val){
    NodoArbol *nuevoNodo;

    nuevoNodo = (NodoArbol *)malloc(sizeof(NodoArbol));
    nuevoNodo->tipo = Key;
    nuevoNodo->valor.val = val;
    nuevoNodo->nombre = (char*)malloc(sizeof(char) * strlen(cA));    
    strcpy(nuevoNodo->nombre, cA);
    nuevoNodo->izda = nuevoNodo->dcha = NULL;    
    return(InsertarNodoEntero(nuevoNodo));
}

int InsertarNodoFuncion(int Key, char * cA, double (*fnct)()){
    NodoArbol *nuevoNodo;

    nuevoNodo = (NodoArbol *)malloc(sizeof(NodoArbol));
    nuevoNodo->tipo = Key;
    nuevoNodo->valor.fnctptr = fnct;
    nuevoNodo->nombre = (char*)malloc(sizeof(char) * strlen(cA));    
    strcpy(nuevoNodo->nombre, cA);
    nuevoNodo->izda = nuevoNodo->dcha = NULL;    
    return(InsertarNodoEntero(nuevoNodo));    
}

/*
 * Función que busca un nodo a partir del nombre y devuelve su valor. Si no lo
 * encuentra, inserta el nodo y devuelve el valor del nuevo nodo.
 */

NodoArbol buscaTS(char * nombre){
    NodoArbol id;   
    id=BuscarArbol(nombre);   
    if(id.tipo==-1){
        id=InsertarNodo(VAR, nombre);
    }    
    return id;
}

void ActualizaNodoFloat(char * nombreNodo, float valor){
    //printf("en actualizarNodoFloat, nombreNodo = %s \n", nombreNodo);

    EliminarNodo(nombreNodo);
    InsertarNodoFloat(VAR, nombreNodo, valor);

    //NodoArbol nodo = BuscarArbol(nombreNodo);
    //printf("en buscar dentro de actualizaNodo%f", nodo.valor.val);
}


/*
 * Función que elimina un árbol desde la raíz, liberando la memoria ocupada por él
 */
void EliminarArbol(){
    LimpiarArbol(raiz);
}

void ImprimirNodoConValores(NodoArbol * nodo){
    if(nodo->izda!=NULL){
        ImprimirNodoConValores(nodo->izda);
    }
    printf("%d - %s", nodo->tipo, nodo->nombre);
    if(nodo->tipo==VAR){
        printf(" --> %f \n", nodo->valor.val);
    }else{
        printf("\n");
    }
    if(nodo->dcha!=NULL){
        ImprimirNodoConValores(nodo->dcha);
    }
}

void ImprimirArbolConValores(){
    ImprimirNodoConValores(raiz);
}

int EliminarNodo(char * nombre){
    NodoArbol * anterior;
    NodoArbol *temp;
    NodoArbol *delParent;    // Parent of node to delete
    NodoArbol *delNode;      // Node to delete

    temp = raiz;
    anterior = NULL;

    //Encontramos el nodo a eliminar
    while((temp != NULL) && (strcmp(temp->nombre, nombre)!=0)){
        anterior = temp;
        if(strcmp(nombre, temp->nombre)<0)
            temp = temp->izda;
        else if(strcmp(nombre, temp->nombre)>0)
            temp = temp->dcha;
    }

    if(temp == NULL){ // No se encontró el nodo    
        printf("Key not found. Nothing deleted. El nombre es %s\n", nombre);
        return 0;
    }else{
        if(temp == raiz){ //Eliminamos la raíz
            delNode = raiz;
            delParent = NULL; 
        }else{
            delNode = temp;
            delParent = anterior;
        }
    }

    // Case 1: Deleting node with no children or one child 
    if(delNode->dcha == NULL){
        if(delParent == NULL)    // If deleting the root    
        {
            raiz = delNode->izda;
            free(delNode);
            return 1;
        }
        else
        {
            if(delParent->izda == delNode)
                delParent->izda = delNode->izda;
            else
                delParent->dcha = delNode->izda;
            free(delNode);
            return 1;
        }
    }
    else // There is at least one child 
    {
        if(delNode->izda == NULL)    // Only 1 child and it is on the right
        {
            if(delParent == NULL)    // If deleting the root    
            {
                raiz = delNode->dcha;
                free(delNode);
                return 1;
            }
            else
            {
                if(delParent->izda == delNode)
                    delParent->izda = delNode->dcha;
                else
                    delParent->dcha = delNode->dcha;
                free(delNode);
                return 1;
            }
        }
        else // Case 2: Deleting node with two children 
        {                          
            temp = delNode->izda;
            anterior = delNode;
            while(temp->dcha != NULL)
            {
                anterior = temp;
                temp = temp->dcha;
            }
            // Copy the replacement values into the node to be deleted 
            delNode->tipo = temp->tipo;
            strcpy(delNode->nombre, temp->nombre);

            // Remove the replacement node from the tree 
            if(anterior == delNode)
                anterior->izda = temp->izda;
            else
                anterior->dcha = temp->izda;
            free(temp);
            return 1;
        }
    }
}

Answer 1

这确实与 bison 或 flex 没有什么关系。

最后一个问题就在这里，在 {ALNUM} 的弹性操作中；特别是突出显示的行:

{ALNUM} {
        NodoArbol s;
        s = buscaTS(yytext);                
        <b>yylval.tptr = &s;</b>
        return s.tipo;
        }

此时，s 是一个局部变量(代码块的局部变量)，这意味着它的生命周期以 return 语句结束。因此，分配给 yylval.tptr 的地址是一个悬空指针，它指向的内容是完全不可预测的。 (这是未定义的行为，因此后果可能更加严重。)

但是，实际上，buscaTS 返回整个 NodoArbol 的副本有点奇怪。通常，二叉树查找将返回一个指向树节点的指针，因为二叉搜索树节点没有理由移动。

不幸的是，在您的设计中，节点确实会移动，因为当您修改与符号关联的值时，您会删除符号的节点，然后重新创建它，而不是仅仅更改关联的值。 IMO，这是完全没有必要的，而且效率非常低，而且它也使得符号表的设计变得更加困难。如果您更改它，则只需从 BuscarArbol(因此从 BuscaTS)返回节点的地址，然后您可以使用返回的指针来更新值在必要的情况下使用符号。

在查看您的代码时我注意到其他一些事情:

1. 当 BuscarArbol 找不到符号时，它会 malloc 一个新节点，然后返回该节点的副本。新分配的节点永远不会进入树中，也永远不会被释放。如果您将 BuscarArbol 更改为返回指针，它可能会将指针返回到新分配的节点，从而使调用者负责将节点插入树中或释放它。或者它可以只返回 NULL，而不是伪造类型为 -1 的节点。 (这是我的偏好，FWIW。)

2. 插入新节点的各种方式存在大量代码重复。我建议有一个例程，它接受一个名称并插入一个具有该名称的新节点，然后返回指向新节点的指针。然后调用者可以修复符号类型和值。

3. 此外，当您创建一个具有名称的新节点时，您可以像这样复制名称:

   nuevoNodo->nombre = (char*)malloc(sizeof(char) * strlen(cA));    
   strcpy(nuevoNodo->nombre, cA);
   

   这是缓冲区溢出，因为 C 中的字符串以 NUL 结尾，因此需要比字符串长度多一个字节。因此，strcpy 将覆盖分配结束后的字节，这是未定义的行为。

这就是我注意到的。我没有详细检查代码。