Simple AST¶
A simple C program that can construct and evaluate a simple Abstract Syntax Tree
(AST). The AST represents a toy "programming language" that only knows how to
add and multiply floating point numbers together.
.. code-block:: console
$ ./simple-ast
*
+
1.00
2.00
3.00
Example 1: 9.00
+
1.00
*
2.00
3.00
Example 2: 7.00
Building
--------
Having no real dependencies beyond the standard library this program can be
compiled with just a C compiler
.. code-block:: console
gcc simple-ast.c -o simple-ast
#include <stdio.h>
typedef enum {
AST_LITERAL,
AST_PLUS,
AST_MULTIPLY,
} AstNodeType;
typedef struct _ast {
/* The type of node this represents e.g.
a literal, an operator etc. */
AstNodeType type;
/* In the case of a literal value, this field
holds the actual value */
float value;
/* In the case of an operator, this pointer
refers to the left child node */
struct _ast *left;
/* In the case of an operator, this pointer
refers to the right child node */
struct _ast *right;
} AstNode;
void
ast_print(AstNode *ast, int level)
{
for (int i = 0; i < level; i++) {
printf(" ");
}
switch(ast->type) {
case AST_LITERAL:
printf("%.2f\n", ast->value);
break;
case AST_PLUS:
printf("+\n");
ast_print(ast->left, level + 1);
ast_print(ast->right, level + 1);
break;
case AST_MULTIPLY:
printf("*\n");
ast_print(ast->left, level + 1);
ast_print(ast->right, level + 1);
break;
}
}
float
ast_evaluate(AstNode *ast)
{
switch(ast->type) {
case AST_LITERAL:
return ast->value;
case AST_PLUS: {
float a = ast_evaluate(ast->left);
float b = ast_evaluate(ast->right);
return a + b;
}
case AST_MULTIPLY: {
float a = ast_evaluate(ast->left);
float b = ast_evaluate(ast->right);
return a * b;
}
}
}
int
main()
{
AstNode one = { .type = AST_LITERAL, .value = 1.0f };
AstNode two = { .type = AST_LITERAL, .value = 2.0f };
AstNode three = { .type = AST_LITERAL, .value = 3.0f };
AstNode plus1 = { .type = AST_PLUS, .left = &one, .right = &two};
AstNode example1 = { .type = AST_MULTIPLY, .left = &plus1, .right = &three};
AstNode mul1 = { .type = AST_MULTIPLY, .left = &two, .right = &three};
AstNode example2 = { .type = AST_PLUS, .left = &one, .right = &mul1};
float result1 = ast_evaluate(&example1);
float result2 = ast_evaluate(&example2);
ast_print(&example1, 0);
printf("Example 1: %.2f\n", result1);
ast_print(&example2, 0);
printf("Example 2: %.2f\n", result2);
return 0;
}
README¶
A simple C program that can construct and evaluate a simple Abstract Syntax Tree (AST). The AST represents a toy “programming language” that only knows how to add and multiply floating point numbers together.
$ ./simple-ast
*
+
1.00
2.00
3.00
Example 1: 9.00
+
1.00
*
2.00
3.00
Example 2: 7.00
Building¶
Having no real dependencies beyond the standard library this program can be compiled with just a C compiler
gcc simple-ast.c -o simple-ast