48994_es-ES

liliconcom

recexion regex

¿Admite JSL la expresión regular recursiva?
Lo he intentado? R y \ g <0> y ninguno de ellos parece funcionar.  

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

Re: regex recursion

Unos minutos después wikipedia da un conjunto de reglas sin recursión izquierda ... que se ejecuta rápido.

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 )
);

Si está siguiendo de cerca, se pregunta cómo se ejecutará la primera versión, con recursión a la izquierda. ¿Por qué no se repite para siempre, o al menos hasta que la recursión agote la memoria disponible? Por defecto, el comparador de patrones asume que cada expr (...) debe coincidir con al menos un carácter. En algún momento, la recursión es lo suficientemente profunda como para que no quede suficiente texto y la coincidencia se respalde. Todo lo que hace una copia de seguridad y vuelve a intentarlo lleva tiempo en una cadena larga. En el segundo ejemplo, sin la recursión a la izquierda, patmatch () requiere que la opción FULLSCAN desactive la suposición porque expr () ahora puede coincidir con "" (cero caracteres).

Re: regex recursion

No, pero el patrón emparejador ama la recursión. Aquí hay un ejemplo completo de un intérprete de expresiones. No soy un experto en gramática; Creo que esto es un analizador de descenso recursivo , y creo que hace mucho seguimiento en expresiones moderadamente largas, por lo que es notablemente lento para expresiones con más de 10-20 operadores.

PatMatch devuelve 1 si el patrón coincide, 0 si falla (paréntesis no balanceados, operadores inválidos, números inválidos).

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 )
);