Left confused by left-recursion

[jjtolton]

So I ran into a "left recursion" situation, where I am struggling to efficiently parse expressions of the form A op B.

expression(num(V)) --> number(V).
expression(expression(L, Op, V)) -->
        expression(L), opr(Op), expression(V).

This wouldn't work at all without @triska's great insight into using tabling for left recursion.

This does indeed end up working:

?- Result^Expr+\(solve("99*99-4*99*1*99", Expr, Result)).
%@    Result = 96020397, Expr = expression(expression(expression(expression(expression(num("99"),"*",num("99")),"-",num("4")),"*",num("99")),"*",num("1")),"*",num("99"))
%@ ;  Result = 92178405, Expr = expression(expression(expression(expression(num("99"),"*",expression(num("99"),"-",num("4"))),"*",num("99")),"*",num("1")),"*",num("99"))
%@ ;  Result = 931095, Expr = expression(expression(expression(expression(num("99"),"*",num("99")),"-",expression(num("4"),"*",num("99"))),"*",num("1")),"*",num("99"))
%@ ;  ... .

But it only works up to a certain number of expressions. The problem calls for solutions of up to 20 expressions. On my machine, which is fairly powerful, this code struggles with expressions of size 12:

?- Result^Expr+\(solve("99*99-4*99*1*99*1*2*99*36*42*74", Expr, Result)).
%@ <diesel engine noises>

Would be interested if anyone has any thoughts!

This gives more insight into the problem:

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   https://leetcode.com/problems/different-ways-to-add-parentheses/description/?envType=daily-question&envId=2024-09-19
Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 104.


Example 1:

Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0 
(2-(1-1)) = 2
Example 2:

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10
 

Constraints:

1 <= expression.length <= 20
expression consists of digits and the operator '+', '-', and '*'.
All the integer values in the input expression are in the range [0, 99].
The integer values in the input expression do not have a leading '-' or '+' denoting the sign.
   
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
:- use_module(library(charsio)).
:- use_module(library(tabling)).   

:-  table(expression//1). % left recursion

solve(String, Expr, Result) :-
   phrase(expression(Expr), String),
   evalexpression(Expr, Result).

?- Result^Expr+\(solve("2-1-1", Expr, Result)).
%@    Result = 0, Expr = expression(expression(num("2"),"-",num("1")),"-",num("1"))
%@ ;  Result = 2, Expr = expression(num("2"),"-",expression(num("1"),"-",num("1")))
%@ ;  false.

?- Result^Expr+\(solve("2*3-4*5", Expr, Result)).
%@    Result = 10, Expr = expression(expression(expression(num("2"),"*",num("3")),"-",num("4")),"*",num("5"))
%@ ;  Result = -10, Expr = expression(expression(num("2"),"*",expression(num("3"),"-",num("4"))),"*",num("5"))
%@ ;  Result = -14, Expr = expression(expression(num("2"),"*",num("3")),"-",expression(num("4"),"*",num("5")))
%@ ;  Result = -10, Expr = expression(num("2"),"*",expression(expression(num("3"),"-",num("4")),"*",num("5")))
%@ ;  Result = -34, Expr = expression(num("2"),"*",expression(num("3"),"-",expression(num("4"),"*",num("5"))))
%@ ;  false.


?- Result^Expr+\(solve("99*99-4*99*1*99", Expr, Result)).
%@    Result = 96020397, Expr = expression(expression(expression(expression(expression(num("99"),"*",num("99")),"-",num("4")),"*",num("99")),"*",num("1")),"*",num("99"))
%@ ;  Result = 92178405, Expr = expression(expression(expression(expression(num("99"),"*",expression(num("99"),"-",num("4"))),"*",num("99")),"*",num("1")),"*",num("99"))
%@ ;  Result = 931095, Expr = expression(expression(expression(expression(num("99"),"*",num("99")),"-",expression(num("4"),"*",num("99"))),"*",num("1")),"*",num("99"))
%@ ;  ... .

   
evalexpression(expression(L, [Op], R), Result) :-
        evalexpression(L, A),
        evalexpression(R, B),
        Term =.. [Op, A, B],
        Result #= Term.
evalexpression(num(V), Result) :-
        append(V, ".", Term),
        read_from_chars(Term, Result).


expression(num(V)) --> number(V).
expression(expression(L, Op, V)) -->
        expression(L), opr(Op) ,expression(V).
   
number([V]) --> digit(V).
number([V1, V2]) --> nonzerodigit(V1), digit(V2).

?- phrase(number(N), Ls).

nonzerodigit(V) --> [V], { member(V, "123456789") }.

digit(V) --> [V], { member(V, "0123456789") }.

opr([Op]) --> [Op], { member(Op, "+-*/") }.


?- length(Ls, _), phrase(expression(Expr), Ls).

?- evalexpression(expression(expression(num("1"), "+", num("2")), "/", num("0")), Result).

?- Result^Expr+\(length(Ls, _), phrase(expression(Expr), Ls), evalexpression(Expr, Result)).

[hurufu]

I don't know exactly how to program it, but more-or-less I would've approached that problem in the following way (which is better to be described using an example):

1. Assume input is "2-1-1"
2. Parse it linearly into 2 lists: [-,-] and [2,1,1]
3. Find all groupings of pairs in a second list: [[2,1],1] and [2,[1,1]], aka Tamari Lattice
4. For every such grouping apply list of operators

I think such approach will be reasonably fast, it all will depend on how well is implemented step 3.

[jjtolton]

Very interesting!! I'll give that a shot.

[hurufu]

I expect it to be a bit faster than parsing with deliberately ambiguous grammar, because you will parse numbers only once. I think it is possible to be really smart and keep partial computations for as long as possible, but that will be even harder to implement.

[jjtolton]

Does anyone have a good algorithm for rewriting left recursion, aka, "left factorization"?

I realize now we can do this automatically with term_expansion/2, but I'm not sure how to do it by hand yet (or even if there is a general case for it).

[UWN]

One way, but I am not sure all this can be done automatically, nor using term expansion.