代码高尔夫：正则expression式分析器
目标
今天的Code Golf挑战是尽可能less地创build一个正则expression式parsing器。
语法
不，我没有要求你匹配Perl风格的正则expression式。 毕竟，已经有一个非常可靠的解释器！ 🙂
以下是关于这个挑战的正则expression式语法的所有知识：
- 一个术语被定义为单个文字字符，或者在分组括号
()的正则expression式。 -
*（星号）字符表示上一个TERM中的Kleene星形运算 。 这意味着零个或更多以前的术语连接在一起。 -
+（加号）字符表示一个方便的捷径：a+等同于aa*，意思是前面的一个或多个术语。 - 这个
?（问号）字符代表零或前一个字词之一。 -
|（pipe）字符表示交替，这意味着任何一方的REGULAR EXPRESSIONS都可用于匹配。 - 所有其他字符被假定为文字。 你可以假定所有其他的字符都在
[0-9A-Za-z]（即所有的英文字母数字）。
换句话说： * / + / ? 具有最高优先级，然后连接，然后交替。 由于交替的优先级比连接低，因此在没有括号的正则expression式中它的使用会导致它被绑定到每一边的完整正则expression式。 *和+和? 另一方面，只适用于前一个任期。
挑战
你的挑战是编写一个程序来编译或解释一个正则expression式（如上面定义的），然后testing一些string。
我将离开input给你。 我的build议是，正则expression式可能应该是第一位的，然后是任何数量的string来testing它。 但如果你想让它持续下去，那很好。 如果你想把所有的命令行参数或标准input，命令行中的正则expression式和标准input中的string，或者其他任何东西，那很好。 只显示一个或两个用法示例。
输出应该是true或false ，每行一个，以反映正则expression式是否匹配。
笔记：
- 我不需要说这个…但是不要在你的语言中使用任何正则expression式库！ 您需要自己编译或解释模式。 （ 编辑：如果需要分割或连接string，则可以使用正则expression式，但不能直接使用它来解决问题，例如，将input正则expression式转换为语言正则expression式并使用它）。
- 正则expression式必须完全匹配这个挑战的inputstring。 （相当于，如果您熟悉类似于Perl的正则expression式，则假定所有匹配的string的起始和结束锚定都已到位）
- 对于这个挑战，所有的特殊字符
()*+?|预计不会真正发生。 如果在input中出现，则假定没有模式可以匹配所讨论的string是安全的。 - input要testing的string应以区分大小写的方式进行评估。
例子
对于这些例子，我假设一切都是在命令行参数中完成的，首先是正则expression式。 （正如我上面所说，input取决于你。） 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 ab true true false true false true
注意：对不起，忘了做社区维基！ 🙁
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}%
有点直接，第一个循环将正则expression式转换成NFA，第二个循环运行。
Sun Aug 22 00:58:24 EST 2010 （271→266）更改variables名称以删除空格
Sun Aug 22 01:07:11 EST 2010 （266→265）使[]variables
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 ab"|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
（口译） 630 622 617 615 582 576 573 572 558 554 544 538 529 504 502 500 499字符
这理解括号，并在正则expression式生活（即不先parsing）
#define C char #define M m(s,o m(C*s,C*o,C*S,C*p,C*P,CT){C*n=P-1,*q=s,h=*P==41,c=1;for(;h*c;c-=*n--==40)c+=*n==41; c=*P-42;c=pP?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,Ph,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。 会崩溃在非法模式。
这从右到左分析正则expression式和string，节省了一些字符。
inputargv，输出反向正常顺序：
$ ./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 ab 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
C（parsing+匹配） 727 670个字符
这还没有完全打高尔夫球，但我想尝试一下，如果首先parsing正则expression式会影响现场解释。 它的确如此，因为它的成本更高，尽pipeparsing和匹配都比较容易编写/理解。
#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");}
它将一个正则expression式parsing成一个结构体，其中每个结构体都有：
- 要匹配的字符或指向要匹配的子模式的结构的指针
- 一个指向下一个符号结构的指针（如果有的话）
- 指向下一个可选模式的指针（如果有的话）
- 乘数是\ 0，
*还是?–(pat)+被立即parsing成(pat)(pat)*，这使得匹配变得容易得多
哈斯克尔：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) snab (x:y)|n<1&&x==a=(j,x:y)|x==a=f(-1)|x==b=f 1|u=f 0where fk=x%s(n+k)aby br|m==j=r|u=b$d(o++"(("++x)++")("++z++")/)"++w where(c,m)=s 0'|''!'r;_:v=m;(o,_:x)=s 0'('')'$dc;(z,_:w)=s 0')''('v (!)gfx=f x>>=g c[]=(:j) cr=f!cs where(s,f)=ir pq@(r:s)|r=='('=(s,(:j))|u=(a,f!g)where(w,f)=iq;(a,g)=pw _?[]=j c?(h:r)|c==h=[r]|u=j i(r:q)=maybe(q,(r?))id$lookup r$zip")/*+?"$pq:zip[e,w,w,w][\s->f s++gs,\s->s:ls,l,\s->s:fs]where(w,f)=iq;(e,g)=iw;ls|fs==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) = (fx, 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 fk = 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]
备忘录：
修改| 到一个后缀forms，然后颠倒整个正则expression式。 现在操作符都是前缀forms，很容易parsing。 该程序像这样parsing正则expression式。 列表单子用于非确定性。
用法：
> runghc Regex.hs a?b+|(a+b|b+a?)+ abb babab aaa aabba ab True True False True False True
Ruby 1.9：709个字符
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 type testcase.txt | ruby regex.rb
Ruby中的Russ Cox的NFAparsing器的实现。 一个状态被表示为一个散列，其中包含一个保存下一个状态数组的键。
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 pr r }
Perl，596个字符
半解释：
- 这是基于Higher Order Perl第8章中的continuation-passing-styleparsing器组合器的。
- 信贷帮助我删除约70个字符去Vincent Pit（VPIT）。
-
S { block }与sub { block }相同，每次只有2个字符。 -
$,是零（一个包含匹配器的coderef总是匹配，不消耗任何东西） -
c是n元级联（取任意数量的匹配器，如果顺序成功则返回成功的匹配器）。 -
a是n-ary交替（如果其中任何一个匹配成功，则返回匹配器）。 -
A是正则expression式生成器的助手 – 它需要一个连接变化的结构，并传递给C和a必要的返回一个匹配器。 -
k是星号（用一个匹配器并返回匹配器，匹配0次或更多次，k为Kleene，因为s()被parsing为s///操作符:) -
do块一次parsing正则expression式的char。@$r是当前的连接列表，@a是当前的交替列表，@p是paren组堆栈。a+被视为aa*，而a?在b被视为(a|)内联（没有plus或者maybe函数）。 - 最后一行中的
S{!length pop}是在input结束时成功的匹配器。 它作为正则expression式匹配的延续而传递，这意味着正则expression式只有匹配整个string才能成功。
对于大部分代码和更多评论的代码，请看这个Gist 。
运行它作为perl regexer.pl 'a?b+|(a+b|b+a?)+' abb babab aaa aabba ab 。 代码中没有强制换行符。
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=ac($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
JavaScript，658个字符
// 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个字符
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; }
这是通过recursion，通过切断正则expression式的前面和string的前面，并调用它自己。 例如， test("hello", "hello") => test("ello", "ello") => test("llo", "llo") => test("lo", "lo") => test("o", "o") => test("", "")返回true。 注意：裸c函数将不支持隐含的交替。 换句话说， hello|hi不行; 它必须用圆括号括起来:( (hello|hi) 。
