48994_de-DE

liliconcom

Regex-Rekursion

Unterstützt JSL rekursive Regex?
Ich habe versucht? R und \ g <0> und keiner von ihnen scheint zu funktionieren.  

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

Re: Regex-Rekursion

Ein paar Minuten später Wikipedia gibt eine Reihe von Regeln ohne Linksrekursion ... die schnell abläuft.

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

Wenn Sie genau beobachten, fragen Sie sich, wie die erste Version überhaupt läuft, mit Linksrekursion. Warum läuft es nicht für immer oder zumindest so lange, bis die Rekursion den verfügbaren Speicher belegt? Standardmäßig geht der Mustervergleicher davon aus, dass jeder Ausdruck (...) mindestens einem Zeichen entsprechen muss. Irgendwann ist die Rekursion so tief, dass nicht mehr genügend Text vorhanden ist und das Match gesichert wird. Alle diese Sicherungen und Wiederholungsversuche benötigen Zeit für eine lange Zeichenfolge. Im zweiten Beispiel erfordert patmatch () ohne die linke Rekursion die Option FULLSCAN, um die Annahme zu deaktivieren, da expr () jetzt mit "" (null Zeichen) übereinstimmen kann.

Re: Regex-Rekursion

Nein, aber der Mustervergleicher liebt die Rekursion. Hier ist ein vollständiges Beispiel eines Ausdrucksinterpreters. Ich bin kein Grammatikexperte. Ich denke das ist ein rekursiver Abstiegsparser Und ich denke, es macht eine Menge Rückverfolgung bei mäßig langen Ausdrücken, wodurch es für Ausdrücke mit mehr als etwa 10 bis 20 Operatoren merklich langsam wird.

PatMatch gibt 1 zurück, wenn das Muster übereinstimmt, 0, wenn es fehlschlägt (unsymmetrische Parens, ungültige Operatoren, ungültige Zahlen).

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