解决 Yacc 和 Flex 编译器项目中的错误 |无法从 YACC Grammar 生成 AST

Question

我想显示给定表达式的 AST，下面给出的是我的代码

Lex 文件

%{
    #include "y.tab.h"
    #include "ast.h"
%}

%option yylineno

digit [0-9]
int {digit}+
%%

"(" {return LPAREN;}
")" {return RPAREN;}
"+" {return PLUS;}
"-" {return MINUS;}
"*" {return MULT;}
"/" {return DIV;}
"%" {return MOD;}
"!" {return NOT;}
"&" {return AND;}
"|" {return OR;}
"^" {return XOR;}
{int} {
    yylval.number = atoi(yytext);
    return NUM;
}
"\n" {return TERM;}

%%

int yywrap() {
    return 1;
}

Yacc 文件

%{
    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    #include "lex.yy.c"
    void yyerror(const char *s);
    int yylex();
    int yywrap();
%}

%union{
    ASTNode* ast_node;
    int number;
}

%token LPAREN RPAREN PLUS MINUS
MULT DIV MOD NOT AND OR XOR TERM


%token <number> NUM

%type <ast_node> main
%type <ast_node> calc
%type <ast_node> expr

%left PLUS MINUS
%left MULT DIV MOD
%left AND OR XOR
%right UNARY_MINUS
%right NOT

%%

main: main calc
| calc
;

calc: expr TERM                 {
    $$ = $1;
    // print_ast($$,0); //print the ast
    // free_ast($$); //free the ast
    printf("\n");
}
;

expr: NUM                       {$<ast_node>$ = create_number_node($1);}
| MINUS expr %prec UNARY_MINUS  {$<ast_node>$ = create_unary_op_node('!', $2);}
| NOT expr %prec NOT            {$<ast_node>$ = create_unary_op_node('!', $2);}
| expr PLUS expr                {$<ast_node>$ = create_binary_op_node('+', $1, $3);}
| expr MINUS expr               {$<ast_node>$ = create_binary_op_node('-', $1, $3);}
| expr MULT expr                {$<ast_node>$ = create_binary_op_node('*', $1, $3);}
| expr DIV expr                 {$<ast_node>$ = create_binary_op_node('/', $1, $3);}
| expr MOD expr                 {$<ast_node>$ = create_binary_op_node('%', $1, $3);}
| expr AND expr                 {$<ast_node>$ = create_binary_op_node('&', $1, $3);}
| expr OR expr                  {$<ast_node>$ = create_binary_op_node('|', $1, $3);}
| expr XOR expr                 {$<ast_node>$ = create_binary_op_node('^', $1, $3);}
| LPAREN expr RPAREN            {$<ast_node>$ = $2;}
;

%%

int main(){
    yyparse();
}

void yyerror(const char *msg){
    fprintf(stderr, " [ line: %d ] %s at at token [ '%s' ] \n", yylineno, msg, yytext);
}

ast.h

#ifndef AST_H
#define AST_H

typedef struct ASTNode {
    char type;
    int value;
    struct ASTNode* left;
    struct ASTNode* right;
} ASTNode;

ASTNode* create_unary_op_node(char type, ASTNode* left);
ASTNode* create_binary_op_node(char type, ASTNode* left, ASTNode* right);
ASTNode* create_number_node(int value);
void print_ast(ASTNode* node, int depth);
void free_ast(ASTNode* node);

#endif

ast.c

#include <stdio.h>
#include <stdlib.h>
#include "ast.h"

ASTNode* create_number_node(int value) {
    ASTNode* node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = 'N';
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

ASTNode* create_unary_op_node(char type, ASTNode* left) {
    ASTNode* node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = type;
    node->value = 0;
    node->left = left;
    node->right = NULL;
    return node;
}

ASTNode* create_binary_op_node(char type, ASTNode* left, ASTNode* right) {
    ASTNode* node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = type;
    node->value = 0;
    node->left = left;
    node->right = right;
    return node;
}

void print_ast(ASTNode* node, int depth) {
    if (node == NULL) {
        return;
    }

    // Indent based on the depth in the tree
    for (int i = 0; i < depth; i++) {
        printf("  ");
    }

    if (node != NULL) {
        printf("%c", node->type);
        if ( node->type == 'N') {
            printf("(%d)\n", node->value);
        } else {
            printf("\n");
        }
    } else {
        printf("NULL\n");
    }

    print_ast(node->left, depth + 1);
    print_ast(node->right, depth + 1);
}

void free_ast(ASTNode* node) {
    if (node == NULL) {
        return;
    }
    free_ast(node->left);
    free_ast(node->right);
    free(node);
}

make 返回以下错误

flex -o bin/lex.yy.c src/bas.l
yacc -o bin/y.tab.c -d src/bas.y
cp src/ast.c bin
cp src/ast.h bin
gcc -o bin/bas bin/y.tab.c bin/ast.c -ll
In file included from src/bas.l:2,
                 from src/bas.y:5:
src/bas.y:12:5: error: unknown type name ‘ASTNode’
   12 |     ASTNode* ast_node;
      |     ^~~~~~~
src/bas.y: In function ‘yyparse’:
src/bas.y:46:71: warning: assignment to ‘int *’ from incompatible pointer type ‘ASTNode *’ {aka ‘struct ASTNode *’} [-Wincompatible-pointer-types]
   46 | expr: NUM         {$<ast_node>$ = create_number_node($1);}
      |                                                                       ^
src/bas.y:47:88: warning: passing argument 2 of ‘create_unary_op_node’ from incompatible pointer type [-Wincompatible-pointer-types]
   47 | | MINUS expr %prec UNARY_MINUS {$<ast_node>$ = create_unary_op_node('!', $2);}
      |                                                                                        ^         
      |                                                                                        |
      |                                                                                        int *
In file included from src/bas.l:3,
                 from src/bas.y:5:
bin/ast.h:11:10: note: expected ‘ASTNode *’ {aka ‘struct ASTNode *’} but argument is of type ‘int *’
   11 | ASTNode* create_unary_op_node(char type, ASTNode* left);
      |          ^~~~~~~~~~~~~~~~~~~~
src/bas.y:47:51: warning: assignment to ‘int *’ from incompatible pointer type ‘ASTNode *’ {aka ‘struct ASTNode *’} [-Wincompatible-pointer-types]
   47 | | MINUS expr %prec UNARY_MINUS {$<ast_node>$ = create_unary_op_node('!', $2);}
      |                                                   ^
src/bas.y:48:96: warning: passing argument 2 of ‘create_unary_op_node’ from incompatible pointer type [-Wincompatible-pointer-types]
   48 | | NOT expr %prec NOT   {$<ast_node>$ = create_unary_op_node('!', $2);}
      |                                                                                                ^         
      |                                                                                                |
      |                                                                                                int *
In file included from src/bas.l:3,
                 from src/bas.y:5:
bin/ast.h:11:10: note: expected ‘ASTNode *’ {aka ‘struct ASTNode *’} but argument is of type ‘int *’
   11 | ASTNode* create_unary_op_node(char type, ASTNode* left);

• 我已经检查了ast文件上的数据类型
• 我检查了其他示例，并尝试使用

  $<ast_node>$

  噱头强制类型
• 我不想在这个中使用类型转换指针，因为我相信必须有一种直接的方法来做到这一点，而且我做错了一些事情。

Answer 1

在 %union 声明中用

ASTNode*

替换

struct ASTNode*

不知何故让它工作得很好，但现在我很困惑为什么 typedef 不起作用？