path: root/src/frontend/parser.c

#ifndef PARSER_C
#define PARSER_C PARSER_C
#include <parser.h>

struct AST* parse_source(struct Translation_Data *translation_data)
{
	return (struct AST*)parse_translation_unit(translation_data);
}
/*
 * translation-unit: (machine)*
 */
struct AST_Translation_Unit* parse_translation_unit(struct Translation_Data *translation_data)
{
	struct Queue *machines;
	struct Map *hold_command_map;
	struct Map *hold_machines_map;
	struct AST_Machine *hold_machine;
	struct AST_Machine *hold_possible_duplicate;

	machines=calloc(1,sizeof(struct Queue));

	hold_command_map=malloc(sizeof(struct Map));
	Map_Init(hold_command_map);

	hold_machines_map=malloc(sizeof(struct Map));
	Map_Init(hold_machines_map);

	translation_data->hold_command_map=hold_command_map;

	while(!get_and_check(translation_data,KW_EOF))
	{
		hold_machine=parse_machine(translation_data);
		if(hold_machine)
		{
			if(hold_possible_duplicate=Map_Check(hold_machines_map,hold_machine->id->data,hold_machine->id->size))
			{
				push_error_with_token("duplicate machine name",hold_machine->id,translation_data);
				push_error_with_token("conflicts with",hold_possible_duplicate->id,translation_data);
				delete_ast_machine(hold_machine);
				return NULL;
			}else
			{
				Map_Push(hold_machines_map,hold_machine->id->data,hold_machine->id->size,hold_machine);
				Queue_Push(machines,hold_machine);
			}
		}
		else
		{
			return NULL;
		}
	}
	return get_ast_translation_unit(machines,hold_command_map,hold_machines_map);
}
/*
 * machine: 'machine' id '[' machine-inner ']' ';'
 *
 */
struct AST_Machine* parse_machine(struct Translation_Data *translation_data)
{
	struct AST_Machine *ret;
	struct token *hold_id;
	if(get_and_check(translation_data,KW_MACHINE))
	{
		if(get_kw(translation_data)==KW_ID) 
		{
			hold_id=Queue_Pop(translation_data->tokens);
			if(get_and_check(translation_data,KW_OPEN_SQUARE))
			{
				ret=(struct AST_Machine*)parse_machine_inner(hold_id,translation_data);
				if(has_new_errors(translation_data))
				{
					touch_errors(translation_data);

					return NULL;
				}
				if(get_and_check(translation_data,KW_CLOSE_SQUARE))
				{
					if(get_and_check(translation_data,KW_SEMI_COLUMN))
						return ret;
					else
					{
						push_parsing_error("';' expected after machine definition",translation_data);
						return NULL;
					}
				}else
				{
					push_parsing_error("closing ']' expected",translation_data);
					return NULL;
				}
			}else
			{
				push_parsing_error("opening '[' expected",translation_data);
				return NULL;
			}
		}else
		{
				push_parsing_error("expected a name for the machine",translation_data);
				return NULL;
		}
	}else
	{
		push_parsing_error("'machine' expected",translation_data);
		return NULL;
	}
}
/*
 * machine-inner : 'states' '[' states-inner ']' ';'
 * 		   'events' '[' events-inner ']' ';'
 * 		   'transitions' '[' transitions-inner ']' ';'
 * 		   'starting' start-on-inner ';'
 */
