48994_fr-FR

liliconcom

récursion de regex

JSL prend-il en charge les expressions rationnelles récursives?
J'ai essayé? R et \ g <0> et aucun d’entre eux ne semble fonctionner.  

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

Re: regex récursivité

Quelques minutes Wikipédia donne un ensemble de règles sans récursivité gauche ... qui court vite.

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 vous suivez de près, vous vous demandez comment fonctionne la première version, avec la récursivité à gauche. Pourquoi ne fait-il pas la boucle pour toujours, ou du moins jusqu'à ce que la récursion utilise la mémoire disponible? Par défaut, l'assistant de modèle suppose que chaque expr (...) doit correspondre à au moins un caractère. À un moment donné, la récursion est suffisamment profonde pour qu'il ne reste plus assez de texte et que la correspondance soit sauvegardée. Toutes ces sauvegardes et tentatives prennent du temps sur une longue chaîne. Dans le deuxième exemple, sans la récursivité gauche, patmatch () nécessite que l'option FULLSCAN désactive l'hypothèse, car expr () peut désormais correspondre à "" (zéro caractère).

Re: regex récursivité

Non, mais le corrélateur aime la récursion. Voici un exemple complet d'interprète d'expression. Je ne suis pas un expert en grammaire. Je pense que c'est un analyseur de descente récursif , et je pense qu’il effectue beaucoup de back-back sur des expressions moyennement longues, ce qui le ralentit considérablement pour les expressions comportant plus de 10 à 20 opérateurs.

PatMatch renvoie 1 si le modèle correspond, 0 s'il échoue (parenthèses non équilibrées, opérateurs non valides, nombres non valides).

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