/////////////
// 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

/////////////
// 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
 
typedef struct AST {
    int type;
    int value;
    struct AST* left;
    struct AST* right;
} AST;
 
static AST* make_seq(AST* l, AST* r) {
    AST* n = malloc(sizeof(AST));
    n->type = NODE_SEQ;
    n->left = l;
    n->right = r;
    return n;
}
 
static AST* make_number(int v) {
    AST* n = (AST*)malloc(sizeof(AST));
    n->type = NODE_NUMBER;
    n->value = v;
    n->left = n->right = NULL;
    return n;
}
 
static AST* make_add(AST* l, AST* r) {
    AST* n = (AST*)malloc(sizeof(AST));
    n->type = NODE_ADD;
    n->left = l;
    n->right = r;
    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_ADD){
        printf("(+ ");
        pretty(n->left);
        printf(" ");
        pretty(n->right);
        printf(")");
    }
    if (n->type == NODE_SEQ) {
        pretty(n->left);
        printf("\n");
        pretty(n->right);
    }
}
 
static void free_ast(AST* n) {
    if (!n) return; /* if n == NULL, return */
    free_ast(n->left);
    free_ast(n->right);
    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;
    AST* node;
}
 
%left '+'
 
%token IF THEN ELSE EOL
%token <i> NUMBER
%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); }
    | expr '+' expr                  { $$ = make_add($1, $3); }
    ;
 
%%
 
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 "syntax_tree.tab.h"
%}
 
%%
 
"if"        { return IF; }
"then"      { return THEN; }
"else"      { return ELSE; }
[0-9]+      { yylval.i = atoi(yytext); return NUMBER; }
"+"         { return '+'; }
[ \t\r]+    ;
\n          { return EOL; }
.           { return yytext[0]; }
 
%%
 
int yywrap(void) { return 1; }