struct AST_Machine* parse_machine_inner(struct token *machine_id,struct Translation_Data *translation_data)
{
	struct AST_States *states=NULL;
	struct AST_Events *events=NULL;
	struct AST_Transitions *transitions=NULL;
	struct AST_State *starting_state=NULL;
	unsigned char i;
	for(i=0;i<4;++i)
		switch(get_kw(translation_data))
		{
			case KW_STATES:
				if(states)
				{
					push_parsing_error("defining two sets of states",translation_data);
					goto error_cleanup;
				}else
				{
					chomp(translation_data);
					if(get_and_check(translation_data,KW_OPEN_SQUARE))
					{
						states=parse_states_inner(translation_data);
						if(!get_and_check(translation_data,KW_CLOSE_SQUARE) 
								|| !get_and_check(translation_data,KW_SEMI_COLUMN))
						{
							push_parsing_error("expected ']' and ';' at "
									"end of states definition",translation_data);
							goto error_cleanup;
						}

					}else
					{
						push_parsing_error("expected '[' ",translation_data);
						goto error_cleanup;
					}
				}
				break;
			case KW_TRANSITIONS:
				if(states==NULL && events==NULL)
				{
					push_parsing_error("defining transitions before states and events",translation_data);
					goto error_cleanup;
				}else if(transitions)
				{
					push_parsing_error("defining two sets of transitions",translation_data);
					goto error_cleanup;
				}else
				{
					chomp(translation_data);
					if(get_and_check(translation_data,KW_OPEN_SQUARE))
					{
						transitions=parse_transitions_inner(translation_data,states,events);
						if(!get_and_check(translation_data,KW_CLOSE_SQUARE) 
								|| !get_and_check(translation_data,KW_SEMI_COLUMN))
						{
							push_parsing_error("expected ']' and ';' at "
									"end of transitions definition",translation_data);
							goto error_cleanup;
						}
					}else
					{
						push_parsing_error("expected '[' ",translation_data);
						goto error_cleanup;
					}
				}
				break;
			case KW_EVENTS:
				if(events)
				{
					push_parsing_error("defining two sets of transitions",translation_data);
					goto error_cleanup;
				}else
				{
					chomp(translation_data);
					if(get_and_check(translation_data,KW_OPEN_SQUARE))
					{
						events=parse_events_inner(translation_data);
						if(!get_and_check(translation_data,KW_CLOSE_SQUARE) 
								|| !get_and_check(translation_data,KW_SEMI_COLUMN))
						{
							push_parsing_error("expected ']' and ';' at "
									"end of events definition",translation_data);
							goto error_cleanup;
						}
					}else
					{
						push_parsing_error("expected '[' ",translation_data);
						goto error_cleanup;
					}
				}
				break;
			case KW_STARTING:
				chomp(translation_data);
				if(!starting_state)
				{
					if(states)
					{
						starting_state=parse_start_on(translation_data,states);
						if(!get_and_check(translation_data,KW_SEMI_COLUMN))
						{
							push_parsing_error("expected ';' at end "
									"of starting state declaration",translation_data);
							goto error_cleanup;
						}
					}else
					{
						push_parsing_error("states need to be defined"
							" before defining a starting one",translation_data);
						goto error_cleanup;
					}
				}else
				{
					push_parsing_error("starting state is defined",translation_data);
					goto error_cleanup;
				}
				break;
			default:
				push_parsing_error("expected states transitions or events",translation_data);
				goto error_cleanup;

		}

	return get_ast_machine(machine_id,states,events,transitions,starting_state);

error_cleanup:
	push_parsing_error("in machine",translation_data);
	return NULL;
}
/*
 * states-inner: state (, state)*
 * 
 */
struct AST_States* parse_states_inner(struct Translation_Data *translation_data)
{
	struct Queue *ids;
	struct AST_State *hold_state;
	
	ids=parse_list((struct AST*(*)(struct Translation_Data*))parse_state,translation_data,KW_COMMA);
	if(ids->size==0)
	{
		push_parsing_error("there needs to be atleast one state",translation_data);
		free(ids);
		return NULL;
	}else
	{

		return get_ast_states(ids,translation_data);
	}
}
/*
 * state : id [ '[' ( 'on' 'entering' statement | 'on 'exiting'  statement )* ']' ]
 *
 */
struct AST_State* parse_state(struct Translation_Data *translation_data)
{
	struct token *hold_id;
	struct AST *hold_entry=NULL;
	struct AST *hold_exit=NULL;
	int i;

	if(get_kw(translation_data)==KW_ID)
	{
		hold_id=Queue_Pop(translation_data->tokens);

		if(get_and_check(translation_data,KW_OPEN_SQUARE))
		{
			for(i=0;i<2;++i)
				if(get_and_check(translation_data,KW_ON))
				{
					if(get_and_check(translation_data,KW_ENTERING))
						hold_entry=parse_statement(translation_data);
					else if(get_and_check(translation_data,KW_EXITING))
						hold_exit=parse_statement(translation_data);
					else 
						break;
				}
			if(get_and_check(translation_data,KW_CLOSE_SQUARE))
			{
			}else
			{
				if(hold_entry)
				       	delete_ast(hold_entry);
				if(hold_exit)
					delete_ast(hold_exit);
				delete_token(hold_id);
				push_parsing_error("missing closing ']' in state definition",translation_data);
				return NULL;
			}

		}
		return get_ast_state(hold_id,hold_entry,hold_exit);
	}else
	{
		return NULL;
	}
}
/*
 * events-inner: id (, id)*
 * 
 */
