Pla*_*ure 53 regex language-agnostic code-golf rosetta-stone
今天的Code Golf挑战是尽可能少地创建一个正则表达式解析器.
不,我不是要求你匹配Perl风格的正则表达式.毕竟,对于那些人来说,已经有一个非常可靠的翻译!:-)
以下是您需要了解的有关此挑战的正则表达式语法的所有信息:
().*(星号)字符表示Kleene星操作在上一届.这意味着前一个词的零个或多个连接在一起.+(加)字符表示一个方便快捷方式:a+相当于aa*,这意味着一个或多个之前的术语的.?(问号)字符代表零或前项之一.|(管)字符代表的交替,也就是说,在任一侧上的正则表达式可以在比赛中使用.[0-9A-Za-z](即所有英语字母数字).或者,换一种说法:*/ +/ ?具有最高的优先级,然后串联,然后交替.由于交替的优先级低于连接,因此在没有括号的正则表达式中使用它会导致它被绑定到每一侧的完整正则表达式.*和+和?,在另一方面,将只适用于前一学期.
您的挑战是编写一个程序来编译或解释正则表达式(如上所定义),然后针对它测试一些字符串.
我要把输入留给你了.我的建议是,正则表达式可能应该首先出现,然后对任何数量的字符串进行测试; 但如果你想让它持久,那很好.如果你想把所有东西放在命令行参数或stdin,或命令行中的正则表达式和stdin中的字符串,或其他什么,那很好.只显示一两个用法示例.
输出应该是true或false每行一个,以反映正则表达式是否匹配.
笔记:
()*+?|都不会按字面意思出现.如果输入中有一个,可以安全地假设没有模式可以匹配相关字符串.对于这些示例,我假设一切都是在命令行参数中完成的,首先是regex.(正如我上面所说,输入取决于你.)myregex这里代表你对程序的调用.
> 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
注意:抱歉,忘了制作社区维基!:-(
mvd*_*vds 20
这理解括号,并在regexp live上工作(即不首先解析)
#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");}
用-Wall编译抱怨argc是char.将非法模式崩溃.
这会从右到左解析regexp和string,从而节省了几个字符.
在argv上输入,以反向正常顺序输出:
$ ./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
Nab*_*abb 15
GolfScript - 254个字符
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}%
有点直截了当,第一个循环将正则表达式转换为NFA,第二个循环运行.
Sun Aug 22 00:58:24 EST 2010 (271→266)更改变量名称以删除空格
Sun Aug 22 01:07:11 EST 2010 (266→265)使[]变量
Sun Aug 22 07:05:50 EST 2010 (265→259)成为空状态转换内联
Sun Aug 22 07:19:21 EST 2010 (259→256)最终状态使隐式
Mon Feb 7 19:24:19 EST 2011 (256→254)使用"()""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
这还没有达到最低限度,但是我想尝试一下,首先解析正则表达式是否会对现场解释它有所作为.它确实如此,因为它的成本更高,尽管解析和匹配都更容易编写/理解.
#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");}
它将regexp解析为一个struct,每个struct都有:
*或?- (pat)+被立即解析(pat)(pat)*,这使得匹配更容易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)
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]
修改|为后缀形式,然后反转整个正则表达式.现在运算符采用前缀形式,便于解析.程序像这样解析正则表达式.列表monad用于非确定性.
> runghc Regex.hs
a?b+|(a+b|b+a?)+ abb babab aaa aabba a b
True
True
False
True
False
True
半解释:
S { block }是sub { block }每次只有2个字符更短的相同.$, 是nil(包含匹配器的coderef始终匹配,不消耗任何东西)c 是n-ary连接(取任意数量的匹配器并返回一个匹配器,如果它们都按顺序成功则成功).a 是n-ary交替(取任意数量的匹配器并返回一个匹配器,如果它们中的任何一个成功则成功).A为正则表达式生成器的辅助-它需要交替- -级联的的结构和传递到C和a在必要时,返回一个匹配器.k是星(取一个匹配器并返回匹配它的匹配器0次或更多次.k对于Kleene,因为s()被解析为s///运算符:)do块一次解析一个char的正则表达式.@$r是当前的串联列表,@a是当前的交替列表,@p是paren-group堆栈.a+被视为aa*,并被a?视为(a|)内联b(没有函数plus或maybe).S{!length pop}最后一行是在成功结束的输入时匹配.它作为正则表达式匹配器的延续传递,这意味着正则表达式只有在匹配整个字符串时才会成功.对于大部分为degolfed和更多评论的代码,请参阅此要点.
运行它perl regexer.pl 'a?b+|(a+b|b+a?)+' abb babab aaa aabba a b.代码中没有强制性的换行符.
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
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}
(通过添加下面的别名,这也可以在Ruby 1.8中使用45个字符)
测试用 type testcase.txt | ruby regex.rb
在Ruby中实现Russ Cox的NFA解析器.状态表示为具有单个键的散列,其中包含下一个状态的数组.
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
}