/////////////
// Compile
/////////////

bison -d syntax_tree.y
flex syntax_tree.l
gcc syntax_tree.tab.c lex.yy.c -ll 

/////////////
// Example Inputs
/////////////

1+2+3
3+4+5+6
7
if (1 then 2 else 3 + 4)
for (x = 0; y; x = x + 1)
y = 5 + z + 1

/////////////
// syntax_tree.y
/////////////

%define parse.error detailed 
 
%{ 
#include <stdio.h>
#include <stdlib.h>
 
#define NODE_NUMBER 0
#define NODE_ADD    1
#define NODE_SEQ    2
#define NODE_IF     3
#define NODE_FOR    4
#define NODE_ID     5
#define NODE_ASSIGN 6
 
typedef struct AST {
    int type;
    int value;    
    char* name;
    struct AST* first;    
    struct AST* second;
    struct AST* third;
} AST;
 
static AST* make_seq(AST* l, AST* r) {
    AST* n = (AST*)malloc(sizeof(AST));
    n->type = NODE_SEQ;
    n->first = l;
    n->second = r;
    n->third = NULL;
    return n;
}
 
static AST* make_number(int v) {
    AST* n = (AST*)malloc(sizeof(AST));
    n->type = NODE_NUMBER;
    n->value = v;
    n->first = n->second = n->third = NULL;
    return n;
}
 
static AST* make_id(char* s) {
    AST* n = (AST*)malloc(sizeof(AST));
    n->type = NODE_ID;
    n->name = s;
    n->first = n->second = n->third = NULL;
    return n;
}
 
 
static AST* make_assign(char* s, AST* expr) {
    AST* n = (AST*)malloc(sizeof(AST));
    n->type = NODE_ASSIGN;
    n->name = s;
    n->first = n->second = n->third = NULL;
    n->first = expr;
    return n;
}
 
static AST* make_if(AST* cond_branch, AST* then_branch, AST* else_branch){
    AST* n = (AST*)malloc(sizeof(AST));
    n->type = NODE_IF;
    n->first = cond_branch;
    n->second= then_branch;
    n->third= else_branch;
    return n;
}
 
static AST* make_for(AST* start, AST* break_cond, AST* loop){
    AST* n = (AST*)malloc(sizeof(AST));
    n->type = NODE_FOR;
    n->first = start;
    n->second= break_cond;
    n->third= loop;
    return n;
}
 
static AST* make_add(AST* l, AST* r) {
    AST* n = (AST*)malloc(sizeof(AST));
    n->type = NODE_ADD;
    n->first = l;
    n->second = r;
    n->third = NULL;
    return n;
}
 
// Functional style : (+ a b)
static void pretty(AST* n) {
    if (!n) return; 
    if (n->type == NODE_NUMBER) {
        printf("%d", n->value);
    }   
    if (n->type == NODE_ID) {
        printf("%s", n->name);
    }   
    if (n->type == NODE_ASSIGN) {
        printf("(%s", n->name);
        printf("= ");
        pretty(n->first);
        printf(")");
    }   
    if (n->type == NODE_ADD){
        printf("(+ ");
        pretty(n->first);
        printf(" ");
        pretty(n->second);
        printf(")");
    }   
     
    if (n->type == NODE_SEQ) {
        pretty(n->first);
        printf("\n");
        pretty(n->second);
    }   
    if (n->type == NODE_IF){
        printf("(if ");
        pretty(n->first);
        printf(" ");
        pretty(n->second);
        printf(" ");
        pretty(n->third);
        printf(")");
    }   
    if (n->type == NODE_FOR){
        printf("(for ");
        pretty(n->first);
        printf("; ");
        pretty(n->second);
        printf("; ");
        pretty(n->third);
        printf(")");
    }   
}
 
 
 
static void free_ast(AST* n) {
    if (!n) return; //if n == NULL, return
    free_ast(n->first);
    free_ast(n->second);
    free_ast(n->third);
    free(n);
}
 
int yylex(void);
void yyerror(const char* s); 
static AST* root = NULL;
%}
 
%code requires {
    typedef struct AST AST;  /* make AST known in ast.tab.h */
} 
 
%union {
    int i;
    char* s;
    AST* node;
}
 
%left '+' '=' 
 
%token FOR IF THEN ELSE EOL 
%token <i> NUMBER
%token <s> ID
%type  <node> expr input seq 
 
%%
 
input
    : seq         { root = $1; $$ = $1; }
    ;
 
seq
    : seq expr EOL { $$ = make_seq($1, $2); }
    | seq EOL      { $$ = $1; }
    | /* empty */  { $$ = NULL; }
    ;
 
expr
    : NUMBER                         { $$ = make_number($1); }
    | ID                             { $$ = make_id($1); }
    | ID '=' expr                    { $$ = make_assign($1,$3); }
    | expr '+' expr                  { $$ = make_add($1, $3); }
    | '(' expr ')'                   { $$ = $2; }
    | IF '(' expr THEN expr ELSE expr ')' { $$ = make_if($3,$5,$7); }
    | FOR '(' expr ';' expr ';' expr ')'  { $$ = make_for($3,$5,$7); }
    ;
 
%%
 
void yyerror(const char* s) {
    fprintf(stderr, "parse error: %s\n", s); 
}
 
int main(void) {
    yyparse();
    pretty(root);
    free_ast(root);
    printf("\n");
    return 0;
}


////////////
// syntax_tree.l
////////////

%{ 
#include <stdlib.h>
#include "ast.tab.h"
%}
 
%%
 
"if"        { return IF; }
"then"      { return THEN; }
"else"      { return ELSE; }
"for"       { return FOR; }
[a-zA-Z_][a-zA-Z0-9_]*  { yylval.s = strdup(yytext); return ID; }
[0-9]+      { yylval.i = atoi(yytext); return NUMBER; }
"+"         { return '+'; }
[ \t\r]+    ;
\n          { return EOL; }
.           { return yytext[0]; }
 
%%
 
int yywrap(void) { return 1; }