struct AST_Events* parse_events_inner(struct Translation_Data *translation_data)
{
	struct Queue *ids;
	ids=parse_list((struct AST*(*)(struct Translation_Data*))parse_event,translation_data,KW_COMMA);
	if(ids->size==0)
	{
		push_parsing_error("there needs to be atleast one event",translation_data);
		return NULL;
	}else
	{
		return get_ast_events(ids);
	}
}
struct AST_Event* parse_event(struct Translation_Data *translation_data)
{
	if(get_kw(translation_data)==KW_ID)
		return get_ast_event(Queue_Pop(translation_data->tokens));
	else
		return NULL;
}
/*
 * transitions-inner: ( transition ;)*
 */
struct AST_Transitions* parse_transitions_inner(struct Translation_Data *translation_data,struct AST_States *states,struct AST_Events *events)
{
	struct Queue *transitions;
	struct AST_Transition *hold_transition;

	transitions=malloc(sizeof(struct Queue));
	Queue_Init(transitions);
	
	while((hold_transition=parse_transition(translation_data,states,events))!=NULL)
	{
		Queue_Push(transitions,hold_transition);
	}

	if(transitions->size==0)
	{
		push_parsing_error("there are no transitions",translation_data);
		return NULL;
	}else if(has_new_errors(translation_data))
	{
		push_parsing_error("in transition",translation_data);
		return NULL;
	}else
	{
		return get_ast_transitions(transitions);
	}
}
/*
 * transition: 'from' state_id 'to' state_id 'on' 'event' event_id [ granted-part ] [ statement-part ]
 *
 */
struct AST_Transition* parse_transition(struct Translation_Data *translation_data,struct AST_States *states,struct AST_Events *events)
{
	struct AST_Transition *ret;
	struct AST_State *hold_from;
	struct AST_State *hold_to;
	struct AST_Event *hold_event;
	struct AST *hold_statement=NULL;
	struct AST *hold_granted=NULL;
	struct token *hold_token;

	if(get_and_check(translation_data,KW_FROM))
	{
		if(get_kw(translation_data)==KW_ID)
		{
			hold_token=Queue_Pop(translation_data->tokens);
			hold_from=Map_Check(states->states_map,hold_token->data,hold_token->size);
			if(hold_from!=NULL)
			{
				if(get_and_check(translation_data,KW_TO))
				{
					if(get_kw(translation_data)==KW_ID)
					{
						hold_token=Queue_Pop(translation_data->tokens);
						hold_to=Map_Check(states->states_map,hold_token->data,hold_token->size);
						delete_token(hold_token);
						if(hold_to!=NULL)
						{
							if(get_and_check(translation_data,KW_ON) && get_and_check(translation_data,KW_EVENT) )
							{
								if(get_kw(translation_data)==KW_ID)
								{
									hold_token=Queue_Pop(translation_data->tokens);
									hold_event=Map_Check(events->events_map,hold_token->data,hold_token->size);
									delete_token(hold_token);
									if(hold_event!=NULL)
									{
										hold_granted=parse_transition_granted(translation_data,states,events);
										
					if(!get_and_check(translation_data,KW_SEMI_COLUMN) && (hold_statement=parse_statement(translation_data))==NULL)
						{ push_parsing_error("in statement of transition",translation_data); return NULL; }

										/*GOAL!!!!!*/
										return get_ast_transition(hold_from,hold_to,hold_event,hold_granted,hold_statement);
									}else { push_parsing_error("event not defined",translation_data); return NULL; }
								}else { push_parsing_error("no event name given in transition",translation_data); return NULL; }
							}else { push_parsing_error("expected 'on event'",translation_data); return NULL; }	
						}else { push_parsing_error("using undefined to state in transition",translation_data); }
					}else { push_parsing_error("expected id in transition expression",translation_data); return NULL; }
				}else { push_parsing_error("expected 'to'",translation_data); return NULL; }	
			}else { push_parsing_error("using undefined from state in transition",translation_data); return NULL; }
		}else { push_parsing_error("expected state id in from field",translation_data); return NULL; }
	}else { return NULL; }
}

