Alex Carney

code/simple-ast/

simple-ast.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#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

References