From 32177a2f45eca10b7c5d4795903653edcdbe9835 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Luk=C3=A1=C5=A1=20Ji=C5=99i=C5=A1t=C4=9B?= Date: Mon, 28 Jul 2025 13:28:36 +0200 Subject: [PATCH] Refactor parsing table generator out of Libft --- .gitignore | 4 + .gitmodules | 3 + Libft | 1 + Makefile | 94 +++++++++++++++++++++++ inc/pt_constructor.h | 109 ++++++++++++++++++++++++++ src/categorize_helpers.c | 43 +++++++++++ src/categorize_helpers.o | Bin 0 -> 6120 bytes src/categorize_tokens.c | 98 ++++++++++++++++++++++++ src/categorize_tokens.o | Bin 0 -> 8256 bytes src/conversion_helpers.c | 117 ++++++++++++++++++++++++++++ src/conversion_helpers.o | Bin 0 -> 10376 bytes src/conversion_subhelpers.c | 42 ++++++++++ src/conversion_subhelpers.o | Bin 0 -> 5024 bytes src/conversion_to_table.c | 48 ++++++++++++ src/conversion_to_table.o | Bin 0 -> 6408 bytes src/fill_closure.c | 89 +++++++++++++++++++++ src/fill_closure.o | Bin 0 -> 7560 bytes src/ft_parsing_table_generate.c | 126 ++++++++++++++++++++++++++++++ src/ft_parsing_table_generate.o | Bin 0 -> 10496 bytes src/helpers.c | 61 +++++++++++++++ src/helpers.o | Bin 0 -> 7992 bytes src/helpers_cmp.c | 42 ++++++++++ src/helpers_cmp.o | Bin 0 -> 6096 bytes src/helpers_free.c | 51 ++++++++++++ src/helpers_free.o | Bin 0 -> 7144 bytes src/helpers_void_cmp.c | 28 +++++++ src/helpers_void_cmp.o | Bin 0 -> 4248 bytes src/init_new_row.c | 83 ++++++++++++++++++++ src/init_new_row.o | Bin 0 -> 7280 bytes src/lookahead.c | 84 ++++++++++++++++++++ src/lookahead.o | Bin 0 -> 8456 bytes src/lookahead2.c | 116 ++++++++++++++++++++++++++++ src/lookahead2.o | Bin 0 -> 9648 bytes src/main.c | 15 ++++ src/main.o | Bin 0 -> 4704 bytes src/prepare_table.c | 78 +++++++++++++++++++ src/prepare_table.o | Bin 0 -> 7888 bytes src/solve_gotos.c | 132 ++++++++++++++++++++++++++++++++ src/solve_gotos.o | Bin 0 -> 9496 bytes 39 files changed, 1464 insertions(+) create mode 100644 .gitignore create mode 100644 .gitmodules create mode 160000 Libft create mode 100644 Makefile create mode 100644 inc/pt_constructor.h create mode 100644 src/categorize_helpers.c create mode 100644 src/categorize_helpers.o create mode 100644 src/categorize_tokens.c create mode 100644 src/categorize_tokens.o create mode 100644 src/conversion_helpers.c create mode 100644 src/conversion_helpers.o create mode 100644 src/conversion_subhelpers.c create mode 100644 src/conversion_subhelpers.o create mode 100644 src/conversion_to_table.c create mode 100644 src/conversion_to_table.o create mode 100644 src/fill_closure.c create mode 100644 src/fill_closure.o create mode 100644 src/ft_parsing_table_generate.c create mode 100644 src/ft_parsing_table_generate.o create mode 100644 src/helpers.c create mode 100644 src/helpers.o create mode 100644 src/helpers_cmp.c create mode 100644 src/helpers_cmp.o create mode 100644 src/helpers_free.c create mode 100644 src/helpers_free.o create mode 100644 src/helpers_void_cmp.c create mode 100644 src/helpers_void_cmp.o create mode 100644 src/init_new_row.c create mode 100644 src/init_new_row.o create mode 100644 src/lookahead.c create mode 100644 src/lookahead.o create mode 100644 src/lookahead2.c create mode 100644 src/lookahead2.o create mode 100644 src/main.c create mode 100644 src/main.o create mode 100644 src/prepare_table.c create mode 100644 src/prepare_table.o create mode 100644 src/solve_gotos.c create mode 100644 src/solve_gotos.o diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..e701477 --- /dev/null +++ b/.gitignore @@ -0,0 +1,4 @@ +.debug +parsing_table_generator +parsing_table +tags diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..626d139 --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "Libft"] + path = Libft + url = git://ljiriste.work/Libft diff --git a/Libft b/Libft new file mode 160000 index 0000000..6e94585 --- /dev/null +++ b/Libft @@ -0,0 +1 @@ +Subproject commit 6e94585db85e9afe7c86ce5947b686b5682b978e diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..a31a85e --- /dev/null +++ b/Makefile @@ -0,0 +1,94 @@ +CC := gcc +CFLAGS = -std=gnu99 -Wall -Wextra -Werror -Wpedantic + +ifneq ("$(wildcard .debug)","") + CFLAGS += -g +endif + +RM := rm -f + + +SUBPROJECTS := Libft + +INCDIR := inc +INCDIR += $(addsuffix /inc, $(SUBPROJECTS)); +INCLUDE := $(addprefix -I, $(INCDIR)) + +SRCDIR := src + +SOURCES := main.c \ + categorize_helpers.c \ + categorize_tokens.c \ + conversion_helpers.c \ + conversion_subhelpers.c \ + conversion_to_table.c \ + fill_closure.c \ + ft_parsing_table_generate.c \ + helpers.c \ + helpers_cmp.c \ + helpers_free.c \ + helpers_void_cmp.c \ + init_new_row.c \ + lookahead2.c \ + lookahead.c \ + prepare_table.c \ + solve_gotos.c \ + +SOURCES := $(addprefix $(SRCDIR)/, $(SOURCES)) + +OBJECTS := $(SOURCES:.c=.o) + +NAME := parsing_table_generator + +all : $(NAME) + +debug : .debug + $(MAKE) -C Libft debug + $(MAKE) all + +nodebug : + $(MAKE) -C Libft nodebug + $(RM) .debug + $(MAKE) shallow_re + +noleaks : .noleaks + $(RM) $(SRCDIR)/readline_input.o + $(MAKE) all + +readline : + $(RM) $(SRCDIR)/noleaks_input.o .noleaks + $(MAKE) shallow_re + +.% : + $(MAKE) shallow_fclean + touch $@ + +$(NAME) : $(OBJECTS) Libft/libft.a + $(CC) $(CFLAGS) -o $@ $^ + +FORCE: ; + +Libft/libft.a : FORCE | Libft/Makefile + $(MAKE) -C Libft + +%.o : %.c | Libft/Makefile + $(CC) $(CFLAGS) -o $@ -c $< $(INCLUDE) + +%/Makefile : + git submodule update --init $($@%/Makefile=%) + +clean : + $(RM) $(OBJECTS) + +fclean : clean + $(RM) $(NAME) + $(MAKE) -C Libft fclean + +re : fclean + $(MAKE) all + +shallow_fclean : clean + $(RM) $(NAME) + +shallow_re : shallow_fclean + $(MAKE) all diff --git a/inc/pt_constructor.h b/inc/pt_constructor.h new file mode 100644 index 0000000..c1abc4b --- /dev/null +++ b/inc/pt_constructor.h @@ -0,0 +1,109 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* pt_constructor.h :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:57:15 by ljiriste #+# #+# */ +/* Updated: 2025/07/28 12:15:17 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#ifndef PT_CONSTRUCTOR_H +# define PT_CONSTRUCTOR_H + +# ifdef __cplusplus +extern "C" { +# endif // __cplusplus + +# include "libft.h" + +typedef struct s_marked_grammar_rule +{ + const t_grammar_rule *rule; + size_t position; +} t_marked_grammar_rule; + +typedef struct s_lr1_item +{ + t_marked_grammar_rule core; + t_vec lookahead; // t_vec of (terminal) t_token +} t_lr1_item; + +typedef struct s_generator_state +{ + t_vec kernel; // t_vec of t_lr1_item + t_vec closure; // t_vec of t_lr1_item + t_vec goto_tokens; // t_vec of t_token + t_vec goto_states; // t_vec of size_t + size_t state_number; +} t_generator_state; + +int cmp_token_type(const t_token *token1, const t_token *token2); +int void_cmp_token_type(const void *v_token1, const void *v_token2); +int cmp_rules( + const t_grammar_rule *rule1, const t_grammar_rule *rule2); +int void_cmp_rules(const void *v_rule1, const void *v_rule2); +int cmp_items(const t_lr1_item *item1, const t_lr1_item *item2); +int void_cmp_items(const void *v_item1, const void *v_item2); + +void free_item(t_lr1_item *item); +void void_free_item(void *v_item); +void free_generator_state(t_generator_state *state); +void void_free_generator_state(void *v_state); + +t_ft_stat prepend_token(t_vec *tokens, const t_token *token); +t_ft_stat append_token(t_vec *tokens, const t_token *token); + +const t_token *get_next_token(const t_marked_grammar_rule *rule); +int is_viable_item(const t_lr1_item *item, const t_token *token); +t_ft_stat v_token_dup(void *dest, const void *src); +t_lr1_item *duplicate_item(const t_lr1_item *item); + +t_ft_stat init_new_row(t_parsing_table *table); +void convert_reduces( + t_vec *lookahead, const t_generator_state *state, + const t_vec *tokens, const t_vec *rules); +void convert_gotos(t_vec *gotos, + const t_generator_state *state, const t_vec *tokens); +void convert_shifts(t_vec *lookahead, + const t_generator_state *state, const t_vec *tokens); + +int is_terminal_token(const t_token *token, const t_vec *tokens); +size_t get_token_position(const t_token *token, const t_vec *tokens); +size_t get_rule_index(const t_grammar_rule *rule, const t_vec *rules); + +t_ft_stat add_lookahead(t_lr1_item *new_item, t_lr1_item *item, + const t_vec *rules, const t_vec *tokens); +t_ft_stat expand_lookahead( + t_vec *lookahead, const t_marked_grammar_rule *rule, + const t_vec *rules, const t_vec *tokens); +void remove_token(t_vec *lookahead, const t_token *removed_token); + +t_ft_stat categorize_tokens(t_vec *tokens, const t_vec *rules); + +t_ft_stat construct_state(t_vec *kernel, t_vec *states, + const t_vec *rules, const t_vec *tokens); + +t_ft_stat solve_gotos(t_generator_state *state, t_vec *states, + const t_vec *rules, const t_vec *tokens); + +t_ft_stat fill_closure(t_vec *closure, t_vec *kernel, + const t_vec *rules, const t_vec *tokens); + +t_ft_stat prepare_table( + t_parsing_table *table, const char *rules_filename); + +t_ft_stat convert_to_table(t_parsing_table *table, const t_vec *states); + +void remove_zeroth_rule(t_vec *rules); + +t_ft_stat ft_parsing_table_generate(t_parsing_table *table, + const char *rules_filename); + +# ifdef __cplusplus +} +# endif // __cplusplus + +#endif // PT_CONSTRUCTOR_H diff --git a/src/categorize_helpers.c b/src/categorize_helpers.c new file mode 100644 index 0000000..a9e25b5 --- /dev/null +++ b/src/categorize_helpers.c @@ -0,0 +1,43 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* categorize_helpers.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 17:04:36 by ljiriste #+# #+# */ +/* Updated: 2024/11/26 17:05:14 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "../Libft/ft_parse/ft_parse_inner.h" +#include "libft.h" + +t_ft_stat append_token(t_vec *tokens, const t_token *token) +{ + t_ft_stat res; + t_token token_clone; + + token_clone = ft_token_dup(token); + if (!token_clone.type) + return (alloc_fail); + res = ft_vec_append(tokens, &token_clone); + if (res != success) + ft_free_token(&token_clone); + return (res); +} + +t_ft_stat prepend_token(t_vec *tokens, const t_token *token) +{ + t_ft_stat res; + t_token token_clone; + + token_clone = ft_token_dup(token); + if (!token_clone.type) + return (alloc_fail); + res = ft_vec_insert(tokens, &token_clone, 0); + if (res != success) + ft_free_token(&token_clone); + return (res); +} diff --git a/src/categorize_helpers.o b/src/categorize_helpers.o new file mode 100644 index 0000000000000000000000000000000000000000..a5b98a4646d601d1df2efab650a565a382e7c16a GIT binary patch literal 6120 zcmbtXZHQb~8Gi5Fxx2HO&Ft()v%A@vowS>eVs~aYjcZa(GIgt=(uTBDP5(H(bLY&= zC9`)X_uh%SX{k{ZEBd4BN3l??P=!YEhd;Cgqf`+5pimU7AShe#haw_D6oUkP-*etG zd*|#dQav#DoaZ_3*Llz9eEj_ne;{R9po;~s!Zy+@z|o2Ac3C#dFb(_Q_ER^m-L_$K zYYc9^m4#bd+43#y{?gWGQrEVo%eUqMZn^-Em*MJTqX1J|FT>_rHhgPqjOEV2^{q4I z>nL~WNtC00sgK<4r+)IvYj)+$x8q|k`$)mnU%g#FG^_>sU^#L`)&K4LND3e=g)%a2 zIL7|+dIF|04k4R9sb5Z)smcsXlvb6MktoGzNFk|}PCI@OgOeG`Y>=W7m4d_Rv&h&} zxgTOBEvPSBlZ-9DY58^JcSr?dzr((YY9siALi#{Hi{scsAYB+aPPGCDCCDgnmjwCj zW#K{k?#v~Wno-u$3(n6G>0zk>OWS#8I{%2a?aXE(vYn0M5S;xIWRwMG&N+l)qa=&7 z2{1IV?+I*=$g~lm*hz!UQI|EJr5xzeA#1)s?bPN4hVTBXgy-|2h`>5H zO8TkIr==6?t}KO-+HAs5h7vQBp-{%9q47RfHR7;XFDkp^^L=i{SNhyc_Pd$txdCh3 zI+UBt+PS&hxHU1HpGNl!kjtq*tz?&@5!FbJ~W9_#638l&KL?|fK*Y}aN4qS zr?Uig9dL%aXPBIy9c<>b#f6Q>-f;Or?mnUdo?;n=5~krK+K($>M{9sP~I z{!|Kc5p_LJL=i+3bqsDR6mD$;-9|nR*>gLt=f@k+sED;ryitkU7e#Yr+LR*n}I z8-+!j-BY+yP;s&DMjL_G4BJ7w8!dK&kNH7uQRX1RL95*LeACb*6@edIc3XZ;4MZkj zXBMPr#lsGv)M!rHb+)>#L}t~naFGsNk?}@Ha8gNFs>(d8luKnDksoxrI0JIp;Oy$^ z{e`0siYjG6WodEc9y4E%$JI&2y7CyL*AG~8qw{blV%*rW$Yb$=T=}b+uML0X_rH^e zbOC!#sBVxaH1}WNe(oAr(QZz|&3_N-vWhraU(&p)-FYuygr0(dG`lmMZ6DDW(nCvE=$$&z?Di!kox zbq<$;$~6Xz<-Mu`;_<1_D~~65y%&jEPw+`Q-$?NLxlPrL1fR5{Md*4>?g~9en%CF1 z-U%s`mrpA;Fv>OYq)U%1Dtd)!{!Dl(1y21aG?LTeszh?du z2LETqUo?1z@PfhX9KB@lIxpWe_)oLnZyWqH$Nyb}|32ea4gO8WKQj23@h=Si5ZnKa z!5?7!2ZR4SCkf#*ubMiZ;JmVV%|2@Wfzv{eQWBwn8 zJpEauV)1;M`*(_YZRZ)*zuVxo-veYf$90&KZ3U zYhLFKiqXazz6!C9Lsd6*D-o57iZwTOp;*PYc`?f_7 zsCFCpaId#fSGL`1H58Zoy4}zX8u+I+se*rYgjS*d-bJsywkGgpSPa^+DB`mi-?*-K zk(ERfFDQ3Ss6qc9-va8=)aiN9rpnxST@zfV4LpaKxU#{&!cUs#n5Xv#`O)XLzOxQ9 zZ@vWezGwAb#mlUR@5L6`{9pB#QI~A;^2C-Zd3I#J%yj%(?ld+?)bw9q{el+c+SEUZ z{Gj}u;LWhadXzt!BdxFV_hIDN6-%nB%;clSz)V@X4+r^gvj3|*;pCruoBpfFnKqGv zO-@M8=rka7chP@|{p#_PO)92-2f0D<|1mGcLF-feG?!-lpGD5JNt$o4{{u#+0pU|9 zJIMdcI9b{LzeWD(eP#OpGIC^7$B9i@{=$#9ckVKOI*zZS^dS8ic63yk>wUGJuCK9v zPk`CH=r>AX<>=--Og*Xw_fZ}RmO7JQZi ny8}7;nffEhnR^#0DDcLAmO!GI +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:24:59 by ljiriste #+# #+# */ +/* Updated: 2024/11/26 17:01:25 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "../Libft/ft_parse/ft_parse_inner.h" +#include "libft.h" + +static int token_in_results(const t_token *token, const t_vec *rules) +{ + size_t i; + const t_grammar_rule *rule; + + i = 1; + while (i < rules->size) + { + rule = ft_vec_caccess(rules, i); + if (!ft_strcmp(token->type, rule->result.type)) + return (1); + ++i; + } + return (0); +} + +static t_ft_stat add_constituents( + t_vec *tokens, const t_vec *constituents, const t_vec *rules) +{ + t_ft_stat res; + size_t i; + const t_token *token; + + i = 0; + while (i < constituents->size) + { + token = ft_vec_caccess(constituents, i); + if (ft_vec_contains(tokens, token, void_cmp_token_type) + || !cmp_token_type(token, &g_empty_token)) + { + ++i; + continue ; + } + if (token_in_results(token, rules)) + res = append_token(tokens, token); + else + res = prepend_token(tokens, token); + if (res != success) + return (res); + ++i; + } + return (success); +} + +static t_ft_stat add_tokens_of_rule( + t_vec *tokens, const t_grammar_rule *rule, const t_vec *rules) +{ + t_ft_stat res; + + if (!ft_vec_contains(tokens, &rule->result, void_cmp_token_type)) + { + res = append_token(tokens, &rule->result); + if (res != success) + return (res); + } + res = add_constituents(tokens, &rule->constituents, rules); + return (res); +} + +t_ft_stat categorize_tokens(t_vec *tokens, const t_vec *rules) +{ + t_ft_stat res; + size_t i; + const t_grammar_rule *rule; + + res = append_token(tokens, &g_eof_token); + if (res != success) + return (res); + i = 1; + while (i < rules->size) + { + rule = ft_vec_caccess(rules, i); + res = add_tokens_of_rule(tokens, rule, rules); + if (res != success) + { + ft_vec_free(tokens, ft_free_token); + return (res); + } + ++i; + } + return (success); +} diff --git a/src/categorize_tokens.o b/src/categorize_tokens.o new file mode 100644 index 0000000000000000000000000000000000000000..d01b4213897707edb7bf9a25ed03c69c10281d6d GIT binary patch literal 8256 zcmbtZdu$v>8K1qqwa-4sIooNRG;MuO+$4SY?i`goN}OD9+t4IRLI{xX=w*GkwvV3o zF1vfF-9*I|ky@U@;?W|dEeJ|q|FjZn8$nCTO97z*6;Ol(I)@5H0wF5?si9H$zM1bk z@6DZs1S5H8zTfx$W_D(7{i!<-+!Zkl!Oajai6x3rA?B`K8fWD&EBeK1apm+Y&s;IZ zd~KyzT!@Rsq?mi7)-M+OgjluEpIxlQvx^}9m0F)ztgXy0Mg(Aeh-DWSOz~{Zj693{ z0U=J>LL3GCBb}gI16>gXyI@P&h=M#|yM_4c*p;hCA)+H!PXFlX3uf+jS5ALV#Q?Gk z;O7#=a&?1PycJ{E!2TeH0fDi631e6o033ag?*;IUJji{%20X^U33v@`$XLK;KiY&m zQ0BF(S0BN+FMv$gUhR-LZ=qbs2V%8D+4CrW0&T)r<{7dr>w<+~M;|{Df+Q^FeOOO}KKL@$7{FT!`ZuC!cU9T7D zVZCbG!2Y(7eKlSMbNU9>el^#G*96ShB^b+f0yZw9&ybB;eNLd>bstnWoFiNxV7IZd`CYD?iW_1RL->HUX_M;z+w+Vmz&y4XED0gH@DXm`jx14;7)-Yipdv)%*Zo=S zV(pTOs?LZ>DneA7qNG+dY8Bl;Sh2R)EGjBdDcBy}3y8U@`xWS<1@$Cr5;5g7Dxa2o zwy8kO>&-b(g9#QQ8NDG9hdf}#L0ZX<+pt%}pd@07STBi0{FIXy(G9VaAhkwWiw;>o z1F8$HaBeDV=^$bCCyuZKYi-O&2XQ~}gmtYXV#asW~}QIpQ|elbRt7V zW+h|jEJ2EcRvxG>lx>SW0?!rbqOEuJJuvQ&rAI)aeHz-0EaN~N>&We88W`tphpAkN zlyP7P$C3GCMDEB+@^Hd)d|@11iTaWGAW;;?p%qxf$o!1-XdGU14&sQ+PeF7Tc3Z3; zo;}j)Xm8l>9AeOnb5GX&?&?y0r26QN~{)U_wDib z#&^W;hLa{r99aI=N)UqbV~4Evs9|>RiX)-q4FF@CLH#-q>*xb+Jif%~ToE$79VFra z#Ml!8T^j}3g}|30h^!H!J7w%%%h0B^clTk~*)?B#-&*vz($d5epkKF(`aLNKMLBBH z?p=llm4-7;z%qg+-+ej4M|gXxgE06k%$g~F0Hdh!@9q`CfCdEo8NQbn>8kIgOU3c@ zWIms^Z7)By^|s+s(XGx5PrB9gNG4r$^QCIR5eJIn69G~J^wOzRS^*P5u3~$>BShW~ zoXN6Ryx++M<$E31Pvy~#9~27CL~07724O$210Y~k0bzSyeJrgsQn{k*Iw*k~vt@`5 zl{gS)k6}d*TCud%x!&sEZ{3ozVkxU_rxj0IX4>lAhGfT>WejeyqMxv0gI0XK)xO_q zJBB*ZeVI|KeLc!|rax-6?YH8isJ7NTxl<~dJv*i9z{jliq-E{1Ix<$T>td1)1 zMy%K&%Q|j#j#|+)#nA!wk6Y1QR(!u@W~^TGKC%`^Ymo@l-mm8Kj_(UUH|g2a)3%rM zswGGGvSBC+bjr-}bG}g4}PUZr8yyWC29jK-qlsysTaKjIBG#|}VC-P<24~jw6aRZ1JCcM?` zmdfsAvg-Q9N!KYP@lf-p%3jb2VHOS6oKg<+6>izh`4uN$oG7X!s-7d9dQ5e@`6=6j zg2^={_8$CDa%{(rJL}l`-*O1SQf~KiYPBZKjlzT(0R%gkY;yPC)17&&?Qtvjr$5Sr7x~+XFOR1^-G?9Re7s{O#6L#- zIqdgzXCI3_-hL19lK{;i4((-p5WhrxgqCZ#xkbg>S6lH-+>cr`6St!l&7>Ql&N79( z$Th&%NU9k}*c9^q*FwG-UjtG`NS^CIL^#vjZ;@7;^Lh{9u;WNBKKPWri*Tm-`tT9L zOQbRfG&fT_YnE_%i)6Cin*z?w7R^+*wI+_Kt}QKad7o;)Rh@gqss>aMrn;Xram@NE zUSi=5hHJQl3V~PhR`{ov!5>)$e|Q=Esb%o*E`$FN@Lrh5ztOzN_W`iqEF*tu8N7Lq zhvRvu(6IG1o-RW(%^OwIX5QkAf=UoGQa62?Mp!<>WTT!euwG zVS5vHr2;!RZG{!j2~kZa5Z)jrJcq6uNTFXupa%H9U|R=u!*`0?9W+3EErZZM9m2!% z&lA24?HYbTqRQ_&8e{hh8ux)b{?_9)_AA1#(eU3Bj&b6C$}IsjHpH)2 zL-`yE;WvcvvxMvMKTNnDKYkFwhW5kpKOMrue%~dW^HSRIq`MmD#dwTxJ^t+>JY4@1 zgk$_kHUfQtaEw2UmqK<1L-IVt+i!T6=6PT|MuNOEM?juskj38x5Qlrd*aJN_-l-UW zQNcp(S5OX;KTbHWJ@iWqk!_un|M+oQrp+xqJnmqfR(Qvl^kcM+S-_h`YlHV5yXTN6&zo^Nx-#0a!=kYHZ z&VGC7s?BxadTrA1HqzfhILAZbh&wfTwsTa&*>6R|xjx~2UVgA52fQwHzr2s?IG@q* znSw)+mUfao#<`v!*KnR+-X~d}*PBTBv(xZ175cza{S=Qpr(~xBXC@G-f*sf*H4dK` zQeIgRl8eI>i~vo+M+3VAeAFs9F}f5&fiN)&J}kB2{eLY9>i8<~ys@<`4fO9|Q5K*c z?=*;IiRSJyO?ZOV9sa&RKfI6eon#~7w47L7yhVC-fClv1)?xg9hc^FL{SnYbo4UKp z1n9rKIDSx(Z5KRIU-$nG=_jSs(nHtZ0jyT_dxtJ7d{4pp;T*9(*YCrC=`{gJtf7GB zw7_&(yr;DCzZow@&@R*E4*jEV-TydXx=nz@qqLwlYfOz4)n)WA(BZ@RqfKnOeg&{r z@h9j)$od#R&ZQpzXIj_iN7OxSl`9@eN?K(zobhy_prMXFcxmeBp6ebeJ#ZVX%eltAy$APlog#)$}=khR?&G zRsD`p{Z5b|)(>9^*5|rn?7DAMxk&yqwEppT1M2AdSZ3`N0Yr#*= +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:35:11 by ljiriste #+# #+# */ +/* Updated: 2024/11/28 15:26:22 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "../Libft/ft_parse/ft_parse_inner.h" +#include "libft.h" + +static void add_shift(t_parser_action *action, const ssize_t *goto_state) +{ + action->type = parser_shift; + action->number = *goto_state; + return ; +} + +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, g_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, g_eof_token.type))) + *(ssize_t *)ft_vec_access(gotos, get_token_position(token, tokens) + - get_token_position(&g_eof_token, tokens) - 1) + = *(const ssize_t *)ft_vec_caccess(&state->goto_states, i); + ++i; + } + return ; +} + +static void add_reduce(t_vec *lookahead, const t_lr1_item *item, + const t_vec *tokens, const t_vec *rules) +{ + size_t i; + size_t rule_num; + 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)); + rule_num = get_rule_index(item->core.rule, rules); + if (rule_num == 0) + action->type = parser_accept; + else + { + action->type = parser_reduce; + action->number = rule_num - 1; + } + ++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 + || !cmp_token_type( + item->core.rule->constituents.vec, &g_empty_token)) + 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 + || !cmp_token_type( + item->core.rule->constituents.vec, &g_empty_token)) + add_reduce(lookahead, item, tokens, rules); + ++i; + } + return ; +} diff --git a/src/conversion_helpers.o b/src/conversion_helpers.o new file mode 100644 index 0000000000000000000000000000000000000000..104e2bfb8d05c38fc1e263f50e3b45b04fb2456e GIT binary patch literal 10376 zcmcIpZ){uD6~E8V&vxR}b(+#7P1-nZ+J?2UlhT!zw$ve%KP^H9I%vCr>o_losbjnL zGbDgUw-u=frjb!#gMvCSG0K>>4{U1%+6t5jZ4+HZ*AJ6mDgAFdut8;!hCINp}u# zyvq}xj0lMFzr?%vGm7_?-otvl6R>V)8esiqi^;RFp16ikE^{XuAb)XK6ZaaCu8bIAJ?&Vqo9;mOAh+&;o#DPB4O|M&u z)@?e5S7aSt6a)CPfMPg9^)f;J7+#10^N)20y0ISOSc`;t=1Tt`f%jm1!c~i}LJVgi zw)Y?hXMlGCV*e%98S2M6;~ao~v?=TC{M5E7z!!2p_d-7ZkN!MV%^!$|{W)9C-*H*< z9k5W?mMv5Lmpwz4fKagoAU#6V;iICdSqXUpz%7J{56{WQICcTQq`ay#pcVl15am;p zl=6D5bk-48K#H5MwsgUyFYo~JD={e)@h%L%1(;Oijnu3{6^dw=L_iUXBoVH;%T5XJ z;=mr@YEqtgJFJI+szoi*mX&EJBJg*3u)iu2X))|;3@?S?rCwii;C^5eHASZ&eDfs{ zP-=WF))%M-d8J^tZ$UUw7HpFfq$LtS>tPaXw=M^^TI3C)a=-Ulc={Imo&rQ=Ts{r? z^vI{FY=nKw!>^ZZbhYMTOg5q+%ndsit3_ohApgAZCoJP{YQnLS@i)&>GQPlW0A+Uk z^Zh4SvfJMp?(s15!lnz;l5KUai2RY78epqMUTJc_e^Ge6EZ8BVCzDGg5s}&TFO@`G z5z8d8OA(!NJ@=ANms(e$epERNoEL#P^Hzc{HPT}Q6xyJnA)GRH%Cf^D>;keG2RDJ_ zY#bXq7vR`4K1^iq7D?_>o9qq@lk2qxMS{Zk~I%ijJfdz zo(6Y)fxpS|1{l}FNEmU+j>F^lfMy*07f31#@iyfS8H}%2O1G-nUUKI;BFUXNy3-e| zaOY|wcPZ~S)uRp1cwUj$G<+(_VQ>&L=?h?0seG*{=j$WoA2>J&uf4LlqNO5VT?;Dm z)zw4!LXTpV9(A(|WT&ZY=TzCwTV*>wnGGiR{{jD%sgR+t_ZFRt_@z_ z09z-`Kn+{7fe8|e9ZvZh3^NoADqaJCz$};O8epvfAi%m1s9h>hGUx@#D}$(JTDqL(7`c>3GxQS2d%}*_Or}2I;a*l&+70F=a-RopbTb6H2RC z0f~b8h9+NLIg$_8VKEKDwGWt0(FqmjH9il`5(YGwhd-lONQqdfScqlP{js4`Dwa$Z zQp2lPb!F1o(rDLEwiN5>j-|7yOliPYoJ3UN>`yyIaYMR)&_RhW<1UUB1+sw)v1l}= zMc1)`RBy=8TmEbn!exzTDfN7p0hF>BX@RD4>hMoKja zkJpG<%dv}EHLCMtx6W!_X)U?c@^7)M%~rV0^6#{)h-J1{(U~Dn>ULP6lI7cB)o<8n zEd+m~mf3B!nhyC8LLb=k+C^6V7OOLAt&3W|h&8+0S_J;LS>Davmbt^4Z;nYRuUP|q zyM^pKW@c|8b`P=}?H&)5SSp!Mrqa%s7|J=hgp=ECXN$r~j3f)Y?SaHlAvprWM4^Fs#FzDqBxu$gksC&vO^L1C}oT3p{zX+!COwT zQop0jySOEj;!h1H3&K`aS4bpN4pyABmC5CHCx`9ifJkL>#Zm!WbCQm&)Sw0#nZgnY zc2m`@lfcQMQ2NAB!p;qn7qSA=PRY(f05CC#t~F34oRT@Y!<9udib0Zz8eKhjD&lCVl@v0}ry5j(bfER~LJE#z>; zim|>JE>=1_lyH*$us}mLyfjI8nIPxYmR72guXxq>nN~iTO4)f_Heyd?3Oxzwsxv(- zha*>v_6c4w3K>@=mBW>iNs*kz%C!~O-uR73-`cg2p6=+%XisEi_sX8`o}TVV*GMMq zI2pUk&JLuLS)h~s=?$6u>Q#}hp-30(I~!m-1i`MsWN|E;8ZP9rxl*yKl)XEh9q5wz zfCZJyK3y4D^W`KZRIzZ0sDdwIxpEqbqx?n;mS8WGQur?53huTGSv!MT-LFu=E|xNm z5ZCtgT@mTL+U~~)RD@ltFV$m(tFdavJvR&Q=t85Vu1(AZ2u>u~S_@-hHR6 z<3}_vZ;rj8_|t)B{GJ<$f##}pc$|5~$5YkjOguHJG!u`FD$S%{WcrjT;5^aVJV{@S zBW&X7qBX^TG2RS(hKrxqX9?j{*iQJnm|KYS4EVh>;1A4zWBpds{~X}xPaWm|BcQRp1b@}|Uk4odkI^M0PI7P0 zz+e5g)G<(T@Kl~P9i#FbQ2V~?MBvSdPFT1e!SRwv;TBzl3mfdwc3~u)O=f7b1_roL zrAG2%$fkofQ9imznuJ+3?UBGP4|&)41q%%P@QOjd^FJ*JI96N zyTolj4H|&o{gysV_$3;S>xT{X&sRhFe38b8x47^lE*$qaZhxkM?&lhi$EM@gxp24t z-y&T1e;47p{~4DaxBvTGxI1qLT(~=~LxiJU`GrBbEq+Qk+I8d46Rzjy6&LQ#Pbby2 zo`*Fq-0jcRF5InWy99CyzjQ(k!IWxS5?OEmu1Kn@$% zB-$lbiC-$8fC0`r5$bl~Xcs@qVEel2BtPP7iSEK^|&hK>1~ ziRS%{@dWYj(fEI%#KreCd$_g&#+;{ZQlQFW1j%_$o@$kVRq;?_BYxpU`gQSn+eVP23ui?KYe6@x@PWT-f z{uJRh;k?hEC;UE*pZ$DD!&(268qR(m)^PUo4GoV|yr(qWM|nA`Az zdktrQPH6bgDQ~9_YnD`o^XCYbp4l;J{{*f9(;$bxNoc? zeT;M7_}pil*O$*9#<`vkYI^v66w%_?2z<$b-YKYlm`4RWlZ-m{s3W2SNhc|y{qTDz zTF5Cv&f+i%BS52>Tq>D?d6XKk`%6Rcfq5_ovT~g4?=RSQRZJ%f$?On(eRGSzS9qI6 zzz-2k~bB-N_Pg(F?Dw*0%LiTWC5WWiWX-`3Zg)RazxHP<;tRl_>TK^eH z`5OsY%KXH5hz=yapU(vx?eIOeiTIWhPOmeepii^Q6I4b_%Kwm{&aW!p1G1=-wu7=> zwh#XZs%Y##gIB@;<#qd8$^Qs5Qm@P7y|`Nb_EUoRevSFVHDYnPL*0IV6`cTy@6v(Zp*g3KqBMj2bM#4y<42v?boo4B)%=gQ zOZM{b6Z9X~QuqHsz;vA`d7A8(w8GGN_W^G;`+2g@>xB04-=(_!#{ff}dYoJ6f2$>} zu-HELhh~sJ7KRCEovJH8S&sX|FvH_A6Aa!bc{he*o%eTyX=y6UAJG(W{0tw3LACtt zZ&w_n#EALB-;pfOc}0J8+bD9V9-r{-i1LTq5&VbwB6%!REyaKcaRd!Qdrx)cryf6= RsU|NLDUmnJl4_vK{|D@nK)V0{ literal 0 HcmV?d00001 diff --git a/src/conversion_subhelpers.c b/src/conversion_subhelpers.c new file mode 100644 index 0000000..584956b --- /dev/null +++ b/src/conversion_subhelpers.c @@ -0,0 +1,42 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* conversion_subhelpers.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:36:10 by ljiriste #+# #+# */ +/* Updated: 2024/11/27 11:12:16 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "libft.h" + +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); +} + +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); +} diff --git a/src/conversion_subhelpers.o b/src/conversion_subhelpers.o new file mode 100644 index 0000000000000000000000000000000000000000..fb25952d583fcfd4930d5dba23a6ce96a78c3a2a GIT binary patch literal 5024 zcmcgwU1%It6h5=FlTNZtx=n18G@5R;YAfB{q}0&XwyupoC@S?2)R*n->|}T7W;V{u z)@f(?q+f`c~S7d&OPTl zKlh$g9PA_hNrHeUOx-tw) zXnNJf;mXotuCj!tFI_a@y~PcZ-wN=A1Mu)7>if`+TF9b5`U(4NWr=)m1^Dfk%U6Wm z<)_b`{oJgc|3CZs8;g(?dD@~J>jj_qe4pSmwndUDKHm;ku+7-(NXleoW7tBMAx(v0Av2!;0x{`a=-oqZQrIR0TME|-A>Vu4b0Kq`{RCQ#$kAlB zTPINJqbO=faMzwu(hS-wi;Xxsq|~sOsg$(YuFe9F>um506rq^;RNGW(1&rPa+HfunT_~{P6?} zjy}n?+Xa#N6@Mn2!f)2NG|&$Q5(@Y;qR@qV{n|`i_5&BnohU4~{93u;x@E@+-R9Ju zV#^OY^TkHcDNjz2RjX6?0Ni$P+zTVW9aN)Et?9MqP%60;bSADkVOVO?7^Ape_hyjC zO@#QI6GooYfMr0h%z}oOH>~V^mc7jyzt*x3SUm@YEo0jxTa2u< z7+ki*3I5n$oVYt^tD!)-btM6w^a>;6Xy)BE-nCMQa}OOu7&6T2rT zCMPEf#o3l0$1Shu1$EyEP;zBx zLA@w)jW9)#4Yn()*BuI_BP=4B=jvobFY2_|NR)?4Ud1lF`GgC_5oyH>b65pYAi~64 ziJ+ozvW7B$Q7$n9aM$$o{=$yiy&5Gd3sIcfsh0%TQyzar##0YMc7EI#TfY^qMwzw` zQHwse4NSbzbH;k?#|z>XEFiR(aHKT7)TDoDKV{+1D`{FY_2#85DQ=ckE+*elNyVrT zsF&4bg1B&2DNK2$r{LmVNWt;uP9aks-K#Vvh_bD~sm1^s@C~t=OvKa3g#J}9z9(QX zQ8zIki0#Ion%kt)ZEN615T`iGU$xaW?AJWkw$H=%dfKkXQw=^lw=-ei%RDs`37q=<6#a;9mW>!E;cBH!YdAfn zi0+Y1*Zw|^^MHnb!SbUTev)Nc2Sh60FFDSPguD3rj6b8{Z!!LyhJVNSiyAKX2f%9@ z{tero)$lVcpVRP%SU#`e4#&Bm;V&`%vxa}e@*f&bFDRluZdHAzSf=$#q;M$#?9lLe zmT%VZ$Jk+7!w<3ixQ0K^vd67jZ)!h3quGDN@<|Qf%>90#;cC7=VO+&md8zqP`98~b zKWTB)xRd)%@f1t#Sv|g54?3>a3qF=s?5_hnFoml+Kq*?7#VZ}#IFxNuaiQ08O0hQ| zL#gh>4wPzmUX=t|_iCL6-qka0)Cu0H)k5$13bhkDK?5IANf&$^ddh|Vz9_lv*;#xb zK`Cg*UJ2hU_yBR-W9;NLt26l4!uR8UqyqX=>65jkkQMqMsq;)q>Tfc$*l{07GL8+?S<1Dkal9o~f+iurH-r_fiANu8GX&XJHH-S!dG=@^+`V1IQ_s1UmC5mcm&{{%lJ zls}E1#;%XwM@)~25cJD`4#4juBuKZdqb{xg54nG}PN;t>sosAFF^Z|iiL9VY-2V?+ zhe}lK3A9f0KhGOthYZ*KDnHe}!2VqWX8zVU6ywTI+0(s5n6}Kij|_F+Dtnc`l3zt8 zt$tsn%pbi4l)tKLYTs!0C_i!*dBB5+rTNn~=cR_+GVSI4PwOK|dj2%8Y5srl_|GPt Ik=OnI0UQ7$umAu6 literal 0 HcmV?d00001 diff --git a/src/conversion_to_table.c b/src/conversion_to_table.c new file mode 100644 index 0000000..9b271fc --- /dev/null +++ b/src/conversion_to_table.c @@ -0,0 +1,48 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* conversion_to_table.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:31:48 by ljiriste #+# #+# */ +/* Updated: 2024/11/27 11:29:21 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "libft.h" + +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 convert_to_table(t_parsing_table *table, const t_vec *states) +{ + size_t i; + t_ft_stat res; + t_generator_state *const *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); +} diff --git a/src/conversion_to_table.o b/src/conversion_to_table.o new file mode 100644 index 0000000000000000000000000000000000000000..55ab5f87b06e278be75a39ef4b508f76bf6fb698 GIT binary patch literal 6408 zcmbVQYit}>6+W}GvtDN%dmWoJY0_qsIEf?JT|19~I)&3JZjQHbFu>LXdb%ZJ{8C_7^`2`NJPXu_;28ijY9%VX7#cbMLw9 z+3PhwdL+-i=R41P?wvbl{mBPUK9n#FP-MVMu)--6AU(V?FNtXhhG7V9UH-*)Z<#Q^ zH~`B_8CYH%C@rJ-ON&K#WwBU#WgEcLX91q1`A&dgk|*X!AN7XuF9|o7Ot`*iCaw#+ zAy|HEsKkDZ`9Gm-DTBOevb?lxDtlNh|8vZC31hrv8rN5RB!v%vxhHO2e(l<~tOb4ZJWb!n+{x=!u2zKz~8H8s z{Ap&7&kFWbzX!&SeyVw5ezrewLojw`$ys8)F@OUYBU_&lsxy#HQ%SPvLGk=7qS-X% zka-rTGLdXYA`9dI$$0T^s39W{Zj_1CnLR+F#Qa$qduY9k{RtU+c*DCwO0f-`Wz)2g zUn0$7+=UFOK@MU0aOA=B@MIx zSSEvFsb-*B&nQ}LMQM5nrJ2l%q<4MH-yzgkhd^2dARx0FC{ka+xNoxxy=U{oLzG-; z)0gkxOaazgF*k`#09f@EHv|kI&`z9yEagj{;Y0X`>qipDQ_ScQf5+P(PI6c#6MlfR zr14(=dN7cX!9ODm94NNJpxE%HiZ#b6+IHa75A4r3Jij%YulcRw_*l{NokpwT!bxwc z8W9Kd2Ts#J?*^gQ^vhAR9NAM1x8RW5FsfACYN1Y9R-*S1uG8bI`ETk6G4)wQj=dD_RE&R$swNoU!sbD^YmV8bt<& zLe4sdvz*m?#xk~#Tgi`F>Fri#ht>P2m8w~p3Ck>6L*}KUR=QyIK7cxj1Xkpn8~APm zLhq7Wjv#0?@bEkKjO}>QMO=>^xe%6XuI~mm<|mfqLR6*|cz#VT9_&V=>6ELs*MMTZ zIqeqDU39$Ssi0X4?CG#LS?o|>afgoRB8$pgEQs7-+VkxO*7cn0hh@Jt&B0t1yVi`F zp~x2+O~00F`Jq?y-Aayb=dj)kqE4vlHQcfr1kC{4Mw!+LV#mP8?F(mI$E$iW_g3J7 z+fJqJ*Qwh9)}Uhv;53>c>7RJ)sodn@!@2RX!oI?IZr|9x@v-sov0Q$-;YCry&AWcZ zvwh_4DQ}`Nb6|fiU(4n3piJNyL&JR44lnvnJ!tyPR+w-37d*d`7a8J4h=UfjPZ_k6 zqQ%M@;gLLVH@u2mnkY$^x&%(K`>CaJ%3Td*J%zETrC4&i?xGBKBXI4?#j=M*$M-^< z589+D7fVEk1$Rbl0XYz^IZ3-xk!PhGG%v_NB1X$`+%UvF){hu(s)(vq==n3P2z>W~ za1x5M(`Yu&*>y|`;KbzQk=*D5?i3YVZb<&XUVUrujY7)G0gOveKyvnOV@uyQ*oqk5 zH-Z-EdAxt@O6scRzxfBeQ1Lp!ze6-Znxn_@{?e87)t-;DoS?Oc?wut3{dPCGNmoY~ zGUbPEmBi$ZCoaItA89Q=qJfF4i@C`ii!Ly=>s853!0xOInewx@N@9X2TL*rp;0Cbw zT}>v4@7*eaDLlr60sm?JYxMpndCxKePt^)EYS6{$2fqh*LfbI1(xvUt81mDQogixO|lvMpa5bw7l4uNtjf7xIc!!oaPx@FiP) znXoU1or#RqzHGsx6wmu4uZQqKp3~5X;TvN3=VLg1x)uG9C*()PB4{y&Z{#@*|B2!8 z(;>QVlqJxQ=&4z+k4M7kwBCm!k;+-&e_{LsQY`$C{wd}+^GFRt`%8@2UdG9fXiAwM zi{a#_#YXpNxXN`>!(V0o5e@%7=lQsXZ)W_ohQGmlS;N1=`BXLhamLSU_+G{@Yxn@i zeNMxvJ0|*~9NP6PF#c5ye~|gFYxu9&|F<;!o9yR%8otE*k2L(h%)hMR^ga^3E{ArW zKV$zlHC&z1H#M9ZbfS0U(Dw6J=2N^5b>5y~TkM|jytE}KWF|q4S$~FzM$diJ^7A??_~X-YBuq3M-5U#>sCu82{=1AH()_4; zIvP&jJEAXWc#ZiNcvNwvHo%WHeHHhHhAaPn)No}Vzi-u?VyJI~9`~1=fR0m-MI`=9 zA*bSbl;;XxP_jaJaT>c}DBw>dIo8!Ia2s|Za%UqbRP4xx!W4Fr1%X!Fsa6fU)M^uD zVs1}O1@8F{u^rfc4L^)=6a4w-Die$Y1*bVZ?P4=q@SBlaz;+*dciTC~MsB@a#h*B? z%JzMaIkcoB6t68gE71d~#OF(L)Jt~K7Gw!4b;9sl{vcjsd=N)+rG7wfVthB__*=Du z)O+0lBBP}vewvfd_iKNki%*KF;=jk|k}x7Y{y1XY);}x$!2&SDEikR0ruzEt@8T07 zxXgwA2Qe|y<5Rz=W28RKaaDhyT^fi>-l?#={^yHD;%Hxrxz!U zg$fG0#oxrun>r^HpZXg;ehV@3sq)0Bpc{Okf4#>3sXXRTyPN&zxXBuo?%Gdfr^e5) zeOrMiKZ!SKF`=?k&{doerlkolv%TuGl)hTO;;FysR=+W>pQ;PhkNQ|;uj<+@Hu=s{ rv5`hOF**+2>?uwC-6Ok0{Qj%Hj4&d7{ghWX`?H+?HDR^#(Cz;RR@v{; literal 0 HcmV?d00001 diff --git a/src/fill_closure.c b/src/fill_closure.c new file mode 100644 index 0000000..dfc6214 --- /dev/null +++ b/src/fill_closure.c @@ -0,0 +1,89 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* fill_closure.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:45:10 by ljiriste #+# #+# */ +/* Updated: 2024/11/27 11:14:12 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "libft.h" +#include + +static t_ft_stat add_predictions(t_vec *closure, t_lr1_item *item, + const t_vec *rules, const t_vec *tokens) +{ + size_t i; + t_lr1_item new_item; + t_ft_stat res; + + i = 1; + while (i < rules->size) + { + new_item.core.rule = ft_vec_caccess(rules, i); + if (!cmp_token_type + (&new_item.core.rule->result, get_next_token(&item->core))) + { + new_item.core.position = 0; + res = add_lookahead(&new_item, item, rules, tokens); + if (res != success) + return (res); + res = ft_vec_setinsert(closure, &new_item, void_cmp_items); + if (res != success) + free_item(&new_item); + if (res != success && res != already_inside) + return (res); + } + ++i; + } + return (success); +} + +static t_ft_stat fill_closure2( + t_vec *closure, const t_vec *rules, const t_vec *tokens) +{ + size_t i; + t_lr1_item *item; + t_ft_stat res; + + i = 0; + while (i < closure->size) + { + item = duplicate_item(ft_vec_caccess(closure, i)); + if (!item) + return (alloc_fail); + res = add_predictions(closure, item, rules, tokens); + free_item(item); + free(item); + if (res != success) + return (res); + ++i; + } + return (success); +} + +t_ft_stat fill_closure(t_vec *closure, t_vec *kernel, + const t_vec *rules, const t_vec *tokens) +{ + size_t i; + t_lr1_item *item; + t_ft_stat res; + + i = 0; + while (i < kernel->size) + { + item = ft_vec_access(kernel, i); + res = add_predictions(closure, item, rules, tokens); + if (res != success) + return (res); + ++i; + } + res = fill_closure2(closure, rules, tokens); + if (res != success) + return (res); + return (success); +} diff --git a/src/fill_closure.o b/src/fill_closure.o new file mode 100644 index 0000000000000000000000000000000000000000..323c6cc262281251662c2cb9bdde241cb86a3ffb GIT binary patch literal 7560 zcmbVRZEz$-8SdHH*=(}8%_cc63ArPi+<6>Ib~o`nzV2h;IF7Hf&hx0k@?)6HPBvpE zv&+ov-G#FtmX^RDA%cQ(ASIv&N)-xKfELORQS={R`B5d9-1);Q{Db^j^*rCV`|Zta zC;Nx4%5=X^zaLM(-P7H(x#!TWHzYKT$)d5B*_tF##_k(lYnOSm%r>(@cK*~W&z{%W z@`oALTp44{)lt?wJH(pj23a%Dmfl`Dz?vn-Hm@EiH&=$rO)!0UWjp9@FE>Bb*>fwS z0$atlKKLB=k1=+qmSo2+Tnc)+wtQ}|3_i=?o9s`pS65DyUq!t;7(0gTZ5RV|!T!Mn zgIHr7bcN2t(*AX_A4{(J>H%LXz?UW2GV$>^J^QV5n^RNPAUxl%s?PE>k&v{)6d}!=AJ~@8i|A7VZ%iwDSVxH@Ral%+vAvdW1 z?1c-DK>SxRSHh0!1F^9~oAZSjoG<1KVBH#%}X2lIz~2QiPx7kKcP zFsJ8WoM(aCD&!P>e+_vZ2406_JfOW9^A_iUK4Lr$p1*MHEcjXlU+Cw>4t^5g2lFfW zKBY4l8kRI)n!UUodsM(emPFdXCYUgmcx$MPRl18yNl|HOE+t4x35i=JlZNX@%t)uw zi)biRxnfuHFd+Ko>}ybQ58_GQIHL1sl0OapObH_THhl@qy5W!Ilb7T&FbZcpC{TEoIya)j2mA9sTXxcu+)~^uR!3OQ^Uj9 zCSha~4lT`6>2CqZCnR-o*CW!hl-inWwk$6heq+sYj1P@Mrt;lyLDwem#k4~iOusBI zP(wTY0IYy4O4^|@Y$uj)C$T8RBSO4k;M=_SMiO@lvE1h}?Z#f@n^-=X zQ$1~Drn7=fU6A=?FNR7idu)Km=x+-x-VzKg!uDT=VfE!#?jd(@S(9n9$2(QLmq(3KkkhC5g$vmYP` zw}t81t25VRuFBj5n@o~=;4LxwKnW6x6?SzcH9fmOgM!f408H-!^R1xPJqW#-%vw*+ zrkLX^K_de|T1G;kcPB%?n+n>25y|1wk(&mQWqJ5J*NtF+tPyjQfYYvTcgzg}IRIKC zK%l<>R79Y4?gl#a!E{}YQ-{+=+X!#MBfg7C4C@B0FrA%&R#N*M&J?S*U9_ygp4+o~(sTXB$;qnUC{C4%u5Wvdiojks% zX(Kt0COs2I_bo=MiYA~nsNaQJ*Bi#?j2`Yp8&4!4&GSy+J01(oYG5raSb-TdJcotu zU5*(sY=_LY>Xz+Bi_CXUm~P}OF#d>4FPIXt<#{#RoV8q!73XRTPH}$Gc8f=X8afS& z2aA|Y*RPt9HRCyE)$yIcf>g4|#GOAfX(HOD3plj`@btS;!||h#c{RV9Z}_2G^_@x{ z&$4i?7DVk3OuS<{K>$G<&&2UCzvi1^-Lc(SSCEA@!JJm?mPdQe3Ltn?n|FMuAu01t zr9D5iqS)b2-3Wh8MNvcv>Wr>!LS4bju4ItFmaikYaeFq75?;E!JU~@Vuj8y%xHWTl1M! zshIV^skksT!o7CXmOJ{9V7^fceDf3i;abYPET54)`$G2a3w; z%nlzscy)f)_09|?Sxmy@p3BtffESb(e&#_-yXz=Rp1edG?HyxzkYStSg`X+cW|y?b zb5HbL_fYok_uhR6Pm`_iw^yhze&k)7J@Rg05`*Qb89NCn>gSo%Ocb@rEw06>*47aj6e4(CdoM`qp6x=;CtK)`zzbxhCQr z2RqGF3E0m&=(lYNa7yktx$ZTN zzj)JZM+Hwy*t$*I5-)VsiA>))DR(S;p)U3=lkXF_DXhK7$7`@rp#~l!q4X3w5o|b4 z02@@`IO1HXH0qvfTM>!a(Z*HU5{VLw56dWwn_pLj$gZavaekL1`A7`McS4prHBdjk z#vUa63cxRt%1}Q{?JE`hG~wuHOHBWz7!DW6R=FJXu&De?F(m1oRaAeUcXy{D&eOyH~-VCizhX&y)O&g5Ni|=I0>o}1yIo4BBC^{$*oSn0$a@d^#G=~ceQG2AN9gh=?U6rnSNXde_ymYOMe*f1 zg%}n!eg&|N;xAErxlS-X{#LHWZ;(&P6GUFN(xvk?WgW@*vR(phY^(Nvq08eg?rrTM z?PPsF*{^AcmL@N{N{6(Q@DtELOrgorWPegBQZ2_XVZ6_6l)pzQe>ajM<_}*qWJP$#%~ +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/06/27 11:16:53 by ljiriste #+# #+# */ +/* Updated: 2024/11/28 11:19:27 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "../Libft/ft_parse/ft_parse_inner.h" +#include "ft_parse.h" +#include "libft.h" +#include + +static t_ft_stat init_state(t_generator_state **state) +{ + t_ft_stat res; + + *state = malloc(sizeof(**state)); + if (!*state) + return (alloc_fail); + res = ft_vec_init(&state[0]->kernel, sizeof(t_lr1_item)); + if (res != success) + return (res); + res = ft_vec_init(&state[0]->closure, sizeof(t_lr1_item)); + if (res != success) + return (res); + res = ft_vec_init(&state[0]->goto_tokens, sizeof(t_token)); + if (res != success) + return (res); + res = ft_vec_init(&state[0]->goto_states, sizeof(size_t)); + if (res != success) + return (res); + return (success); +} + +t_ft_stat construct_state(t_vec *kernel, t_vec *states, + const t_vec *rules, const t_vec *tokens) +{ + t_generator_state *state; + t_ft_stat res; + + res = init_state(&state); + if (res != success) + return (res); + state->state_number = states->size; + res = ft_vec_append(states, &state); + if (res != success) + return (res); + state->kernel = *kernel; + res = fill_closure(&state->closure, &state->kernel, rules, tokens); + if (res != success) + return (res); + return (solve_gotos(state, states, rules, tokens)); +} + +static t_ft_stat construct_first_kernel(t_vec *kernel, const t_vec *rules) +{ + t_ft_stat res; + t_lr1_item item; + t_token token; + + res = ft_vec_init(&item.lookahead, sizeof(t_token)); + if (res != success) + return (res); + token = ft_token_dup(&g_eof_token); + if (!token.type) + return (alloc_fail); + res = ft_vec_append(&item.lookahead, &token); + if (res != success) + { + ft_free_token(&token); + return (res); + } + item.core.rule = ft_vec_caccess(rules, 0); + item.core.position = 0; + res = ft_vec_append(kernel, &item); + if (res != success) + ft_vec_free(&item.lookahead, ft_free_token); + return (res); +} + +static t_ft_stat construct_states( + t_vec *states, const t_vec *rules, const t_vec *tokens) +{ + t_vec kernel; + t_ft_stat res; + + res = ft_vec_init(&kernel, sizeof(t_lr1_item)); + if (res != success) + return (res); + res = construct_first_kernel(&kernel, rules); + if (res != success) + return (res); + res = construct_state(&kernel, states, rules, tokens); + if (res != success) + return (res); + return (success); +} + +t_ft_stat ft_parsing_table_generate( + t_parsing_table *table, const char *rules_filename) +{ + t_ft_stat res; + t_vec states; + + res = ft_vec_init(&states, sizeof(t_generator_state *)); + if (res != success) + return (res); + res = prepare_table(table, rules_filename); + if (res != success) + return (res); + res = construct_states(&states, &table->rules, &table->tokens); + if (res != success) + return (res); + res = convert_to_table(table, &states); + if (res != success) + return (res); + ft_vec_free(&states, void_free_generator_state); + remove_zeroth_rule(&table->rules); + return (success); +} diff --git a/src/ft_parsing_table_generate.o b/src/ft_parsing_table_generate.o new file mode 100644 index 0000000000000000000000000000000000000000..1739c7ffb216ece2e7bd5df84f108df014058bd8 GIT binary patch literal 10496 zcmbtadu$xV8K1qoJ)eEfE2iG2hJ2%A*~wJ; zEbt!e2OieJrN?9AY~qu+ZGJA(CbU3(yR-b8bV*hH#t8&bv~$_x&V3Y52a70L+oUKXe->clV}%ngS-n-;PHIdwil*2BoE_3-nS0`NRwet&_n*Wk8b|De4pw>5Z; zz&j7T8Tq9-C!UjE@;-F{3Cn5-_P;3sov{!nM)>m6tSYsMRt^Uuz-BCnm%wl5r|}kP z;8IB3vAsvOpk;kV~7fB1J=1xLudz7gIC2~h8uKQUNv41@N1A? zL;R}qYgj}RToQZ)6q-;g5n39LLuaBWgc6PG@GgXQE<}W|oD1>hJ!Y1LRzw~IR-3RE z>d=1!QUh9%9TZ*X4&wU!_&w5rz98bDgJ#FInZA$<5n)DOq^E$^fLyNFtuKkg6C#4q zmo;Gn35f_gi<4rzo&%`?xm+=)ua92pFZsbB*2%C8S`pIOk{-m@P z54XnW!^6O7;kGucldxbGW-G$Nkt4w7107!2@OP=%9bO#2)6-nqwq#m!S+lPL;Y4F6 zH1XIU4KI)X(9`Mg#U5Vii#@!`7khX$7y3nnYj{V-DV$FIKClMQJtSyuYZgLlU&cF?cj>Mj*#_FPQPLi0#d=`kW)eGZ;bJ;&n-0_R&8Q!kIKZ7~g+}ae zV4@Flg+mjLj6?Gr_+#2VbN#LkBL+n~@}lReuNmu}tG@PEg)8B??>ZEN6K4(zU!Rx0 zL?rjhNWduu5soZ|t8m?0<@%!V46bj4$5A`wnA}7qulU)QeXrF0ww3V@zXfU=YHb~F`=db z*tiC)ECzN{3$#X~(=E|iKKnNSqZxpRbcg^vmD3Rf;LH_EYFidaX!U|yS}^Q%+c!S7 z0A0=26?z=>J%gw}CkZhK4>PpcwU7}=E)>2n^BP|KTY(2cr4`6Q_9v)?w2x!6m<9y| z_|qIa%Tg7`PUWqE)NnSNG7LMLyMA3)-YQl`yM~LER8M!xDrWPQL6hBP4Gg&`G5iDF zR5F7V3W-^N|9d~fh97^V}2S9aP!vz6mJP3wu zdv$J2NM$#ZEfrz?u4LU3GGIzbe;KO?)&avkOxIYWNDK(U7EOP;zq zVM>oAb-h<_>Xr3dKdIiB(zW)rdgKAp0Ygg@dTUaTwCnmV)C44+&=*zoNJ76hfmaCLz5dIF<}KsdYf;AX71bnA0A>GRsjVz5_l92UChcek*{HF%(? zI*fiXGW39~+f~-`l->ie$es#+pcF{$npO#4I|@%@hoK z#2m~F+eQJZ8M~4h3P^5PshDxfX4V?AvY8>n%A?z=Zh3PrGi2G0o1q}eCC75D zQjtFgpET*+44z=jduA4Wz%;KPB6hSrytloV2`gMt};Y1fKKfSQ3fnwK? z;fxitIlELWRh+I$aj#Vz?BY>75G$=WVw#BOgHJ|>kBkFzA#WCqf(aqf0#~w$49|gB z@;t=I+c3+=V6k#6SVy@boV5d{4f<6BhxYu>9h_|{d3d%e*{ta}jP2OAZDV51c5?tb zCpzDCeW#iRIH`)F?YoPGMwe=fnwPP~0KwkE3*Uve#=4J&kLmmV_y>Mg!1f!cogWmo z#?nV4#~LcW_C9LAi1)3r^3m9_S$lo$qtwn1Ra;~IN1KmDv(%n|wkN2apYOKDb{=gy z*62_>HPyV~h81ETU8&U=todaI_dM8EYLpgUbV$w`I#U507~rgH_vc^$y%I>fa@%7uu@LbsDBcx4^eX^a`6P ztfQ7YV~wUZqg;liA2*(S#yduo@_XPQ3WppAP4GQ0Ggv93Fl3u>u)!@>TF)9{ttEp< zz^1BY+UqVW+a|Pt2|Vm#P7JcStvnN`%Js!=ENauddwC<-rHat zW!X*@#1}{q?&Ui8kvjMrb@1(A7Yo{7B&z&+*oWi(Aj?ZWTs*s?{dS%p{00R- z?z7YGv;US4_vc|TJ*U_&_>S$B-9FsUANS!aJT_zR`tS}P{!hX&{*^xb--KiQeq3&a z7*D&89|;Ko@l`%tR`CtezbneMM&fd3kvm}k_>zM*-6#cyGOSVN54NH`8ox^hU9Gu{s=kwjDq93isepmgU_d;UmJ)o z&rK2^B|h%YSR@W7JYI(AF7X{?=YWDgPWTrU{Asc;&s);YDVhhz6n>8I?2=F z+`KsD^Ye^?pP+btrr-mFKd<0Hvj2*L|AhE&E4WSg`wC7X`-_4*WdC0ZK0^2$y372S zBzGwIdeXl}!A-)u6pzn$mddIJ@F?L{4nvqtKeTI z{*M*>ILXf|_z~*YuN3_IB)_NNr^)_B1%H_0xuoD9kbGIezfE!z`IqChiSVTgF4v2z z6eq;Z%jZNsH!}Wjl6|?ZNSyz80&QPa>~xa- z?mbaQsmN%dZKSaSD{Na|&PD@t-&RZ=Z2eRPFq&4ld8SI^>Z; z;ml3Mm$=N^ZUvX)dqBbEJUpV{^0{D1XRH9P5^#5IanH$`ZRU-nYmT}sIcT^BOAf#X zp`=|B0&m4?5^8`Z;ZvfKhj!E&GzTif@Y*y~0$pA=1_o?%PgS#F8^vMx_y=;VT?`QZuq6q-5scT?fC4{l6sv25<_?@s#$`R8fEHpy?oK z{2c}{$(IeI@J|a^TdwNR{q-Pz}-!Hm_HmNsW0<)H(+W`P~}nb zANIdI)ZpSdx|aW&$$yy~qJONa{s(H<1c-fwHrALDoFcMH9sMKxH*>~h|IsEERlf{a zt@zKhbGoOG@#9#k@#DEnwTYTj zar>z|BPZl_Fuwh zp;9YZtlSO_dY_!dQY1ws$KXRz&{G RdoBG@ivJC6ZTh0>{|DLiU*rG) literal 0 HcmV?d00001 diff --git a/src/helpers.c b/src/helpers.c new file mode 100644 index 0000000..e282cf3 --- /dev/null +++ b/src/helpers.c @@ -0,0 +1,61 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* helpers.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/28 11:14:16 by ljiriste #+# #+# */ +/* Updated: 2024/11/28 11:17:22 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "../Libft/ft_parse/ft_parse_inner.h" +#include "libft.h" +#include + +t_ft_stat v_token_dup(void *dest, const void *src) +{ + if (dest == NULL) + return (alloc_fail); + *(t_token *)dest = ft_token_dup((t_token *)src); + return (success); +} + +t_lr1_item *duplicate_item(const t_lr1_item *item) +{ + t_lr1_item *res; + + res = malloc(sizeof(*res)); + if (!res) + return (res); + if (ft_vec_copy(&res->lookahead, &item->lookahead, v_token_dup, + ft_free_token) != success) + { + free(res); + return (NULL); + } + res->core = item->core; + return (res); +} + +int is_viable_item(const t_lr1_item *item, const t_token *token) +{ + const t_token *wanted_token; + + wanted_token + = ft_vec_caccess(&item->core.rule->constituents, item->core.position); + return (cmp_token_type(wanted_token, token) == 0); +} + +const t_token *get_next_token(const t_marked_grammar_rule *rule) +{ + return (ft_vec_caccess(&rule->rule->constituents, rule->position)); +} + +void remove_zeroth_rule(t_vec *rules) +{ + ft_vec_erase(rules, 0, ft_free_rule); + return ; +} diff --git a/src/helpers.o b/src/helpers.o new file mode 100644 index 0000000000000000000000000000000000000000..71cc42d46299e59ec1850c2cc29df68272b40bbf GIT binary patch literal 7992 zcmbVReT*AN6@TmXI==Jea=A-#ANg`hnx+c2@7mBNP0~6f(2tZT{QxznbhBsg*-PxT zySq;Bno12&m7*e%v_M;trV&z65+uH)s(@%4fj|MNQd`vKAA*vo@CQO_BY{MOLV0iI zjlG`uKihwe=QEIFSkUPhB|Uqo3k2`2&ZD+hml;aG5*8HF+S-NkMZ82 zJT4+nwva5Iq&!G|<=}6w%0rC<(0794q0QwBCY(BNCPWO%@dA!Z#h{qyM_-zN6)@cK z*{O|)`#=13>d~>m+;LnuR?J`8}ol4IUDpiHzg5>Rpm`es< z!%ldRPxdAdQ#_O6X^Ce_CStBM520Bf{y{dmYAAyV_Y;%M_HCqIGHV2rmdrJR8Oj`R zOOX6T`eD=>lireRt=}W3h9w6qd=FWpL!VQ=t?_h7zB6GIfHfhQwDe#tx2{FC0n!zQ zlh(?iC)8;|jlSoH8$tefQJj6m-baEEabw-#OByK8yj{fhoYqyz01vqwg+dvG}l- z*u)kgD0;+qu{MarCY&)7-b5;C{CjXA7}$`(KZB;G&&6_S%N~MD11f}Xt8*??! zZ_VZ^eycDwS@8T)tyOm6Zf|-fA`a*eZ43E)L4q@p-E@M`1*p2UrW=HLoO6IMDwo}v zd=)TXR0$&|LI&3oGENY*X<;k5W@MKdK5jX!Qq&*~+_{x^+w*;wFxqS_1NvkckTHi1 z%i3l2Z?l#btiD~Av1ZCj-)33c2uc+!>zHLuS^WiTU{Z-!@3ySG)!(x6TPM^>w_1$b%^X*Fl7tUsnr@Kd&coDVr} znow)_m2Aroy^8OavvlT!)kY9?Lo;5@wcQ|S1mM{tyg55HnZF@FmAzr|hN;P^smW}v zUh|@;=H^_#>^VO2&a}6!*1TzBHdo2!aFJ}om4=4787G|cOVyy^H(Ft?y+nkS%)6}zM`Hbj^>)U;Kb~b+h!y5BCp|##V6MR!KDUHBrgZyTMf?hn=PC@ zntaRv7h0{+*zZ&^E>zse_T5=kSh#)1j$5+pce>LwNpcc%H(jq!C!Z0tgFJdKBxhF{ z%Li8D6_BnMvK6V@KA3$mdCc7X=X1EJgOG0`0-HE-whvCem^xN4Z_Zn9V$x0l(#CywtEv~ zR&9U@Q(mZa7{?{2Fmjc_SDpUkK*^r^SOEOA0SSCR`3*y-wR@|FusRz zb&I8Vz5KsB4<0+?*WxY`+Z4M`z_qhoXBM7sVjC3)n6^9C#py@~{Y>EE(JD?*p*i32nKBrRdPq3(WQEm1BfkC+ueHX*D9Jg(%Bgv4RnhUZ9VtPv0nHt-fnwh_*fgo z3mDTkqyBgdKg2X$#Nzl9jE^9`G^S7UO>L=$AC@psKJ?pG?Kl&JFIOP;|A^r$V|Wtv zsFD6ENs8yr7#`PukZ~HN?@No_`U`1wKB=PAb3`c(K{#=oNJ|AqNyHJn*^ zLBk(nKQC$cF6Lj>@N+!gA8Pn7+0RckT)k$#s^M=j|GI{&cjiB6_?ztitcI^;{(TKU z!}^zWocRGBhpK0p@d*w88}n;4JjedmY4{cPbEAfTjrDhH_|weW8m@jv>i4MfG}zCa zrvEs{{kn!f%lz{i-p~BY8vZ@@|1%ALhVkENc%AXH8cydVwf8mrBU@7e(^vI>MZ;Adr!_xkMD_q@HT^A&|5d}&%>Prvvt0KKUyW6r>B|qbWsIx* zivq>{Ti0j&UJd^y<6qMJFbqviAHNWY7C%SS*+Bv|Zz>be!ICsF7bDlHj+B zX9q7b|DcAeIzOi2Y95bjxLPNW59jLm@``;F$iAwmz^ys?2w&nLUv?q~^3(XWA|Es) zBcw#;kwP?&pCFtX%E_wiPPZ!f?m5#yTR}V1(}8=SOY8)WU%|KUxCwq7a+L{v8_t&+ z^*Vl{fV|&`+&q2;z;}A5w4aUKDqiZGy1G^IAU{TzMH`w@HJ{2wk%`B6z7?KS1ow0| zBCN=~>ell@Q1xDd0&=DHPj$yz$2c!DWe&g6;wpg-(|wzKeq8%0v?ZVMwTCR6=0Ng& zi4fUT{))d92~ySLzs2@hrO3T*zZvmf^_yKR4JO%+>PK^=>{b2fKE|O~Q+6LR_$@6l zUH2YT?-l<9$G?LY2F0h?di-g`be{;p<9rz{YC?^L);#uaa9lNh@<~m%Zz9$!{}1`X zsO%|!noB+ZZ}jkq5PZP#w`u`37M?)eUh%U$L28~TKHazV_}@W{e5yQ=6m0`5{#{#` zD!%HEqjoR*QC_&~rMvc1*{S{{+qV^%xJ_U9j4L~(PxnN^v^1f}_CHsO+^g{`_!mg@ zs^2Cq+$<|n{pjn2vR8HO6`M@{#qsap^-u4D^rzd?f4sDx2qL(j@k`1@!F3+`_~~cT Q%l;>v;F*r8pmh8H0w8>P5dZ)H literal 0 HcmV?d00001 diff --git a/src/helpers_cmp.c b/src/helpers_cmp.c new file mode 100644 index 0000000..fb2f67b --- /dev/null +++ b/src/helpers_cmp.c @@ -0,0 +1,42 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* helpers_cmp.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:22:19 by ljiriste #+# #+# */ +/* Updated: 2024/11/28 11:12:17 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "libft.h" + +int cmp_token_type(const t_token *token1, const t_token *token2) +{ + if ((!token1 && !token2)) + return (0); + else if (!token1 || !token2) + return (1); + if ((!token1->type && !token2->type)) + return (0); + else if (!token1->type || !token2->type) + return (1); + return (ft_strcmp(token1->type, token2->type)); +} + +int cmp_rules(const t_grammar_rule *rule1, const t_grammar_rule *rule2) +{ + return (cmp_token_type(&rule1->result, &rule2->result) + || !ft_vec_is_equal(&rule1->constituents, + &rule2->constituents, void_cmp_token_type)); +} + +int cmp_items(const t_lr1_item *item1, const t_lr1_item *item2) +{ + return (cmp_rules(item1->core.rule, item2->core.rule) + || item1->core.position != item2->core.position + || !ft_vec_is_setequal(&item1->lookahead, &item2->lookahead, + void_cmp_token_type)); +} diff --git a/src/helpers_cmp.o b/src/helpers_cmp.o new file mode 100644 index 0000000000000000000000000000000000000000..9d6fb74712a13d94f8556db11a7d47e5c28c54c9 GIT binary patch literal 6096 zcmbtYU2Ggz6+W}GW3Ro5y@~T<$4$IRoZ?V+cGn7NV(P|?p&@N3rI5lyrS*7sygT)J zb~7_;?4}hi;-Reo5m8m)uYh<-D-h6^_5mSCdEliI47awjaBFjT?$!jrd%p(w+-6pe9UKE}JT?iiPw6)_eIE69u^vF$Z81m5$`6Jj z{3!efJ$U3V!@LywqgaT)Wx}hQX6jX3!i%@B-n{WEv+{>tYuFNecoElf#W8R#xGr-J z*NM1+J=%Xm_%%)8OYkrbnm2{>(t7`w|2xG*evYQ(d`6n%#{L|@-~Qh?zJ`INF>rv4 zLC;|=7?#q9bF;DGgix@Te1@XUvEfl`Khg$?D`&J0 zWZjkfS!{V^^yzKOiCu{)t^B}qs2U`0 z79D~yX+23jx97MwzMI0=D_*HFd6dSfYilgdNU@Ev{33R9xXaB#?B-(Z=I{wxPVDCJ zc`3Fzj$D_6-^31Hh#lmP(>QjJn~@^Lkwed5>@iLZjbzQC@u5A&-u~P{Bu_#%dp|;$ zvIAfa&1658J)6Baf;*Qr_;RgbBmwkMN2>l2!yL+HCD%Y8vpZpW2B`xGWRx!g2JZ&4 z%-Y7eF*VDF#x9Of9CM>DogX7NyR3wp)F?*$5&Xj?VH0~yjOda4a$*n%3%E=ZzKx@_ z@vouXU|>T5|BNuG!X_RDUtXzeXpgSK^C%40En zsAx^uq%mg8*5JdIIcxQ!GG$vPbzjDZ*=OT3jTG$q`;JN8s3Ur%&Yz^?U(e`7G`eG%PGR;ksXK1TDYS2@4(ni=JOAM9yN<4S^C=7Eek=SK8tr zX-UOKYsD=tuUEa|qd|*!VR61l8_DzQ72&K>cYQZ-a2v^#?95BxhMi`V(2{470!lT7 zLaFbS1o;9)TFIu}3cbi{`66)XPq=CY^tQ!&5N<_Y%VGmycIllqTdifM;W{;(h_fD4 zi`^d&T$rDq$xnUUU8KCqycbTN)ZYMp8`N^L1LLX3AiZ|P7~eGkShwKaB%3$}9~jDi zFa5IF`pY|bjDgUfVf_O2tbd&Kd4#?|I5u&dvwnf~Qq%iMr%4*#`%f>e*|Udl=MiqM-N(%Qw9<>@dLUOSoz zauvG5gxxv>HX?fyc~jTge#F(gPa0vpCisfCz{-=@_u|jq0sj=@H18y*TI>VFK7R+k zb^}bV!DNjNdpz6m>k@~V{K8gSUX8Aax78_6IfM56Gc- zmUyiE{Db{`RKr!S=QZ4C`5_H|ko|l{!+*%KI)Bu>8;n;p{%!WNq~U*L{AmsU3FFUd z_pXGS|q~YIZ{2dMdDa-F_`0tsI zm5696Zznj;0~*fea9qQ$vs}_}hYjx6aN6(GKCR)eOBkNe@ON4EG<=KYXEdCCA5eQ< z!ylJ0yrkjpv-~3sALl&$T*Ik=rgl@q@0BpT#kl%j)Oq+?E^#86(@5}-sb3mP5+^nmT>$W#}Q$3F(L<3e4(gwhwc%YM^!|l z%)gs)y+Zpt?>nZ&oetCYMLs{M{b{t-ebQuV{%gri)Pq|_tk?Qgsdb$bM(d~QQD6W0 z9zGF*XV~sF5)w_1^)l*ojOax!Rn`5fTl83HWlti-uE*~oru#$)Dm;Hp zQ)(jAklSni-}3xwpO8rRqCS5IG4iS6#Gz +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:20:25 by ljiriste #+# #+# */ +/* Updated: 2024/11/27 11:18:32 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "../Libft/ft_parse/ft_parse_inner.h" +#include "libft.h" +#include + +void free_item(t_lr1_item *item) +{ + if (!item) + return ; + ft_vec_free(&item->lookahead, ft_free_token); + return ; +} + +void void_free_item(void *v_item) +{ + free_item(v_item); + return ; +} + +void free_generator_state(t_generator_state *state) +{ + if (!state) + return ; + ft_vec_free(&state->kernel, void_free_item); + ft_vec_free(&state->closure, void_free_item); + ft_vec_free(&state->goto_tokens, ft_free_token); + ft_vec_free(&state->goto_states, NULL); + return ; +} + +void void_free_generator_state(void *v_state) +{ + t_generator_state **state; + + state = v_state; + free_generator_state(*state); + free(*state); + return ; +} diff --git a/src/helpers_free.o b/src/helpers_free.o new file mode 100644 index 0000000000000000000000000000000000000000..6b220f74070a285429742f41e48aa99c740f49c4 GIT binary patch literal 7144 zcmbVQYm6IL6+UBocD-@3aW=_5vUyCJ&5Pn!6w;(+Q%iICpI| z+_<*7cw-B|b#!oo+OZ;>L+aB86mMLM$G(g0^D%&RTder+Za#7OrJu!1zt`=F^S|`u z|5^-A{1yF6-x!;Hiu=WMw3U6l1AR zO2R6UFdJ?NX0k82Ko*iJh*oTK`Z8kD*c#YNW>VNHgrpR16GD1m&Z$6bTk=t4jmm6d z6XqgHDjS)n@SRSKq!ZW&;UO`W43Gu`LFhwbgAkI^Lt@;#ikcO~6^8l5ru1ZFxJ4+~ zilaT#vLB#FY`v;q;s`G)G6NEe*}FRn)a4^d%oaP>iFwq5qh&%$pn2uSS-e zM^7(VZdut8(zFK7Dx0(BZRr%QZqYw;LS)9mb|F|&vqK0)DeM%&loWP}QC;M8cAGy% z*C|XB`i6$n*d7ph5+KpF8Y-5Ial4pnV(q5~7US7P%xjfs-oAq-D|W6fTo{>QQpL{A z<4Al3TYX9Df^=j>j!u&)7US6;M~PcoW5a*58j!&D|I0Cz*^iztieGw zS0f2~MHQ*~*BbG`R7!FU1d^*dO!p&o0D+|PMZk(3K$fY!9mLouj#1XQdrXDhIYwy} zM=yM0jJ&QgH8Ok@JAs3NMNGA5(W7%yM<6zau-9?;IkpnUzXn%ZuBVw4)L z>kvj~j%mPv>^=(dA;UB$&Dg=38Q*Lg+X`lEGG`iF3le>#Ry$(G$4z5L!A#z5#&VOB zsEoyM3}zhPb(#>AYQEiS*?!4yHysEXk2|FhYF_A-g3u0~04nyZU1@|1m^;c)D><#% zaG?}>GmZ<5&}l(fYWjteXwG?!s_1&D=3vS;c18L@5*=`Jk`^pkh)y@cw&R8YG(ERw zwcVgmbDgS1C+m_!;XkN*e%Q@$nkC8_XuzfS$U&uU``AO7YEZ&n&N$WX4p*99(Dog; z|JbLkLkA96g?x5TwqWha?;uy|)K_hHBp=6Dr}nGVEK zYI@#`U3cs%!2O2~-D&N**D2Es$r;S-+pW(fz1(Cm9)B1T^P7$Fm0MsVLU;s;Ql#fS zgVuA2=i|rz{4O4cAoS|+w+LYU;ST*t!m)_6o%Nq(y@mKZDX|DY_YCHr>wDfj%6h5k z{iI_m0oVW2OB?Tbv!s(Qdb4$z#ra0m1)>lahe|gp$4Ojpx)p*Sy>23%DpUu9ga z@B2{h6<2?$O;qVM5FI1kuY`$tdT)s%K%R9d;n6P;{WxDb-Sy2cGP5|pJ8(&Kd@@Df z1N$|cZU$7w5yxvyRE~3t@bwYO`xWK2h>v#Qi`=Fwa3_A2aozuU#&ti>+``YrTljf} zalOB0iu)xt`k02RwRK3t zzs@r4FDfdZr#PR7Bpl&?V)>+ozs7P&!(ZflrZxOw#?^jRakn%6MUDRx#=oZFYFxgl z;jc0OB@O=t%WrA;EX!|e_!S<9cQib~{@>N`_gVgjhJT9rc(oNp^;djkA~LMu;)@jV zZ5sX;mh&2}_U%Cp|2)eNYWQ`T2AtCHGn{8b!&@w$(eOK%|D=YWVgDC2{Hx6WmWIE{ z_zyJv2>W?m!~f3mFEyO$@COa=XZdd${wT-2uHl>5(Z4nPBg|jPwVKDLSsvB!57=I< zYueXpZYe}o1)El{NnNSyug4`R`#rPig#9EYlxx zRMfdNB_x3FX?*2J?N{ahJIueV`6)8~N6pV1 zQmJuO{Zf8@%MBgh$T;m|PC+0a*YG0Cr!;(u<Zbv74wTtEy9O*YF#A+Cy8>w##MTnd?&9zU|iV zQ?Anl{~K_W3H|w&t$3{#e#k=B^+G3$-<0@)Xjf*~$f@Hc$Zk2RHy^sT(2}-}nm6UB z$PN9U5cyxIV##+rVT!Lb$N8nb$orD+x71Yc_faP9V4Rl|qW~w^E&{lr!*ow0pC8t~ zfVSkbbB&=0Cpi%Q)zno~{tBdfG*R{Vb+)$@k!#)l0OGyI@7Lms5g^ZYG=4Nk%3h5h zol6{wnX;n)KdEfe64SX4A*WY-;LFb?zN}Gvimk^lBc}UA2)@k=oVF7^DML`?UI5M1E+>b^i26`lKK#CpYlkK?O(B9XR) z9-r=oOE!UdNT4!r#CK zVOpASk?o&RM6Ol;75pP?^cp|)aW%z68bA6PR`zOKd&MS`{ro9^krP{w82xm6N>ke+ fhyc99FRwsIOAo#OYf#n8eu{!&xgx9RsoVb-PnGGJ literal 0 HcmV?d00001 diff --git a/src/helpers_void_cmp.c b/src/helpers_void_cmp.c new file mode 100644 index 0000000..2c8e2e3 --- /dev/null +++ b/src/helpers_void_cmp.c @@ -0,0 +1,28 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* helpers_void_cmp.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/28 11:11:32 by ljiriste #+# #+# */ +/* Updated: 2024/11/28 11:12:54 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" + +int void_cmp_token_type(const void *v_token1, const void *v_token2) +{ + return (cmp_token_type(v_token1, v_token2)); +} + +int void_cmp_rules(const void *v_rule1, const void *v_rule2) +{ + return (cmp_rules(v_rule1, v_rule2)); +} + +int void_cmp_items(const void *v_item1, const void *v_item2) +{ + return (cmp_items(v_item1, v_item2)); +} diff --git a/src/helpers_void_cmp.o b/src/helpers_void_cmp.o new file mode 100644 index 0000000000000000000000000000000000000000..6f5a988685dae872f103c97c6ae77a717074fbc1 GIT binary patch literal 4248 zcmb_eUx*uJ5TDH^y|igB?cIqzPwXPs+DenVoLX(`)oah%9v)JZLXl#+Nw!I7vI)DJ z^Ugjf2!d}dh$z_NV@2N;1gZ7i$G)lcL3|Pw1T9i@=KE&$Hs9^}P#oBuncw{R=9}-^ z@7p&|F29hmED*Bbb6D2|1^A$_E-xr?0VZG^?p^-slY2H?y;Fp{KNjd&xO=C#a2H+P zyLb84jhlA$_W$KGkA-E`*m+grb|oiXorIjp=Sa)sM-ogP!#}ERrS;R52W$U>~ zd-O=*XyI_-vB{-za$nf}{)tIz9Ba&h*p|jKy8*ToG075IM)u(>^P2{v@gVgFA9Pc1 zc_o)lFyiO&v7v$e!Ug+ z{N5le4gA;Jexnq*wT>5ps%fZ<^-_mmnYk{#8m;v`na3Oo?a1p^n3En1Iv(l7=ho+0 zZ@B@e*LpL!r7A@TVXGHJ&d|`@BNY~xL5anix;NA6b-kHOYxVZbnV{DU+-^9tIMa87 zuCgeQ$*>dGmB@PIWyr2RVohz|0}rE) zyHSz)I**S!*Rt2`Q{R7w+Z&Yq8Eu9%yMwlK|6ylSDx*!Ah2Q^4Guo*qD(!1K%^gv7 zP7K*5lt!a$BwL>v8w@t6V=e_B{`SPdhHWAaaT_+Aw90OSYU_|M9w|sgyc;%>jd&W_ zuww)K5F%rVzNz&>Y!5!N_Q{|!`-`9OCpPh)XaCcjMEp-|;-7ZVOs~Rp1LBRZjt>6* z)#mo66gPxaak8x$Da)UUs?ad!2e`D%lV|9TZ|VOm;4OFqlUkn02Kqj%>l{%DKeR4 z&zt#W|C>0S?L>I7^Z$d^#b0pg!+C9v{iXj<4%fPP=^&2+&08V`UdJs*-f9Hph8ww1 zu7x3#725D>gJ!kuU+kex$!@I{cq>C@H*ozX-hIiCPTTh+1jm7Lz1Qt}crBLwUgVYW z9|C^}-1;RB@>qpCM7|p?^(2&7`gX(TsdbYh3R_+4QcgX;45C@seY>6tiO$z znG+$9d0!wUL8fm5ZE53Q;qhgk(D($I;|~y{oKh!>ns`H8F$NS>_*>|m7Jr3`LfWrc z{FXT3@1jNI*a?L%I6jGyZ2DejjF&5Rm-y8f(SpohV7edE`geo-cbXlkfAm)+@zPhS w#~hnNW@)n`{lx{-KSo+S-Rb7HM{)ak|1Xo0AanjyS6cjUT>p(kEQx0Pzo286M*si- literal 0 HcmV?d00001 diff --git a/src/init_new_row.c b/src/init_new_row.c new file mode 100644 index 0000000..b6d5c0f --- /dev/null +++ b/src/init_new_row.c @@ -0,0 +1,83 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* init_new_row.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:29:27 by ljiriste #+# #+# */ +/* Updated: 2024/11/27 11:29:56 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "libft.h" + +static t_ft_stat prefill_lookahead(t_vec *lookahead, size_t size) +{ + t_ft_stat res; + size_t i; + const t_parser_action refuse = {.type = parser_refuse, .number = 0}; + + res = ft_vec_reserve(lookahead, size); + if (res != success) + return (res); + i = 0; + while (i < size) + { + res = ft_vec_append(lookahead, &refuse); + if (res != success) + return (res); + ++i; + } + return (success); +} + +static t_ft_stat prefill_gotos(t_vec *gotos, size_t size) +{ + t_ft_stat res; + size_t i; + const ssize_t refuse = -1; + + res = ft_vec_reserve(gotos, size); + if (res != success) + return (res); + i = 0; + while (i < size) + { + res = ft_vec_append(gotos, &refuse); + if (res != success) + return (res); + ++i; + } + 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) + return (res); + ft_vec_free(&new_row.lookahead, NULL); + ft_vec_free(&new_row.gotos, NULL); + return (res); +} diff --git a/src/init_new_row.o b/src/init_new_row.o new file mode 100644 index 0000000000000000000000000000000000000000..559b2f53139ba1056bb67b2b3c0989fb3b8c12be GIT binary patch literal 7280 zcmbVQeQX>@6@Pns>pT16^VtrKgVXrZxcN}yJG=S*aB^*$mXZKXX{5FwUDkJN-zw+5 z>+W6>H=srZ6;&#trV$i1DM1J+6jTZRX)Qp2sMMnV0Y%UXi6R>zil{1D@dveN2=C3j zx!aqZ0d*wb&ilRZ_hx5j{K%1Gcg73@)G*)$Xi*9UsIO_w3u0P;)i4NG&;9tjS525- z?1SZ{6f9@q{Jo1CVd2^uq6^E5eT8Kdzp%I)78Z9G7DfObItg$e%|8OL`q~IAr}4S? z1(;tl;ko}N-%WBOXfKZbP;Uw6i|FGJz}x1(uiXde`|7!uuKdg_zOKiGyss|mF&)B~ z4n<F<3@1Un7HV7gqiJJtG={fC`z}lF6 z2&IOkHEY!R6;dM7uIgZb^VE%KQDrOZ5Q#dmv1Ipfe; z<$Ckly9X(_!qC@lUrP>pt%#Y}5CAU8mKg&25NHNYK!)Na%l$cwNqW4_?!XE>Ec!P5 z!`|W$%UsOpC%We}L7Y5CD+u1fS={(nx)%%_NZ_9l_$A0U0zY4Mr}8tUQr@=xQf1eU zv8wAe&W_D^jr_!T-t|h=M%j^)OmvW(a>D?Qxl_|2Y5XtgU@ib~JvS_R&Y7ZLJCiF> zNI_UGJJY!eWf;!YodBmMz;sv)LOVnPw_PM`-C!lJz%9KEfdMzR`+q#iN%c#6IKRg$Nx{+WPt^fdCPi$ ztZzqiIR^X3t@Sx;P0mV=Sk{ADnt`@`EDaQ+nUSk#l z4oL+*QwwVW>WE(WqHPXHkR+j6^JcOQFK}l(r<|paTTrR_VLOB+aEgxaV+>BUDD*^Z z;9;^s-6^@#uFR<6J6H`BAQrC?I9z~cM&LK9xVhf-$rIVbd-rB1#&fskCbGAV-#Rfq zF)^MUo2|NGSarr6uk6|$()N@)S*`EdksX`Kj^UD=#5VyI$ENLI&MQ^?npbNCV-4?& z>y^huU@GI5&t{6HitR&_qJ(Aju(7A@s#})niLzW@n`RwlqoG(-^~TyyIX-Zi?NZ69 zhl=7dv}}qpx3@%uWmkP%Vsk|o`+;vby<=D?v6^I8NKtjN;!ZaS-zhgr+)QD-fdK>o zu20ccVO-_sdi6#K{F-BLXic@2H|{~WU$pH5aM$6(`?6c^aHgmovRz}lw(5<;_Zmk= zKEQbRUWlJvZw#**fpv)CPAkUK^m|*na4Gq0qWs4<@lyhVzlSC`F3=D2OU%zAbU)!Z z#8>;abp2BL+1}WlEFf7Oe`#-x!+X~{F-_XyIt){u9j@b;e9DY6WWLwi!4C>t=h?SksVyV~`` z1aVrpj$z7ER2#kvDYYh|j3X=HpGJHD>$Z(cC;E-p$ra?QE8uPWG=9uR&w|<#TZ>&G zaz7j`(?<(mha#T+9RIYVNV{Igy{OHiV$rLj=F`68z$nH;V;JKXr$b4?ef%U`oZ*;$ zF@i_s{~E!g@&&F7*@^b1vI72Y1jjpSb0qm=tjDu0f=A^KtbmLA16qxtA94O>59$s^ zIL$x9ai|;>{vO*^z7$?$J8St#ha?si$X3Ql9#4nOF&@Fm@AIs*Q^WE931S@9@Fk`{ zuHkQR{Kqx?myE0ZNyYyUmQ#5s{HGkxv}WgV#zPGsVf;}IcNzbZhVS5bzM3bQ z+++MZ8m`vs_cZ)%w*LbSf0gaLpy6FC{}T-#Vf-Zxe~Rf}Yxok|e^bNp{~codO~e1d z^glIRTssjPVE?KwUuL=W8m{u3(D3(}-lO5_*gvV^o7n!RG<=-%I-%hQ8CUO(it{q# zwkH1+<7yvJ@^`S`h9>_-mVZ>kw=({uhW9c4Ee(H=@#i)CEyjPO;jeQ%>b+5MzRdXV zH2EV;|4GADz5cG@pJ%@xX!xI*R+kXv_Y(VE!+Hu|VEK(2uJ+;_<7!`0->V~<{93kC z*6`mmeNMv{IG)ECSN7F;;gTk=>iK;QSL^=`4L`{7yrbdl7T#xE`BiuduYELBeN=xx zs^QA-5e-*Ze!cN?akl;KB|IO zc}JvLW$baHqp!W)iVI>ky(r8teZLWiUO@Q*C2QtMUym8Akt)V`%~ zyx6ymVWbEvw4r#e=cC}ejMMj>{HWdzF;4p*;k+yu1$ctjTNB_3$wtREB*^B6)u(f) zZjB9uj*(us{C6#k z6A>A@>^;cq6#t$Zq>|F7_$hWheit#_CTZ?v|7!myjD{{-My!+n3j0^{`X|C(P&48a=AtlyH5vq5#x)fh@o!O!A^FnzfX zvHn>l$WN8Og6TZhseb3Vejj5&svo_QN?+BrlW$UalKp2mF#5i!H9&l&PiK3r#KeZn Ye09|0*YhWvo%CPf_^$|Stsh_9dH?_b literal 0 HcmV?d00001 diff --git a/src/lookahead.c b/src/lookahead.c new file mode 100644 index 0000000..a0da3f8 --- /dev/null +++ b/src/lookahead.c @@ -0,0 +1,84 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* lookahead.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:48:32 by ljiriste #+# #+# */ +/* Updated: 2025/03/26 20:54:48 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "../Libft/ft_parse/ft_parse_inner.h" +#include "libft.h" + +static t_ft_stat add_to_lookahead( + const t_vec *lookahead, t_vec *new_lookahead) +{ + t_ft_stat res; + size_t i; + t_token token; + + i = 0; + while (i < lookahead->size) + { + token = ft_token_dup(ft_vec_caccess(lookahead, i)); + res = ft_vec_setinsert(new_lookahead, &token, void_cmp_token_type); + if (res != success) + ft_free_token(&token); + if (res != success && res != already_inside) + return (res); + ++i; + } + return (success); +} + +static 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, &g_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_item, t_lr1_item *item, + const t_vec *rules, const t_vec *tokens) +{ + t_ft_stat res; + + res = ft_vec_init(&new_item->lookahead, sizeof(t_token)); + if (res != success) + return (res); + ++item->core.position; + res = expand_lookahead(&new_item->lookahead, &item->core, rules, tokens); + remove_nonterminals(&new_item->lookahead, tokens); + --item->core.position; + if (res != success) + { + ft_vec_free(&new_item->lookahead, ft_free_token); + return (res); + } + if (ft_vec_contains(&new_item->lookahead, &g_empty_token, void_cmp_token_type)) + { + remove_token(&new_item->lookahead, &g_empty_token); + res = add_to_lookahead(&item->lookahead, &new_item->lookahead); + } + return (res); +} diff --git a/src/lookahead.o b/src/lookahead.o new file mode 100644 index 0000000000000000000000000000000000000000..cec075f867091ea13f59345c36292e9ca7c17b09 GIT binary patch literal 8456 zcmbVQZ)_aJ6`#GmJ)eDvbGC#3BoLp2;{=ND>?kD;#L0o75P~SAp@ORFWqr3kuX4BN z?Cu3Ssc8CFty)!B(4tBKS~ZnQDplnZjRYtXd;p3BR4ue0ifo`?T2(4iE7fg{``*lZ z=e_Y+l^E%E=KbE^c{BHBcE57xy`PC0hTvw1=fyh3s1SGWTp#DQ(zg5xh(3Y8rMB3!%U>6ZFn%m1fR|FdrGw(i(!uBJcOB60KxjP)^?`{GiMiVb7R8{i-0q%Y8uaicH5(ANj6YbRr1 zYcON}J}Q@LVSgFya!#VMy3MJN*G{6n)$=b?{FGzxzYKA{54rvTaxHD-#i9|r@LP!e ziKU~E%cGH8!uS@<70w4@HZWf>hQ6VTF?|4Q@jk7Uw1M*lyUTz-x3>0VME~uEKKaQ| zeqtc6@&|J?W0zGt`71lnKiD&gk87{wAQsbDZVY2g@DgowS}m&Y#ICaJjUjHIMuL?sj@ zwc>Hh^+I7K6UhZsRH9O_Eq)gu=Jw7Pp_3NWldMU^l+U<)TJo7tftc5s7eK8Yej*d! zl}^Dt;2#3h%CsNAUJ*l*NGf8tB+{v~PEo|KPo4p(eq}8_Y`q557PP{1Q?r&1(pF#k z1Us+>k^wqM1)(pj9g;{YGuBS)MiASAvQlx(x-R|QhT>ocGE`(%CW+3{q&Q?1f!czy z%44E8{R$8=@I-$FSU_TQFHovtEgdke%kkuA9%+4bzB$T`XU~(U*UkhUGJ-|(+);S$pBZenHA_YK_ zJt44VM4(;RVCxaY`i1Ds8b=2h+B_WVcoDxYN0E zv6!=Mzc_pIfzgWV)#pdcUOhKHmUF#grCxHxz3%i(h?Kw|=;pH7oC0UU!kp~~ju4ev z?X*4X*rjX{T?ApNEL$TTydip;+^vh}4T=4JDu;v;BhW zc@AP&LoGwJt3&`{b{kgwvsQA*>fddp4qNRxD^a%MlU5>U^@>>BIBcaREfWZH{;-wI zTJ2`XVXy$4p>ZpIA8Mv{Tgl^A;vUN!vw9Aq5a6-vt>h%K%;S?*&jg~e+bv^gzm;?? z>tU;7((24vu`EjE;F+;v$F0ueh*;q8h}BWHddI8;kTYm_N7-u6&Vqqh43;9O7mH31 zh@epR?P}Hb3x2)gh`>GP6heXHKospcyXb}sqFivQbKycEteti|;W>{K+|a2C`3MUY ze_YW)0SmcZsnm*v8QZOh+-$AtksF z>S2MFOZsW7Dg@f_BUi}{>y8%&;Le9dUw{P)T-Ym>npe)$VO;i{QU*`DV7BIm&CrYs zjve0zr%t7Sa~59BD+F^+(VcNs@O9r2P9v6v#p0~(Lo6y2xD^`_!oCX%kjT?csX3>2 z-S=Q->d>Lg_*iy-c099xZ2$P!`1n|6v|4e)u;Pq5UdgpRpzUdQvNCt`fy`(*GYUI+ z68;FFI67ko3tn;7uX(k4Fk1H>alO*0OkV(5Q?Z22P8$JZ3Zz5;|DLmU#Vx4`%S3I= z7S#NDg*0&8YcphjT^=pUG}xt5p)q|3q}AlZg*n(&atTmxt`@kVTl3@&Q;Q|d)garn zW)0I}En=NxcfGkftSK&;?^J7NodT>}==fFFvn#=R6%gXCsi|8s`|fb2F}EuBqc`86 zuLAsov87cfjB_VMe14a)bIYKB_XoI+s3wn{+dA`4C7*69zxOA3@FIVL_*b#Nt#jcgdu-sCbhFeMrYvU7s5;Q) zMX{LylquvrvI$r68*$915s~NoV$Kj}n)@52)s6ES1suwisV+DhIA$X|>#P$negX6Zuy+!T-1k{^w2b^*=t8;o(wK z4 znDHGrP356UE)>yRI7!p>+)z04bG8?)s>DP~XiaWr8 zKSbZuDq<&^H)RECHQ0}y z2JD}4eiPsmAO`aC#f%K_cMQbwb?!9u*tk+MekbAAC^meSQ1TAZoGbK8Axq8;5qY+W z&{zaVzuzRKPir{u(J2k*{dbRsFHxKiXn2lrKJPjHzmQx(lYgAznbGhn;a}G9qlAA| z!}pM1tl!w!ucF``j0TLqM)Wfp{sp3crs4k}`@hieUr{{IY4|G9&ue&^?7XDm9N+62 z&h_P84d=S{p@zRi@qDD=>T4SOugO2>f%7$};Re|m(eQD?Kc(T5L}OjR#`b4P{&O1s z8qs_{vONEf&S>&nUmn$PJWsKGPs86P`Y8>6km$=Aeu3hAUc(%5_BSV@z-W#!H31@k(Uk5e$JBYqLB9B8} zr-wE9Tcvd&c%3=UI|%3eF}{oNZ)tY^M)QA8!(S%)*VJ>}yF_;0)Z{sz?`b&O|F?z@ z65R`5M6hw3&k#ODIQvyna8Jp0&H;Dbuj zxp0`|8RxuxQNwwCMK)Nd!W%X8p|AQ`9{Eni&W6r>D6%Cxv_*CrzMEwInj$0@hglc_ znuV_)b_MvTRdS~5W%x8PQv+Q&wx_3k=WG+(_HC~WpIf3T@Ey!y75uE7E!L`4_}(G1 zUM+O8@JRu_57@=iq~y%PUDK}eX-Sj(1YHJna7*&~u!%ek^lyD}7N8#QMu_E!=5C@( zjrbmd??dQ^>mJ`xM+m2FqmwG+_Kji8eo}{y6BOP2C;)*WVO5eo&DO z-%C+n_rF92Gg4~(q3a(4R;&Cy)}wUzUW56=HDZ0v-{%3-b0ReMS{{qGT LYC}^Ebp8JU+C$|- literal 0 HcmV?d00001 diff --git a/src/lookahead2.c b/src/lookahead2.c new file mode 100644 index 0000000..3bd0e20 --- /dev/null +++ b/src/lookahead2.c @@ -0,0 +1,116 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* lookahead2.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:50:11 by ljiriste #+# #+# */ +/* Updated: 2024/11/27 11:23:23 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "../Libft/ft_parse/ft_parse_inner.h" +#include "libft.h" + +int is_terminal_token(const t_token *token, const t_vec *tokens) +{ + size_t i; + const t_token *table_token; + + i = 0; + while ((i == 0 || cmp_token_type(table_token, &g_eof_token)) + && i < tokens->size) + { + table_token = ft_vec_caccess(tokens, i); + if (!cmp_token_type(table_token, token)) + return (1); + ++i; + } + return (0); +} + +static t_ft_stat insert_terminal(t_vec *lookahead, const t_token *token) +{ + t_ft_stat res; + t_token token_copy; + + token_copy = ft_token_dup(token); + res = ft_vec_setinsert(lookahead, &token_copy, void_cmp_token_type); + if (res != success) + ft_free_token(&token_copy); + if (res == already_inside) + return (success); + return (res); +} + +static t_ft_stat add_first(t_vec *lookahead, const t_token *token, + const t_vec *rules, const t_vec *tokens) +{ + t_ft_stat res; + size_t i; + t_marked_grammar_rule rule; + + if (is_terminal_token(token, tokens) + || !cmp_token_type(token, &g_empty_token)) + return (insert_terminal(lookahead, token)); + append_token(lookahead, token); + rule.position = 0; + i = 1; + while (i < rules->size) + { + rule.rule = ft_vec_caccess(rules, i); + if (!cmp_token_type(token, &rule.rule->result)) + { + res = expand_lookahead(lookahead, &rule, rules, tokens); + if (res != success) + return (res); + } + ++i; + } + return (success); +} + +void remove_token(t_vec *lookahead, const t_token *removed_token) +{ + size_t i; + const t_token *token; + + i = lookahead->size; + while (i > 0) + { + --i; + token = ft_vec_caccess(lookahead, i); + if (!cmp_token_type(token, removed_token)) + ft_vec_erase(lookahead, i, ft_free_token); + } +} + +t_ft_stat expand_lookahead( + t_vec *lookahead, const t_marked_grammar_rule *rule, + const t_vec *rules, const t_vec *tokens) +{ + size_t i; + t_ft_stat res; + const t_token *token; + + res = append_token(lookahead, &g_empty_token); + if (res != success) + return (res); + i = rule->position; + while (ft_vec_contains(lookahead, &g_empty_token, void_cmp_token_type) + && i < rule->rule->constituents.size) + { + remove_token(lookahead, &g_empty_token); + token = ft_vec_caccess(&rule->rule->constituents, i); + 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); +} diff --git a/src/lookahead2.o b/src/lookahead2.o new file mode 100644 index 0000000000000000000000000000000000000000..79ee9c69ba3b787765e6ece824eb02cf90486c79 GIT binary patch literal 9648 zcmbVRdu$xV8K1qqvClro&yYAV;Im_r@bH}-97=+nTriM8C`|(`DMeh?cWZl_^WCw# z7wm+#rVl|2m9QEfRTD~zkP`T#P*nxgf>Hr0g;s@@NB^L$4V7pGm7ot5w?yvu&3v=o z8=ouGk#2Xs-+b?Hc4l_(%a>n$MZ_?eY6g3PEm8_)?ETKgep+$4xj36&Sk2~}7+X2FIz2xdPtODEk=ZsFYXZ7W(xB>Qi?QnxYF-&!dg)jJ^BNM+?9^z4!FtXHT3mGq0aM{L>1b0zYn# zoSb`z&7j^01Ao9L=pUKg&Yqgxo_-4b+K>7r58!}BrLU+zg1!QF`tWmP=O@w*_&o

r9xh;cv0F)pHK< z$+_}BV!aUk!#N1?VNMf3FOd^-6nN5X26G_t26aF_;b$kvk`0_Mw?V#xT+`SgsAaWW zi@6@kwbH5kfO=(K+k*fzlA`8aJyltFp0#o*CmtN}0KHf=6a zkr+opAdy#Ar=cH-)gly$%9{}rRD`G+NeQWFlsg5V@mNi43MC|~V62Vq1jJm~_%z&v z26-iI0x`ukDz02yYosIQS>`l|)xnP?qGvb9Ar6?u5LTjY0Pm9M5=2ZA-GXS2AGEV9 zx-NDzaJ5Tq(H{N_pc+t%icLl>3^eoA&3lyrz9#0Ofw{5)W5Kwcr( z$IoiMGZ5^o#{uaXPsGqzGYNL_EKm)|D=pTnYJLs~;do7ZJNAiKvjXFbv6|R@0E(*A ztgSr?{e~CevH}KKZR@I=pkEhMQKD@c+K9Zy4RI`hYRw>r%{V#(D;+H2(EWS^_9HX< zh#a_2kb5L~W9uVYwHzbu)=>3(U_XnYiXfJG{Xwj1aQ8vhg^kj287ArEdpFHWV z@MK&%0-n4Zc+!1tg(uy^ZEn;H>DFx zG`CgCh3rBdE`T3A1kl9tCVF_84xZfr5}kLTt|ogK`cdOQjVqV|4G8!do||QtIDFXa@n`Et%?S34u4K2i*SAe%}iQxY8YGbPLQ zY{v4%;sI;iwsM=2S+wE#xtu+k97mUd%kwQC2yhh$%XNdk5SLWR&t!`QSS-s~zla>L z@hAfsr%Z%py-BsUXaqXBGmMIumGubj==p2xh*m}^Z; zSZ>BG=WXUWhwO~cu_h9A}#uDX%=ZqEXTmsJk-gwdVE1^*bY}u|0cI)k#|8v@M=fuvkR5l6g<{$3Ef;Qa3b|g9 zEDy3nZd4i#e8uPmhX>EvK`Za%WUL}bOA`f~M>$Ut%*y35qmJtVEh-}|LA8scWOY#s z+7WrN@-95HQ}B3s4m|39)tvZKC74X2C@5GedXDcD3*e$>yAYD?PB;ZCFD9BSr>LSV zs4!zsmaIZ96HK%qI;T)7L&340o|r!&7N{9%CjZ&a;o+@`jhERYSOHm~-iyxFYXyq} z9G7G>4((;p$+L})hE8@SK(IKACN{PmjeW;z9^lzO{9c@IaQtE#7yIgt#`Lk+1GW1? z;I%RdD1oS#a74ge3n`9FJ#4h+oy`EW#D7?&k}Q7hNP)&n8X6OI5aCVxSI@)2349VkIYL(OnJPlf{R0G1upZ` zDqbWj27oZ-2~URsS6Nvc+6CR#P~Fu*?FPV?ax->#8QfV0Ke!D3&1LZKE`y(32LCbO z=zod!arH9sbHd-J(oX}8?N#_yi)(Hfyz)HKlfzvvSO+V2z@Et^3)$jQ>MU7=V0(jo zE|az7mJ6iZQ*z}JJ6MDTJ3CP#NUWR0@7cawF7Ze+>e^~!v`Qt|QD}i%vP@R&p`;16 zTR3nL0XwO0fnv-NwuHDc)&cozr#{~LLim~xek1kUfM2|86TP4AXK1*3-cWy7&k5p3 z9KJmT?MKx61mGP3%Gi_CzgWXh5srFrJyz{^)Il8A4AssA8XMy9S`oC3gsZsJ+_`{o z6_>&XLVCh+?F->&2ih6)LwGpPcZBe;o)aM)zSjh;hvq-}AJ#Jv!ozyfgkwI#dAN*l z%x4(i6VlTaSY_-E!u9;zMYx`yBOyKEJe*oa&vVP@`DI8?BIM6(2oLAs&xGsq=RLyp z`SW2&Pj^WFAZ>-Zo;2aQp34Z=^RtU^JwJO0$2x}XDi`q8OMK=cK+QXa#|T$DX9W1g zJ2v6!yBp&8MPfJHv8f$K;g?95ok4enUr)4}OK6u;B}UE-@hhDOsdYo?QS)PSh#&n? z&)%?xKTY&i8h(oW|Fnj$Bz&KS|C;EGhTlU$jB0p}@LM%}GvT*scs<$uwuTeQzN6t= zNzeB*{A!{f*6>$J|DziIL(=oOhQCGh6B_EVYWN({>ot4>`E$O8cN2}zAvUEyL;Tlj_(`I38m^wBn>GAHqQ9i! zk4bavE)9R2=wlkbndnC}{C4v52@Nk0{*s1YN%)%@-a+_Z2*>9%yf6PvLPvd`y=q(zq;@zd;YHzq+!+%BoeMQ5S-;ZecJrvjDgeyPQ zx$p&zU-|ilhJT;*{9VJ9U6a;rl^;%gjf5+^>b>F|jbGUv&~T-HSi@C*_G-Aw&lfdZ z<@sA0ehc||KjF$x^&ap8jbHisjD{;e-_-E)s9x`B_-kbMUxX{Wlx9{>ua+vGO8*)S zSMhGv@Fvn9-UsD7leD1bwQl#1M7=tfeSgku6#epqE4FD(34Hc>t7m_|B7!LbWmQm z|1tpy#YlHuehc8$^4CWPHg&$k{9%ohyvpBa0n>8=5PP5OU#=BQ=f(3~HT(O?zWjSw z{;`g>b^9ZL={f;on~CuXZBQdwc^Ub`;?L8?^DXMcrpuQAtLFbWE#%?+VJ&t4zfnae zKapMp-c{5?kbn"); + return (1); + } + ft_parsing_table_generate(&table, argv[1]); + ft_parsing_table_save(&table, "parsing_table"); + return (0); +} diff --git a/src/main.o b/src/main.o new file mode 100644 index 0000000000000000000000000000000000000000..e3b80c1eecab843725efdee64cc2ee6c6473d100 GIT binary patch literal 4704 zcmbVPU2GIp6h1Sv16vkKfB0*vbkM3Lvb!z8LV@B+QN#d2A`u>Not>TC9od~NGqZ() zq%|?ds8N~_HBpR4Lr@cAd?7?1h(7sZ+<_F;FuPL}aKajgR zkc5-h0G>g!^Z1*?-vtY14=)E;HJ{4e1`Fmi$lad*nD_n0^?4k3Zr;#8BYQymJ7>SY ze9g%Jgcy#5cG=x-O-6aA?uSv(aH4u(?JRj!*SBl#F0vt+w1d#|%lXJIR9%?GkO{^o z*`zRoRw>4yo-_#=>~Vc<4z-?KN=Q#|r6n2C1zN%p^GYO4&yT=NE=f+42RCJgmcG90 zTjaR2)v<-#IM~2Il7ssg=<1kq9nkMjo=uFp%S5CmZN_9y>8^{(?Ts$Wb%Q7f1_{i=(}N4u?n)s~MeSVa&ZTBXB?U z8FRBUY;85Ohte_T-kpIZ$&k5pYY%kxri{-1&Tg$|Y1dku$RMOryO2W5HDGjZPwhyJ zrS|pW%Mv}9sJRl20G5!VuBE*=cq+whH6)TNVy@fJv;&Exj77wi{m$_`*92z$D%(&Tc3=Q;zwn5i1 zztB75<|7CiRW}63p0ph=nuctpUURc2rX4SPD5#eMyB20AvMpyTUv_;ru<;Z^l&38l zxk1hI?P@-%pK$#!?>A~d(J@s!!r;}qU$z>4=#_o9XwhK_EA=31rQB+s`S9c0w00_X z03n;@!r`WcfxQQhSQBGo*2r*Xb7sWaJiK{icw}VQO4q7h6jj}{>lZ!SM{F0o@#^I0 z7Asx0(ztx%xX|dBF4^IpPIoqFt`9MWTo2V(2Omq<*S))w|oOl-G?_P7O_3!iIxbfY?JeBWL8Bhk(r zhQ#UhTL1C^un^<+X2N#vW1Z)ISV+P(?+BX%Pf2$T_u^uV>py2zF?-6ZMIngGb<|^e$(U9?n1l}*Sj4ye* zgpg32_`8rhMMplq3*-%fcxqoGXOwQP@WameDr%C|Ts8SM0{00`^}kt+k=q!v=X;qG z!!e%5eO<(VMBxR535A#6?WYtzBjP-*@D~L>s_-ugoLBe@B2G!+PYGW7$@M7<{w2l! zL&3kP@bYB6r|{1Sd|Bb&68JlX-y`sKh2Jg4{aN9U3I2w{e=hLv3eRp`$o;ACSfiOF zL_E0;I|S}lc=?_N6rOHRBo8b6*PMn?!K?e~fMWlWz{eH-6@hCC|Bi?sKNm^Ck!pTd z&@aB9UlTTJKC%wrU8BVwGU0R$zpkjGfa{8E1#Z>OMDFPbGDSPGAyWuL$OLr`SZ~oS zG|G9;FV)e8we3P7aHr6WoCOuwei?5ZaSrcRu5`iiAmh|)H5b3X8NVL68N5c|oxpZZ z2q(9aFX63+m9*F@{P(7XF0|BgU1fxvXvlgl`Gjl;-H)2MoWN2Y5-&%d3#y$oj(lhG zd;g%|4e2QKCkmF3V#H+=0*d*6{YTK3V#fCjLXdfn5{QY+UsCkPPR)t>ZVH2!l}-i1 z7}~X4zguFUbz)+)e)Nvy_;UT|oT@RAf`XXPHw0p$+8)O~l_T@@Vq97GWeC-l>T|pN zyTpe|`cwY&9aHl^iJTe}DL5#`|B66NRNE@{wHrSt#+U0vgi^nXHtqZ`iOahv|GQUZPt%!tn`=b+HP!$ofHM-mPnZHNZoDxX-}wU7pdkz2N+m*h;U7UVz%?2 N6#0MIwB!xd{~wySxRw9_ literal 0 HcmV?d00001 diff --git a/src/prepare_table.c b/src/prepare_table.c new file mode 100644 index 0000000..014f708 --- /dev/null +++ b/src/prepare_table.c @@ -0,0 +1,78 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* prepare_table.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:26:32 by ljiriste #+# #+# */ +/* Updated: 2024/11/28 11:51:00 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "../Libft/ft_parse/ft_parse_inner.h" +#include "libft.h" + +static t_ft_stat init_table(t_parsing_table *table) +{ + t_ft_stat res; + + res = ft_vec_init(&table->rules, sizeof(t_grammar_rule)); + if (res != success) + return (res); + res = ft_vec_init(&table->states, sizeof(t_parser_state)); + if (res != success) + return (res); + res = ft_vec_init(&table->tokens, sizeof(t_token)); + if (res != success) + return (res); + return (success); +} + +static t_ft_stat add_zeroth_rule(t_vec *rules) +{ + t_ft_stat res; + t_grammar_rule rule; + t_token first_token; + + rule.result.type = NULL; + rule.result.str = NULL; + first_token = ft_token_dup( + &((const t_grammar_rule *)ft_vec_caccess(rules, 0))->result); + if (!first_token.type) + return (alloc_fail); + res = ft_vec_init(&rule.constituents, sizeof(t_token)); + if (res != success) + return (res); + res = ft_vec_append(&rule.constituents, &first_token); + if (res != success) + ft_free_token(&first_token); + res = ft_vec_insert(rules, &rule, 0); + if (res != success) + ft_free_rule(&rule); + return (success); +} + +t_ft_stat prepare_table(t_parsing_table *table, const char *rules_filename) +{ + t_ft_stat res; + + res = init_table(table); + if (res != success) + return (res); + res = load_rules_name(&table->rules, rules_filename); + if (res != success) + return (res); + res = add_zeroth_rule(&table->rules); + if (res != success) + { + ft_vec_free(&table->rules, ft_free_rule); + return (res); + } + res = categorize_tokens(&table->tokens, &table->rules); + table->terminal_tokens_num = get_terminal_tokens_num(&table->tokens); + if (res != success) + ft_vec_free(&table->rules, ft_free_rule); + return (res); +} diff --git a/src/prepare_table.o b/src/prepare_table.o new file mode 100644 index 0000000000000000000000000000000000000000..caeab85e56337d5a69adf2f3e4da2553a8dc803d GIT binary patch literal 7888 zcmbtYeQX>@6`#Gmwa-51a<*cdpVjPU7@JfTV4J5<*2J$Yp)EKCg1# zyX@|TIEiS4_$Z=()DpCnXsaSXO$!KAA!yW6B3g;^p#l{}P(I`o1m!PO6_6|%h4*IO zJMWF}gajkq&3nK1Id5iXX7|4L9C>fdFa$S4d`~QKj0%w+TA~Y*EQmE?wYYZv`%hgn z#r(obvAD3ZuxNB$d=!Kf-7mnda zG=`;mUQMc+K6(B6!|m#MGu7#85^CC^=9@_8vgQLO`Pdsc7eYK}h{EE68GBm!C|tgQ zYy{N*s?t&ODQQFI%;PfhkR#3W6{u$?pFBsS5Cq%St*ZZT|0z?5xKv8WWeIDewdG+I zaEm1@B*8?8*e}-s@+ISqwe@2Ak9^& zA41myKl(Q$9h3j2{Ey3jOa6DMY|IVjr@^2XtupbA=`;)`iA+4xvlDy8j7TP-m`##N z_nmP{BEC6s8no6bZ}Cy<72tSmYShwq+FFx7%D%0kM1a2gg3uS%I>{uI2W!2x1Jt@v zR~qK64e8G}4TpPCppvpO3CuQ4h9g#qZDy?7)4y%nOh`4d*&~^Z9Ei17G6lu#lcPFG z-X^Vw!NCg5vTI=V37~uA>>;4gK@Clz$e2jtEO1*O!g$n%)vyvdV`2x=vH2NdCo7UY znf9GP7<>EBJ~n?rbR}>IU5Sgp_rp&ZBLgVo_7V}sqpyGiZH55dB$7Uqu*f<_m_#O{u}8nOdLf zHwL=Xuq(wzMKZY`APBQsn5jLorAEvNCGR^S_w)pQtVLFy+vS`h#O{Ve-bfe zW&qf;4ZPe4+P#AyO(vHl$rTa*yFsH5fCL9bV8zaeMr^GRsjP9w5GS>D=*~e*yRi15 zcMV~vm6oQS2K%N%wC~SC4l2Sj>wyk3sOBy3gIR(mA74q~Uv$H0fFf+<42nT$hrqz20F3SXOz1JGZ zTUN&E&FR{vvaeV`pqYrp(KPWs%bH}L%_x(Wx!>wNZYA>8j;xi)Si?DM!(En@lh(%} zXe1*X@!U&WTFVnXQL&#jtkD@szMQ z?N%Mno&^&qvtCoXTCJ6e)3#d`xtZFmlRGt6a&!0iH4GNy4(70uu2)f$P^>smLp!Yb zA}r#58y0C6MCkalu4h+O=%DB|W+7#jN2%rop&K?FFAPMr=2bEcFK{cKQ_kQ~63o>6 zuoc3bi;nL@Ag5Zyu?o2ggje&5LES02)2>Rp;XA@JvUSX5r^LY z;mpB_iOhIDduw()b8G(A@%;FBJ~K93b;Gdgj5%J}wLReNDR;73-?cL{R>_RP`kRDh z42EOVb};9aX8f90YXoBr@8hml9+OE1P!=`tuyxMV%5GLuG_%DjNQ(e+JY!egvKq6j z)$)SD*4(IuIN7yninOGOzU1ibs_)q4Iav3B3y&KcKv_{+_JocICSvfp3Js)J5yLnRqC-_+x4Qu zBM8T)YR0*vB7SzGvA%Cu+z1ftYqH6G|3E7LSl8p0{l`DZ(+%ajNiL6{1F8CBsmE8; zNS*=NM@YVaJ=vcjIf>eKxTVF#Ti4qOP27pvG*cbc%Oob<%yfY%K+Bq`ZWwKFuF8_=2$0KBwZ7Wnl@9u02mF&A z@CQ5Kk9WYo4)_4f*F7|43&3N$48L}H{Hf-9P`OEy$JE=2tE?Q{}I7AMetR0o73a2C0vi2AzY8kF7Zwq-JSW_VVv*E zyu-#oKe{XRkt4+MJ?37@n|CP2?;<_;mLMDBF7Z6q7?)C(lI`7|JxdVKl%BthX0fJ=QTV+mq?4Qu#2#Bb5?E#&`Z4afICZ1`MZWB(r@{SRsQcZe@* zI6p_HHGGi#d_u#yjt^+~^Ta=*;d_bynuc#wX^Uqx{4mA+frh_HJnvUL-Y3b=>ze*g ziT{g+uOt6&6OPYyH~GMh=Yjo?k&NF~S)cc#0rJQC-z0tm^}KKJeSn`Q)>mH(g*d4B z*-LRf4L?EroaUeJfe&i>T<33TIQxA;!@o@YYZ`tx)oX!p9v7u4-q!SaT+#hmzBG^l z*H8EJ6O!vVpNa5J-?9(yBYnoX4j*$!=y zor2f?tY1@%lp>i03eYUPxZ72bqgC0NYEHlpRaDY?F^TYlMMCf0i;;cYD z-dzwY5YJtPCiZ1oFX}yL>Dw0HskVRts=%kCmR6^A)B*xS?war|K;ho?zuJ$JPdyyR zhYy4;jrU0g_XE)`|BK`>!-~}F_7i}&tKXY+naGnJ)(_{1?YVyU0;bmlO`f3m16pBp zUA#xMi@#QW^aVe3`NH@ZTaP~lnC=rG@eJ8*(}Wr;8XfFkrv=I5N1xbq`#NCl@_&{t zR&0;?<6P?bf3A&BfJ84H26Zi<#)?mYZoBwzQhc5#jE|q!_4r=|41IE*K+1NG6ra-; zCdcRg3D9n5e;X~_ZOUEqpY6DRitL*TM0`wN_=K|^>%Ra5Vp^KwB-x*3Me2F{4CDK7 zyZZ45r^BR(^}{8}_FUI?vC-r=6#p=-{~G|qDbekF0Mi~3K!nK9ON9R6NgqExrtRzx OQ-Uu`Z%co={eJ-W(wZ;; literal 0 HcmV?d00001 diff --git a/src/solve_gotos.c b/src/solve_gotos.c new file mode 100644 index 0000000..2aae385 --- /dev/null +++ b/src/solve_gotos.c @@ -0,0 +1,132 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* solve_gotos.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/11/26 16:40:59 by ljiriste #+# #+# */ +/* Updated: 2024/11/27 11:25:58 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "pt_constructor.h" +#include "libft.h" +#include + +static t_ft_stat add_viable_items(t_vec *kernel, + const t_vec *candidate_items, const t_token *token) +{ + const t_lr1_item *item; + t_lr1_item *new_item; + size_t i; + t_ft_stat res; + + i = 0; + while (i < candidate_items->size) + { + item = ft_vec_caccess(candidate_items, i++); + if (is_viable_item(item, token)) + { + new_item = duplicate_item(item); + if (!new_item) + return (alloc_fail); + ++new_item->core.position; + res = ft_vec_append(kernel, new_item); + if (res != success) + free_item(new_item); + free(new_item); + if (res != success) + return (res); + } + } + return (success); +} + +static t_ft_stat create_goto_kernel(t_vec *kernel, + const t_generator_state *state, const t_token *token) +{ + t_ft_stat res; + + ft_vec_init(kernel, sizeof(t_lr1_item)); + res = add_viable_items(kernel, &state->kernel, token); + if (res != success) + return (res); + res = add_viable_items(kernel, &state->closure, token); + return (res); +} + +static size_t find_kernel(const t_vec *kernel, const t_vec *states) +{ + size_t i; + const t_vec *state_kernel; + + i = 0; + while (i < states->size) + { + state_kernel + = &(*(t_generator_state **)(ft_vec_caccess(states, i)))->kernel; + if (ft_vec_is_setequal(state_kernel, kernel, void_cmp_items)) + return (i); + ++i; + } + return (states->size); +} + +static int is_at_mark(const t_token *token, const t_generator_state *state) +{ + size_t i; + const t_lr1_item *item; + + i = 0; + while (i < state->kernel.size) + { + item = ft_vec_caccess(&state->kernel, i); + if (!cmp_token_type(token, + ft_vec_caccess(&item->core.rule->constituents, + item->core.position))) + return (1); + ++i; + } + i = 0; + while (i < state->closure.size) + { + item = ft_vec_caccess(&state->closure, i); + if (!cmp_token_type(token, + ft_vec_caccess(&item->core.rule->constituents, + item->core.position))) + return (1); + ++i; + } + return (0); +} + +t_ft_stat solve_gotos(t_generator_state *state, t_vec *states, + const t_vec *rules, const t_vec *tokens) +{ + size_t i; + const t_token *token; + t_vec new_kernel; + size_t state_num; + + i = 0; + while (i < tokens->size) + { + token = ft_vec_caccess(tokens, i++); + if (is_at_mark(token, state)) + { + create_goto_kernel(&new_kernel, state, token); + state_num = find_kernel(&new_kernel, states); + if (state_num >= states->size) + { + state_num = states->size; + construct_state(&new_kernel, states, rules, tokens); + } + else + ft_vec_free(&new_kernel, void_free_item); + ft_vec_append(&state->goto_states, &state_num); + append_token(&state->goto_tokens, token); + } + } + return (success); +} diff --git a/src/solve_gotos.o b/src/solve_gotos.o new file mode 100644 index 0000000000000000000000000000000000000000..7fb3372fbbf4831c867ca181bfa0507eefc17936 GIT binary patch literal 9496 zcmb_heQaCR6~FfLbDTJJoTN1A2aQ8ZzaVx}y0*}Sx|Gotx~_C(>&8^`V!tGhIJRp) zhlauk651FbL^j5U)D|>0)-g@$&@|`<8yZX-?4NBQVBbzblLphIZqr17EIa4kbDZZ} zN0ZR56yJM(_k5rG-o5YUj*suX#_#h9Za(phn5P&OqBAx>PRe0YEEerz_SlcUJ!^=m zN{5)4ZWl9WTg1%VS~0Uhh{ct)$r)cjOicqlZHT8T?a3JseXz0$=$7P6WtF14ggEko zAr3NK=@K)QuH+2h=PV%(CdK4|6{rs|5l}jD47z8gp|5n1-Yw!xWlQo5>bnW#BtP0i zIqbc2Fm6Dd=o9Fi24A-e@oxJ4xq|}i%^v&NsTYjY>$At6J1;(8aPl`*n;?G{Vv+HI zAJ5IrJzUuier)&n0pmutH7TaN{HHzqv&UW{o6jqokjv>X;ME)=0`@ynxAgXXg$wHhb*F1?_jB959bbI%$;OYK+gUjcAM(iT|A$QC%~?% zJ?G)fd9{BF>#;@5^rEgUw7!9su~Ka+mjMlVs$7>ihlCOhiIrjX#Y0MM;kcosu{J-u< z!q^{zrwh7(>U<$d`H2FrVa_k50s+&>xxx$uLlcN9R>{~9*ae8OIPyGnQiJ*>Z4xo$ zZ$SQ<@;9g)F)lPFK@1)|A!31*(J;gTD*(cZHEzOQ5#5pqDdHkYM8o5DS_D>wjsRDu z(iT{4z6?||YT?*a)Y3rI?1&y<1Lo3D2@QlxZc&)aBoR_-%;n|=U~5KRDcEaX7`?YD z*wus+$}=+-LSs=9>^9RtH6yRG7+ey42?*(Uu(K1#L@Zr|@r6V%^e}+3D#2w9$62yB zxFY(Ws^rSfSLP+VWPD^Y7;AhTrkasgn!G!BQS`8%t*n;rk;#iC5mU~rkwj7vYb9}$ zBG$?LPLfaS%@)wsj4Bs_!@@Tb#zJ%ZkOscv%@9KbDc{Hj92-;5-a+)%Hc6i*+G*>Q z^eLv-DEjd`S{&gU4P#>bQ%9pxS+;d0F#D$piX3Z_#hu!($Q&{6hCHH+K^aIe)B))L z1b$nkmc7k4V^2*zE#T?#J3+T{a_<^tXN1UWaLPY*6S}moxyGeWF8-2o2~6B9jW)rr zGPJElE?Y7*Nxkp*J5@v5)?u{%DKfNeK#|hWKvRvOD_hiDft1JFys3Aq%J;xaK)D^i z6jNPQo>)mysM*9O72~0nqFoZczGhVCpSq3Ix7MhyRMo#)Ro}WnsXwIjwaG&Ir}h)M zQK{dpYO|Qrq{s`Rs0Uobj4t7fDo;A(%fmmFfsEox7QR;B#gX=~5m_E-^|dubVQ2HN z7UA%f0Kw8)B82j zc9;!^=VzK0c@%F2jxYcrwuC_Q8i9Hj#eLhCvJY#Q?rBFalbsJ;wG<6ROph8r?2xc1 z=G7n&1)v%M03Q3iv*VED}CwK)|1` zR7{IRxl~MKox#L#I-RhrVtQorrk<>mD+U(b{kNx;L8s8_m#wX$~WAC}B310qrvb`%rCcl^N&wdqSRCpgfx*EB)3jc$bdkaL+aAvps^BlObCuFvUA%ZaHGnb4s?7J0)Q zQJ~k1US~%7&E?%@Tik4jnH{}mOWZWO9W(IR>%g5O*Q$WpP~Pu{BBrf^m3G_-ffY!( z`B6Jp5^ieDDvsKj)Ns)ngJG&z&e~8I%e7Ov@|Y+&x7sO}fKj`cv$MjTDA*#K&ke`q zPdQg|hI4i%hFg58R*|dhc(^5#;!lrQMVQHtS|hfV5wNxrwM!(O&6mnWa!2Vv@wAo8 zI2rWNaqY2^kPE_b%XZE!iCjLHDi!RsGvuUGLza_81vM@f@+HT0@;RljX39M7@Lfzbm#Y|;cr`Qf6=O^HWN~1% za?)tZ%0gu_6DbE4HN3&955k~b6kMp=W=Rj}I;*?*$xWaIds{wQ}zoZpH#G`WNC zh$K&hPBz@=nLnha#U%DSBE2VqC(Xm2`J*&1&oMObPb!8O%soQ$@^H2zQaBMgx#)J1 zr>VLfZV~};Zm!;>QTN6H_nG>ekU?K2UR^DcKr6KkzMEkOna3+My^3(A`NXrC@Pi~W z2{g8=;1Bh@MmV4IaLy3&Lk5R6%@Fb{rUpa8pl=y{!cd249R~jMzP==np-yHs{GX6i z3*60|-wdI$q|X@Y_+10<2a4CAcOta_o?8IFeF6Nh3*hfBfZw|S{_q0$lMCQy7QlZ2 zcpKFB4|G=GkB`?D;D37o{GSWpxbW-c)B7fegU{-t;=FC6&VEp{lg#f(t21~yf^905 zw$vL3wkyvTBr@ef)=Bg3$jnxu054RgoSfr|@jSe`(_;nNMM*1YE7`7nq-9^9+Hlh&thceMw{eSllmgM0PBrJ-!Pp5q?et0zjYVx9js55AI(LVq{m zn1?P8ejnkO2QU7hM^DVd{|yiBt>gDSc(;dN-Yfy_2mSC(Rc-tRMI1NF`zcQOX$>^v zkCOziCB~lvIc&TJ@T-SZNPNBgReI!Q2GP8pSHn&RAEr7zs^J$C{+Nc3lb&yC z_yMx}9St8R{CgVSPxvz${uiQutl@VN|0^24m+&_$0ZsbBtP-F!p8ddC{lb%!}+|E(Qupik7)R3s9s;t@ZS>ueHy-- z_)lo~J48RF;dc`KjE3_$>z5kN&*vK&9-%zEt>L=}Kd0djk^gfVzLfZ*)N?-DDXt4O zdJ$o`g#rDMEd#pV}ITwzJkVon&LS|IKQv>eDf8J|A*w~ z*EKvt^wS#tMbiIM4S$UAKWjL@EdQ?IqeRbY_$A~Izb81}^`yU-^1*TOxqKJl%+Gc| zt>GMRQNwxN->=~|*?p97wtJB9(;7doho5LT=kxa(-cRwqtKs}y{hM&MTOs~Mc*g~e z<7K-mG@RqTM8i2h*J?P&bpzpSS6LGxtMRklV;cT43EZRMZ1+(O=lq}2@Ft4iyT3QF zGtl$dTKDq@#G~VUwt?$Gc13b>9T=~W{O74>obz*=hVwc+uHpRLiFj#Z3@##|cZ;eY z;Zf1fT5;Dt>WVnrU|AwQ2zLf?iDvA<@-SRH4CP@?j;+DLqCH+SZ56HDFx;?sMd0q$ zW)b{%R6Ly@8-vR*5zpmaI}SH3aBX6xM@h&YNe#gT67K>O#7F32AcKzv*NasoX`tUP zQ@NQinqkn?Y9B ziOSjj?=(Mj-ag>17yqy55L}_F1&kkWAN2UI0!-HlkoX5NMzl$d6gMm&&sP+Du0@^L zbb0(PtLOh|`bc1T^dDW){del<1W5GKL(ls@V%T*18Nlkh{Z|ll=rz zwg&o;7}6F7+vk1~xN)q@kI@y(I;m~`hvm5cGRe<#sL|KzU*Vh=|4EXk$E2#}5t4tl zil_m{&oG|X>*en~%HL69#QdR3mgl@;9J*~3QU6?pyioq|eh$A&b$L7=X(