/*
 * granted-part : 'granted' expression
 */
struct AST* parse_transition_granted(struct Translation_Data *translation_data,struct AST_States *states,struct AST_Events *events)
{
	if(get_and_check(translation_data,KW_GRANTED))
	{
		return parse_expression(translation_data);
	}else
	{
		return NULL;
	}
}

/*
 * statement : 'execute' pipeline ; | 'if' expression statement [ else statement ]
 */
struct AST* parse_statement(struct Translation_Data *translation_data)
{
	struct AST *hold_expression;
	struct AST *hold_body;
	struct AST *hold_else=NULL;

	if(get_and_check(translation_data,KW_EXECUTE))
	{
		hold_body=(struct AST*)parse_pipeline(translation_data);
		if(get_and_check(translation_data,KW_SEMI_COLUMN))
		{
			return hold_body;
		}else
		{
			push_parsing_error("expected ';' at the end of pipeline",translation_data);
			return NULL;
		}
	}else if(get_and_check(translation_data,KW_IF))
	{
		hold_expression=parse_expression(translation_data);
		hold_body=parse_statement(translation_data);
		if(hold_body)
		{
			if(get_and_check(translation_data,KW_ELSE))
			{
				hold_else=parse_statement(translation_data);
				if(hold_else==NULL)
				{
					push_parsing_error("expected a statement after else",translation_data);	
					return NULL;
				}
			}
			return (struct AST*)get_ast_if_statement(hold_expression,hold_body,hold_else);
		}else
		{
			push_parsing_error("expected body statement in if",translation_data);
			return NULL;
		}
	}else
	{
		return NULL;
	}
}
/*
 * pipeline: [ command ( | command )* ]
 *
 */
struct AST_Pipeline* parse_pipeline(struct Translation_Data *translation_data)
{
	struct Queue *pipeline;
	pipeline=parse_list((struct AST*(*)(struct Translation_Data*))parse_command,translation_data,KW_PIPE);
	if(pipeline->size==0)
	{
		free(pipeline);
		push_parsing_error("pipeline is empty",translation_data);
		return NULL;
	}else
	{
		return get_ast_pipeline(pipeline);
	}
}
/*
 * command: id [ string ]
 *
 */
struct AST_Command* parse_command(struct  Translation_Data *translation_data)
{
	struct token *id;
	struct token *string=NULL;
	struct AST_Command *ret;

	if(get_kw(translation_data)==KW_ID)
	{
		id=Queue_Pop(translation_data->tokens);
		if(get_kw(translation_data)==KW_STRING)
			string=Queue_Pop(translation_data->tokens);
		ret=get_ast_command(id,string);
		if(!Map_Check(translation_data->hold_command_map,ret->function_name->data,ret->function_name->size))
			Map_Push(translation_data->hold_command_map,ret->function_name->data,ret->function_name->size,ret);

		return ret;
	}else
	{
		push_parsing_error("expected command id",translation_data);
		return NULL;
	}
}
/*
 * starting-on-inner: 'on' id ;
 */
struct AST_State* parse_start_on(struct Translation_Data *translation_data,struct AST_States *states)
{
	struct token *hold_id;
	struct AST_State *hold_state;

	if(get_and_check(translation_data,KW_ON))
	{
		if(get_kw(translation_data)==KW_ID)
		{
			hold_id=Queue_Pop(translation_data->tokens);
			hold_state=Map_Check(states->states_map,hold_id->data,hold_id->size);
			free(hold_id);
			if(hold_state)
			{

					return hold_state;

			}else { push_parsing_error("starting state is not defined",translation_data); return NULL; }
		}else { push_parsing_error("expected an identifier for starting state",translation_data); return NULL; }
	}else { push_parsing_error("expected 'on'",translation_data); return NULL; }
}
struct AST_State* get_ast_state(struct token *id,struct AST *entry,struct AST *exit)
{
	struct AST_State *ret;
	assert(entry==NULL || entry->type==AST_TYPE_COMMAND || entry->type==AST_TYPE_PIPELINE || entry->type==AST_TYPE_IF);
	assert(exit==NULL || exit->type==AST_TYPE_COMMAND || exit->type==AST_TYPE_PIPELINE || exit->type==AST_TYPE_IF);

	ret=malloc(sizeof(struct AST_State));
	ret->type=AST_TYPE_STATE;
	ret->name=id;
	ret->on_entry_statement=entry;
	ret->on_exit_statement=exit;
	
	/*number is assigned in get_ast_states*/
	/*parent machine is determined in anotation stage*/

	return ret;
}
struct AST_Event* get_ast_event(struct token *id)
{
	struct AST_Event *ret;

	ret=malloc(sizeof(struct AST_Event));

	ret->name=id;

	return ret;
}
struct AST_States* get_ast_states(struct Queue *states,struct Translation_Data *translation_data)
{
	struct AST_States *ret;
	struct AST_State *hold_state;

	/*perhaps no states error should be handled here*/
	assert(states && states->size>0);

	ret=malloc(sizeof(struct AST_States)+sizeof(struct AST_Event *[states->size]));
	ret->type=AST_TYPE_STATES;
	ret->number_of_states=states->size;
	ret->states_map=malloc(sizeof(struct Map));

	Map_Init(ret->states_map);

	while(states->size>0)
	{
		hold_state=Queue_Pop(states);

		if(Map_Check(ret->states_map,hold_state->name->data,hold_state->name->size))
		{
			size_t i;

			push_error_with_token("duplicate state in states definition",hold_state->name,translation_data);

			for(i=states->size+1;i<ret->number_of_states;++i)
				delete_ast_state(ret->states[i]);
			delete_ast_state(hold_state);
			while(states->size>0)
				delete_ast_state(Queue_Pop(states));

			return NULL;
		}else
		{
			Map_Push(ret->states_map,hold_state->name->data,hold_state->name->size,hold_state);
		}

		ret->states[states->size]=hold_state;
		hold_state->number=states->size;
	}

	assert(states->size==0);
	free(states);

	return ret;
}
struct AST_Events* get_ast_events(struct Queue *events)
{
	struct AST_Events *ret;
	struct AST_Event *hold_event;

	/*perhaps no events error should be handled here*/
	assert(events && events->size>0);

	ret=malloc(sizeof(struct AST_Events)+sizeof(struct AST_Event *[events->size]));
	ret->type=AST_TYPE_EVENTS;
	ret->number_of_events=events->size;
	ret->events_map=malloc(sizeof(struct Map));

	Map_Init(ret->events_map);

	while(events->size>0)
	{
		hold_event=Queue_Pop(events);
		/*TODO check for redeclaration*/
		Map_Push(ret->events_map,hold_event->name->data,hold_event->name->size,hold_event);
		ret->events[events->size]=hold_event;
	}

	assert(events->size==0);
	free(events);

	return ret;
}
struct AST_Transition* get_ast_transition(struct AST_State *from,struct AST_State *to,struct AST_Event *event,struct AST *granted,struct AST *statement)
{
	struct AST_Transition *ret;
	ret=malloc(sizeof(struct AST_Transition));
	ret->type=AST_TYPE_TRANSITION;
	ret->from=from;
	ret->to=to;
	ret->event=event;
	ret->granted=granted;
	ret->statement=statement;

	return ret;
}
struct AST_Command* get_ast_command(struct token *function_name,struct token *argument)
{
	struct AST_Command *ret;
	ret=malloc(sizeof(struct AST_Command));
	ret->type=AST_TYPE_COMMAND;
	ret->function_name=function_name;
	ret->argument=argument;

	return ret;
}
struct AST_Pipeline* get_ast_pipeline(struct Queue *pipeline)
{
	struct AST_Pipeline *ret;

	ret=malloc(sizeof(struct AST_Pipeline)+sizeof(struct AST_Command *[pipeline->size]));
	ret->type=AST_TYPE_PIPELINE;
	ret->size=pipeline->size;
	pointer_array_fill((void**)ret->pipeline,pipeline);

	assert(pipeline->size==0);
	free(pipeline);

	return ret;
}
struct AST_Machine* get_ast_machine(struct token *id,struct AST_States *states,struct AST_Events *events,struct AST_Transitions *transitions,struct AST_State *starting_state)
{
	struct AST_Machine *ret;

	ret=malloc(sizeof(struct AST_Machine));
	ret->type=AST_TYPE_MACHINE;
	ret->id=id;
	ret->states=states;
	ret->events=events;
	ret->transitions=transitions;
	ret->starting_state=starting_state;

	return ret;
}
struct AST_Transitions* get_ast_transitions(struct Queue *transitions)
{
	struct AST_Transitions *ret;
	ret=malloc(sizeof(struct AST_Transitions)+sizeof(struct AST_Transition *[transitions->size]));
	ret->type=AST_TYPE_TRANSITIONS;
	ret->size=transitions->size;

	pointer_array_fill((void**)ret->transitions,transitions);

	assert(transitions->size==0);
	free(transitions);

	return ret;
}
void delete_ast(struct AST* ast)
{
	switch(ast->type)
	{
		case AST_TYPE_MACHINE:
			delete_ast_machine((struct AST_Machine*)ast);
			break;
		case AST_TYPE_STATE:
			delete_ast_state((struct AST_State*)ast);
			break;
		case AST_TYPE_STATES:
			delete_ast_states((struct AST_States*)ast);
			break;
		case AST_TYPE_EVENT:
			delete_ast_event((struct AST_Event*)ast);
			break;
		case AST_TYPE_EVENTS:
			delete_ast_events((struct AST_Events*)ast);
			break;
		case AST_TYPE_TRANSITION:
			delete_ast_transition((struct AST_Transition*)ast);
			break;
		case AST_TYPE_TRANSITIONS:
			delete_ast_transitions((struct AST_Transitions*)ast);
			break;
		case AST_TYPE_COMMAND:
			delete_ast_command((struct AST_Command*)ast);
			break;
		case AST_TYPE_PIPELINE:
			delete_ast_pipeline((struct AST_Pipeline*)ast);
			break;
		case AST_TYPE_TRANSLATION_UNIT:
			delete_ast_translation_unit((struct AST_Translation_Unit*)ast);
			break;
		case AST_TYPE_OP_AND:
		case AST_TYPE_OP_OR:
		case AST_TYPE_OP_SELECTOR:
			delete_ast_binary_expression((struct AST_Binary_Expression*)ast);
			break;
		case AST_TYPE_OP_NOT:
			delete_ast_unary_expression((struct AST_Unary_Expression*)ast);
			break;
		case AST_TYPE_UNFINISHED_STATE:
			delete_ast_unchecked_state((struct AST_Unchecked_State*)ast);
			break;
		case AST_TYPE_IF:
			delete_ast_if_statement((struct AST_If_Statement*)ast);
			break;
	}
}
void delete_ast_event(struct AST_Event* ast)
{
	if(ast==NULL)return;
	delete_token(ast->name);
	free(ast);
}
void delete_ast_states(struct AST_States* ast)
{
	size_t i;
	if(ast==NULL)return;
	for(i=0;i<ast->number_of_states;++i)
		delete_ast_state(ast->states[i]);
	free(ast);
}
void delete_ast_events(struct AST_Events* ast)
{
	size_t i;
	if(ast==NULL)return;
	for(i=0;i<ast->number_of_events;++i)
		delete_ast_event(ast->events[i]);
	free(ast);
}
void delete_ast_transition(struct AST_Transition* ast)
{
	if(ast==NULL)return;
	if(ast->statement!=NULL)
		delete_ast(ast->statement);
	free(ast);
}
void delete_ast_command(struct AST_Command* ast)
{
	if(ast==NULL)return;
	delete_token(ast->function_name);
	if(ast->argument!=NULL)
		delete_token(ast->argument);
	free(ast);
}
void delete_ast_pipeline(struct AST_Pipeline* ast)
{
	size_t i;
	if(ast==NULL)return;
	free(ast);
}
void delete_ast_machine(struct AST_Machine* ast)
{
	if(ast==NULL)return;
	if(ast->id!=NULL)
		delete_token(ast->id);
	if(ast->states!=NULL)
		delete_ast_states(ast->states);
	if(ast->events!=NULL)
		delete_ast_events(ast->events);
	if(ast->transitions!=NULL)
		delete_ast_transitions(ast->transitions);
}
void delete_ast_transitions(struct AST_Transitions* ast)
{
	size_t i;
	if(ast==NULL)return;
	for(i=0;i<ast->size;++i)
		delete_ast_transition(ast->transitions[i]);
	free(ast);
}
void delete_ast_state(struct AST_State* ast)
{
	if(ast==NULL)return;
	if(ast->name!=NULL)
		delete_token(ast->name);
	free(ast);
}
void pointer_array_fill(void **array,struct Queue *q)
{
	size_t i;
	for(i=0;q->size>0;++i)
		array[i]=Queue_Pop(q);
}

