From d8e560f8909ddbba58f5e35eacac4b73b18aa124 Mon Sep 17 00:00:00 2001 From: Lukas Jiriste Date: Thu, 18 Jul 2024 13:32:26 +0200 Subject: [PATCH] Fix infinite recursion The previous commit solved some wierd things around the add_first function. These were created because of my misunderstanding of the process but also (almost) prevented infinite recursion. The infinite recurson is caused when a search for a first (nonterminal) tokens encounteres the original token, because then it searches for it again and is able to again find the token along the search. The solution is to make the algorithm log what nonterminals it already went through so that it does not try to find their first tokens during the search for their first tokens. --- ft_parse/ft_parsing_table_generate.c | 44 +++++++++++++++++++++++----- 1 file changed, 36 insertions(+), 8 deletions(-) diff --git a/ft_parse/ft_parsing_table_generate.c b/ft_parse/ft_parsing_table_generate.c index 0396f64..acc0f80 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/18 11:47:10 by ljiriste ### ########.fr */ +/* Updated: 2024/07/18 12:16:01 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -278,6 +278,7 @@ t_ft_stat add_first(t_vec *lookahead, const t_token *token, const t_vec *rules, return (success); return (res); } + append_token(lookahead, token); rule.position = 0; i = 1; while (i < rules->size) @@ -294,7 +295,7 @@ t_ft_stat add_first(t_vec *lookahead, const t_token *token, const t_vec *rules, return (success); } -void remove_empty_token(t_vec *lookahead) +void remove_token(t_vec *lookahead, const t_token *removed_token) { size_t i; const t_token *token; @@ -304,7 +305,7 @@ void remove_empty_token(t_vec *lookahead) { --i; token = ft_vec_caccess(lookahead, i); - if (!cmp_token_type(token, &empty_token)) + if (!cmp_token_type(token, removed_token)) ft_vec_erase(lookahead, i, ft_free_token); } } @@ -321,11 +322,14 @@ t_ft_stat expand_lookahead(t_vec *lookahead, const t_marked_grammar_rule *rule, i = rule->position; while (ft_vec_contains(lookahead, &empty_token, void_cmp_token_type) && i < rule->rule->constituents.size) { - remove_empty_token(lookahead); + remove_token(lookahead, &empty_token); token = ft_vec_caccess(&rule->rule->constituents, i); - res = add_first(lookahead, token, rules, tokens); - if (res != success) - return (res); + if (!ft_vec_contains(lookahead, token, void_cmp_token_type)) + { + res = add_first(lookahead, token, rules, tokens); + if (res != success) + return (res); + } ++i; } return (success); @@ -351,6 +355,29 @@ t_ft_stat add_to_lookahead(const t_vec *lookahead, t_vec *new_lookahead) return (success); } +void remove_nonterminals(t_vec *lookahead, const t_vec *tokens) +{ + size_t i; + const t_token *token; + + i = 0; + while (i < tokens->size) + { + token = ft_vec_caccess(tokens, i); + if (!cmp_token_type(token, &eof_token)) + break ; + ++i; + } + ++i; + while (i < tokens->size) + { + token = ft_vec_caccess(tokens, i); + remove_token(lookahead, token); + ++i; + } + return ; +} + t_ft_stat add_lookahead(t_lr1_item *new, t_lr1_item *item, const t_vec *rules, const t_vec *tokens) { t_ft_stat res; @@ -360,6 +387,7 @@ t_ft_stat add_lookahead(t_lr1_item *new, t_lr1_item *item, const t_vec *rules, c return (res); ++item->core.position; res = expand_lookahead(&new->lookahead, &item->core, rules, tokens); + remove_nonterminals(&new->lookahead, tokens); --item->core.position; if (res != success) { @@ -368,7 +396,7 @@ t_ft_stat add_lookahead(t_lr1_item *new, t_lr1_item *item, const t_vec *rules, c } if (ft_vec_contains(&new->lookahead, &empty_token, void_cmp_token_type)) { - remove_empty_token(&new->lookahead); + remove_token(&new->lookahead, &empty_token); res = add_to_lookahead(&item->lookahead, &new->lookahead); } return (res); -- 2.30.2