Código de Golf: analizador Regex

language-agnostic code-golf

Question

La meta

El reto actual de Code Golf es crear un analizador de expresiones regulares en el menor número de caracteres posible.

La sintaxis

No, no te pido que coincigas con las expresiones regulares estilo Perl. ¡Ya hay un intérprete muy confiable para ellos, después de todo! :-)

Aquí encontrará todo lo que necesita saber sobre la sintaxis de regex para este desafío:

• Un término se define como un carácter literal único, o una expresión regular dentro de la agrupación de paréntesis () .
• El carácter * (asterisco) representa una operación de estrella Kleene en el TÉRMINO anterior. Esto significa cero o más del término anterior, concatenado juntos.
• El carácter + (más) representa un atajo conveniente: a+ es equivalente a aa* , lo que significa uno o más del término anterior.
• El ? El carácter (signo de interrogación) representa cero o uno del término anterior.
• El | El carácter (tubería) representa una alternancia, lo que significa que las EXPRESIONES REGULARES de cualquier lado se pueden usar en la coincidencia.
• Se supone que todos los demás caracteres son literales. Puede suponer que todos los demás caracteres están dentro de [0-9A-Za-z] (es decir, todos los caracteres alfanuméricos en inglés).

O dicho de otra manera: * / + / ? tienen la precedencia más alta, luego la concatenación, luego la alternancia. Como la alternancia tiene una prioridad menor que la concatenación, su uso dentro de una expresión regular sin paréntesis hace que se vincule con la expresión regular completa en cada lado. * y + y ? , por otro lado, solo se aplicaría al término inmediato anterior.

El reto

Su desafío es escribir un programa que compilará o interpretará una expresión regular (como se definió anteriormente) y luego probará una serie de cadenas en su contra.

Te dejo la opinión. Mi recomendación sería que la expresión regular probablemente sea lo primero, y luego cualquier cantidad de cadenas para probar en su contra; pero si quieres que dure, está bien. Si quiere poner todo en argumentos de línea de comandos o en stdin, o la expresión regular en la línea de comandos y las cadenas en stdin, o lo que sea, está bien. Solo muestre un ejemplo de uso o dos.

La salida debe ser true o false , una por línea, para reflejar si la expresión regular coincide o no.

Notas:

• No debería necesitar decir esto ... ¡pero no use ninguna biblioteca regex en su idioma! Necesita compilar o interpretar el patrón usted mismo. ( Editar: puede usar expresiones regulares si es necesario para dividir o unir cadenas. Simplemente no puede usarlo para resolver directamente el problema, por ejemplo, convertir la expresión regular de entrada en una expresión regular del idioma y usar eso).
• La expresión regular debe COMPLETAR COMPLETAMENTE la cadena de entrada para este desafío. (De manera equivalente, si está familiarizado con la expresión regular de Perl, suponga que el anclaje de inicio y fin de cadena está en su lugar para todas las coincidencias)
• Para este desafío, todos los caracteres especiales ()*+?| no se espera que ocurran literalmente. Si aparece uno en la entrada, es seguro suponer que ningún patrón puede coincidir con la cadena en cuestión.
• Las cadenas de entrada para probar se deben evaluar de una manera que distinga entre mayúsculas y minúsculas.

Los ejemplos

Para los ejemplos, supongo que todo se hace en argumentos de línea de comandos, primero en expresiones regulares. (Como dije antes, la entrada depende de usted.) myregex aquí representa su invocación del programa.

> myregex easy easy Easy hard
true
false
false

> myregex ab*a aa abba abab b
true
true
false
false

> myregex 0*1|10 1 10 0110 00001
true
true
false
true

> myregex 0*(1|1+0) 1 10 0110 00001
true
true
true
true

> myregex a?b+|(a+b|b+a?)+ abb babab aaa aabba a b
true
true
false
true
false
true