struct Queue* parse_list(struct AST *(*parser)(struct Translation_Data*),struct Translation_Data *translation_data,enum Keyword delim)
{
	struct Queue *q;
	struct AST* hold_ast;

	q=malloc(sizeof(struct Queue));
	Queue_Init(q);
	while(hold_ast=parser(translation_data))
	{
		Queue_Push(q,hold_ast);
		if(!get_and_check(translation_data,delim))
			break;
	}
	return q;
}

void delete_ast_translation_unit(struct AST_Translation_Unit *ast)
{
	size_t i;
	Map_Map(ast->used_commands_map,(void (*)(void*))delete_ast_command);
	Map_Destroy(ast->used_commands_map);
	for(i=0;i<ast->number_of_machines;++i)
	{
		delete_ast_machine(ast->machines[i]);
	}
	free(ast->used_commands_map);
	free(ast);
}
struct AST_Translation_Unit* get_ast_translation_unit(struct Queue *machines,struct Map *command_map,struct Map *machines_map)
{
	struct AST_Translation_Unit *ret;
	struct AST_Machine *hold_machine;

	ret=malloc(sizeof(struct AST_Translation_Unit)+sizeof(struct AST_Machine *[machines->size]));
	ret->type=AST_TYPE_TRANSLATION_UNIT;
	ret->used_commands_map=command_map;
	ret->machines_map=machines_map;
	ret->number_of_machines=machines->size;

	while(machines->size>0)
	{
		hold_machine=Queue_Pop(machines);
		ret->machines[machines->size]=hold_machine;
	}

	return ret;
}
/*
 * expression: or-expression
 */
struct AST* parse_expression(struct Translation_Data *translation_data)
{
	return parse_or_expression(translation_data);
}
/*
 * or-expression: and-expression [ || and-expression ]
 */
struct AST* parse_or_expression(struct Translation_Data *translation_data)
{
	struct AST *hold_left_expression;
	struct AST *hold_right_expression;

	hold_left_expression=parse_and_expression(translation_data);
	if(hold_left_expression==NULL)
		return NULL;

	if(get_and_check(translation_data,KW_OR))
	{
		hold_right_expression=parse_and_expression(translation_data);
		if(hold_right_expression==NULL)
		{
			push_parsing_error("expected expression in right side of ||",translation_data);
			delete_ast(hold_left_expression);
			return NULL;
		}
		return (struct AST*)get_ast_binary_expression(hold_left_expression,hold_right_expression,AST_TYPE_OP_OR);
	}else
	{
		return hold_left_expression;
	}

}
/*
 * and-expression: not-expression [ && not-expression ]
 */
struct AST* parse_and_expression(struct Translation_Data *translation_data)
{
	struct AST *hold_left_expression;
	struct AST *hold_right_expression;

	hold_left_expression=parse_not_expression(translation_data);
	if(hold_left_expression==NULL)
		return NULL;

	if(get_and_check(translation_data,KW_AND))
	{
		hold_right_expression=parse_not_expression(translation_data);
		if(hold_right_expression==NULL)
		{
			push_parsing_error("expected expression in right side of &&",translation_data);
			delete_ast(hold_left_expression);
			return NULL;
		}
		return (struct AST*)get_ast_binary_expression(hold_left_expression,hold_right_expression,AST_TYPE_OP_AND);
	}else
	{
		return hold_left_expression;
	}
}
/*
 * not-expression: [!]primary-expression
 */
struct AST* parse_not_expression(struct Translation_Data *translation_data)
{
	struct AST *hold_expression;
	if(get_and_check(translation_data,KW_NOT))
	{
		hold_expression=parse_primary_expression(translation_data);
		if(hold_expression!=NULL)
		{
			return (struct AST*)get_ast_unary_expression(hold_expression,AST_TYPE_OP_NOT);
		}else
		{
			push_parsing_error("in '!' expression",translation_data);
			return NULL;
		}
	}
		return parse_primary_expression(translation_data);
}
/*
 * primary-expression: (expression) | id.id
 */
