Courtesy ChatGPT:
Explain Spec to Algorithm’s Context Free Grammar Generator’s top-down and bottom-up recursive structure finding algorithms. The top down algorithm is:
find_lists3a(L1,L32,Rest) :-
find_lists3(L1,[],L91,_Rest_a),
(fail
->(L4=_L92,Flag=true);
(L4=L91,Flag=false)),
(L4=[]->L4=L3;
(L4=[_L2]->L4=L3;
(L4=[L2|L31],
check14(L31,L2,[],L5,Rest),
(L5=[['&r'|_]|_]->L5=L3;
((L5=[L51]->true;L51=L5),
L3=[['&r',L51]]))
))),
(Flag=true->L32=[['&r',L3]];L32=L3),
!.
find_lists3([],L,L,_) :- !.
find_lists3(L1,L2,L3,Rest) :-
repeating_unit(L1,U,Rest),
(U=['&r',U1]->
try(U1,U2);
U2=U),
append(L2,[['&r',U2]],L3).
match_char("[","]").
match_char("(",")").
match_char("{","}").
match_char(A,A).
find_lists3(L1,L2,L3,Rest) :-
L1=[L4|L5],
match_char(L4,L41),
find_lists4(L2,L5,L4,L41,L3,Rest).
find_lists4(L2,L5,L4,L41,L3,Rest) :-
member(L4,L5),
sub_list(L5,Before_list,[L41],After_list),
Before_list1=[L4|Before_list],After_list1=[L41|After_list],
find_lists32(Before_list1,[],L6,_),
find_lists3(After_list1,[],L7,Rest),
foldr(append,[[L6,L7]],L8),
foldr(append,[L2,L8],L33),
L3=L33.
find_lists4(L2,L5,L4,L41,L3,Rest) :-
not((member(L41,L5),
sub_list(L5,_Before_list,[L4],_After_list))),
append(L2,[L4],L6),
find_lists3(L5,L6,L3,Rest).
find_lists32(L1,L2,L3,Rest) :-
find_lists3(L1,L2,L3,Rest).
repeating_unit(L1,U,Rest) :-
(only_item(L1)->fail;
(length(L1,L),
L2 is (floor(L/2)),
numbers(L2,1,[],Ns),
find_first((member(N,Ns),
split12(L1,N,[],A,Rest),
maplist(=(_),A))),
(N=L->U=L1;
(length(L21,N),
append(L21,_,L1),
U=['&r',L21])))),!.
split12([],_,A,A,[]):-!.
split12(L
,L16,
A1,A2,_Rest) :- length(L,LL),LL<L16,
append(A1,L,A2),
!.
split12(Q2,L16,%N1,N2,
L20,L17,Rest) :-
length(L18,L16),
append(L18,L19,Q2),
append(L20,[L18],L21),
split12(L19,L16,L21,L17,Rest),!.
split12(A,_B,C,C,A) :-!.
check14([],_,A,A,[]
):-!.
check14(A0,B,C,D1,Rest
) :-
A0=[A01|A02],
check141(A01,B,[],D),
append(C,[D],C1),
(check14(A02,B,C1,D1,Rest
)
),
!.
check141([],[],A,A):-!.
check141(A,B,C,D1) :-
append(A31,B3,A),append([A1],A2,B3),
append(A41,B4,B),append([B1],B2,B4),
((A31=[],A41=[])->A51=[];
(A31=[],not(A41=[]))->A51=A41;
(not(A31=[]),A41=[])->A51=A31),
(A1=B1->(A3=A1,A2=A22,B2=B22
);
((not(A1=['&r',_]),not(B1=['&r',_]))->fail;
(
((A1=['&r',A11]->true;A1=A11),
(B1=['&r',B11]->true;B1=B11),
(not(is_list(A11))->(A11=A13
,(append([A21],A22,A2)->append([A13],[A21],A23);(A22=[],A23=[A13])
));(A11=A23,
A22=A2
)),
(not(is_list(B11))->(B11=B13%,B14=[]
,(append([B21],B22,B2)->append([B13],[B21],B23);(B22=[],B23=[B13])
));(B11=B23,
B22=B2
)),
check141(A23,B23,[],D),A3=['&r',D])))),
(optional_s2g(on)->
(A51=[]->A52=[];A52=[['&o',A51]]
);
(A51=[]->A52=[];fail
)),
foldr(append,[C,A52,[A3]],C1),
check141(A22,B22,C1,D1),!.
And the bottom up algorithm is:
find_lists3_optimized([], L, L, _) :- !.
find_lists3_optimized(L1, L2, L3, Rest) :-
% Use optimized repeating_unit that tries smallest patterns first
repeating_unit_optimized(L1, U, Rest),
(U=['&r',U1] ->
try(U1, U2);
U2=U
),
append(L2, [['&r',U2]], L3).
find_lists3_optimized(L1, L2, L3, Rest) :-
L1=[L4|L5],
match_char(L4, L41),
find_lists4_optimized(L2, L5, L4, L41, L3, Rest).
% Optimized find_lists4 - reduce redundant processing
find_lists4_optimized(L2, L5, L4, L41, L3, Rest) :-
member(L4, L5),
sub_list(L5, Before_list, [L41], After_list),
Before_list1=[L4|Before_list], After_list1=[L41|After_list],
find_lists32_optimized(Before_list1, [], L6, _),
find_lists3_optimized(After_list1, [], L7, Rest),
foldr(append, [[L6,L7]], L8),
foldr(append, [L2,L8], L33),
L3=L33.
find_lists4_optimized(L2, L5, L4, L41, L3, Rest) :-
not((member(L41, L5),
sub_list(L5, _Before_list, [L4], _After_list))),
append(L2, [L4], L6),
find_lists3_optimized(L5, L6, L3, Rest).
find_lists32_optimized(L1, L2, L3, Rest) :-
find_lists3_optimized(L1, L2, L3, Rest).
% Optimized repeating_unit - bottom-up approach
% Key optimization: try patterns starting from length 1 (bottom-up)
repeating_unit_optimized(L1, U, Rest) :-
(only_item(L1) -> fail;
(length(L1, L),
L2 is (floor(L/2)),
% Bottom-up: try patterns starting from length 1
try_pattern_lengths_bottomup(L1, 1, L2, U, Rest))), !.
% Try pattern lengths from 1 up to max (bottom-up approach)
try_pattern_lengths_bottomup(L1, CurrentLen, MaxLen, U, Rest) :-
CurrentLen =< MaxLen,
(try_pattern_length(L1, CurrentLen, U, Rest) ->
true % Found pattern at this length
; NextLen is CurrentLen + 1,
try_pattern_lengths_bottomup(L1, NextLen, MaxLen, U, Rest)
).
% Try a specific pattern length
try_pattern_length(L1, N, U, Rest) :-
split12_optimized(L1, N, [], A, Rest),
maplist(=(_), A), % Check if all parts are the same
(N=L1 ->
length(L1, L1Len),
(N=L1Len -> U=L1;
(length(L21, N),
append(L21, _, L1),
U=['&r', L21]))
;
(length(L21, N),
append(L21, _, L1),
U=['&r', L21])
).
% Optimized split12 - more efficient splitting
split12_optimized([], _, A, A, []) :- !.
split12_optimized(L, L16, A1, A2, _Rest) :-
length(L, LL),
LL < L16,
append(A1, L, A2), !.
split12_optimized(Q2, L16, L20, L17, Rest) :-
length(L18, L16),
append(L18, L19, Q2),
append(L20, [L18], L21),
split12_optimized(L19, L16, L21, L17, Rest), !.
split12_optimized(A, _B, C, C, A) :- !.
The top-down algorithm says, “Find the largest recursive explanation for the whole input, then refine,” while the bottom-up algorithm says, “Find the smallest repeating building blocks first, then assemble them into a larger recursive grammar structure.”
Video 1: The top-down algorithm says, “Find the largest recursive explanation for the whole input, then refine”.
Video 2: The bottom-up algorithm says, “Find the smallest repeating building blocks first, then assemble them into a larger recursive grammar structure.”
Top comments (0)