# HG changeset patch # User Ryoma SHINYA # Date 1281556549 -32400 # Node ID e79cdc772194dc561f561a1ec9490a1ebc6f86e1 # Parent 9275fe406966a8e10d26d309d1ce5bd264434af8 add nfa figs diff -r 9275fe406966 -r e79cdc772194 fig1.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fig1.eps Thu Aug 12 04:55:49 2010 +0900 @@ -0,0 +1,281 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: graphviz version 2.26.3 (20100126.1600) +%%Title: G +%%Pages: 1 +%%BoundingBox: 36 36 284 125 +%%EndComments +save +%%BeginProlog +/DotDict 200 dict def +DotDict begin + +/setupLatin1 { +mark +/EncodingVector 256 array def + EncodingVector 0 + +ISOLatin1Encoding 0 255 getinterval putinterval +EncodingVector 45 /hyphen put + +% Set up ISO Latin 1 character encoding +/starnetISO { + dup dup findfont dup length dict begin + { 1 index /FID ne { def }{ pop pop } ifelse + } forall + /Encoding EncodingVector def + currentdict end definefont +} def +/Times-Roman starnetISO def +/Times-Italic starnetISO def +/Times-Bold starnetISO def +/Times-BoldItalic starnetISO def +/Helvetica starnetISO def +/Helvetica-Oblique starnetISO def +/Helvetica-Bold starnetISO def +/Helvetica-BoldOblique starnetISO def +/Courier starnetISO def +/Courier-Oblique starnetISO def +/Courier-Bold starnetISO def +/Courier-BoldOblique starnetISO def +cleartomark +} bind def + +%%BeginResource: procset graphviz 0 0 +/coord-font-family /Times-Roman def +/default-font-family /Times-Roman def +/coordfont coord-font-family findfont 8 scalefont def + +/InvScaleFactor 1.0 def +/set_scale { + dup 1 exch div /InvScaleFactor exch def + scale +} bind def + +% styles +/solid { [] 0 setdash } bind def +/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def +/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def +/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def +/bold { 2 setlinewidth } bind def +/filled { } bind def +/unfilled { } bind def +/rounded { } bind def +/diagonals { } bind def + +% hooks for setting color +/nodecolor { sethsbcolor } bind def +/edgecolor { sethsbcolor } bind def +/graphcolor { sethsbcolor } bind def +/nopcolor {pop pop pop} bind def + +/beginpage { % i j npages + /npages exch def + /j exch def + /i exch def + /str 10 string def + npages 1 gt { + gsave + coordfont setfont + 0 0 moveto + (\() show i str cvs show (,) show j str cvs show (\)) show + grestore + } if +} bind def + +/set_font { + findfont exch + scalefont setfont +} def + +% draw text fitted to its expected width +/alignedtext { % width text + /text exch def + /width exch def + gsave + width 0 gt { + [] 0 setdash + text stringwidth pop width exch sub text length div 0 text ashow + } if + grestore +} def + +/boxprim { % xcorner ycorner xsize ysize + 4 2 roll + moveto + 2 copy + exch 0 rlineto + 0 exch rlineto + pop neg 0 rlineto + closepath +} bind def + +/ellipse_path { + /ry exch def + /rx exch def + /y exch def + /x exch def + matrix currentmatrix + newpath + x y translate + rx ry scale + 0 0 1 0 360 arc + setmatrix +} bind def + +/endpage { showpage } bind def +/showpage { } def + +/layercolorseq + [ % layer color sequence - darkest to lightest + [0 0 0] + [.2 .8 .8] + [.4 .8 .8] + [.6 .8 .8] + [.8 .8 .8] + ] +def + +/layerlen layercolorseq length def + +/setlayer {/maxlayer exch def /curlayer exch def + layercolorseq curlayer 1 sub layerlen mod get + aload pop sethsbcolor + /nodecolor {nopcolor} def + /edgecolor {nopcolor} def + /graphcolor {nopcolor} def +} bind def + +/onlayer { curlayer ne {invis} if } def + +/onlayers { + /myupper exch def + /mylower exch def + curlayer mylower lt + curlayer myupper gt + or + {invis} if +} def + +/curlayer 0 def + +%%EndResource +%%EndProlog +%%BeginSetup +14 default-font-family set_font +1 setmiterlimit +% /arrowlength 10 def +% /arrowwidth 5 def + +% make sure pdfmark is harmless for PS-interpreters other than Distiller +/pdfmark where {pop} {userdict /pdfmark /cleartomark load put} ifelse +% make '<<' and '>>' safe on PS Level 1 devices +/languagelevel where {pop languagelevel}{1} ifelse +2 lt { + userdict (<<) cvn ([) cvn load put + userdict (>>) cvn ([) cvn load put +} if + +%%EndSetup +setupLatin1 +%%Page: 1 1 +%%PageBoundingBox: 36 36 284 125 +%%PageOrientation: Portrait +0 0 1 beginpage +gsave +36 36 248 89 boxprim clip newpath +1 1 set_scale 0 rotate 40 41 translate +% regex +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +21.5 12.9 moveto 11 (A) alignedtext +grestore +% q0 +gsave +0 0 1 nodecolor +113 56 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +113 56 20.8 20.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +105 50.9 moveto 16 (q0) alignedtext +grestore +% q1 +gsave +0 0 1 nodecolor +215 56 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +215 56 20.8 20.8 ellipse_path stroke +1 setlinewidth +filled +0 0 0 nodecolor +215 56 24.8 24.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +207 50.9 moveto 16 (q1) alignedtext +grestore +% q0->q1 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 134.13 56 moveto +147.31 56 164.6 56 179.81 56 curveto +stroke +0 0 0 edgecolor +newpath 179.93 59.5 moveto +189.93 56 lineto +179.93 52.5 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 179.93 59.5 moveto +189.93 56 lineto +179.93 52.5 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +152.5 58.4 moveto 19 ('A') alignedtext +grestore +% start +gsave +0 0 0 nodecolor +27 56 1.8 1.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +27 56 1.8 1.8 ellipse_path stroke +grestore +% start->q0 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 29.13 56 moveto +36.43 56 61.18 56 81.91 56 curveto +stroke +0 0 0 edgecolor +newpath 81.98 59.5 moveto +91.98 56 lineto +81.98 52.5 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 81.98 59.5 moveto +91.98 56 lineto +81.98 52.5 lineto +closepath stroke +grestore +endpage +showpage +grestore +%%PageTrailer +%%EndPage: 1 +%%Trailer +end +restore +%%EOF diff -r 9275fe406966 -r e79cdc772194 fig2.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fig2.eps Thu Aug 12 04:55:49 2010 +0900 @@ -0,0 +1,305 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: graphviz version 2.26.3 (20100126.1600) +%%Title: G +%%Pages: 1 +%%BoundingBox: 36 36 284 125 +%%EndComments +save +%%BeginProlog +/DotDict 200 dict def +DotDict begin + +/setupLatin1 { +mark +/EncodingVector 256 array def + EncodingVector 0 + +ISOLatin1Encoding 0 255 getinterval putinterval +EncodingVector 45 /hyphen put + +% Set up ISO Latin 1 character encoding +/starnetISO { + dup dup findfont dup length dict begin + { 1 index /FID ne { def }{ pop pop } ifelse + } forall + /Encoding EncodingVector def + currentdict end definefont +} def +/Times-Roman starnetISO def +/Times-Italic starnetISO def +/Times-Bold starnetISO def +/Times-BoldItalic starnetISO def +/Helvetica starnetISO def +/Helvetica-Oblique starnetISO def +/Helvetica-Bold starnetISO def +/Helvetica-BoldOblique starnetISO def +/Courier starnetISO def +/Courier-Oblique starnetISO def +/Courier-Bold starnetISO def +/Courier-BoldOblique starnetISO def +cleartomark +} bind def + +%%BeginResource: procset graphviz 0 0 +/coord-font-family /Times-Roman def +/default-font-family /Times-Roman def +/coordfont coord-font-family findfont 8 scalefont def + +/InvScaleFactor 1.0 def +/set_scale { + dup 1 exch div /InvScaleFactor exch def + scale +} bind def + +% styles +/solid { [] 0 setdash } bind def +/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def +/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def +/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def +/bold { 2 setlinewidth } bind def +/filled { } bind def +/unfilled { } bind def +/rounded { } bind def +/diagonals { } bind def + +% hooks for setting color +/nodecolor { sethsbcolor } bind def +/edgecolor { sethsbcolor } bind def +/graphcolor { sethsbcolor } bind def +/nopcolor {pop pop pop} bind def + +/beginpage { % i j npages + /npages exch def + /j exch def + /i exch def + /str 10 string def + npages 1 gt { + gsave + coordfont setfont + 0 0 moveto + (\() show i str cvs show (,) show j str cvs show (\)) show + grestore + } if +} bind def + +/set_font { + findfont exch + scalefont setfont +} def + +% draw text fitted to its expected width +/alignedtext { % width text + /text exch def + /width exch def + gsave + width 0 gt { + [] 0 setdash + text stringwidth pop width exch sub text length div 0 text ashow + } if + grestore +} def + +/boxprim { % xcorner ycorner xsize ysize + 4 2 roll + moveto + 2 copy + exch 0 rlineto + 0 exch rlineto + pop neg 0 rlineto + closepath +} bind def + +/ellipse_path { + /ry exch def + /rx exch def + /y exch def + /x exch def + matrix currentmatrix + newpath + x y translate + rx ry scale + 0 0 1 0 360 arc + setmatrix +} bind def + +/endpage { showpage } bind def +/showpage { } def + +/layercolorseq + [ % layer color sequence - darkest to lightest + [0 0 0] + [.2 .8 .8] + [.4 .8 .8] + [.6 .8 .8] + [.8 .8 .8] + ] +def + +/layerlen layercolorseq length def + +/setlayer {/maxlayer exch def /curlayer exch def + layercolorseq curlayer 1 sub layerlen mod get + aload pop sethsbcolor + /nodecolor {nopcolor} def + /edgecolor {nopcolor} def + /graphcolor {nopcolor} def +} bind def + +/onlayer { curlayer ne {invis} if } def + +/onlayers { + /myupper exch def + /mylower exch def + curlayer mylower lt + curlayer myupper gt + or + {invis} if +} def + +/curlayer 0 def + +%%EndResource +%%EndProlog +%%BeginSetup +14 default-font-family set_font +1 setmiterlimit +% /arrowlength 10 def +% /arrowwidth 5 def + +% make sure pdfmark is harmless for PS-interpreters other than Distiller +/pdfmark where {pop} {userdict /pdfmark /cleartomark load put} ifelse +% make '<<' and '>>' safe on PS Level 1 devices +/languagelevel where {pop languagelevel}{1} ifelse +2 lt { + userdict (<<) cvn ([) cvn load put + userdict (>>) cvn ([) cvn load put +} if + +%%EndSetup +setupLatin1 +%%Page: 1 1 +%%PageBoundingBox: 36 36 284 125 +%%PageOrientation: Portrait +0 0 1 beginpage +gsave +36 36 248 89 boxprim clip newpath +1 1 set_scale 0 rotate 40 41 translate +% regex +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +15 12.9 moveto 24 (A|B) alignedtext +grestore +% q0 +gsave +0 0 1 nodecolor +113 56 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +113 56 20.8 20.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +105 50.9 moveto 16 (q0) alignedtext +grestore +% q1 +gsave +0 0 1 nodecolor +215 56 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +215 56 20.8 20.8 ellipse_path stroke +1 setlinewidth +filled +0 0 0 nodecolor +215 56 24.8 24.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +207 50.9 moveto 16 (q1) alignedtext +grestore +% q0->q1 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 134.13 56 moveto +147.31 56 164.6 56 179.81 56 curveto +stroke +0 0 0 edgecolor +newpath 179.93 59.5 moveto +189.93 56 lineto +179.93 52.5 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 179.93 59.5 moveto +189.93 56 lineto +179.93 52.5 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +152.5 58.4 moveto 19 ('A') alignedtext +grestore +% q0->q1 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 131.01 45.12 moveto +137.41 41.83 144.81 38.66 152 37 curveto +162.35 34.61 173.5 36.47 183.49 39.8 curveto +stroke +0 0 0 edgecolor +newpath 182.45 43.14 moveto +193.03 43.52 lineto +184.99 36.62 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 182.45 43.14 moveto +193.03 43.52 lineto +184.99 36.62 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +153 39.4 moveto 18 ('B') alignedtext +grestore +% start +gsave +0 0 0 nodecolor +27 56 1.8 1.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +27 56 1.8 1.8 ellipse_path stroke +grestore +% start->q0 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 29.13 56 moveto +36.43 56 61.18 56 81.91 56 curveto +stroke +0 0 0 edgecolor +newpath 81.98 59.5 moveto +91.98 56 lineto +81.98 52.5 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 81.98 59.5 moveto +91.98 56 lineto +81.98 52.5 lineto +closepath stroke +grestore +endpage +showpage +grestore +%%PageTrailer +%%EndPage: 1 +%%Trailer +end +restore +%%EOF diff -r 9275fe406966 -r e79cdc772194 fig3.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fig3.eps Thu Aug 12 04:55:49 2010 +0900 @@ -0,0 +1,270 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: graphviz version 2.26.3 (20100126.1600) +%%Title: G +%%Pages: 1 +%%BoundingBox: 36 36 186 158 +%%EndComments +save +%%BeginProlog +/DotDict 200 dict def +DotDict begin + +/setupLatin1 { +mark +/EncodingVector 256 array def + EncodingVector 0 + +ISOLatin1Encoding 0 255 getinterval putinterval +EncodingVector 45 /hyphen put + +% Set up ISO Latin 1 character encoding +/starnetISO { + dup dup findfont dup length dict begin + { 1 index /FID ne { def }{ pop pop } ifelse + } forall + /Encoding EncodingVector def + currentdict end definefont +} def +/Times-Roman starnetISO def +/Times-Italic starnetISO def +/Times-Bold starnetISO def +/Times-BoldItalic starnetISO def +/Helvetica starnetISO def +/Helvetica-Oblique starnetISO def +/Helvetica-Bold starnetISO def +/Helvetica-BoldOblique starnetISO def +/Courier starnetISO def +/Courier-Oblique starnetISO def +/Courier-Bold starnetISO def +/Courier-BoldOblique starnetISO def +cleartomark +} bind def + +%%BeginResource: procset graphviz 0 0 +/coord-font-family /Times-Roman def +/default-font-family /Times-Roman def +/coordfont coord-font-family findfont 8 scalefont def + +/InvScaleFactor 1.0 def +/set_scale { + dup 1 exch div /InvScaleFactor exch def + scale +} bind def + +% styles +/solid { [] 0 setdash } bind def +/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def +/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def +/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def +/bold { 2 setlinewidth } bind def +/filled { } bind def +/unfilled { } bind def +/rounded { } bind def +/diagonals { } bind def + +% hooks for setting color +/nodecolor { sethsbcolor } bind def +/edgecolor { sethsbcolor } bind def +/graphcolor { sethsbcolor } bind def +/nopcolor {pop pop pop} bind def + +/beginpage { % i j npages + /npages exch def + /j exch def + /i exch def + /str 10 string def + npages 1 gt { + gsave + coordfont setfont + 0 0 moveto + (\() show i str cvs show (,) show j str cvs show (\)) show + grestore + } if +} bind def + +/set_font { + findfont exch + scalefont setfont +} def + +% draw text fitted to its expected width +/alignedtext { % width text + /text exch def + /width exch def + gsave + width 0 gt { + [] 0 setdash + text stringwidth pop width exch sub text length div 0 text ashow + } if + grestore +} def + +/boxprim { % xcorner ycorner xsize ysize + 4 2 roll + moveto + 2 copy + exch 0 rlineto + 0 exch rlineto + pop neg 0 rlineto + closepath +} bind def + +/ellipse_path { + /ry exch def + /rx exch def + /y exch def + /x exch def + matrix currentmatrix + newpath + x y translate + rx ry scale + 0 0 1 0 360 arc + setmatrix +} bind def + +/endpage { showpage } bind def +/showpage { } def + +/layercolorseq + [ % layer color sequence - darkest to lightest + [0 0 0] + [.2 .8 .8] + [.4 .8 .8] + [.6 .8 .8] + [.8 .8 .8] + ] +def + +/layerlen layercolorseq length def + +/setlayer {/maxlayer exch def /curlayer exch def + layercolorseq curlayer 1 sub layerlen mod get + aload pop sethsbcolor + /nodecolor {nopcolor} def + /edgecolor {nopcolor} def + /graphcolor {nopcolor} def +} bind def + +/onlayer { curlayer ne {invis} if } def + +/onlayers { + /myupper exch def + /mylower exch def + curlayer mylower lt + curlayer myupper gt + or + {invis} if +} def + +/curlayer 0 def + +%%EndResource +%%EndProlog +%%BeginSetup +14 default-font-family set_font +1 setmiterlimit +% /arrowlength 10 def +% /arrowwidth 5 def + +% make sure pdfmark is harmless for PS-interpreters other than Distiller +/pdfmark where {pop} {userdict /pdfmark /cleartomark load put} ifelse +% make '<<' and '>>' safe on PS Level 1 devices +/languagelevel where {pop languagelevel}{1} ifelse +2 lt { + userdict (<<) cvn ([) cvn load put + userdict (>>) cvn ([) cvn load put +} if + +%%EndSetup +setupLatin1 +%%Page: 1 1 +%%PageBoundingBox: 36 36 186 158 +%%PageOrientation: Portrait +0 0 1 beginpage +gsave +36 36 150 122 boxprim clip newpath +1 1 set_scale 0 rotate 40 41 translate +% regex +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +17.5 12.9 moveto 19 (A*) alignedtext +grestore +% q0 +gsave +0 0 1 nodecolor +117 56 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +117 56 20.8 20.8 ellipse_path stroke +1 setlinewidth +filled +0 0 0 nodecolor +117 56 24.8 24.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +109 50.9 moveto 16 (q0) alignedtext +grestore +% q0->q0 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 108.85 79.88 moveto +108.18 90.18 110.9 99 117 99 curveto +120.91 99 123.43 95.38 124.56 90.07 curveto +stroke +0 0 0 edgecolor +newpath 128.07 90.06 moveto +125.15 79.88 lineto +121.08 89.66 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 128.07 90.06 moveto +125.15 79.88 lineto +121.08 89.66 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +107.5 101.4 moveto 19 ('A') alignedtext +grestore +% start +gsave +0 0 0 nodecolor +27 56 1.8 1.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +27 56 1.8 1.8 ellipse_path stroke +grestore +% start->q0 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 28.88 56 moveto +35.73 56 60.11 56 81.49 56 curveto +stroke +0 0 0 edgecolor +newpath 81.65 59.5 moveto +91.65 56 lineto +81.65 52.5 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 81.65 59.5 moveto +91.65 56 lineto +81.65 52.5 lineto +closepath stroke +grestore +endpage +showpage +grestore +%%PageTrailer +%%EndPage: 1 +%%Trailer +end +restore +%%EOF diff -r 9275fe406966 -r e79cdc772194 fig4.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fig4.eps Thu Aug 12 04:55:49 2010 +0900 @@ -0,0 +1,329 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: graphviz version 2.26.3 (20100126.1600) +%%Title: G +%%Pages: 1 +%%BoundingBox: 36 36 294 187 +%%EndComments +save +%%BeginProlog +/DotDict 200 dict def +DotDict begin + +/setupLatin1 { +mark +/EncodingVector 256 array def + EncodingVector 0 + +ISOLatin1Encoding 0 255 getinterval putinterval +EncodingVector 45 /hyphen put + +% Set up ISO Latin 1 character encoding +/starnetISO { + dup dup findfont dup length dict begin + { 1 index /FID ne { def }{ pop pop } ifelse + } forall + /Encoding EncodingVector def + currentdict end definefont +} def +/Times-Roman starnetISO def +/Times-Italic starnetISO def +/Times-Bold starnetISO def +/Times-BoldItalic starnetISO def +/Helvetica starnetISO def +/Helvetica-Oblique starnetISO def +/Helvetica-Bold starnetISO def +/Helvetica-BoldOblique starnetISO def +/Courier starnetISO def +/Courier-Oblique starnetISO def +/Courier-Bold starnetISO def +/Courier-BoldOblique starnetISO def +cleartomark +} bind def + +%%BeginResource: procset graphviz 0 0 +/coord-font-family /Times-Roman def +/default-font-family /Times-Roman def +/coordfont coord-font-family findfont 8 scalefont def + +/InvScaleFactor 1.0 def +/set_scale { + dup 1 exch div /InvScaleFactor exch def + scale +} bind def + +% styles +/solid { [] 0 setdash } bind def +/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def +/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def +/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def +/bold { 2 setlinewidth } bind def +/filled { } bind def +/unfilled { } bind def +/rounded { } bind def +/diagonals { } bind def + +% hooks for setting color +/nodecolor { sethsbcolor } bind def +/edgecolor { sethsbcolor } bind def +/graphcolor { sethsbcolor } bind def +/nopcolor {pop pop pop} bind def + +/beginpage { % i j npages + /npages exch def + /j exch def + /i exch def + /str 10 string def + npages 1 gt { + gsave + coordfont setfont + 0 0 moveto + (\() show i str cvs show (,) show j str cvs show (\)) show + grestore + } if +} bind def + +/set_font { + findfont exch + scalefont setfont +} def + +% draw text fitted to its expected width +/alignedtext { % width text + /text exch def + /width exch def + gsave + width 0 gt { + [] 0 setdash + text stringwidth pop width exch sub text length div 0 text ashow + } if + grestore +} def + +/boxprim { % xcorner ycorner xsize ysize + 4 2 roll + moveto + 2 copy + exch 0 rlineto + 0 exch rlineto + pop neg 0 rlineto + closepath +} bind def + +/ellipse_path { + /ry exch def + /rx exch def + /y exch def + /x exch def + matrix currentmatrix + newpath + x y translate + rx ry scale + 0 0 1 0 360 arc + setmatrix +} bind def + +/endpage { showpage } bind def +/showpage { } def + +/layercolorseq + [ % layer color sequence - darkest to lightest + [0 0 0] + [.2 .8 .8] + [.4 .8 .8] + [.6 .8 .8] + [.8 .8 .8] + ] +def + +/layerlen layercolorseq length def + +/setlayer {/maxlayer exch def /curlayer exch def + layercolorseq curlayer 1 sub layerlen mod get + aload pop sethsbcolor + /nodecolor {nopcolor} def + /edgecolor {nopcolor} def + /graphcolor {nopcolor} def +} bind def + +/onlayer { curlayer ne {invis} if } def + +/onlayers { + /myupper exch def + /mylower exch def + curlayer mylower lt + curlayer myupper gt + or + {invis} if +} def + +/curlayer 0 def + +%%EndResource +%%EndProlog +%%BeginSetup +14 default-font-family set_font +1 setmiterlimit +% /arrowlength 10 def +% /arrowwidth 5 def + +% make sure pdfmark is harmless for PS-interpreters other than Distiller +/pdfmark where {pop} {userdict /pdfmark /cleartomark load put} ifelse +% make '<<' and '>>' safe on PS Level 1 devices +/languagelevel where {pop languagelevel}{1} ifelse +2 lt { + userdict (<<) cvn ([) cvn load put + userdict (>>) cvn ([) cvn load put +} if + +%%EndSetup +setupLatin1 +%%Page: 1 1 +%%PageBoundingBox: 36 36 294 187 +%%PageOrientation: Portrait +0 0 1 beginpage +gsave +36 36 258 151 boxprim clip newpath +1 1 set_scale 0 rotate 40 41 translate +% regex +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +8 12.9 moveto 50 (\(A|B\)*C) alignedtext +grestore +% q0 +gsave +0 0 1 nodecolor +125 56 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +125 56 20.8 20.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +117 50.9 moveto 16 (q0) alignedtext +grestore +% q0->q0 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 121.32 76.86 moveto +120.92 86.54 122.15 95 125 95 curveto +126.74 95 127.87 91.86 128.4 87.22 curveto +stroke +0 0 0 edgecolor +newpath 131.91 86.95 moveto +128.68 76.86 lineto +124.91 86.77 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 131.91 86.95 moveto +128.68 76.86 lineto +124.91 86.77 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +115.5 97.4 moveto 19 ('A') alignedtext +grestore +% q0->q0 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 111.79 72.34 moveto +102.41 91.18 106.81 113 125 113 curveto +140.2 113 145.78 97.75 141.72 81.74 curveto +stroke +0 0 0 edgecolor +newpath 144.98 80.49 moveto +138.21 72.34 lineto +138.43 82.93 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 144.98 80.49 moveto +138.21 72.34 lineto +138.43 82.93 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +116 115.4 moveto 18 ('B') alignedtext +grestore +% q1 +gsave +0 0 1 nodecolor +225 56 20.8 20.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +225 56 20.8 20.8 ellipse_path stroke +1 setlinewidth +filled +0 0 0 nodecolor +225 56 24.8 24.8 ellipse_path stroke +0 0 0 nodecolor +14 /Times-Roman set_font +217 50.9 moveto 16 (q1) alignedtext +grestore +% q0->q1 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 146.21 56 moveto +158.85 56 175.21 56 189.75 56 curveto +stroke +0 0 0 edgecolor +newpath 189.94 59.5 moveto +199.94 56 lineto +189.94 52.5 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 189.94 59.5 moveto +199.94 56 lineto +189.94 52.5 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +164 58.4 moveto 18 ('C') alignedtext +grestore +% start +gsave +0 0 0 nodecolor +33 56 1.8 1.8 ellipse_path fill +1 setlinewidth +filled +0 0 0 nodecolor +33 56 1.8 1.8 ellipse_path stroke +grestore +% start->q0 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 34.92 56 moveto +42.48 56 70.91 56 93.83 56 curveto +stroke +0 0 0 edgecolor +newpath 93.88 59.5 moveto +103.88 56 lineto +93.88 52.5 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 93.88 59.5 moveto +103.88 56 lineto +93.88 52.5 lineto +closepath stroke +grestore +endpage +showpage +grestore +%%PageTrailer +%%EndPage: 1 +%%Trailer +end +restore +%%EOF diff -r 9275fe406966 -r e79cdc772194 paper.pdf Binary file paper.pdf has changed diff -r 9275fe406966 -r e79cdc772194 paper.tex --- a/paper.tex Tue Aug 10 18:27:06 2010 +0900 +++ b/paper.tex Thu Aug 12 04:55:49 2010 +0900 @@ -44,7 +44,7 @@ % % ここにタイトル英訳 (英文の場合は和訳) を書く． % -\ejtitle{Implimentation Regular Expression Engine with Just-In-Time Compile.} +\ejtitle{Implimentation of Regular Expression Engine with Just-In-Time Compilation.} % % ここに著者英文表記 (英文の場合は和文表記) および % 所属 (和文および英文) を書く． @@ -67,61 +67,85 @@ % 和文アブストラクト % 和文アブストラクト \Jabstract{% -当研究室では, Concinuation based C という 状態遷移記述に適した C の下位言語を提案している. -Continuous bsed C は ステートメントより大きく, 関数よりも小さなプログラ +当研究室では, Concinuation based C という, 状態遷移記述に適した C の下位 +言語を提案している.Continuous bsed C は ステートメントより大きく, 関数よりも小さなプログラ ミング単位としてコードセグメントを持ち, コードセグメントからの継続を基本としている. -本研究では, 与えられた正規表現から, 等価な う右舷状態オートマトンに変換し, さらにその状態遷遷移 -を CbC 等のプログラミング言語の記述に変換し, 実行時コンパイルによって得 -られた正規表現評価器を生成するコンパイラを Python で記述し, 評価を行った.} +本研究では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し, +オートマトンにおける状態遷遷移を Continuous based C/Cによる継続/関数呼び出 +しに変換する正規表現コンパイラを Python で実装した.} % \maketitle \section{はじめに} -... +近年, 実行時コンパイルによる高速化(Just-in-Time Compile)が様々 +なプログラムで用いられている. これらは, コンパイラ理論の発展により +実行時コンパイルにかかるオーバーヘッドよりも, コンパイルによって得られる +機械語レベルのプログラムの実行速度が上回る場合において有効であり, たとえ +ば Java の HotSpot や Python の PyPy など, 仮想マシンを持つ言語処理系の +最適化技術として利用されている. -\section{CbC} -... +実行時コンパイルが可能な対象として, 正規表現評価器に着目し,コンパイラ基 +盤であるLLVM, GCC をバックエンドに用いた実行時コンパイルを行う評価器を +Pythonによって実装した. + +本論文では, まず正規表現のコンパイル方法について説明し, 実装した評価器の +性能調査のために, 正規表現を用いてテキストマッチ検査を行う grep と同等の +機能を実装し, GNU grep との比較を行う. \section{正規表現} -\section{正規表現によるテキストマッチ} +\subsection{正規表現によるテキストマッチ} 正規表現は与えられた文字列を受理するかどうかを判定できるパターンマッチン グの機構であり, sed, grep, awk を始めとするテキスト処理ツールに広く利用 されている. 正規表現には定められた文法によって記述され, 例えば,正規表現 ``a*b''は''a''の0回以上の繰り返し ``b'' で終わる文字列(``b'', ``ab'', ``'aaaab')を受理し, ``a(b|c)'' は ``a''で始まり,直後が ``b'' または ``c''で終わる文字列(``ab'', ``ac'') を受理する. -% -% -\section{正規表現の評価器} -\section{grep} -\section{正規表現からCbCへの変換} + +\subsection{grep} + +\section{正規表現の実行時コンパイル} +\subsection{正規表現からNFAへの変換} +\subsection{NFAからDFAへの変換} +は + +\begin{figure}[!tb] +\begin{center} +\scalebox{0.80}{\includegraphics{fig1.eps}} +\end{center} +\end{figure} + +\begin{figure}[tb] +\begin{center} +\scalebox{0.80}{\includegraphics{fig2.eps}} +\end{center} +\end{figure} + +\begin{figure}[tb] +\begin{center} +\scalebox{0.80}{\includegraphics{fig3.eps}} +\end{center} +\end{figure} + +\subsection{DFAからContinuous base Cへの変換} % -% +\section{評価} + +... + \begin{adjustvboxheight} % needed only when Appendix follows \begin{thebibliography}{99} -\bibitem{LS86} Lanin, V. and Shasha, D.：A Symmetric Concurrent B-Tree -Algorithm, -Proc.\ 1986 Fall Joint Computer Conference, IEEE, 1986, pp.~380--389． - -\bibitem{ST85} Sleator, D. D. and Tarjan, R. E.：Self-Adjusting Binary Search -Trees, {\it J. ACM}, Vol.~32, No.~3 (1985), pp.~652--686． +\bibitem{K} Ken Thompson : Regular Expression Search Algorithm, 1968 -\bibitem{S89} Shapiro E.：The Family of Concurrent Logic Programming Languages. -{\it ACM Computing Surveys}, Vol.~21, No.~3 (1989), pp.~413--510． +\bibitem{R1} Russ Cox : Regular Expression Matching Can Be Simple And + Fast, 2007 +\bibitem{R2} Russ Cox : Regular Expression Matching: the Virtual Machine + Approach, 2009 +\bibitem{R3} Russ Cox : Regular Expression Matching in the Wild, 2010 -\bibitem{T85} Tarjan, R. E.：Amortized Computational Complexity, {\it -SIAM J.\ Alg.\ Disc.\ Math.}, Vol.~6, No.~2 (1985), pp.~306--318. +\bibitem{H} 長谷川 勇 : 国際正規表現ライブラリの開発 -\bibitem{W90} 和田久美子：スプレイ木の並列データ探索, Proc.\ KL1 -Programming Workshop '90, Tokyo, ICOT, 1990, pp.~42--49． \end{thebibliography} \end{adjustvboxheight} % needed only when Appendix follows -\appendix -\section{付録: \LaTeX による論文作成のガイド} - -ここに，以前の \verb|sample.tex| では，論文作成のガイドがあったが， -その内容は \verb|guide.tex| に移動した． - \end{document}