guest@BipbopPC:~/fun$ ./a.out < input > sierpinski.html
Hello Sierpinski
A recursively subdivided Sierpinski triangle, also compiled from Lisp.
Lisp · Flex · Bison · C · OpenGL 1.1 · 2025
sierpinski.html
guest@BipbopPC:~/fun/sierpinski$ cat NOTES
The smaller of the two compiler outputs, and the one that came first. A single triangle is subdivided at its edge midpoints, recursing on three of the four resulting triangles until it bottoms out.
It is the "hello world" of the graphics course, which makes it a reasonable smoke test for a compiler: if recursion, arithmetic, and per-vertex color all survive the trip through the AST, most of the language works.
SOURCE
What went in, and what turned it into the page above. These are the actual files, unedited.
[+] [-] input 38 lines the scene, in the toy Lisp
(defun draw_tri (a_x a_y b_x b_y c_x c_y)
(triangle
(color 1 0 0 pos a_x a_y)
(color 1 0 0 pos b_x b_y)
(color 0.5 0.0 0.9 pos c_x c_y)))
; what am i doing with my life
(defun subdivide (a_x a_y b_x b_y c_x c_y depth)
(define m1_x (/ (+ a_x b_x) 2))
(define m1_y (/ (+ a_y b_y) 2))
(define m2_x (/ (+ b_x c_x) 2))
(define m2_y (/ (+ b_y c_y) 2))
(define m3_x (/ (+ a_x c_x) 2))
(define m3_y (/ (+ a_y c_y) 2))
(sierpinski a_x a_y m1_x m1_y m3_x m3_y (- depth 1))
(sierpinski m1_x m1_y b_x b_y m2_x m2_y (- depth 1))
(sierpinski m3_x m3_y m2_x m2_y c_x c_y (- depth 1)))
(defun sierpinski (a_x a_y b_x b_y c_x c_y depth)
(if (= depth 0)
(draw_tri a_x a_y b_x b_y c_x c_y)
(subdivide a_x a_y b_x b_y c_x c_y depth)))
(clear (0.05 0.05 0.05 1))
(sierpinski .8 0. -.8 0. 0 -.9 5)
(sierpinski -.8 0. .8 0. 0 .9 5)
(sierpinski -.8 0. 0. -.9 -.8 -.9 5)
(sierpinski .8 0. 0. -.9 .8 -.9 5)
(sierpinski -.4 0.45 0. .9 -.8 .9 5)
(sierpinski .4 0.45 0. .9 .8 .9 5)
(sierpinski -.4 0.45 -0.8 0. -.8 .9 4)
(sierpinski .4 0.45 0.8 0. .8 .9 4)
(define n)
(loop for n from 1 to 100 by 1 do (display "IT DUZ LUPESS 2 NOT ~%JUST RECURRSIVISIONINING"))
(newline)
(display (- 1 10 100))
(display (* 100 10 1))
[+] [-] lisp.l 74 lines Flex lexer
%{
#include <stdlib.h>
#include <string.h>
#include "lisp.tab.h"
%}
%%
"define" { return DEFINE; }
"defun" { return DEFUN; }
"set!" { return SET; }
"if" { return IF; }
"then" { return THEN; }
"else" { return ELSE; }
"for" { return FOR; }
"from" { return FROM; }
"to" { return TO; }
"by" { return BY; }
"do" { return DO; }
"and" { return AND; }
"or" { return OR; }
"not" { return NOT; }
">=" { return GREATER_EQ; }
"<=" { return LESS_EQ; }
"loop" { return LOOP; }
"display" { return DISPLAY; }
"newline" { return NEWLINE; }
"clear" { return CLEAR; }
"triangle" { return TRIANGLE; }
"color" { return COLOR; }
"pos" { return POS; }
-[0-9]+\.[0-9]* { yylval.f = atof(yytext); return NUMBER; }
-\.[0-9]+ { yylval.f = atof(yytext); return NUMBER; }
-[0-9]+ { yylval.f = atof(yytext); return NUMBER; }
[0-9]+\.[0-9]* { yylval.f = atof(yytext); return NUMBER; }
\.[0-9]+ { yylval.f = atof(yytext); return NUMBER; }
[0-9]+ { yylval.f = atof(yytext); return NUMBER; }
\"([^\"\\]|\\.)*\" { char* str = strdup(yytext);
if (strstr(str, "~%") != NULL) {
char* pos;
while ((pos = strstr(str, "~%")) != NULL) {
*pos = '\\';
*(pos+1) = 'n';
}
}
yylval.s = str;
return STRING;
}
[a-zA-Z_][a-zA-Z0-9_]* { yylval.s = strdup(yytext); return ID; }
"+" { return '+'; }
"-" { return '-'; }
"*" { return '*'; }
"/" { return '/'; }
">" { return '>'; }
"<" { return '<'; }
"=" { return '='; }
"(" { return '('; }
")" { return ')'; }
";"[^\n]* ;
[ \t\r\n]+ ;
. { return yytext[0]; }
%%
int yywrap(void) { return 1; }
[+] [-] lisp.y 419 lines Bison grammar, AST, codegen
%define parse.error detailed
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NODE_NUMBER 0
#define NODE_SEQ 1
#define NODE_FOR 2
#define NODE_ID 3
#define NODE_STRING 4
#define NODE_ASSIGN 5
#define NODE_DEFINE 6
#define NODE_SET 7
#define NODE_ADD 8
#define NODE_SUBTRACT 9
#define NODE_MULTIPLY 10
#define NODE_DIVIDE 11
#define NODE_GREATER_THAN 12
#define NODE_LESS_THAN 13
#define NODE_GREATER_EQUAL 14
#define NODE_LESS_EQUAL 15
#define NODE_EQUAL 16
#define NODE_AND 17
#define NODE_ARGLIST 18
#define NODE_OR 19
#define NODE_NOT 20
#define NODE_IF 21
#define NODE_LOOP 22
#define NODE_DEFUN 23
#define NODE_CALL 24
#define NODE_DISPLAY 25
#define NODE_NEWLINE 26
#define NODE_CLEAR 28
#define NODE_COLOR 29
#define NODE_TRIANGLE 30
#define NODE_VERTEX 31
char* header = "<!DOCTYPE html>\n<html>\n<head>\n\
<title>Hello Triangle!!!11!1</title>\n\
<style>\n\
body { background: DarkSlateGrey; display: flex; flex-direction: column;\n\
align-items: center; justify-content: center;}\n\
canvas { border: 2px solid; display: block; }\n\
</style>\n\
<script src=\"https://www.ecst.csuchico.edu/~oal-saadi/Graphics/source/glsim.js\"></script>\n\
</head>\n\
<body>\n\
<canvas id=\"glcanvas\" width=\"600\" height=\"600\">\n\
<script>\n\
glsimUse(\"glcanvas\");\n";
char* footer = "</script>\n\
</body>\n\
</html>\n";
typedef struct AST {
int type;
float value;
char* name;
struct AST* first;
struct AST* second;
struct AST* third;
struct AST* fourth;
} AST;
static void pretty(AST* n);
static void free_ast(AST* n) {
if (!n) return;
free_ast(n->first);
free_ast(n->second);
free_ast(n->third);
free_ast(n->fourth);
if (n->name) free(n->name);
free(n);
}
static AST* make_node(int type, float value, char* name, AST* first, AST* second, AST* third) {
AST* n = (AST*)malloc(sizeof(AST));
n->type = type;
n->value = value;
n->name = name;
n->first = first;
n->second = second;
n->third = third;
n->fourth = NULL;
return n;
}
static AST* make_arglist(AST* head, AST* tail) {
return make_node(NODE_ARGLIST, 0, NULL, head, tail, NULL);
}
static AST* make_node_four(int type, float value, char* name, AST* first, AST* second, AST* third, AST* fourth) {
AST* n = (AST*)malloc(sizeof(AST));
n->type = type;
n->value = value;
n->name = name;
n->first = first;
n->second = second;
n->third = third;
n->fourth = fourth;
return n;
}
static void unroll_list(AST* n, const char* delimiter) {
if (!n) return;
pretty(n->first);
if (n->second) {
printf("%s", delimiter);
unroll_list(n->second, delimiter);
}
}
static void print_vertex(AST* v) {
printf(" glColor3f(");
pretty(v->first->first);
printf(", ");
pretty(v->first->second->first);
printf(", ");
pretty(v->first->second->second->first);
printf(");\n");
printf(" glVertex2f(");
pretty(v->second->first);
printf(", ");
pretty(v->second->second->first);
printf(");\n");
}
static void pretty(AST* n) {
if (!n) return;
switch (n->type) {
case NODE_NUMBER:
printf("%g", n->value);
break;
case NODE_ID:
printf("%s", n->name);
break;
case NODE_STRING:
printf("%s", n->name);
break;
case NODE_SEQ:
pretty(n->first);
pretty(n->second);
printf(";\n");
break;
case NODE_DEFINE:
printf("let %s", n->name);
if (n->first) { printf(" = "); pretty(n->first); }
break;
case NODE_SET:
printf("%s = ", n->name);
pretty(n->first);
break;
case NODE_DEFUN:
printf("function %s(", n->name);
unroll_list(n->first, ", ");
printf(") {\n");
for (AST* s = n->second; s; s = s->second) {
pretty(s->first);
printf(";\n");
}
printf("}");
break;
case NODE_IF:
printf("if (");
pretty(n->first);
printf(") {\n");
pretty(n->second);
printf(";\n}");
if (n->third) {
printf(" else {\n");
pretty(n->third);
printf(";\n}");
}
break;
case NODE_LOOP:
printf("for (let %s = ", n->name);
pretty(n->first);
printf("; %s <= ", n->name);
pretty(n->second);
printf("; %s += ", n->name);
pretty(n->third);
printf(") {\n");
for (AST* s = n->fourth; s; s = s->second) {
pretty(s->first);
printf(";\n");
}
printf("}");
break;
case NODE_ADD:
printf("(");
unroll_list(n->first, " + ");
printf(")");
break;
case NODE_SUBTRACT:
printf("(");
unroll_list(n->first, " - ");
printf(")");
break;
case NODE_MULTIPLY:
printf("(");
unroll_list(n->first, " * ");
printf(")");
break;
case NODE_DIVIDE:
printf("(");
unroll_list(n->first, " / ");
printf(")");
break;
case NODE_GREATER_THAN:
printf("(");
pretty(n->first); printf(" > ");
pretty(n->second); printf(")");
break;
case NODE_LESS_THAN:
printf("(");
pretty(n->first); printf(" < ");
pretty(n->second); printf(")");
break;
case NODE_GREATER_EQUAL:
printf("(");
pretty(n->first); printf(" >= ");
pretty(n->second); printf(")");
break;
case NODE_LESS_EQUAL:
printf("(");
pretty(n->first); printf(" <= ");
pretty(n->second); printf(")");
break;
case NODE_EQUAL:
printf("(");
pretty(n->first); printf(" === ");
pretty(n->second); printf(")");
break;
case NODE_AND:
printf("(");
unroll_list(n->first, " && ");
printf(")");
break;
case NODE_OR:
printf("(");
unroll_list(n->first, " || ");
printf(")");
break;
case NODE_NOT:
printf("(!");
pretty(n->first);
printf(")");
break;
case NODE_DISPLAY:
printf("console.log(");
pretty(n->first);
printf(")");
break;
case NODE_NEWLINE:
printf("console.log(\"\")");
break;
case NODE_CALL:
printf("%s(", n->name);
unroll_list(n->first, ", ");
printf(")");
break;
case NODE_CLEAR:
printf("glClearColor(");
unroll_list(n->first, ", ");
printf(");\n");
printf("glClear(GL_COLOR_BUFFER_BIT)");
break;
case NODE_TRIANGLE:
printf("glBegin(GL_TRIANGLES);\n");
print_vertex(n->first->first);
print_vertex(n->first->second->first);
print_vertex(n->first->second->second->first);
printf("glEnd();");
break;
default:
fprintf(stderr, "/* unknown node type %d */", n->type);
break;
}
}
int yylex(void);
void yyerror(const char* s);
static AST* root = NULL;
%}
%code requires {
typedef struct AST AST;
}
%union {
float f;
char* s;
AST* node;
}
%left '+' '-' '='
%token FOR IF THEN ELSE SET DEFINE DEFUN LOOP FROM TO BY DO AND OR NOT DISPLAY NEWLINE CLEAR TRIANGLE COLOR POS GREATER_EQ LESS_EQ
%token <f> NUMBER
%token <s> STRING ID
%type <node> expr expr_list input seq vertex arg_list param_list
%%
input
: seq { root = $1; $$ = $1; }
;
seq
: seq expr { $$ = make_node(NODE_SEQ, 0, NULL, $1, $2, NULL); }
| { $$ = NULL; }
;
expr
: NUMBER { $$ = make_node(NODE_NUMBER, $1, NULL, NULL, NULL, NULL); }
| ID { $$ = make_node(NODE_ID, 0, $1, NULL, NULL, NULL); }
| STRING { $$ = make_node(NODE_STRING, 0, $1, NULL, NULL, NULL); }
| '(' DEFINE ID expr ')' { $$ = make_node(NODE_DEFINE, 0, $3, $4, NULL, NULL); }
| '(' DEFINE ID ')' { $$ = make_node(NODE_DEFINE, 0, $3, NULL, NULL, NULL); }
| '(' SET ID expr ')' { $$ = make_node(NODE_SET, 0, $3, $4, NULL, NULL); }
| '(' DEFUN ID '(' param_list ')' expr_list ')' { $$ = make_node(NODE_DEFUN, 0, $3, $5, $7, NULL); }
| '(' IF expr expr expr ')' { $$ = make_node(NODE_IF, 0, NULL, $3, $4, $5); }
| '(' IF expr expr ')' { $$ = make_node(NODE_IF, 0, NULL, $3, $4, NULL); }
| '(' LOOP FOR ID FROM expr TO expr BY expr DO expr_list ')' { $$ = make_node_four(NODE_LOOP, 0, $4, $6, $8, $10, $12); }
| '(' DISPLAY expr ')' { $$ = make_node(NODE_DISPLAY, 0, NULL, $3, NULL, NULL); }
| '(' NEWLINE ')' { $$ = make_node(NODE_NEWLINE, 0, NULL, NULL, NULL, NULL); }
| '(' '+' expr_list ')' { $$ = make_node(NODE_ADD, 0, NULL, $3, NULL, NULL); }
| '(' '-' expr_list ')' { $$ = make_node(NODE_SUBTRACT, 0, NULL, $3, NULL, NULL); }
| '(' '*' expr_list ')' { $$ = make_node(NODE_MULTIPLY, 0, NULL, $3, NULL, NULL); }
| '(' '/' expr_list ')' { $$ = make_node(NODE_DIVIDE, 0, NULL, $3, NULL, NULL); }
| '(' '>' expr expr ')' { $$ = make_node(NODE_GREATER_THAN, 0, NULL, $3, $4, NULL); }
| '(' '<' expr expr ')' { $$ = make_node(NODE_LESS_THAN, 0, NULL, $3, $4, NULL); }
| '(' GREATER_EQ expr expr ')' { $$ = make_node(NODE_GREATER_EQUAL, 0, NULL, $3, $4, NULL); }
| '(' LESS_EQ expr expr ')' { $$ = make_node(NODE_LESS_EQUAL, 0, NULL, $3, $4, NULL); }
| '(' '=' expr expr ')' { $$ = make_node(NODE_EQUAL, 0, NULL, $3, $4, NULL); }
| '(' AND arg_list ')' { $$ = make_node(NODE_AND, 0, NULL, $3, NULL, NULL); }
| '(' OR arg_list ')' { $$ = make_node(NODE_OR, 0, NULL, $3, NULL, NULL); }
| '(' NOT expr ')' { $$ = make_node(NODE_NOT, 0, NULL, $3, NULL, NULL); }
| '(' CLEAR '(' arg_list ')' ')' { $$ = make_node(NODE_CLEAR, 0, NULL, $4, NULL, NULL); }
| '(' TRIANGLE vertex vertex vertex ')'
{
AST* vl = make_arglist($3, make_arglist($4, make_arglist($5, NULL)));
$$ = make_node(NODE_TRIANGLE, 0, NULL, vl, NULL, NULL);
}
/* Function Call */
| '(' ID arg_list ')' { $$ = make_node(NODE_CALL, 0, $2, $3, NULL, NULL); }
;
vertex
: '(' COLOR expr expr expr POS expr expr ')'
{
AST* rgb = make_arglist($3, make_arglist($4, make_arglist($5, NULL)));
AST* xy = make_arglist($7, make_arglist($8, NULL));
$$ = make_node(NODE_VERTEX, 0, NULL, rgb, xy, NULL);
}
;
expr_list
: expr { $$ = make_arglist($1, NULL); }
| expr expr_list { $$ = make_arglist($1, $2); }
;
arg_list
: { $$ = NULL; }
| expr arg_list { $$ = make_arglist($1, $2); }
;
param_list
: { $$ = NULL; }
| ID param_list { $$ = make_arglist(make_node(NODE_ID, 0, $1, NULL, NULL, NULL), $2); }
;
%%
void yyerror(const char* s) {
fprintf(stderr, "parse error: %s\n", s);
}
int main(void) {
printf(header);
yyparse();
pretty(root);
free_ast(root);
printf("\n");
printf(footer);
return 0;
}