From 043c05bc2f9a922559a4b33ee6ec7d6069ae0b11 Mon Sep 17 00:00:00 2001 From: Lukas Jiriste Date: Wed, 10 Jul 2024 19:34:30 +0200 Subject: [PATCH] Add the translation from state graph to table This compiles but crashes. --- ft_parse/ft_parsing_table_generate.c | 195 ++++++++++++++++++++++++++- 1 file changed, 192 insertions(+), 3 deletions(-) diff --git a/ft_parse/ft_parsing_table_generate.c b/ft_parse/ft_parsing_table_generate.c index db5617d..42d463c 100644 --- a/ft_parse/ft_parsing_table_generate.c +++ b/ft_parse/ft_parsing_table_generate.c @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/06/27 11:16:53 by ljiriste #+# #+# */ -/* Updated: 2024/07/09 11:06:22 by ljiriste ### ########.fr */ +/* Updated: 2024/07/10 00:27:24 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -639,9 +639,198 @@ t_ft_stat construct_states(t_vec *states, const t_vec *rules, const t_vec *token return (success); } -t_ft_stat translate_to_table(__attribute__((unused))t_parsing_table *table,__attribute__((unused)) const t_vec *states) +t_ft_stat prefill_lookahead(t_vec *lookahead, size_t size) { - ft_printf("translate_to_table is not yet implemented\n"); + t_ft_stat res; + const t_parser_action refuse = {.type = parser_refuse, .number = 0}; + + res = ft_vec_reserve(lookahead, size); + if (res != success) + return (res); + res = ft_vec_insert_range(lookahead, &refuse, size, 0); + return (res); +} + +t_ft_stat prefill_gotos(t_vec *gotos, size_t size) +{ + t_ft_stat res; + const ssize_t refuse = -1; + + res = ft_vec_reserve(gotos, size); + if (res != success) + return (res); + res = ft_vec_insert_range(gotos, &refuse, size, 0); + return (res); +} + +t_ft_stat init_new_row(t_parsing_table *table) +{ + t_ft_stat res; + t_parser_state new_row; + + res = ft_vec_init(&new_row.lookahead, sizeof(t_parser_action)); + if (res != success) + return (res); + res = ft_vec_init(&new_row.gotos, sizeof(ssize_t)); + if (res != success) + return (res); + res = prefill_lookahead(&new_row.lookahead, table->terminal_tokens_num + 1); + if (res != success) + return (res); + res = prefill_gotos(&new_row.gotos, table->tokens.size - table->terminal_tokens_num - 1); + if (res != success) + { + ft_vec_free(&new_row.gotos, NULL); + return (res); + } + res = ft_vec_append(&table->states, &new_row); + if (res != success) + { + ft_vec_free(&new_row.lookahead, NULL); + ft_vec_free(&new_row.gotos, NULL); + } + return (res); +} + +void add_shift(t_parser_action *action, const ssize_t *goto_state) +{ + action->type = parser_shift; + action->number = *goto_state; + return ; +} + +size_t get_token_position(const t_token *token, const t_vec *tokens) +{ + size_t i; + + i = 0; + while (i < tokens->size) + { + if (!cmp_token_type(token, ft_vec_caccess(tokens, i))) + return (i); + ++i; + } + return (i); +} + +void convert_shifts(t_vec *lookahead, const t_generator_state *state, const t_vec *tokens) +{ + size_t i; + const t_token *token; + + i = 0; + while (i < state->goto_tokens.size) + { + token = ft_vec_caccess(&state->goto_tokens, i); + if (is_terminal_token(token, tokens) || !ft_strcmp(token->type, eof_token.type)) + add_shift(ft_vec_access(lookahead, get_token_position(token, tokens)), ft_vec_caccess(&state->goto_states, i)); + ++i; + } + return ; +} + +void convert_gotos(t_vec *gotos, const t_generator_state *state, const t_vec *tokens) +{ + size_t i; + const t_token *token; + + i = 0; + while (i < state->goto_tokens.size) + { + token = ft_vec_caccess(&state->goto_tokens, i); + if (!(is_terminal_token(token, tokens) || !ft_strcmp(token->type, eof_token.type))) + *(ssize_t *)ft_vec_access(gotos, get_token_position(token, tokens)) = *(const ssize_t *)ft_vec_caccess(&state->goto_states, i); + ++i; + } + return ; +} + +size_t get_rule_index(const t_grammar_rule *rule, const t_vec *rules) +{ + size_t i; + + i = 0; + while (i < rules->size) + { + if (!cmp_rules(rule, ft_vec_caccess(rules, i))) + return (i); + ++i; + } + return (i); +} + +void add_reduce(t_vec *lookahead, const t_lr1_item *item, const t_vec *tokens, const t_vec *rules) +{ + size_t i; + const t_token *token; + t_parser_action *action; + + i = 0; + while (i < item->lookahead.size) + { + token = ft_vec_caccess(&item->lookahead, i); + action = ft_vec_access(lookahead, get_token_position(token, tokens)); + action->type = parser_reduce; + action->number = get_rule_index(item->core.rule, rules); + ++i; + } + return ; +} + +void convert_reduces(t_vec *lookahead, const t_generator_state *state, const t_vec *tokens, const t_vec *rules) +{ + size_t i; + const t_lr1_item *item; + + i = 0; + while (i < state->kernel.size) + { + item = ft_vec_caccess(&state->kernel, i); + if (item->core.position == item->core.rule->constituents.size) + add_reduce(lookahead, item, tokens, rules); + ++i; + } + i = 0; + while (i < state->closure.size) + { + item = ft_vec_caccess(&state->closure, i); + if (item->core.position == item->core.rule->constituents.size) + add_reduce(lookahead, item, tokens, rules); + ++i; + } + return ; +} + +t_ft_stat add_table_row(t_parsing_table *table, const t_generator_state *state) +{ + t_ft_stat res; + t_parser_state *new_row; + + res = init_new_row(table); + if (res != success) + return (res); + new_row = ft_vec_access(&table->states, table->states.size - 1); + convert_shifts(&new_row->lookahead, state, &table->tokens); + convert_gotos(&new_row->gotos, state, &table->tokens); + convert_reduces(&new_row->lookahead, state, &table->tokens, &table->rules); + return (success); +} + +t_ft_stat translate_to_table(t_parsing_table *table, const t_vec *states) +{ + size_t i; + t_ft_stat res; + const t_generator_state *state; + + i = 0; + while (i < states->size) + { + state = ft_vec_caccess(states, i); + res = add_table_row(table, state); + if (res != success) + return (res); + ++i; + } return (success); } -- 2.30.2