NOTA: ¡ Lo siento, olvidé hacer wiki de la comunidad! :-(

Answer 1

Haskell: 610 612 627

main=getLine>>=f.words
d=reverse
u=0<1
j=[]
f(r:s)=mapM_(print.any null.c(d$b$''('':r++")"))s
c%(x,y)=(c:x,y)
s _ _ _[]=(j,j)
s n a b (x:y)|n<1&&x==a=(j,x:y)|x==a=f(-1)|x==b=f 1|u=f 0where f k=x%s(n+k)a b y
b r|m==j=r|u=b$d(o++"(("++x)++")("++z++")/)"++w where(c,m)=s 0''|''''!''r;_:v=m;(o,_:x)=s 0''('''')''$d c;(z,_:w)=s 0'')''''(''v
(!)g f x=f x>>=g
c[]=(:j)
c r=f!c s where(s,f)=i r
p q@(r:s)|r==''(''=(s,(:j))|u=(a,f!g)where(w,f)=i q;(a,g)=p w
_?[]=j
c?(h:r)|c==h=[r]|u=j
i(r:q)=maybe(q,(r?))id$lookup r$zip")/*+?"$p q:zip[e,w,w,w][/s->f s++g s,/s->s:l s,l,/s->s:f s]where(w,f)=i q;(e,g)=i w;l s|f s==j=j|u=f s++(f s>>=l)

Ungolfed:

import Control.Monad
import Data.List

-- (aa|bb|cc)   -->  )|)cc()|)bb()aa((( 

testRegex = "a?b+|(a+b|b+a?)+"

interpret regex = any null . interpret'' regex

interpret'' regex = compile (rewrite regex)

mapFst f (x, y) = (f x, y)

splitWhileBalanced _ _ _ "" = ("", "")
splitWhileBalanced n b1 b2 (x:xs)
  | n < 1 && x == b1 = ("", x:xs)
  | x == b1   = f (-1)
  | x == b2   = f 1
  | otherwise = f 0
  where
    f k = mapFst (x:) $ splitWhileBalanced (n+k) b1 b2 xs

rewrite regex = reverse $ moveBars $ ''('' : regex ++ ")"

moveBars regex
  | mtBar == "" = regex
  | otherwise = moveBars $ reverse (hOpen ++ "((" ++ tOpen) ++ ")(" ++ hClose ++ ")/)" ++ tClose
  where
    (hBar, mtBar) = splitWhileBalanced 0 ''|'' ''!'' regex -- ''!'' is a dummy character
    b:tBar = mtBar
    (hOpen, o:tOpen) = splitWhileBalanced 0 ''('' '')'' $ reverse hBar
    (hClose, c:tClose) = splitWhileBalanced 0 '')'' ''('' $ tBar

compile "" = /x -> [x]
compile rs = f <=< compile rs''
  where 
    (rs'', f) = compile'' rs

paren regex@(r:rs0)
  | r == ''(''  = (rs0, /x -> [x])
  | otherwise = (rs2, f <=< g)
  where
    (rs1, f) = compile'' regex
    (rs2, g) = paren rs1

compile'' (r:rs0) = case r of
  ''/'' -> (rs2, bar)
  ''*'' -> (rs1, star)
  ''+'' -> (rs1, plus)
  ''?'' -> (rs1, mark)
  '')'' -> paren rs0
  _   -> (rs0, lit)
  where
    (rs1, f) = compile'' rs0
    (rs2, g) = compile'' rs1
    bar str = f str ++ g str
    plus str
      | null (f str) = []
      | otherwise = f str ++ (f str >>= plus)
    star str = str : plus str
    mark str = str : f str
    lit = maybe [] (/x -> [x]) . stripPrefix [r]

Memorándum:

Modifica | a un sufijo y luego invierte toda la expresión regular. Ahora los operadores están en forma de prefijo, lo que facilita el análisis. El programa analiza la expresión regular de esta manera. La lista de mónada se usa para el no determinismo.

Uso:

> runghc Regex.hs
a?b+|(a+b|b+a?)+ abb babab aaa aabba a b
True
True
False
True
False
True

Answer 2

JavaScript, 658 caracteres

// All whitespace is optional
function c(f,p){
    var x=f[0],w=p[0],h="substr",s=f[h](2),b=p[h](1),m=0,t=0,r,g,a=0,l,u="length",y="*";
    switch(f[1]){
        case"+":if(x!=w)return;f=x+y+s;
        case y:return x==w&&c(f,b)||c(s,p);
        case"?":return x==w&&c(s,b)||c(s,p)
    }
    if(x=="("){
        o:for(l=[""];t<f[u];t++){
            switch(f[t]){
                case"|":if(a==1){m=l.push("")-1;continue}break;
                case"(":if(++a==1)continue;break;
                case")":if(!--a)break o
            }
            l[m]+=f[t]
        }
        var v=0,e=t+1;
        return l.some(function(g){
            switch(f[t+1]){
                case y:v=1;
                case"+":e=t+2;
                    for(var q=0;q<f[u];q++)
                        if(c(g+Array(q).join(f[h](0,e))+f[h](e),p))
                            return 1;
                    return;
                case"?":v=1;e=t+2;default:if(c(g+f[h](e),p))return 1;
            }
        })||(v&&c(f[h](e),p))
    }
    return p[u]?(x==w&&c(f[h](1),b)):!f[u]
}

// Make it look nicer
function test(regex, string) { return !!c(''('' + regex + '')'', string); }

test(''a?b+|(a+b|b+a?)+'', ''abb'') // true
test(''a?b+|(a+b|b+a?)+'', ''babab'') // true

Ungolfed, ~ 1500 caracteres

function test(reg, str) {
    console.log(''Testing '' + reg + '' against '' + str);
    var c = reg[0], d = str[0];


    switch (reg[1]) {
        case ''+'': 
            if (c != d) 
                return false;   
            reg = c + ''*'' + reg.substr(2);
        case ''*'': 
            return (c == d && test(reg, str.substr(1))) || test(reg.substr(2), str);
        case ''?'': 
            return (c == d && test(reg.substr(2), str.substr(1))) || test(reg.substr(2), str);
    }

    if (c == ''('') {
        var regs = [''''];
        o: for (var level = n = i = 0; i < reg.length; i++) {
            //console.log(level + '': '' + n + '': '' + reg[i]);
            switch (reg[i]) {
                case ''|'': 
                    if (level == 1) { n = regs.push('''') - 1; continue; } 
                    break;
                case ''('': 
                    if (++level == 1) continue; 
                    break;
                case '')'': 
                    if (!--level) break o; 
                    break;
            };
            regs[n] += reg[i];
        }
        //console.log(regs); // An array of alternates (hello|hi) => [''hello'', ''hi'']        

        var optional = false, end = i+1;
        return regs.some(function(jitem) {
            switch (reg[i+1]) {
                case ''*'': optional = true; // Fall through
                case ''+'': 
                    end = i+2;
                    for (var k = 0; k < reg.length; k++)
                        if (test(jitem + Array(k).join(reg.substr(0, i+2)) + reg.substr(i+2), str))
                            return true;
                    return false;

                case ''?'': optional = true; end = i+2; // Fall through
                default: if (test(jitem + reg.substr(end), str)) return true;       
            }

        }) || (optional && test(reg.substr(end), str));
    }

    if (str == '''')
        return reg == '''';

    return c == d ? test(reg.substr(1), str.substr(1)) : false;

}

Esto funciona recursivamente, cortando el frente de la expresión regular y el frente de la cuerda, y llamándose a sí mismo. Por ejemplo, test("hello", "hello") => test("ello", "ello") => test("llo", "llo") => test("lo", "lo") => test("o", "o") => test("", "") devuelve verdadero. Nota: la función bare c no admitirá la alternancia implícita. En otras palabras, hello|hi no funcionará; tiene que estar envuelto entre paréntesis: (hello|hi) .

Answer 3

C (análisis + coincidencia) 727 670 caracteres

Esto todavía no está completamente desarrollado al mínimo, pero quería probar y ver si analizar primero la expresión regular marcaría la diferencia para interpretarla en vivo. Sí, porque cuesta más, aunque tanto el análisis como la coincidencia son más fáciles de escribir / comprender.

#define Q struct q
#define C char
#define R return
Q{Q*u,*n,*a;C c,m};Q*P(C*p,C*e){Q*r=calloc(99,1);C*n=p+1,c=1,w;if(p==e)R
r;if(*p==40){for(;c;)c+=(*n==40)-(*n++==41);r->u=P(p+1,n-1);}else
if(*p==''|''){r->a=P(p+1,e);R r;}else r->c=*p;if(n<e){if(*n==43)*n=42,r->n=P(p,e);else
w=*n==42|*n==63,r->n=P(n+w,e),r->m=w?*n:0;r->a=r->n->a;}R r;}M(Q*r,C*s,C*o,C*z){C*p,
e;e=r?r->m==63|r->m==42&&M(r->n,s,o,z)?:*s&&r->c==*s?M(r->m==42?r:r->n,s+1,o,z):2:s
==z;if(e-2)R e;for(p=s,e=0;!r->c&p<=z;p++)e|=M(r->u,s,s,p)&(r->m!=42|p>s)&&M(r->m==
42?r:r->n,p,p,z);R e||r->a&&M(r->a,o,o,z);}main(C
c,C**v){for(;--c>1;)puts(M(P(v[1],index(v[1],0)),v[c],v[c],index(v[c],0))?"true":"false");}

analiza una expresión regular en una estructura, donde cada estructura tiene:

• el caracter que se emparejará o un puntero a una estructura de un subpatrón que se emparejará
• un puntero a la siguiente estructura de símbolo (si hay)
• un puntero al siguiente patrón alternativo (si lo hay)
• un multiplicador que es / 0, * o ? - (pat)+ se analiza en (pat)(pat)* inmediato lo que hace que la coincidencia sea mucho más fácil

Answer 4

C (interpretación), 630 622 617 615 582 576 573 572 558 554 544 538 529 504 502 500 499 caracteres

Esto entiende paréntesis, y funciona en la expresión regular en vivo (es decir, no se analiza primero)

#define C char
#define M m(s,o
m(C*s,C*o,C*S,C*p,C*P,C T){C*n=P-1,*q=s,h=*P==41,c=1;for(;h*c;c-=*n--==40)c+=*n==41;
c=*P-42;c=p-P?c-82?T&&c&~1&&c-21?h?2:*S==*P&s<S?M,S-1,p,n,2)||(T&4&&M,S-1,p,P,T|1)):
4:M,T?S:o,p,P-1,T?c&~1?3:7-c:0):T&&s==S||M,o,p,P-1,2):T&&s==S;if(c==2)for(c=4;q<=S;q
++)c|=m(q,S,S,n+h,P-h,2)?M,q,p,n,2)||q<S&T/4&&M,q,p,P,T&6):0;return
c&4?c&1?:T&1&&M,S,p,n,2)||M,o,p,n,0):c;}main(C*w,C**v){C*u;for(w=*++v;*++v;)puts(m(*v
-1,u,u=index(*v,0)-1,w-1,index(w,0)-1,2)?"true":"false");}

compilando con -Wall se queja de que argc sea char. Se bloqueará en patrones ilegales.

Esto analiza expresiones regulares y cadenas de derecha a izquierda, guardando algunos caracteres.

entrada en argv, salida en orden inverso normal:

$ ./a.out ab*a aa abba abab b
true
true
false
false

$ ./a.out "0*1|10" 1 10 0110 00001
true
true
false
true

$ ./a.out "0*(1|1+0)" 1 10 0110 00001
true
true
true
true

$ ./a.out "a?b+|(a+b|b+a?)+" abb babab aaa aabba a b
true
true
false
true
false
true

$ ./a.out "((A|B|C)+(a|(bbbbb)|bb|c)+)+" ABCABCaccabbbbbaACBbbb
false
$ ./a.out "((A|B|C)+(a|(bbbbb)|bb|c)+)+" ABCABCaccabbbbbaACBbbbb
true

Answer 5

Perl, 596 caracteres

Semi-explicación:

• Esto se basa en los combinadores de analizadores de continuación de estilo de paso que se encuentran en el Capítulo 8 de Higher Order Perl .
• El crédito por ayudarme a eliminar unos 70 caracteres va a Vincent Pit (VPIT).
• S { block } es lo mismo que sub { block } solo que es 2 caracteres más cortos cada vez.
• $, es nil (un coderef que contiene un matcher que siempre coincide, sin consumir nada)
• c es una concatenación n-aria (tome cualquier número de emparejamientos y devuelva un emparejamiento que tenga éxito si todos tienen éxito en secuencia).
• a es a alternancia n-aria (tome cualquier número de emparejamientos y devuelva un emparejamiento que tenga éxito si alguno de ellos tiene éxito).
• A es un ayudante para el generador de expresiones regulares: toma una estructura de alternancias de concatenaciones y pasa a C y a según sea necesario, devolviendo un marcador.
• k es la estrella (toma una coincidencia y devuelve una coincidencia que coincida con 0 o más veces en la secuencia. k para Kleene, porque s() se analiza como el operador s/// :)
• El bloque do analiza la expresión regular de a char a la vez. @$r es la lista de concatenación actual, @a es la lista de alternancia actual, @p es la pila de grupo paren. a+ se trata como aa* , y a? se trata como (a|) en línea en b (no hay funciones para plus o maybe ).
• La S{!length pop} Length S{!length pop} en la última línea es una coincidencia que tiene éxito al final de la entrada. Se aprobó como la continuación para el regex matcher, lo que significa que la expresión regular solo tiene éxito si puede hacer coincidir toda la cadena.

Para el código mayormente desglosado y más comentado, vea este Gist .

Ejecútelo como perl regexer.pl ''a?b+|(a+b|b+a?)+'' abb babab aaa aabba ab . No linebreaks obligatorios en el código.

use feature'':5.12'';
sub S(&){pop}
$,=S{goto pop};
sub p{push@{+shift},@_}
sub c{my$l=$,;for my$r(@_){my$L=$l;
$l=S{my($i,$c)=@_;&$L($i,S{&$r(shift,$c)})}}$l}
sub a{my@A=@_;S{my($i,$c,$o)=@_;$o=&$_($i,$c)and return$o for@A;0}}
sub A{$#_?a(map c(@$_),@_):c(@{+pop})}
sub k{my($I,$k)=@_;$k=a c($I,S{&$k}),$,}
$_=shift;$P=do{@a=$r=[];for(/./g){
when(''(''){p/@p,[@a];@a=$r=[]}
when('')''){$p=A@a;@a=@{pop@p};p$r=$a[-1],$p}
p/@a,$r=[]when''|'';
p$r,k pop@$r when''*'';
p$r,c $$r[-1],k pop@$r when''+'';
p$r,a pop@$r,$,when ''?'';
my$s=$_;p$r,S{my($_,$c)=@_;s/^/Q$s//&&$_->$c}}A@a};
say&$P($_,S{!length pop})?"true":"false"for@ARGV

Answer 6

GolfScript - 254 caracteres

n%([]:B:$:_"()"@*{:I"()*+|?"[{}/]?[{[[0B$,+:B))/;)]_]+}{B)):ß;:B;qß(:ß;}{8q}{[[0ß0$,)]]+}:8{[[0B-1=:ß)]]+:$q}{ß>$ß</([0+$,+]/++}:q{[[I$,:ß)]]+}]=~:$}/;{n+[0]:3/{:c;;3:1_:3;{,}{)[$=]_*2/{~/.{c={3|:3}*;}{;.1|1,/:1,<{+0}*;}if}/}/;}/;1$,?)"true""false"if n}%

De manera bastante directa, el primer ciclo convierte la expresión regular en un NFA, que se ejecuta en el segundo bucle.

Sun Aug 22 00:58:24 EST 2010 (271 → 266) cambió los nombres de variables para eliminar espacios
Sun Aug 22 01:07:11 EST 2010 (266 → 265) hizo [] una variable
Sun Aug 22 07:05:50 EST 2010 (265 → 259) realizó transiciones de estado nulo en línea
Sun Aug 22 07:19:21 EST 2010 (259 → 256) estado final implícito
Mon Feb 7 19:24:19 EST 2011 (256 → 254) usando "()""str"*

$ echo "ab*a aa abba abab b"|tr " " "/n"|golfscript regex.gs
true
true
false
false

$ echo "0*1|10 1 10 0110 00001"|tr " " "/n"|golfscript regex.gs
true
true
false
true

$ echo "0*(1|1+0) 1 10 0110 00001"|tr " " "/n"|golfscript regex.gs
true
true
true
true

$ echo "a?b+|(a+b|b+a?)+ abb babab aaa aabba a b"|tr " " "/n"|golfscript regex.gs
true
true
false
true
false
true

$ echo "((A|B|C)+(a|(bbbbb)|bb|c)+)+ ABCABCaccabbbbbaACBbbb ABCABCaccabbbbbaACBbbbb"|tr " " "/n"|golfscript regex.gs
false
true

Answer 7

Ruby 1.9: 709 caracteres

R=gets.chop;s='''';k=[];n=a=0
G={?(=>(A="(a-=1;s<<0)if a>1;")+"k<<[n,a];n=a=0",
Y=?|=>(B="s<<0while 0<a-=1;")+"n+=1",
?)=>B+(C="s<<?|while 0<=n-=1;")+"n,a=k.pop"+F=";a+=1",
?*=>D="s<<c",?+=>D,??=>D}
R.each_char{|c|eval G[c]||A+D+F};eval B+C
def P l,s;l.map{|a|a<<s};end
J={??=>(K="a=k.pop;")+"k<<[{Y=>n=[a[0]]},a[1]<<n]",
?*=>K+(H="P a[1],s={Y=>n=[a[0]]};")+"k<<[s,[n]]",
?+=>K+H+"k<<[a[0],[n]]",
Y=>(I=K+"b=k.pop;")+"k<<[{Y=>[a[0],b[0]]},a[1]+b[1]]",
?/0=>I+"P b[1],a[0];k<<[b[0],a[1]]"}
k=[];s.each_char{|c|eval J[c]||"k<<[{c=>a=[]},[a]]"}
e=k[0];P e[1],R;
p $<.map{|l|s=l.chop;*a=e[0]
s.each_char{|c|eval@f="n=a;a=a.map{|h|h[Y]||[h]}.flatten"while a!=n
a=a.inject([]){|a,h|a+(h[c]||[])}}
eval@f;a.include? R}

(Esto también funcionará en Ruby 1.8 con 45 caracteres más agregando el alias siguiente)

Prueba con el type testcase.txt | ruby regex.rb type testcase.txt | ruby regex.rb

Una implementación del analizador NFA de Russ Cox en Ruby. Un estado se representa como un hash con una sola clave que contiene una matriz de estados siguientes.

Ungolfed:

#needed to run on ruby 1.8
class String
  alias :each_char :each_byte 
end  

## Infix to Postfix

R=gets.chop  
p "regexp = #{R}"
k=[] 
s=''''  #will hold postfix string
n=a=0 #count braNches and Atoms
postfix = R.each_char{|c|
  case c
    when ?(
        (a-=1;s<<0)if a>1
        k<<[n,a]
        n=a=0
    when ?|
      s<<0while 0<a-=1
      n+=1
    when ?)
      s<<0while 0<a-=1
      s<<?|while 0<=n-=1
      n,a=k.pop;a+=1
    when ?*,?+,??
      s<< c
    else
      (a-=1;s<<0)if a>1
      s<< c
      a+=1
  end
}
s<<0while 0<a-=1
s<<?|while 0<=n-=1

## Postfix to NFA
# State is {char=>s0=[state,state]]
# Frag is [state, [s0,...]]

Y=?|   #choice indicator
X={:true=>[R]} #matcstate

 def patch l,s   #l is list of arrays, s is state.  Put s in each array
   l.map{|a|   a<< s   }
end

k=[]
s.each_char{|c|
 case c
    when ??
      a=k.pop
      s={Y=>n=[a[0]]}
      k<<[s,a[1]<<n]
    when ?*
      a=k.pop
      s={Y=>n=[a[0]]}
      patch(a[1],s)
      k<<[s,[n]]
    when ?+
      a=k.pop
      s={Y=>n=[a[0]]}
      patch(a[1],s)
      k<<[a[0],[n]]
    when ?|
     b=k.pop
     a=k.pop
      s={Y=>[a[0],b[0]]}
      k<<[s,a[1]+b[1]]
    when 0
     b=k.pop
     a=k.pop
     patch(a[1],b[0])
     k<<[a[0],b[1]]
   else
     k<<[{c=>a=[]},[a]]
   end
}
e=k.pop
patch(e[1],X)

#Running the NFA

E=[e[0]] #Evaluator
p $<.map{|l|s=l.chop
  p "evaluating: #{s}" 
  a=E
  s.each_char{|c|
    begin     #skip past split nodes
      s=a.size
      a=a.map{|h|h[?|]||[h]}.flatten  
    end while a.size!=s
    a=a.inject([]){|a,h|
    a+(h[c]||[])}  #add next state or null
  }
  a=a.map{|h|h[?|]||[h]}.flatten
  r = a.include? X  #check for end of pattern
  p r
  r
}