06/10/14 05:40:11
お久しぶりです。part1でお世話になったトリッキーの１です。
>>60-64で晒されていますが、そのサイトは私のサイトです。
正規表現が面白そうだったので久々に作ってみましたが、9行になりました。
縮めるテクニックなどを完全に忘れてしまっていますが、頑張れば7行は可能そうです。
仕事の合間に7行目指して頑張ってみようと思います。
使える記号は()*|のみです。とりあえずこれだけあれば他のも表現できると思います。
文脈自由文法は、
R ::= T | T "|" R
T ::= ε | FT
F ::= P | P*
P ::= char | "(" R ")"
となっています。gcc2.91でのみコンパイル確認しました。
使い方は、"a.exe regexp"とすれば、標準入力から読んだ内容をregexpで走査します。
見つかればmatchと表示して終了します
#include <stdio.h>
int n[999][99],z=2,i;char*s,c[999][99],v[9999];h(f,t,k){for(i=0;c[f][i]!=0;i++)
;c[f][i]=k;n[f][i]=t;}p(int o,int f,int t,char*l){int x;if(l){for(x=0;(f=c[o][x
])!=0;x++)if((f==1||*l==f)&&(n[o][x]==1||p(n[o][x],0,0,(f==1)?l:l+1)))return 1;
}else{(o==0)?p(1,f,t,0),(*s=='|')?s++,p(0,f,t,0):0:(o==1)?(*s==')'||*s=='|'||*s
==0)?h(f,t,1):(x=z++,p(2,f,x,0),p(1,x,t,0)):(o==2)?(x=z++,c[x][0]=1,n[x][0]=t,p
(3,f,x,0),(*s=='*')?h(f,t,1),s++,n[x][0]=f:0):(*s)?(*s=='(')?(s++,p(0,f,t,0),++
s,0):h(f,t,*s++):0;}}main(int x, char**o){s=o[1];p(0,0,1,0);while(gets(v)){s=v;
while(*s){if(p(0,0,0,s++))return printf("match");}}}