#!/usr/bin/perl -l

use strict;
use warnings;
my (%vars, %funcs);

# Evaluate the sexp
# Apply the first argument to the tail
sub sexp {
    my ($hd, @tl) = @_;
    if (exists $funcs{$hd}) {
        $funcs{$hd}->(@tl);
    } else {
        die "Unknown function `$hd'";
    }
}
# Either evaluate the sexp or returns the direct value
sub comp {
    my $val = shift;
    if (ref $val eq 'ARRAY') {
        sexp(@$val)
    } elsif ($val =~ /^\d+$/) {
        int $val
    } elsif (exists $vars{$val}) {
        $vars{$val}
    } else {
        die "Unknow variable `$val'"
    }
}

# Variable definition
$funcs{define} = sub {
    my ($name, $val) = @_;
    die "Bad variable name: `$name'" unless $name =~ /^[a-z]\w*$/;
    die "Variable already defined: `$name'" if exists $vars{$name};
    $val = comp($val);
    $vars{$name} = $val;
    return "$name => $val";
};

# Basic binary ops
sub basic_binop {
    my $op = shift;
    $funcs{$op} = sub {
        my ($a, $b) = @_;
        $a = comp($a); $b = comp($b);
        eval qq{$a $op $b};
    };
}
basic_binop $_ for qw{+ - * / < > <= >=};

# Booleans & branching
$funcs{not}  = sub { not(comp(shift)) };
$funcs{and}  = sub { comp(shift) and comp(shift) };
$funcs{or}   = sub { comp(shift) or  comp(shift) };
$funcs{if}   = sub {
    my ($cond, $a, $b) = @_;
    comp($cond) ? comp($a) : comp($b);
};
# Imperative tasks
$funcs{set} = sub {
    my ($n, $v) = @_;
    die "Unknow variable: `$n'" unless exists $vars{$n};
    $vars{$n} = comp($v);
};
$funcs{begin} = sub { comp($_) for @_ };
$funcs{while} = sub {
    my ($cond, $block) = @_;
    comp($block) while comp($cond);
};

# The "parsing"
# Produces arrays like ['+', '1', '2', '3'] from '(+ 1 2 3)'
my $txt = join '', <>;
$txt =~ y/()/[]/;
$txt =~ s/\s+/,/g;
$txt =~ s/([^\[\],]+)/'$1'/g;
my @code = eval $txt;

# Main
print comp $_ for @code;

