BISON AST 生产打印乱序值

Question

我正在尝试制作一个简单的解析器。这是为了家庭作业，也是为了自己的实验。我已经完成了词法分析器和解析器，现在正在尝试输出 AST。问题是，例如，当我添加两个整数时，结果树会打印出无法识别的符号。有效输入应为 +(1,1)，有效输出应为 (+ 1 1)。而不是这个，我得到 ( + �|k �|k )。我尝试了很多东西，实际上没有任何显着的结果。 sprintf 函数 returns 是一个空终止符，所以这可能不是问题所在。下面是 parser 代码（.y 文件）：

%{
#define YYDEBUG 1
%}

%start program

%token  NUMBER
%token  ID
%token  PLUS    MINUS   TIMES
%token  LP  RP  EQUALS  COMMA
%token  END

%token  LET IN  AND

%left   PLUS    MINUS
%left   TIMES
%left   LET IN  AND
%left   EQUALS

%%

program:{printf("Empty Input\n");}  /* empty */
        | program line /* do nothing */

line:   expr END        { printtree(); printf("\n");}
    ;

expr    : /*Empty*/
    | LET deflist IN expr {}
    | ID        { printf("Found ID\n"); $$ = make_id_leaf();}
    | NUMBER    { printf("Found NUMBER\n"); $$ = make_number_leaf();}
        | PLUS LP expr COMMA expr RP  {$$ = make_plus_tree(,); printf("Found expr PLUS expr.\n"); }
        | TIMES LP expr COMMA expr RP {$$ = make_times_tree(,); printf("Found expr TIMES expr. Result:%d\n", $$);}
    | MINUS ID
    | MINUS NUMBER     { printf("found MINUS NUMBER\n"); }
        ;

deflist : definition
    | definition AND deflist
    ;

definition : /*Empty*/
       | ID EQUALS expr {printf("Found EQ\n");}
       ;
%%

/*int main (void) {return yyparse ( );}*/

int yyerror (char *s) {fprintf (stderr, "%s\n", s);}

词法分析器 文件：

%{
#include "parser.h"
%}
DIGIT [0-9]
LETTER [a-zA-Z]
%%

LET {printf("Encountered LET\n"); return(LET);}
IN  {printf("Encountered IN\n"); return(IN);}
AND {printf("Encountered AND\n"); return(AND);}
{DIGIT}+    {yylval = atoi(yytext); return NUMBER;}
{LETTER}*       { if (strlen(yytext) <= 8){
                    yylval = strlen(yytext);
            printf( "<ID, %s> ", yytext );
            return(ID);
                  } else {
                        yytext[8] = '[=11=]';
                        printf("WARNING! Long identifier. Truncating to 8 chars\n");
                        printf( "<ID, %s> ", yytext );
            return(ID);
                  }
                }
[ \t] ;
[\n]     return(END); 
"+"      return(PLUS);
"-"      return(MINUS);
"*"      return(TIMES);
"="  return(EQUALS);
"("      return(LP);
")"      return(RP);
","  return(COMMA);
<<EOF>>  return(0);
%%

int yywrap (void) {return 1;}

包含yyparse()函数的main.c：

#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
#include "treedefs.h"

int main(int argc, char **argv){
    yyparse();

    return 0;
}

以及包含函数定义的 treedefs.h 文件（我只包含结构定义、数字叶和加号树）：

typedef struct tree{
    char *token;
    TREE *l;
    TREE *r;
    TREE *child;
}TREE;

/* Make number leaves */

TREE *make_number_leaf(int n){

    TREE *leafNum = malloc(sizeof(TREE));

    char *c, ch[8];
    sprintf(ch, "%d", n); /* Effective way to convert int to string */
    c = ch;
    leafNum->token = c;
    leafNum->l = NULL;
        leafNum->r = NULL;
        leafNum->child = NULL;

    printf("NUM Leaf is: %s\n", leafNum->token);

    return (leafNum);
}

/* Addition tree */

TREE *make_plus_tree(TREE *l, TREE *r){

    TREE *plusTree = malloc(sizeof(TREE));

    plusTree->token = "+";
    plusTree->l = l;
    plusTree->r = r;
    plusTree->child = NULL;

    return (plusTree);

}
void printtree(TREE *tree)
{
    if (tree->l || tree->r){
            printf("(");
    }

    printf(" %s ", tree->token);

    if (tree->l){
        printtree(tree->l);
    }
    if (tree->r){
        printtree(tree->r);
    }
    if (tree->l || tree->r){
        printf(")");
    }
}

文件tree.h只是一些声明，没什么大不了的，绝对与问题无关。

为什么数字看起来像这样？我该如何解决？任何帮助将不胜感激。

Answer 1

这个问题其实跟bison和flex都没有关系。它在您的 make_number_leaf 实现中：

TREE *make_number_leaf(int n){
    TREE *leafNum = malloc(sizeof(TREE));
    char *c, ch[8];
    //       ^ local variable
    sprintf(ch, "%d", n); /* Effective way to convert int to string */
    c = ch;
    leafNum->token = c;
    //               ^ dangling pointer
    // Remainder omitted
 }

如上面的注释所示，ch 是一个局部（堆栈分配）变量，其生命周期在函数 returns 时结束。将其地址分配给变量 c 不会改变它。所以 leafNum->token 中存储的 c 的值一旦函数 returns.

就会变成一个悬空指针

因此，当您稍后尝试打印出令牌时，您正在打印出随机存储器的内容。

您需要 malloc 一个字符缓冲区，并记得在 free 编辑 TREE 时 free 它。（不过，在leafNum->token是字符串字面量的情况下，你不能调用free，所以你需要聪明一点。）

BISON AST 生产打印乱序值

BISON AST production prints scrambled values

c

compiler-construction

bison

abstract-syntax-tree

yacc