I'm working on a project where I'm using Bison to generate a parser and Flex to generate a lexer. My parser is meant to generate an Abstract Syntax Tree (AST), and I've defined the ASTNode structure within my Bison file. However, I keep encountering the following error:
In file included from lexer.l:5:0:
parser.y:39:5: error: unknown type name 'ASTNode'
ASTNode *astNode; // Add ASTNode pointer for expression and other nodes
This is my current parser file, parser.y
:
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
extern FILE *yyin;
extern FILE *yyout;
void yyerror(const char *s);
// Define NodeType enumeration for AST node types
typedef enum { NODE_VAR, NODE_ICONST, NODE_ADD, NODE_SUB, NODE_MUL, NODE_DIV } NodeType;
// Define the structure for AST nodes
typedef struct ASTNode {
NodeType type;
union {
char *sval; // for variables
int ival; // for integer constants
struct {
struct ASTNode *left;
struct ASTNode *right;
} binary; // for binary operations
} data;
} ASTNode;
// Function prototypes for creating AST nodes
ASTNode* createVarNode(char *name);
ASTNode* createIntNode(int value);
ASTNode* createBinaryNode(NodeType type, ASTNode *left, ASTNode *right);
void printAST(ASTNode *node);
%}
// Union for semantic values
%union {
int ival;
char *sval;
ASTNode *astNode; // Add ASTNode pointer for expression and other nodes
}
%token <sval> VAR
%token <ival> ICONST
%token EQUOP ADDOP SUBOP MULOP DIVOP LPAREN RPAREN
%type <astNode> program expression expression_suffix term term_suffix factor
%start program
%%
// Rules of the grammar
program:
VAR EQUOP expression {
printf("Parsed program: %s = <expression>\n", $1);
free($1); // Free the variable name after use
$$ = $3; // Set the result of the program to the expression
}
;
expression:
term expression_suffix {
printf("Parsed expression\n");
}
;
expression_suffix:
ADDOP term expression_suffix {
printf("Parsed ADDOP\n");
}
| SUBOP term expression_suffix {
printf("Parsed SUBOP\n");
}
| /* empty */ {
}
;
term:
factor term_suffix {
$$ = $1; // Assign the factor to the term result
printf("Parsed term\n");
}
;
term_suffix:
MULOP factor term_suffix {
printf("Parsed MULOP\n");
}
| DIVOP factor term_suffix {
printf("Parsed DIVOP\n");
}
| /* empty */ {
}
;
factor:
LPAREN expression RPAREN {
$$ = $2; // The result is the expression inside the parentheses
printf("Parsed factor: (expression)\n");
printAST($$); // Print the AST for the expression inside the parentheses
}
| ICONST {
$$ = createIntNode($1); // Create an integer node
printf("Parsed ICONST: %d\n", $1);
}
| VAR {
$$ = createVarNode($1); // Create a variable node
printf("Parsed VAR: %s\n", $1);
}
;
%%
void yyerror(const char *s) {
fprintf(stderr, "Error: %s\n", s);
}
// Function definitions for AST creation and printing
ASTNode* createVarNode(char *name) {
ASTNode *node = malloc(sizeof(ASTNode));
node->type = NODE_VAR;
node->data.sval = strdup(name);
return node;
}
ASTNode* createIntNode(int value) {
ASTNode *node = malloc(sizeof(ASTNode));
node->type = NODE_ICONST;
node->data.ival = value;
return node;
}
ASTNode* createBinaryNode(NodeType type, ASTNode *left, ASTNode *right) {
ASTNode *node = malloc(sizeof(ASTNode));
node->type = type;
node->data.binary.left = left;
node->data.binary.right = right;
return node;
}
void printAST(ASTNode *node) {
if (!node) return;
switch (node->type) {
case NODE_VAR:
printf("VAR(%s)\n", node->data.sval);
break;
case NODE_ICONST:
printf("ICONST(%d)\n", node->data.ival);
break;
case NODE_ADD:
printf("ADD\n");
printAST(node->data.binary.left);
printAST(node->data.binary.right);
break;
case NODE_SUB:
printf("SUB\n");
printAST(node->data.binary.left);
printAST(node->data.binary.right);
break;
case NODE_MUL:
printf("MUL\n");
printAST(node->data.binary.left);
printAST(node->data.binary.right);
break;
case NODE_DIV:
printf("DIV\n");
printAST(node->data.binary.left);
printAST(node->data.binary.right);
break;
}
}
int main() {
yyin = fopen("input.txt", "r");
if (!yyin) {
perror("Failed to open input file");
return 1;
}
yyout = fopen("lexicalOutput.txt", "w");
if (!yyout) {
perror("Failed to open output file");
fclose(yyin);
return 1;
}
yyparse();
fclose(yyin);
fclose(yyout);
return 0; // Add return statement at the end
}
And this is my current lexer file, lexer.l
:
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "parser.tab.h"
extern int yylex();
%}
/* Lexical analyzer rules */
%%
[ \t]+ ; /* Ignore whitespace */
[0-9]+ {
yylval.ival = atoi(yytext);
fprintf(yyout, "Read ICONST: %d\n", yylval.ival);
return ICONST;
}
[a-zA-Z_][a-zA-Z0-9_]* {
yylval.sval = strdup(yytext);
fprintf(yyout, "Read VAR: %s\n", yylval.sval);
return VAR;
}
"=" { fprintf(yyout, "Read =\n"); return EQUOP; }
"+" { fprintf(yyout, "Read +\n"); return ADDOP; }
"-" { fprintf(yyout, "Read -\n"); return SUBOP; }
"*" { fprintf(yyout, "Read *\n"); return MULOP; }
"/" { fprintf(yyout, "Read /\n"); return DIVOP; }
"(" { fprintf(yyout, "Read (\n"); return LPAREN; }
")" { fprintf(yyout, "Read )\n"); return RPAREN; }
. { /* Ignore unrecognized characters */ }
%%
int yywrap(void) {
return 1;
}
I believe the error is occurring because the lexer isn't recognizing the ASTNode type from my Bison file, but I'm not sure how to resolve it as I have the AST node defined before specifying it as a type.
Command line commands to compile the lexer and bison file:
$ bison -d parser.y
$ flex lexer.l
$ gcc -o myparser parser.tab.c lex.yy.c
[produces error shown above]
The cause of the error message is that the generated parser.tab.h
file
does not contain the definition of ASTNode
. You can open that file
yourself after running bison
to see that. (The main thing in the
generated .tab.h
file is enum yytokentype
, which allows the lexer to
know the token codes that bison
has chosen.) Consequently, when the
compiler tries to compile lex.yy.c
, the definition of ASTNode
is not
available.
To fix this, you need to put the defintion of ASTNode
into its own
file and #include
it in both parser.y
and lexer.l
.
For example, create astnode.h
:
#ifndef ASTNODE_H
#define ASTNODE_H
// Define NodeType enumeration for AST node types
typedef enum { NODE_VAR, NODE_ICONST, NODE_ADD, NODE_SUB, NODE_MUL, NODE_DIV } NodeType;
// Define the structure for AST nodes
typedef struct ASTNode {
NodeType type;
union {
char *sval; // for variables
int ival; // for integer constants
struct {
struct ASTNode *left;
struct ASTNode *right;
} binary; // for binary operations
} data;
} ASTNode;
#endif // ASTNODE_H
Then remove those definitions from parser.y
and add #include "astnode.h"
to both files near the top. In lexer.l
, it must come
before #include "parser.tab.h"
since the latter header needs the
ASTNode
definition.