48994_it-IT

liliconcom

regex ricorsione

JSL supporta l'espressione regolare ricorsiva?
Ho provato? R e \ g <0> e nessuno di loro sembra funzionare.  

regex("test(1, (2, 3));", "\(([^()]|(?R))*\");

Re: regex ricorsione

A pochi minuti wikipedia dà un insieme di regole senza ricorsione a sinistra ... che scorre veloce.

text = "(1+2)*(3+4+5)*6*7*8*21*(0+(1+(2*3))+4*(5+6)*7*8+(((12+13+14)*15+16+17)*18+19+20))*22"; // plus, star, paren, integer.  pattern does not handle spaces. 

stack = {}; // the "working" stack... holds the RPN numbers
// the following add and mul routines pop two numbers and push the result...
addstack = Function( {},
    {num1 = Num( Remove From( stack )[1] ), num2 = Num( Remove From( stack )[1] )},
    Insert Into( stack, Char( num1 + num2 ) )
);
mulstack = Function( {},
    {num1 = Num( Remove From( stack )[1] ), num2 = Num( Remove From( stack )[1] )},
    Insert Into( stack, Char( num1 * num2 ) )
);
dummy = {}; // dummy variable with a subscript that will evaluate as needed

// BNF-like grammar of Expression, Term, Factor, Constant
// >? is the conditional assignment from LHS to RHS. The >>
// immediate assignment will not work because of back-up and retry
// which would push incorrect items to stack. The RHS of the >? is either
// the dummy[] list or working stack. The dummy stack reference uses the 
// calculation of its subscript to manipulate the working stack.
// As the grammar/pattern runs, the expression is evaluated.
/*
E = (Expr( T ) + "+" + Expr( E )) >? dummy[addstack(); 1] | Expr( T );
T = (Expr( T ) + "*" + Expr( F )) >? dummy[mulstack(); 1] | Expr( F );
F = ("(" + Expr( E ) + ")") | Expr( C );
C = Pat Span( "0123456789" ) >? stack[N Items( stack ) + 1];
*/
// re-written without left recursion 
// https://en.wikipedia.org/wiki/Left_recursion#Removing_left_recursion
//
E = Expr( T ) + Expr( EP );
EP = ("+" + Expr( T ) >? dummy[addstack(); 1] + Expr( EP )) | "";
T = Expr( F ) + Expr( TP );
TP = ("*" + Expr( F ) >? dummy[mulstack(); 1] + Expr( TP )) | "";
F = ("(" + Expr( E ) + ")") | Expr( C );
C = Pat Span( "0123456789" ) >? stack[N Items( stack ) + 1];

rc = Pat Match( text, Pat Pos( 0 ) + E + Pat R Pos( 0 ), NULL, FULLSCAN );
If( rc,
    Show( rc, Num( stack[1] ), Eval( Parse( text ) ) ); // use JMP's parse to verify the answer
,
    Show( rc )
);

Se stai seguendo da vicino ti stai chiedendo come funziona la prima versione, con ricorsione a sinistra. Perché non loop per sempre, o almeno fino a quando la ricorsione utilizza la memoria disponibile? Di default il pattern matcher presuppone che ciascun expr (...) debba corrispondere ad almeno un carattere. Ad un certo punto, la ricorsione è abbastanza profonda da non lasciare abbastanza testo e la partita viene ripristinata. Tutto ciò che esegue il backup e riprova richiede tempo su una lunga stringa. Nel secondo esempio, senza la ricorsione a sinistra, il patmatch () richiede l'opzione FULLSCAN per disattivare l'assunto perché expr () può ora corrispondere a "" (zero caratteri).

Re: regex ricorsione

No, ma il pattern matcher ama la ricorsione. Ecco un esempio completo di un interprete di espressioni. Non sono un esperto di grammatica; Penso che questo sia un parser di discesa ricorsivo e penso che faccia molto back tracking su espressioni moderatamente lunghe, rendendolo notevolmente lento per le espressioni con più di 10-20 operatori.

PatMatch restituisce 1 se il modello corrisponde, 0 se fallisce (parenti sbilanciati, operatori non validi, numeri non validi).

text = "3+4*((5+7)*(9+11*2+2)+13)"; // plus, star, paren, integer.  pattern does not handle spaces. 

stack = {}; // the "working" stack... holds the RPN numbers
// the following add and mul routines pop two numbers and push the result...
addstack = Function( {},
    {num1 = Num( Remove From( stack )[1] ), num2 = Num( Remove From( stack )[1] )},
    Insert Into( stack, Char( num1 + num2 ) )
);
mulstack = Function( {},
    {num1 = Num( Remove From( stack )[1] ), num2 = Num( Remove From( stack )[1] )},
    Insert Into( stack, Char( num1 * num2 ) )
);
dummy = {}; // dummy variable with a subscript that will evaluate as needed

// BNF-like grammar of Expression, Term, Factor, Constant
// >? is the conditional assignment from LHS to RHS. The >>
// immediate assignment will not work because of back-up and retry
// which would push incorrect items to stack. The RHS of the >? is either
// the dummy[] list or working stack. The dummy stack reference uses the 
// calculation of its subscript to manipulate the working stack.
// As the grammar/pattern runs, the expression is evaluated.
E = (Expr( T ) + "+" + Expr( E )) >? dummy[addstack(); 1] | Expr( T );
T = (Expr( T ) + "*" + Expr( F )) >? dummy[mulstack(); 1] | Expr( F );
F = ("(" + Expr( E ) + ")") | Expr( C );
C = Pat Span( "0123456789" ) >? stack[N Items( stack ) + 1];

rc = Pat Match( text, Pat Pos( 0 ) + E + Pat R Pos( 0 ) );
If( rc,
    Show( rc, Num( stack[1] ), Eval( Parse( text ) ) ); // use JMP's parse to verify the answer
,
    Show( rc )
);