Сегодняшняя задача Code Golf состоит в том, чтобы создать синтаксический анализатор с минимальным количеством символов.
Нет, я не прошу вас соответствовать Регулярные выражения в стиле Perl. В конце концов, для них уже есть очень надежный переводчик! : -)
Вот все, что вам нужно знать о синтаксисе регулярных выражений для этой задачи:
()
. *
(звездочка) представляет операцию Клини со звездой в предыдущем TERM. Это означает ноль или более предыдущего термина, объединенного вместе. +
(плюс) представляет удобный ярлык: a +
эквивалентен aa *
, что означает один или несколько из предыдущего термина. ?
(вопросительный знак) представляет ноль или один из предыдущих терминов. |
(труба) символ представляет собой чередование, означающее, что в матче могут использоваться РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ с любой стороны. [0-9A-Za-z]
(т.е. все английские буквенно-цифровые символы). Или, другими словами: *
/ +
/ ?
имеют наивысший приоритет, затем конкатенация, затем чередование. Поскольку чередование имеет более низкий приоритет, чем конкатенация, его использование в регулярном выражении без скобок приводит к тому, что оно связывается с полным регулярным выражением с каждой стороны. *
и +
и ?
, с другой стороны, относятся только к непосредственно предшествующему сроку.
Ваша задача состоит в том, чтобы Напишите программу, которая скомпилирует или интерпретирует регулярное выражение (как определено выше), а затем проверит несколько строк против него.
Я оставляю ввод за вами. Я бы порекомендовал, чтобы сначала было регулярное выражение, а затем любое количество строк для его проверки; но если вы хотите, чтобы это длилось хорошо. Если вы хотите поместить все в аргументы командной строки или в стандартный ввод, или регулярное выражение в командной строке и строки в стандартный ввод, или что-то еще, это нормально. Просто покажите один или два примера использования.
Вывод должен быть true
или false
, по одному на строку, чтобы отразить, соответствует ли регулярное выражение.
Примечания:
() * +? |
не ожидается в буквальном смысле. Если кто-то приходит на вход, можно с уверенностью предположить, что ни один шаблон не может соответствовать рассматриваемой строке. Для В примерах я предполагаю, что все делается в аргументах командной строки, в первую очередь регулярное выражение. (Как я уже говорил выше, ввод зависит от вас.) 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
ПРИМЕЧАНИЕ: Извините, забыл создать вики сообщества! : - (
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, которое запускается во втором цикле.
Вс, 22 августа, 00:58:24 EST 2010
(271 → 266) изменил имена переменных, чтобы удалить пробелы
Вс, 22 августа, 01:07:11 EST 2010
(266 → 265 ) сделал []
переменную
Вс 22 августа 07:05:50 EST 2010
(265 → 259) сделал переходы в нулевое состояние встроенными
Вс 22 августа 07:19:21 EST 2010
(259 → 256) конечное состояние сделано неявно
Понедельник, 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 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. Вылетит из-за запрещенных шаблонов.
Это анализирует регулярное выражение и строку справа налево, сохраняя несколько символов.
ввод в 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
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]
Преобразует |
в суффиксную форму, а затем полностью меняет регулярное выражение. Теперь операторы имеют префиксную форму, что упрощает анализ. Программа анализирует регулярное выражение следующим образом. Монада списка используется для недетерминизма.
> runghc Regex.hs
a?b+|(a+b|b+a?)+ abb babab aaa aabba a b
True
True
False
True
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");}
он анализирует регулярное выражение в структуру, где каждая структура имеет:
*
или ?
- (pat) +
сразу анализируется в (pat) (pat) *
, что значительно упрощает сопоставление Полуобъяснение:
S {блок}
совпадает с под {блоком}
только каждый раз на 2 символа короче. $,
равно нулю (ссылка на код, содержащая сопоставление, которое всегда совпадает, ничего не потребляя) c
- n-арная конкатенация (взять любое количество сопоставителей и вернуть сопоставление, которое будет успешным, если все они успешно по порядку). a
- n-арное чередование (возьмите любое количество сопоставителей и верните сопоставление, которое будет успешным, если какое-либо из них выполнено успешно).
является помощником для построителя регулярных выражений - он принимает структуру чередования-конкатенации и при необходимости передает C
и a
, возвращая сопоставление. k
звездочка (возьмите сопоставитель и верните сопоставитель, который соответствует ему 0 или более раз подряд. k
для Клини, потому что s ()
анализируется как оператор s ///
:) do
анализирует регулярное выражение по символу за раз. @ $ r
- текущий список конкатенации, @a
- текущий список чередования, @p
- стек групп пар. a +
обрабатывается как aa *
, а a?
обрабатывается как (a |)
inline в b
(нет функций для плюс
или , возможно,
). S {! Length pop}
в последней строке - это сопоставление, которое успешно завершается в конце ввода. Он передается как продолжение для средства сопоставления регулярных выражений, что означает, что регулярное выражение будет успешным только в том случае, если оно может соответствовать всей строке. Для большей части дегольфированного и более комментируемого кода см. this Gist .
Запустите его как 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
// 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;
}
Это работает путем рекурсии, отсекая переднюю часть регулярного выражения и переднюю часть строки и вызывая себя. Например, test ("hello", "hello") => test ("ello", "ello") => test ("llo", "llo") => test ("lo", "lo ") => test (" o "," o ") => test (" "," ")
возвращает истину. Примечание: простая функция c
не поддерживает подразумеваемое чередование. Другими словами, привет | привет
работать не будет; его нужно заключить в круглые скобки: (привет | привет)
.
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 символами, если добавить псевдоним ниже)
Тест с типом testcase.txt | ruby regex.rb
Реализация парсера NFA Расса Кокса на Ruby. Состояние представляется в виде хэша с одним ключом, который содержит массив следующих состояний.
Без гольфа:
#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
}