I am trying to implement a mathematical expression parser that receives a string as input and eventually outputs a conditional representation to the console. I have already implemented a similar working program in Python:
def term(self):
result = self.factor()
while self.current_token.type in (MUL, DIV):
token = self.current_token
if token.type == MUL:
self.eat(MUL)
result = result * self.factor()
elif token.type == DIV:
self.eat(DIV)
result = result / self.factor()
But now, due to my inexperience in the C language, I am having some problems.
I have attached a sketch of the future program, and in it I am interested in the parser_term function.
AST_T* parser_term(Parser_T* parser) {
AST_T* result;
while (parser->current_token->type == TOKEN_MUL
|| parser->current_token->type == TOKEN_DIV) {
if (parser->current_token->type == TOKEN_MUL) {
parser_eat(parser, TOKEN_MUL);
} else if (parser->current_token->type == TOKEN_DIV) {
parser_eat(parser, TOKEN_DIV);
}
}
return result;
}
How should I create a new binary operation node? This is probably a somewhat stupid question, but I hope you can help me figure it out.
I will also be glad if you point out to me other mistakes, which may be enough in my code.
Full code:
#include <stdio.h>
#include <stdlib.h>
//============================ LEXICAL ANALYSIS ============================================
//---------------------------- Token -------------------------------------------------------
typedef struct TOKEN_STRUCT
{
enum
{
TOKEN_INTEGER,
TOKEN_PLUS, TOKEN_MINUS,
TOKEN_MUL, TOKEN_DIV,
TOKEN_LBRA, TOKEN_RBRA,
TOKEN_EOF
} type;
char* value;
} Token_T;
Token_T* init_token(int type, char* value)
{
Token_T* token = calloc(1, sizeof(struct TOKEN_STRUCT));
token->type = type;
token->value = value;
return token;
}
void token_debug_print(Token_T* token)
{
printf(
"Token( type: '%d', value: '%s' )\n",
token->type, token->value
);
}
//------------------------------------------------------------------------------------------
//---------------------------- Lexer -------------------------------------------------------
typedef struct LEXER_STRUCT
{
char current_char;
unsigned int position;
char* content;
} Lexer_T;
Lexer_T* init_lexer(char* content)
{
Lexer_T* lexer = calloc(1, sizeof(struct LEXER_STRUCT));
lexer->content = content;
lexer->position = 0;
lexer->current_char = lexer->content[lexer->position];
return lexer;
}
void lexer_advance(Lexer_T* lexer)
{
if (lexer->current_char != '\0')
{
lexer->position += 1;
lexer->current_char = lexer->content[lexer->position];
}
}
void lexer_skip_whitespace(Lexer_T* lexer)
{
while (lexer->current_char == ' ')
{
lexer_advance(lexer);
}
}
char* lexer_get_current_char_as_string(Lexer_T* lexer)
{
char* stringus = calloc(1, sizeof(char));
stringus[0] = lexer->current_char;
stringus[1] = '\0';
return stringus;
}
Token_T* lexer_get_digit(Lexer_T* lexer)
{
char* lexem = calloc(1, sizeof(char));
lexem[0] = '\0';
while (lexer->current_char >= '0' && lexer->current_char <= '9')
{
char* part = lexer_get_current_char_as_string(lexer);
lexem = realloc(lexem, (strlen(lexem) + strlen(part) + 1) * sizeof(char));
strcat(lexem, part);
lexer_advance(lexer);
}
return init_token(TOKEN_INTEGER, lexem);
}
Token_T* lexer_get_op(Lexer_T* lexer)
{
switch (lexer->current_char)
{
case '+':
lexer_advance(lexer);
return init_token(TOKEN_PLUS, "+");
case '-':
lexer_advance(lexer);
return init_token(TOKEN_MINUS, "-");
case '*':
lexer_advance(lexer);
return init_token(TOKEN_MUL, "*");
case '/':
lexer_advance(lexer);
return init_token(TOKEN_DIV, "/");
}
}
Token_T* lexer_get_next_token(Lexer_T* lexer)
{
while (lexer->current_char != '\0')
{
if (lexer->current_char == ' ')
lexer_skip_whitespace(lexer);
else if (lexer->current_char >= '0' && lexer->current_char <= '9')
return lexer_get_digit(lexer);
else if (lexer->current_char == '+' || lexer->current_char == '-' ||
lexer->current_char == '*' || lexer->current_char == '/')
return lexer_get_op(lexer);
else if (lexer->current_char == '(')
{
lexer_advance(lexer);
return init_token(TOKEN_LBRA, "(");
}
else if (lexer->current_char == ')')
{
lexer_advance(lexer);
return init_token(TOKEN_RBRA, ")");
}
}
return init_token(TOKEN_EOF, "\\0");
}
//-----------------------------------------------------------------------------------------
//=========================================================================================
//============================ SYNTAX ANALYSIS ============================================
//---------------------------- AST --------------------------------------------------------
typedef struct AST_STRUCT
{
enum{
AST_NUMBER,
AST_BINOP,
AST_PAREN_EXPR
} type;
char* number_value;
char* bin_operator;
struct AST_STRUCT* left;
struct AST_STRUCT* right;
struct AST_STRUCT* paren_expr;
} AST_T;
AST_T* init_AST(int type)
{
AST_T* ast = calloc(1, sizeof(struct AST_STRUCT));
ast->type = type;
return ast;
}
//-----------------------------------------------------------------------------------------
//---------------------------- Parser -----------------------------------------------------
typedef struct PARSER_STRUCT
{
Lexer_T* lexer;
Token_T* current_token;
} Parser_T;
Parser_T* init_parser(Lexer_T* lexer)
{
Parser_T* parser = calloc(1, sizeof(struct PARSER_STRUCT));
parser->lexer = lexer;
parser->current_token = lexer_get_next_token(parser->lexer);
return parser;
}
AST_T* parser_factor(Parser_T* parser);
AST_T* parser_term(Parser_T* parser);
AST_T* parser_expr(Parser_T* parser);
void parser_eat(Parser_T* parser, int type)
{
if (parser->current_token->type == type)
{
parser->current_token = lexer_get_next_token(parser->lexer);
}
else
{
printf("Unexpected token");
exit(0);
}
}
AST_T* parser_expr(Parser_T* parser)
{
}
AST_T* parser_factor(Parser_T* parser)
{
if (parser->current_token->type == TOKEN_INTEGER)
{
AST_T* node = init_AST(TOKEN_INTEGER);
node->number_value = parser->current_token->value;
parser_eat(parser, TOKEN_INTEGER);
return node;
}
}
AST_T* parser_term(Parser_T* parser)
{
AST_T* result;
while (parser->current_token->type == TOKEN_MUL || parser->current_token->type == TOKEN_DIV)
{
if (parser->current_token->type == TOKEN_MUL)
{
parser_eat(parser, TOKEN_MUL);
}
else if (parser->current_token->type == TOKEN_DIV)
{
parser_eat(parser, TOKEN_DIV);
}
}
return result;
}
//-----------------------------------------------------------------------------------------
//=========================================================================================
//============================ VISITOR ====================================================
typedef struct VISITOR_STRUCT
{
} Visitor_T;
Visitor_T* init_visitor(AST_T* ast)
{
Visitor_T* visitor = calloc(1, sizeof(struct VISITOR_STRUCT));
return visitor;
}
void visitor_visit_number(Visitor_T* visitor, AST_T* node)
{
printf("Number {\n");
printf(" %s\n", node->number_value);
printf("}\n");
}
void visitor_visit_bin_op(Visitor_T* visitor, AST_T* node)
{
printf("Binop {\n");
visitor_visit(visitor, node->left);
visitor_visit(visitor, node->right);
printf("\n}\n");
}
void visitor_visit_paren_expr(Visitor_T* visitor, AST_T* node)
{
visitor_visit(visitor, node);
}
void visitor_visit(Visitor_T* visitor, AST_T* ast)
{
if (ast->type == AST_NUMBER)
{
visitor_visit_number(visitor, ast);
}
else if (ast->type == AST_BINOP)
{
visitor_visit_bin_op(visitor, ast);
}
else if (ast->type == AST_PAREN_EXPR)
{
visitor_visit_paren_expr(visitor, ast);
}
}
//=========================================================================================
int main()
{
char* code = "77 * 12 * 9 * 2";
Lexer_T* lexer = init_lexer(code);
Parser_T* parser = init_parser(lexer);
AST_T* ast = parser_term(parser);
Visitor_T* visitor = init_visitor(ast);
visitor_visit(visitor, ast);
return 0;
}
I tried to get the factor value first and add it to the node, and then continue parsing the expression, but this only confused me. I expect that this program will be able to process similar binary operations and turn them into one AST .
The one explicit question here is this:
How should I create a new binary operation node?
You need an object that is created at need but whose lifetime is not automatically limited to the function execution in which it begins. This combination requires dynamic allocation. (You get that automatically in Python, all the time, but in C, you have to ask for it.) For example:
AST_T *result = malloc(sizeof(*result));
As a matter of best practices, you should always verify that the allocation succeeded before trying to use the allocated object. If not, you should fall back to some kind of alternative or recovery operation or, more commonly, just fail. In a program, as opposed to a library, it's reasonable to fail by printing a diagnostic and terminating. For example:
if (result == NULL) {
fputs("fatal error: memory allocation failure\n", stderr);
abort();
}
But the allocations in your program are very unlikely to fail unless something else is badly wrong.
Supposing that the allocation succeed, you will want to set the members of the new object appropriately. Maybe something along these lines:
result->type = /* as appropriate */; // ...
result->number_value = NULL;
result->bin_operator = // ...
result->left = NULL; // probably something other than NULL in some cases
result->right = NULL;
result->paren_expr = NULL; // WTH?
Ultimately, you will need to either return the pointer to the new node (which seems to be what you anticipate doing) or maybe assign it to a member of the parser. Or both. These are easy. For example,
return result;
I will also be glad if you point out to me other mistakes
I'm afraid that's too broad an ask for SO. But do turn up your compiler's warnings and pay attention to them. At your level of experience, you should assume that every warning describes a problem that will make your program work incorrectly.