struct AST* parse_primary_expression(struct Translation_Data *translation_data)
{
	struct AST *hold_expression;
	struct AST_Unchecked_State *hold_id1;
	struct AST_Unchecked_State *hold_id2; 

	if(get_and_check(translation_data,KW_OPEN_NORMAL))
	{
		hold_expression=parse_expression(translation_data);
		if(get_and_check(translation_data,KW_CLOSE_NORMAL))
		{
			return hold_expression;
		}else
		{
			push_parsing_error("expected ')' in expression",translation_data);
			delete_ast(hold_expression);
			return NULL;
		}

	}else if(get_kw(translation_data)==KW_ID)
	{
		hold_id1=get_ast_unchecked_state(Queue_Pop(translation_data->tokens));
		if(get_and_check(translation_data,KW_DOT))
		{
			if(get_kw(translation_data)==KW_ID)
			{
				hold_id2=get_ast_unchecked_state(Queue_Pop(translation_data->tokens));
				return (struct AST*)get_ast_binary_expression((struct AST*)hold_id1,(struct AST*)hold_id2,AST_TYPE_OP_SELECTOR);
			}else
			{
				push_parsing_error("expected a state id in selector",translation_data);
				delete_ast((struct AST*)hold_id1);
				return NULL;
			}	
		}else
		{
			delete_ast((struct AST*)hold_id1);
			push_parsing_error("expected a selector",translation_data);
			return NULL;
		}
	}else
	{
		push_parsing_error("expected an expression",translation_data);
		return NULL;
	}
}
struct AST_Binary_Expression* get_ast_binary_expression(struct AST *left,struct AST *right,enum AST_Type type)
{
	struct AST_Binary_Expression *ret;

	ret=malloc(sizeof(struct AST_Binary_Expression));
	ret->type=type;
	ret->left=left;
	ret->right=right;

	return ret;
}
struct AST_Unary_Expression* get_ast_unary_expression(struct AST *operand,enum AST_Type type)
{

	struct AST_Unary_Expression *ret;

	ret=malloc(sizeof(struct AST_Unary_Expression));	

	ret->type=type;
	ret->operand=operand;

	return ret;
}
struct AST_Unchecked_State* get_ast_unchecked_state(struct token *name)
{
	struct AST_Unchecked_State *ret;

	ret=malloc(sizeof(struct AST_Unchecked_State));
	ret->type=AST_TYPE_UNFINISHED_STATE;
	ret->name=name;

	return ret;
}
struct AST_If_Statement* get_ast_if_statement(struct AST *condition,struct AST *body,struct AST *else_statement)
{
	struct AST_If_Statement *ret;

	ret=malloc(sizeof(struct AST_If_Statement));
	ret->type=AST_TYPE_IF;
	ret->condition=condition;
	ret->body=body;
	ret->else_statement=else_statement;

	return ret;
}

struct AST_State* ast_check_state(struct AST_Unchecked_State *state,struct AST_States *states,struct Translation_Data *translation_data)
{
	struct AST_State *ret;
	ret=Map_Check(states->states_map,state->name->data,state->name->size);
	if(ret==NULL)
	{
		push_error_with_token("undefined state",state->name,translation_data);
		delete_ast_unchecked_state(state);
		return NULL;
	}else
	{
		delete_ast_unchecked_state(state);
		return ret;	
	}
}

void delete_ast_binary_expression(struct AST_Binary_Expression *ast)
{
	if(ast->right)
		delete_ast(ast->right);
	if(ast->left)
		delete_ast(ast->left);
	free(ast);
}
void delete_ast_unary_expression(struct AST_Unary_Expression *ast)
{
	if(ast->operand)
		delete_ast(ast->operand);
	free(ast);
}
void delete_ast_unchecked_state(struct AST_Unchecked_State *ast)
{
	delete_token(ast->name);
	free(ast);
}
void delete_ast_if_statement(struct AST_If_Statement *ast)
{
	delete_ast(ast->condition);
	delete_ast(ast->body);
	if(ast->else_statement)
		delete_ast(ast->else_statement);
}
#endif