(* Définition de l'arbre abstrait *)

type instrs =
| Instrs of instr * instrs
| Lf
 and instr =
| Define of string * expr
| If of expr * instr * instr
| While of expr * instr
| Set of string * expr
| Print of expr
| Begin of instrs
 and expr =
| PLInt of int
| PLId of string
| Op of string * expr * expr

(* Analyse lexicale *)

open Genlex

let analex = function
| "" -> failwith "Error in [analex] : Void src"
| str -> let kwd = ["("; ")"; "define"; "if"; "while"; "set"; "begin"; "end"; "print";
                    "+"; "-"; "**"; "/"; "*"; "<="; "<>"; ">="; ">"; "="; "<"; "and"; "or"]
  in make_lexer kwd (Stream.of_string str)
  
(* Analyse syntaxique *)

let anasyn stm =

  let is_op = function
  | ("+"| "-"| "**"| "/"| "*"| "<="| "<>"| ">="| ">"| "="| "<"| "and"| "or") -> true
  | _ -> false
  
  in let rec instrs = parser
  | [< 'Kwd "("; i = instr; 'Kwd ")"; is = instrs >] -> Instrs (i, is)
  | [< >] -> Lf
  
   and instr = parser
  | [< 'Kwd "define"; 'Ident n; e = expr >] -> Define (n, e)
  | [< 'Kwd "if"; e = expr; 'Kwd "("; i1 = instr; 'Kwd ")"; 'Kwd "("; i2 = instr; 'Kwd ")" >] -> If (e, i1, i2)
  | [< 'Kwd "while"; e = expr; 'Kwd "("; i = instr; 'Kwd ")" >] -> While (e, i)
  | [< 'Kwd "set"; 'Ident n; e = expr >] -> Set (n, e)
  | [< 'Kwd "print"; e = expr >] -> Print e
  | [< 'Kwd "begin"; is = instrs; 'Kwd "end" >] -> Begin is
  | [< >] -> failwith "Error in [instr] : no match case"
  
   and expr = parser
  | [< 'Int i >] -> PLInt i
  | [< 'Ident n >] -> PLId n
  | [< 'Kwd "("; 'Kwd op when is_op op; e1 = expr; e2 = expr; 'Kwd ")" >] -> Op (op, e1, e2)
  | [< >] -> failwith "Error in [expr] : no match case"
  
  in instrs stm
  
(* Evaluation *)

let eval ast tbl =

  let bool_of_int = function
  | 0 -> false
  | _ -> true
  
  in let int_of_bool = function
  | true -> 1
  | false -> 0
  
  in let rec eval_instrs = function
  | Instrs (i, is) -> eval_instr i; eval_instrs is
  | Lf -> ()
  
   and eval_instr = function
  | Define (n, e) -> Hashtbl.add tbl n (eval_expr e)
  | If (e, i1, i2) -> if bool_of_int (eval_expr e) then eval_instr i1 else eval_instr i2
  | While (e, i) -> while bool_of_int (eval_expr e) do eval_instr i done
  | Print e -> print_int (eval_expr e); print_newline ()
  | Set (n, e) ->
    if Hashtbl.mem tbl n then
      Hashtbl.replace tbl n (eval_expr e)
    else failwith ("Error in [eval_instr] : " ^ n ^ " undefined")
  | Begin is -> eval_instrs is
  
   and eval_expr = function
  | PLInt i -> i
  | PLId n ->
    if Hashtbl.mem tbl n then
      Hashtbl.find tbl n
    else failwith ("Error in [eval_expr] : " ^ n ^ " undefined")
  | Op (op, e1, e2) ->
    let a, b = eval_expr e1, eval_expr e2
    in ( match op with
    | "+" -> a + b
    | "-" -> a - b
    | "**" -> int_of_float ( float_of_int a ** float_of_int b )
    | "/" -> a / b
    | "*" -> a * b
    | "<=" -> int_of_bool ( a <= b)
    | "<>" -> int_of_bool ( a <> b)
    | ">=" -> int_of_bool ( a >= b)
    | ">" -> int_of_bool ( a > b)
    | "=" -> int_of_bool ( a = b)
    | "<" -> int_of_bool ( a < b)
    | "and" -> int_of_bool ( bool_of_int a && bool_of_int b)
    | "or" -> int_of_bool ( bool_of_int a || bool_of_int b)
    | _ -> failwith "Error in [eval_expr] : no match case" )
	
  in eval_instrs ast
   
(* Pour tester *)

let plang () =
  let read_bloc () =
    let rec read acc = match read_line () with
    | ";;" -> acc
    | s -> read (s :: acc)
    in String.concat " " (List.rev (read []))
  in let src = read_bloc ()
  in eval (anasyn (analex src)) (Hashtbl.create 1)

# plang ();;
(define a 5)
(while a
  (begin
    (print a)
    (set a (- a 1))
   end)
)
;;
5
4
3
2
1
- : unit = ()

program         ::= statement_list

statement_list  ::= "(" statement ")" statement_list
                 |  NOTHING

statement       ::= assign_stmt
                 |  expr_stmt

assign_stmt     ::= "define" ID expr_stmt

expr_stmt       ::= "if" atom "then" atom "else" atom
                 |  OP atom_list
                 |  atom

atom_list       ::= atom atom_list
                 |  NOTHING

atom            ::= NUM
                ::= ID
                 |  "(" expr_stmt ")"

#!/usr/bin/env python
# coding: utf-8


# -- Lexical errors


class PLLexicalError(Exception):
    def __init__(self, value, start_pos, end_pos):
        self.value = value
        self.start_pos = start_pos
        self.end_pos = end_pos


class UnknownOpError(PLLexicalError):
    def __str__(self):
        return "Unknown operator '" + str(self.value) + "'"


class IllicitCharError(PLLexicalError):
    def __str__(self):
        return "Illicit character '" + str(self.value) + "'"


# -- Syntax errors


class PLSyntaxError(Exception):
    def __init__(self, msg=""):
        self.msg = msg

    def __str__(self):
        return self.msg


class UnknownIdError(PLSyntaxError):
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return "Unknown identifier '" + self.name + "'"

#!/usr/bin/env python
# coding: utf-8

import string

from error import *

# Some utility lists
_end_char = '\0'
_digits = list(string.digits)
_letters = list(string.letters)
_whitespace = list(string.whitespace)
_opchars = ['+', '-', '*', '/', '<', '>', '=',]


# The token types
ID = 'an identifier'
KEYWD = 'a keyword'
NUM = 'a number'
OP = 'an operator'
LPAREN = 'a left parenthesis'
RPAREN = 'a right parenthesis'
END = 'the end'

class Lexer:
    def __init__(self, input="", keywords=[], operators=['+', '-', '*', '/']):
        self.keywords = keywords
        self.operators = operators
        self.set_input(input)

    def set_input(self, input):
        self.pos = 0
        self.start_pos = 0
        self.pos_max = len(input)
        self.input = input + _end_char
        self.current_token = self.read_next_token()

    # Return the token being read and scan the next.
    def get_token(self):
        current_token = self.current_token
        self.current_token = self.read_next_token()
        return current_token

    # Return the token being read without scanning the next. That is, several
    # successive calls to 'peek()' will give the same result, while successive
    # calls to 'get_token()' would give three different results (the three next
    # tokens).
    def peek(self):
        return self.current_token

    # Scan the next token and return it.
    def read_next_token(self):
        self.last_start_pos = self.start_pos
        self.last_pos = self.pos

        # Skip _whitespace
        while self.input[self.pos] in _whitespace:
            self.pos += 1

        # Remember the start position of the token being read for debugging
        self.start_pos = self.pos
        cur_char = self.input[self.pos] # The current characterbeing read

        # If we are reading an identifier or a keyword
        if cur_char in _letters:
            result = ''
            while self.input[self.pos] in _letters + _digits + ['_']:
                result += self.input[self.pos]
                self.pos += 1
            
            # Check whether what was read is a keyword
            if result in self.keywords:
                return Token(KEYWD, result)
            else:
                return Token(ID, result)

        # If we are reading a number (positive or negative)
        elif cur_char in _digits + ['-', '+']:
            result = ''
            
            # We first have to check that if we read a '+' or '-', it is
            # followed by a digit to ensure it was a unary operator and not a
            # binary one
            if cur_char in ['+', '-'] and not self.input[self.pos+1] in _digits:
                self.pos += 1
                return Token(OP, cur_char)
            else:
                result += cur_char
                self.pos += 1

            while self.input[self.pos] in _digits:
                result += self.input[self.pos]
                self.pos += 1

            return Token(NUM, int(result))

        # If we are reading an operator
        elif cur_char in _opchars:
            result = ''
            while self.input[self.pos] in _opchars:
                result += self.input[self.pos]
                self.pos += 1

            if result in self.operators:
                return Token(OP, result)
            else:
                raise UnknownOpError(result, self.start_pos, self.pos)

        # Parentheses
        elif cur_char == '(':
            self.pos += 1
            return Token(LPAREN)
        elif cur_char == ')':
            self.pos += 1
            return Token(RPAREN)
                
        # The end of the input
        elif cur_char == _end_char:
            return Token(END)
        
        # Woops, that's not legal
        else:
            raise IllicitCharError(cur_char, self.start_pos, self.pos)


class Token:
    def __init__(self, type, value=None):
        self.type = type
        self.value = value

#!/usr/bin/env python
# coding: utf-8

from error import *

# Map an operator name to a function
op_dict = {
        '+':    lambda x,y: x + y,
        '-':    lambda x,y: x - y,
        '*':    lambda x,y: x * y,
        '/':    lambda x,y: x / y,
        '<':    lambda x,y: x < y,
        '<=':   lambda x,y: x <= y,
        '>':    lambda x,y: x > y,
        '>=':   lambda x,y: x >= y,
        '=':    lambda x,y: x == y,
        '<>':   lambda x,y: x != y
        }

# A generic syntax tree node.
# The __str__ part is there for debugging purposes.
class PLNode():
    def __str__(self):
        return '<(%s)>' % self.__class__.__name__


class AssignStmt(PLNode):
    def __init__(self, target, ast, context):
        self.target = target
        self.ast = ast
        self.context = context

    def eval(self):
        self.context.assign(target=self.target, ast=self.ast)


class IfThenElse(PLNode):
    def __init__(self, condition, then_block, else_block):
        self.condition = condition
        self.then_block = then_block
        self.else_block = else_block

    def eval(self):
        if self.condition.eval():
            return self.then_block.eval()
        else:
            return self.else_block.eval()


class Id(PLNode):
    def __init__(self, name, context):
        self.name = name
        self.context = context

    def eval(self):
        return self.context.fetch(target=self.name)


class Op(PLNode):

    def __init__(self, name, operands):
        self.name = name
        self.operands = operands

    def eval(self):
        if len(self.operands) != 2:
            msg = "Wrong number of arguments. Operator " + self.name +\
            " expected 2 arguments but got %d" % len(self.operands)
            raise PLSyntaxError(msg)
        func = op_dict[self.name]
        arg1 = self.operands[0].eval()
        arg2 = self.operands[1].eval()
        return func(arg1, arg2)


class Atom(PLNode):
    def __init__(self, value):
        self.value = value

    def eval(self):
        return self.value

class Num(Atom): pass

#!/usr/bin/env python
# coding: utf-8

import sys

from lex import *
from ast import *
from error import *


# For debugging only. When 'pass' is replaced by 'print msg', it prints the
# list of the names of the productions that are matched.
def dump(msg):
    pass


class Parser:
    def __init__(self, keywords=[], operators=['+','-','*','/']):
        self.input = input
        self.lexer = Lexer(keywords=keywords, operators=operators)
        self.global_context = Context(father=None)
        self.results = None
    
    # Parse the input into an abstract syntax tree
    def parse(self, input=""):
        self.input = input
        try:
            self.lexer.set_input(self.input)
            self.results = self.statement_list
        except PLLexicalError as e:
            print "(!) Lexical error (%d-%d): %s." \
                    % (self.lexer.last_start_pos, self.lexer.last_pos, e)
        except PLSyntaxError as e:
            print "(!) Syntax error (%d-%d): %s." \
                    % (self.lexer.last_start_pos, self.lexer.last_pos, e)
        except: raise

    def report_error(self, name_error, msg_error):
        start = self.lexer.last_start_pos
        stop = self.lexer.last_pos - 1
        print "(!) %s:" % (name_error)
        print "    %s" % self.input
        print "    %s^%s" % (" " * (start), "^" * (stop-start))
        print "    %s." % msg_error

    # A generator that returns the evaluations of the successive statements
    def eval(self):
        try:
            for result in self.results():
                yield result
        except PLSyntaxError as e:
            self.report_error("Syntax error", e)
        except: raise

    # Check that the current token is of the expected type. If it is, return
    # the value of the token; if a value was provided, check that the value of
    # the token is what we expected.
    def match(self, expected_type, expected_value=None):
        token = self.lexer.get_token()
        if token.type == expected_type:
            if expected_value == None or \
                (expected_value != None and token.value == expected_value):
                return token.value
            else:
                raise PLSyntaxError("I expected '%s' but got '%s'" %
                        (expected_value, token.value))
        else:
            raise PLSyntaxError("I expected %s but got %s" % 
                    (expected_type, token.type))

    # -- The functions correponding to productions in the grammar
        
    def statement_list(self):
        dump('statement_list')
        while self.lexer.peek().type == LPAREN:
            self.lexer.get_token()
            statement = self.statement()
            self.match(RPAREN)
            yield statement.eval()

    def statement(self):
        dump('statement')
        token = self.lexer.peek()
        
        # assign_stmt
        if token.type == KEYWD and token.value == "define":
            self.match(KEYWD)
            dump('assign_stmt')
            target = self.match(ID)
            ast = self.atom()
            return AssignStmt(target=target, ast=ast,
                    context=self.global_context)

        # expr_stmt
        else: return self.expr_stmt()

    def expr_stmt(self):
        dump('expr_stmt')
        token = self.lexer.peek()
        
        # if-then-else expression
        if token.type == KEYWD and token.value == "if":
            dump('if_stmt')
            self.match(KEYWD)
            condition = self.atom()
            self.match(KEYWD, "then")
            then_block = self.expr_stmt()
            self.match(KEYWD, "else")
            else_block = self.expr_stmt()
            return IfThenElse(condition=condition, then_block=then_block,
                    else_block=else_block)
        
        # An operation
        if token.type == OP:
            operator = self.match(OP)
            operands = self.atom_list()
            return Op(name=operator, operands=operands)
            
        # atom
        else: return self.atom()

    def atom_list(self):
        dump('atom_list')
        atoms = []

        # Get as much atoms as possible
        while self.lexer.peek().type in [NUM, ID, LPAREN]:
            atoms.append(self.atom())

        return atoms

    def atom(self):
        dump('atom')
        token = self.lexer.get_token()
        dump(token.type)

        # A number
        if token.type == NUM:
            return Num(value=token.value)
        
        # An identifier
        elif token.type == ID:
            return Id(name=token.value, context=self.global_context)

        # ( expr_stmt )
        elif token.type == LPAREN:
            result = self.expr_stmt()
            self.match(RPAREN)
            return result

        else:
            raise PLSyntaxError("I did not expect %s" % token.type)


# A context acts as a dictionary that maps an identifier to a syntax tree. Not
# that useful for now, but it will be when the keyword 'let' is introduced.
class Context():

    def __init__(self, father):
        # 'father' is the context of which 'self' is a sub-context; that is,
        # the father is a broader context.
        # father == None for the global context
        self.father = father
        

    # Assign a syntax tree to a name
    def assign(self, target, ast):
        return setattr(self, target, ast)

    # Get the tree associated to a name, searching from the current context
    # outwards
    def fetch(self, target):
        if hasattr(self, target):   # If the name is defined in this context
            return getattr(self, target).eval()
        elif self.father != None:   # If this is not the global context
            return self.father.fetch(target)
        else:               
            raise UnknownIdError(target)

# A very simple interface: the string that the parser should parse is given as
# a command line argument.
if __name__ == '__main__':
    try:
        parser = Parser(
                keywords=['define', 'if', 'then', 'else'],
                operators=['+', '-', '*', '/', '<', '<=', '>', '>=', '=', '<>']
                )
        parser.parse(input=' '.join(sys.argv[1:]))
        for result in parser.eval():
            print ":", result
    except PLSyntaxError as e: exit()
    except: raise

#ifndef DATA_TREE_H
#define DATA_TREE_H

typedef struct data_tree data_tree;
struct data_tree
{
  char *id;
  int val;
  data_tree * left;
  data_tree * right;
};

data_tree * dt_add (data_tree * dt, char *ident, int value);
int dt_search (data_tree * dt, char *ident, int *error);
void dt_delete (data_tree ** dt);

#endif

#include <stdlib.h>
#include <string.h>
#include "data-tree.h"

#include "stdio.h"

data_tree *
dt_add (data_tree * dt, char *ident, int value)
{
  if (dt == NULL)
    {
      data_tree *d = malloc (sizeof (data_tree));
      d->left = NULL;
      d->right = NULL;
      d->id = malloc (strlen(ident) * sizeof(char));
      strcpy(d->id, ident);
      d->val = value;
      return d;
    }
  if (strcmp (dt->id, ident) == 0)
    dt->val = value;
  else if (strcmp (dt->id, ident) > 0)
    dt = dt_add (dt->left, ident, value);
  else
    dt = dt_add (dt->right, ident, value);

  return dt;
}

int
dt_search (data_tree * dt, char *ident, int *error)
{
  *error = 1;
  if (dt == NULL)
    return -1;
  
  if (strcmp (dt->id, ident) == 0)
    {
      *error = 0;
      return dt->val;
    }
  else if (strcmp (dt->id, ident) > 0)
    {
      int nb = dt_search (dt->left, ident, error);
      if (*error = 0)
	return nb;
    }
  else
    {
      int nb = dt_search (dt->right, ident, error);
      if (*error = 0)
	return nb;

      return 0;
    }
}

void
dt_delete (data_tree ** dt)
{
  if (*dt == NULL)
	  return;
  if ((*dt)->left != NULL)
    dt_delete (&((*dt)->left));
  if ((*dt)->right != NULL)
    dt_delete (&((*dt)->right));
  free((*dt)->id);
  free (*dt);
}

#ifndef LEXER_H
#define LEXER_H

#define MAX_DIGIT 40
#define MAX_ALPHA 40

enum
{ INT, KWD, IDENT };

typedef struct token token;
struct token
{
  token *next;
  void *data;
  int type;
};

token *gen_lexer (char *str, char *kwd[], int nb_kwd);
void next_token (token ** t);
void print_all_token (token *t);

#endif

#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "lexer.h"

void
print_all_token (token * t)
{
  if (t == NULL)
    {
      printf ("\n");
      return;
    }

  printf (" - ");
  if (t->type == INT)
    printf ("(INT : %d)", *((int *) t->data));
  else if (t->type == KWD)
    printf ("(KWD : %s)", (char *) t->data);
  else
    printf ("(IDENT : %s)", (char *) t->data);

  t = t->next;
  print_all_token (t);
}

int is_not_end (char t)
{
	return t != ' ' && t != '\n' && t != '\0';
}

void
del_space (char **str)
{
  while (**str == ' ' || **str == '\n' || **str == '\t')
    (*str)++;
}

token *
digit (char **str)
{
  token *tok = malloc (sizeof (token));

  char tmp[MAX_DIGIT];
  int i;
  int *nb = malloc (sizeof (int));

  for (i = 0; i < MAX_DIGIT && isdigit (**str); i++, (*str)++)
    tmp[i] = **str;

  *nb = atoi (tmp);
  tok->data = nb;
  tok->type = INT;

  return tok;
}

token *
string (char **str, char *kwd[], int nb_kwd)
{
  token *tok = malloc (sizeof (token));

  char tmp[MAX_ALPHA];
  char *data = NULL;
  int i;
  int boo = 1;

  for (i = 0; i < MAX_ALPHA && is_not_end(**str); i++, (*str)++)
  {
   if (i > 0 && (isdigit(**str) || *(*str-1) == '(' || **str == ')'))
	   break;
   else
    	tmp[i] = **str;
  }
  tmp[i] = '\0';

  data = malloc (i * sizeof (char));
  strcpy (data, tmp);
  tok->data = data;

  for (i = 0; i < nb_kwd && boo; i++)
    if (strcmp (data, kwd[i]) == 0)
      boo = 0;

  if (boo == 1)
    tok->type = IDENT;
  else
    tok->type = KWD;

  return tok;
}

token *
gen_lexer (char *str, char *kwd[], int nb_kwd)
{
  if (*str == '\0')
    return NULL;

  token *tok = NULL;
  del_space (&str);

  if (isdigit (*str))
    tok = digit (&str);
  else
    tok = string (&str, kwd, nb_kwd);
 
  tok->next = gen_lexer (str, kwd, nb_kwd);
  return tok;
}

void
next_token (token ** t)
{
  if (*t == NULL)
    return;
  token *next = (*t)->next;

  free ((*t)->data);
  free (*t);
  (*t) = next;
}

#ifndef PARSER_H
#define PARSER_H

#include "lexer.h"

enum e_expr
{ Int, Ident, Bin_Op, Un_Op, Define, If, Begin, While, Print};

enum e_bin_op
{ Add, Sub, Mul, Div, Equ, Dif, Sup, Low, E_Sup, E_Low, And, Or };

enum e_un_op
{ Not, Opp };

typedef struct s_bin_op s_bin_op;
struct s_bin_op
{
  enum e_bin_op type_op;
  void *expr1;
  void *expr2;
};

typedef struct s_un_op s_un_op;
struct s_un_op
{
  enum e_un_op type_op;
  void *expr;
};

typedef struct s_define s_define;
struct s_define
{
  char *id;
  void *expr_var;
};

typedef struct s_if s_if;
struct s_if
{
  void *expr_bool;
  void *expr_then;
  void *expr_else;
};

typedef struct s_while s_while;
struct s_while
{
  void *expr_bool;
  void *expr_then;
};

typedef struct s_begin s_begin;
struct s_begin
{
  void * seq;
};

typedef struct s_print s_print;
struct s_print
{
  void * expr;
};

typedef union u_expr u_expr;
union u_expr
{
  int nb;
  char *id;
  s_bin_op expr_bin_op;
  s_un_op expr_un_op;
  s_define expr_define;
  s_if expr_if;
  s_begin expr_begin;
  s_while expr_while;
  s_print expr_print;
};

typedef struct s_expr s_expr;
struct s_expr
{
  enum e_expr type_expr;
  u_expr expr;
};

typedef struct s_seq s_seq;
struct s_seq
{
  s_expr * expr;
  s_seq * next;
};
 
s_expr *parse_expr (token ** tok);
s_seq *parse_seq (token ** tok);

#endif

#include <stdlib.h>
#include <string.h>
#include "parser.h"
#include "lexer.h"

int
is_bin_op (char *op)
{
  return strcmp (op, "+") == 0 ||
    strcmp (op, "*") == 0 || strcmp (op, "/") == 0 || strcmp (op, "-") == 0 ||
    strcmp (op, "=") == 0 || strcmp (op, ">=") == 0 || strcmp (op, "<=") == 0
    || strcmp (op, "<") == 0 || strcmp (op, ">") == 0
    || strcmp (op, "<>") == 0 || strcmp (op, "and") == 0
    || strcmp (op, "or") == 0;
}

int
is_un_op (char *op)
{
  return strcmp (op, "!") == 0 || strcmp (op, "~") == 0;
}

enum e_bin_op
char_to_bin_op (char *op)
{
  if (strcmp (op, "*") == 0)
    return Mul;
  else if (strcmp (op, "/") == 0)
    return Div;
  else if (strcmp (op, "+") == 0)
    return Add;
  else if (strcmp (op, "-") == 0)
    return Sub;
  else if (strcmp (op, "=") == 0)
    return Equ;
  else if (strcmp (op, "<>") == 0)
    return Dif;
  else if (strcmp (op, ">") == 0)
    return Sup;
  else if (strcmp (op, "<") == 0)
    return Low;
  else if (strcmp (op, ">=") == 0)
    return E_Sup;
  else if (strcmp (op, "=<") == 0)
    return E_Low;
  else if (strcmp (op, "and") == 0)
    return And;
  else if (strcmp (op, "or") == 0)
    return Or;
}

enum e_un_op
char_to_un_op (char *op)
{
  if (strcmp (op, "!") == 0)
    return Not;
  else if (strcmp (op, "~") == 0)
    return Opp;
}


s_expr *
parse_expr (token ** tok)
{
  if (*tok == NULL)
  {
   return NULL;
  }

  s_expr *e = malloc (sizeof (s_expr));
  if ((*tok)->type == INT)
    {
      e->type_expr = Int;
      e->expr.nb = *((int *) (*tok)->data);
      next_token (tok);
    }
  else if ((*tok)->type == IDENT)
    {
      e->type_expr = Ident;
      char *ident = (char *) ((*tok)->data);
      e->expr.id = malloc (strlen (ident) * sizeof (char));
      strcpy (e->expr.id, ident);
      next_token (tok);
    }

  else if ((*tok)->type == KWD
	   && (strcmp ("define", (char *) ((*tok)->data)) == 0 ||
	       strcmp ("set", (char *) ((*tok)->data)) == 0))
    {
      e->type_expr = Define;

      next_token (tok);
      char *ident = (char *) ((*tok)->data);
      e->expr.expr_define.id = malloc (strlen (ident) * sizeof (char));
      strcpy (e->expr.expr_define.id, ident);

      next_token (tok);
      e->expr.expr_define.expr_var = parse_expr (tok);
    }
  else if ((*tok)->type == KWD && is_bin_op ((*tok)->data))
    {
      e->type_expr = Bin_Op;
      e->expr.expr_bin_op.type_op = char_to_bin_op ((char *) ((*tok)->data));
      next_token (tok);
      e->expr.expr_bin_op.expr1 = parse_expr (tok);
      e->expr.expr_bin_op.expr2 = parse_expr (tok);
    }
  else if ((*tok)->type == KWD && is_un_op ((*tok)->data))
    {
      e->type_expr = Un_Op;
      e->expr.expr_un_op.type_op = char_to_un_op ((char *) ((*tok)->data));
      next_token (tok);
      e->expr.expr_un_op.expr = parse_expr (tok);
    }
  else if ((*tok)->type == KWD && strcmp ("(", (char *) ((*tok)->data)) == 0)
    {
      next_token (tok);
      e = parse_expr (tok);
      next_token (tok);
    }
  else if ((*tok)->type == KWD && strcmp ("if", (char *) ((*tok)->data)) == 0)
    {
      e->type_expr = If;
      next_token (tok);
      e->expr.expr_if.expr_bool = parse_expr (tok);
      e->expr.expr_if.expr_then = parse_expr (tok);
      e->expr.expr_if.expr_else = parse_expr (tok);
    }
  else if ((*tok)->type == KWD && strcmp ("while", (char *) ((*tok)->data)) == 0)
    {
      e->type_expr = While;
      next_token (tok);
      e->expr.expr_while.expr_bool = parse_expr (tok);
      e->expr.expr_while.expr_then = parse_expr (tok);
    }
  else if ((*tok)->type == KWD && strcmp("begin", (char *) ((*tok)->data)) == 0)
  {
    e->type_expr = Begin;
    next_token (tok);
    e->expr.expr_begin.seq = parse_seq (tok);
  }
  else if ((*tok)->type == KWD && strcmp("print", (char *) ((*tok)->data)) == 0)
  {
    e->type_expr = Print;
    next_token (tok);
    e->expr.expr_print.expr = parse_expr (tok);
  }
  else
  {
    free(e);
    e = NULL;
  }
  return e;
}

s_seq * 
parse_seq (token ** tok)
{
  s_seq *s = malloc(sizeof (s_seq));
  s->expr = parse_expr (tok);
  if (s->expr == NULL)
  {
    free (s);
    s = NULL;
  }
  else
    s->next = parse_seq (tok);
  return s;
}

#include <stdlib.h>
#include <stdio.h>
#include "exec.h"

void delete_seq (s_seq ** s);

void
delete_expr (s_expr ** e)
{
  if ((*e)->type_expr == Ident)
    free ((*e)->expr.id);
  else if ((*e)->type_expr == Define)
  {
    
    free ((*e)->expr.expr_define.id);
    delete_expr ((s_expr **) &((*e)->expr.expr_define.expr_var));
  }
  else if ((*e)->type_expr == Bin_Op)
  {
    delete_expr ((s_expr **) &((*e)->expr.expr_bin_op.expr1));
    delete_expr ((s_expr **) &((*e)->expr.expr_bin_op.expr2));
  }
  else if ((*e)->type_expr == Un_Op)
    delete_expr ((s_expr **) &((*e)->expr.expr_un_op.expr));
  else if ((*e)->type_expr == If)
  {
    delete_expr ((s_expr **) &((*e)->expr.expr_if.expr_bool));
    delete_expr ((s_expr **) &((*e)->expr.expr_if.expr_then));
    delete_expr ((s_expr **) &((*e)->expr.expr_if.expr_else));
  }
  else if ((*e)->type_expr == While)
  {
    delete_expr ((s_expr **) &((*e)->expr.expr_while.expr_bool));
    delete_expr ((s_expr **) &((*e)->expr.expr_while.expr_then));
  }
  else if ((*e)->type_expr == Print)
    delete_expr ((s_expr **) &((*e)->expr.expr_print.expr));
  else if ((*e)->type_expr == Begin)
    delete_seq ((s_seq **) &((*e)->expr.expr_begin.seq));

  free (*e);
}

void
delete_seq (s_seq ** s)
{
  if (*s == NULL)
   return;
  delete_expr ((s_expr **) &((*s)->expr));
  delete_seq ((s_seq **) &((*s)->next));
  free(*s);
}

int
exec_bin_op (enum e_bin_op op, int a, int b)
{
  if (op == Add)
    return a + b;
  else if (op == Sub)
    return a - b;
  else if (op == Mul)
    return a * b;
  else if (op == Div)
    return a / b;
  else if (op == Equ)
    return a == b;
  else if (op == E_Sup)
    return a >= b;
  else if (op == E_Low)
    return a <= b;
  else if (op == Dif)
    return a != b;
  else if (op == Sup)
    return a > b;
  else if (op == Low)
    return a < b;
  else if (op == And)
    return a && b;
  else if (op == Or)
    return a || b;
}

int
exec_un_op (enum e_un_op op, int a)
{
  if (op == Not)
    return !a;
  if (op == Opp)
    return -a;
}

int
exec_expr (s_expr * e, data_tree ** dt)
{
  int nb;
  if (e->type_expr == Int)
    nb = e->expr.nb;
  else if (e->type_expr == Bin_Op)
    {
      enum e_bin_op op = e->expr.expr_bin_op.type_op;
      int nb1 = exec_expr ((s_expr *) e->expr.expr_bin_op.expr1, dt);
      int nb2 = exec_expr ((s_expr *) e->expr.expr_bin_op.expr2, dt);

      nb = exec_bin_op (op, nb1, nb2);
    }
  else if (e->type_expr == Un_Op)
  { 
	  enum e_un_op op = e->expr.expr_un_op.type_op;
	  int nb1 = exec_expr ((s_expr *) e->expr.expr_un_op.expr, dt);

	  nb = exec_un_op (op, nb1);
  }
  else if (e->type_expr == Ident)
    {
      int error;
      nb = dt_search (*dt, e->expr.id, &error);
      if (error == 1)
	printf ("ERROR :- no var named %s\n", e->expr.id);
    }
  else if (e->type_expr == Define)
    {
      nb = exec_expr ((e->expr.expr_define.expr_var), dt);
      *dt = dt_add (*dt, e->expr.expr_define.id, nb);
    }
  else if (e->type_expr == If)
    {
      if (exec_expr ((s_expr *) (e->expr.expr_if.expr_bool), dt))
	nb = exec_expr ((s_expr *) (e->expr.expr_if.expr_then), dt);
      else
	nb = exec_expr ((s_expr *) (e->expr.expr_if.expr_else), dt);
    }
  else if (e->type_expr == Begin)
    nb = exec_seq((s_seq *) e->expr.expr_begin.seq, dt);
  else if (e->type_expr == While)
    { 
      nb = 0;
      while (exec_expr (e->expr.expr_while.expr_bool, dt))
	nb = exec_expr (e->expr.expr_while.expr_then, dt);
    }
  else if (e->type_expr == Print)
   {
    nb = exec_expr((s_expr *) (e->expr.expr_print.expr), dt);
    printf("%d\n", nb);
   }
  

  return nb;
}

int 
exec_seq (s_seq * s, data_tree ** dt)
{
  int nb = exec_expr(s->expr, dt);
  if (s->next != NULL)
  	nb = exec_seq (s->next, dt);
  return nb;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lexer.h"
#include "parser.h"
#include "exec.h"

#define MAX_INPUT 200

void read (char * t)
{
  int i;
  int nb_pth = 1;
  t[0] = fgetc(stdin); 

  for (i = 1; i < MAX_INPUT-1 && nb_pth > 0; i++)
  {
    t[i] = fgetc(stdin);	  
    if (t[i] == '(')
	nb_pth++;
    else if (t[i] == ')')
	nb_pth--;
  }
  fgetc(stdin); 
  t[i] = '\0';  
}

int
main (void)
{
  char *kwd[] = { "+", "-", "/", "*", "~", "(", ")", "define", "set",  "if",
	  "and", "or", "=", ">=", "<=", "<", ">", "<>", "!", 
	  "print", "begin", "while"};
  data_tree * dt = NULL;

  while (1)
  {
    char str[MAX_INPUT] = {0};
    read(str);
    if (strcmp(str, "(end)") == 0)
	    break;

    token *lex = gen_lexer (str, kwd, 22);
   print_all_token (lex);
    s_seq *seq = parse_seq (&lex);
   printf (" - Result :- %d\n", exec_seq (seq, &dt));
    delete_seq (&seq);
  }

  dt_delete(&dt);
  return 1;
}