Skip to content

Instantly share code, notes, and snippets.

@masak
Created January 22, 2010 17:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save masak/283928 to your computer and use it in GitHub Desktop.
Save masak/283928 to your computer and use it in GitHub Desktop.
$ ./test-regex '^ [ <[a..d]>+ | <[b..e]>+ ] $' bcd
Concat[
Anchor ('^')
Group[
Alt[
Quant ('greedy 1..Inf') [
EnumCharList ('abcd')
]
Quant ('greedy 1..Inf') [
EnumCharList ('bcde')
]
]
]
Anchor ('$')
]
sub ($target, :$debug) {
my $mfrom;
my $cpos = 0;
my $pos;
my $rep;
my $lastpos = $target.chars;
my @gpad; # TODO: PGE generates this one only when needed
my @ustack; # TODO: PGE generates this one only when needed
my @cstack = 'try_match';
my &goto = -> $label { @cstack[*-1] = $label };
my &local-branch = -> $label {
@cstack[*-1] ~= '_cont';
@cstack.push($label)
};
my &local-return = -> { @cstack.pop };
loop {
given @cstack[*-1] {
when 'try_match' {
if $cpos > $lastpos {
goto('fail');
break;
}
$mfrom = $pos = $cpos;
local-branch('R');
}
when 'try_match_cont' {
++$cpos;
goto('try_match');
}
when 'succeed' {
return GGE::Match.new(:$target, :from($mfrom), :to($pos));
}
when 'fail' {
local-return();
if !@cstack {
return GGE::Match.new(:$target, :from(0), :to(-2));
}
}
# concat
when 'R' { # anchor ^
if $pos == 0 { goto('R0'); break; }
goto('fail');
}
when 'R0' {
push @ustack, $pos;
local-branch('R2');
}
when 'R0_cont' {
$pos = pop @ustack;
goto('R3');
}
when 'R2' { # quant greedy 1..Inf
push @gpad, 0;
local-branch('R2_repeat');
}
when 'R2_cont' {
pop @gpad;
goto('fail');
}
when 'R2_repeat' {
$rep = @gpad[*-1];
++$rep;
@gpad[*-1] = $rep;
push @ustack, $pos;
push @ustack, $rep;
local-branch('R4');
}
when 'R2_repeat_cont' {
$rep = pop @ustack;
$pos = pop @ustack;
--$rep;
goto('R2_1');
}
when 'R2_1' {
pop @gpad;
push @ustack, $rep;
local-branch('R1');
}
when 'R2_1_cont' {
$rep = pop @ustack;
push @gpad, $rep;
goto('fail');
}
when 'R4' {
if $pos >= $lastpos
|| !defined 'abcd'.index($target.substr($pos, 1)) {
goto('fail');
break;
}
++$pos;
goto('R2_repeat');
}
when 'R3' { # quant greedy 1..Inf
push @gpad, 0;
local-branch('R3_repeat');
}
when 'R3_cont' {
pop @gpad;
goto('fail');
}
when 'R3_repeat' {
$rep = @gpad[*-1];
++$rep;
@gpad[*-1] = $rep;
push @ustack, $pos;
push @ustack, $rep;
local-branch('R5');
}
when 'R3_repeat_cont' {
$rep = pop @ustack;
$pos = pop @ustack;
--$rep;
goto('R3_1');
}
when 'R3_1' {
pop @gpad;
push @ustack, $rep;
local-branch('R1');
}
when 'R3_1_cont' {
$rep = pop @ustack;
push @gpad, $rep;
goto('fail');
}
when 'R5' {
if $pos >= $lastpos
|| !defined 'bcde'.index($target.substr($pos, 1)) {
goto('fail');
break;
}
++$pos;
goto('R3_repeat');
}
when 'R1' { # anchor $
if $pos == $lastpos { goto('succeed'); break; }
goto('fail');
}
default {
die "Don't know a label {@cstack[*-1]}";
}
}
}
}
mob: <bcd @ 0>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment