PHPで学ぶVM型正規表現エンジンの仕組み

PHPカンファレンス福岡での発表資料です。

Transcript

1. 
   1)1ΧϯϑΝϨϯε෱Ԭ
    1)1ͰֶͿԾ૝Ϛγϯܕ
   ਖ਼نදݱΤϯδϯͷ࢓૊Έ
2. ࣗݾ঺հ ‣ ٱอాޫଇ
   
   !BOBUPP
   
   ‣ 6*69σβΠφʔɺ
 ιϑτ΢ΣΞΤϯδχΞ
   ‣ "TQFDUJWF
   --$
   ୅ද
   ‣ IUUQBTQFDUJWFJP
3. ࠓ೔࿩͢͜ͱ
   ‣ Ծ૝Ϛγϯܕਖ਼نදݱΤϯδϯͷ࢓૊Έ
4. ॱʹ࿩͍ͯ͘͜͠ͱ ‣ ਖ਼نදݱΤϯδϯͷ࣮૷ํ๏
   ‣ Ծ૝Ϛγϯܕਖ਼نදݱΤϯδϯͱ͸
   ‣ ϚονϯάॲཧͷྲྀΕ
   ‣ 7.ͷ࣋ͭϨδελͱεϨουͱ໋ྩ
   ‣ ਖ਼نදݱ͸ͲͷΑ͏ʹίϯύΠϧ͞ΕΔ͔
5. ࠓ೔ͷ࿩Λฉ͘ͱͲ͏ͳΔ͔ ‣ ਖ਼نදݱΤϯδϯͷ࢓૊Έͬͯ͜Μͳʹ୯७ͳͷ͔
 ͬͯͼͬ͘Γ͠·͢ ࢲ͸ͼͬ͘Γ͠·ͨ͠
   ‣ ਖ਼نදݱΤϯδϯ ͷ7. ͕ॻ͚ΔΑ͏ʹͳΓ·͢
6. ਖ਼نදݱΤϯδϯͷ
   ࣮૷ํ๏
7. ‣ ͦ΋ͦ΋ਖ਼نදݱΤϯδϯͷ
 ࣮૷ํ๏ʹ͸ͳʹ͕͋Δ
8. ͭʹେผ ‣ %'"ϕʔεͷ࣮૷ํ๏
   ‣ Ծ૝Ϛγϯ 7. ϕʔεͷ࣮૷ํ๏
9. Ծ૝Ϛγϯϕʔεͷ
 ਖ਼نදݱΤϯδϯͱ͸
10. Ծ૝Ϛγϯϕʔεͷ࣮૷ VM ‣ ਖ਼نදݱ༻ͷ໋ྩΛ࣋ͭ7. Ծ૝Ϛγϯ Λߏங
    ‣ ਖ਼نදݱΛ7.޲͚ͷ໋ྩʹίϯύΠϧ࣮ͯ͠ߦ
    ‣ 1$3&ͷ࣮૷͸͜Ε
11. ϚονϯάॲཧͷྲྀΕ  ਖ਼نදݱΛύʔε
     Ծ૝Ϛγϯ༻ͷ໋ྩྻʹม׵
     Ծ૝ϚγϯͰ࣮ߦ /(hoge|fuga)/ match “hoge”?
12. 
    ਖ਼نදݱΛύʔε ‣ ਖ਼نදݱͷจࣈྻΛड͚औͬͯϝλจࣈΛύʔε /hoge?|fuga(piyo)*/ /hoge?|fuga(piyo)*/
13. 
    7.༻ͷ໋ྩྻʹม׵ char ‘h’ char ‘o’ char ‘g’ char ‘e’ split 1, 6 jmp 11 a(piyo)*/
14. 
    Ծ૝ϚγϯͰ࣮ߦ VM char ‘h’ char ‘o’ char ‘g’ char ‘e’ split 1, 6 jmp 11 ্͔Β
    ໋ྩղऍ
    ͍ͯ͘͠ ‣ ݁Ռ༩͑ΒΕͨจࣈྻ͕Ϛον͢Δ͔Λ൑ఆ
15. ͦ΋ͦ΋Ծ૝Ϛγϯ 7.
    ͬͯͳʹ
16. ීஈΑ͘ݟ͔͚Δ7. ‣ ࣮ࡍͷίϯϐϡʔλΛԾ૝Խͨ͠΋ͷ
    ‣ ࠓճͷ࿩ͱ͸͋·Γؔ܎͋Γ·ͤΜ
17. ࠓճͷ࿩ͷ7. ‣ ಛఆͷ໨తͷͨΊʹઃܭ͞ΕͨԾ૝తͳϚγϯ
    ‣ ྫ
    +7.
    ;FOE
    &OHJOF
    :"37 VM
18. 7.ͷجຊߏ଄͸γϯϓϧ Ϩδελ͕छྨ
    εϨου
    ໋ྩ͕छྨ
19. Ϩδελ PC SP จࣈྻͷݱࡏҐஔ
    4USJOH
    1PJOUFS ໋ྩͷҐஔ
    1SPHSBN
    $PVOUFS ‣ 7.ʹͦͳΘΔม਺ηοτ
    ‣ ࠷ॳ͸ͲͪΒʹ΋͕ೖ͍ͬͯΔ
20. 1$ʹ͕ೖ͍ͬͯͨΒ ‣ ൪໨ͷ໋ྩΛࠓݟ͍ͯΔͱ͍͏͜ͱ
    ‣ ໋ྩΛಡΈ͜Ή͝ͱʹΠϯΫϦϝϯτ͢Δ PC=3 char ‘h’ char ‘o’ char ‘g’ char ‘e’ split 1, 6 jmp 11
21. 41ʹ͕ೖ͍ͬͯͨΒ ‣ ࢼߦ͢Δจࣈྻͷ൪໨ͷจࣈΛࠓݟ͍ͯΔͱ͍͏ ͜ͱ SP=2 “hogehoge”
22. εϨου ‣ εϨου͸Ϩδελ 1$ͱ41 Λ࣋ͭ
    ‣ ࣮ߦ࣌ͷίϯςΩετΈ͍ͨͳ΋ͷ
    ‣ ฒྻॲཧͱ͸ؔ܎ͳ͍ Thread PC SP
23. 7.ͷ࠷ॳͷঢ়ଶ ‣ 7.͸࠷ॳ͸Ұ͚ͭͩεϨουΛ࣋ͬͯ࢝·Δ
    ‣ ໋ྩΛղऍ͢Δ͏ͪʹ૿ݮ͢Δ Thread VM ݱࡏͷεϨου
24. 7.ͱεϨου ‣ 7.͸εϨουΛελοΫ͢Δ
    ‣ 7.͸Ұ൪্ͷεϨουͷϨδελΛૢ࡞͢Δ Thread Thread Thread VM ݱࡏͷεϨου
25. 7.ʹඋΘΔͭͷ໋ྩ ‣ KNQ໋ྩ
    
    ࢦఆ͢ΔҐஔ΁δϟϯϓ
    ‣ DIBS໋ྩ
    
    จࣈͷϚονΛࢼߦ͢Δ
    ‣ NBUDI໋ྩ
    
    7.ΛࢭΊͯϚον׬ྃ͢Δ
    ‣ TQMJU໋ྩ
    
    εϨουΛ෼ׂ͢Δ
26. KNQ໋ྩ ‣ KNQ
    Y
    ͸
    Y
    ͷҐஔʹ
    1$
    Λઃఆ͢Δ
    ‣ ཁ͢ΔʹHPUP jmp x
27. ਤ PC=0 SP=0 PC=5 SP=0 jmp 5 ‣ 1$Ϩδελ͕ॻ͖׵Θ͍ͬͯΔ
28. DIBS໋ྩ ‣ ݱࡏҐஔ 41 ͔Β
    Y
    ͱ͍͏จࣈΛফඅ͢Δ
    ‣ Ϛονͨ͠Β41͕̍ͭ૿͑Δ
    ‣ Ϛον͠ͳ͔ͬͨΒݱࡏͷεϨου͸ফ͑Δ char x
29. ਤ ‣ ࢼߦ͍ͯ͠Δจࣈྻ͕zBBzͷͱ͖
    ‣ DIBS໋ྩΛ࣮ߦ͢Δͱ41  ൪໨ͷจࣈͱൺֱͯ͠
 Ϛον͢ΔͷͰ41ͱ1$͕૿͑Δ PC=0 SP=0 PC=1 SP=1 char ‘a’
30. ਤ ‣ ࢼߦ͍ͯ͠Δจࣈྻ͕zCCzͷͱ͖
    ‣ DIBS໋ྩΛ࣮ߦ͢Δͱ41  ൪໨ͷจࣈͱൺֱͯ͠
 Ϛον͠ͳ͍ͷͰݱࡏͷεϨου͕ফ͑Δ PC=0 SP=0 char ‘a’
31. εϨου͕ফ͑ΔͱͲ͏ͳΔ ‣ ελοΫͷҰ൪্ͷεϨου͕ݱࡏͷ
 εϨουʹͳ໋ͬͯྩͷॲཧ͕࢝·Δ
    ‣ ελοΫ͕ۭʹͳͬͨΒ7.͸ఀࢭ
    
    Ϛονࣦഊ Thread Thread VM
32. NBUDI໋ྩ ‣ ਖ਼نදݱͷϚον͕׬ྃͨ͠ͱͯ͠
 7.ͷ࣮ߦΛࢭΊΔ Ϛον੒ޭ match
33. TQMJU໋ྩ ‣ ݱࡏͷεϨουΛ෼ׂͯ͠ɺ
 ͦΕͧΕͷεϨουͷ
    1$
    ʹ
    Y
    ͱ
    Z
    Λ୅ೖ͢Δ
    ‣ ͪΐͬͱΘ͔ΓͮΒ͍͚ͲҰେࣄͳ໋ྩ split x, y
34. ਤ PC=0 SP=2 PC=1 SP=2 split 1,5 PC=5 SP=2 ‣ ෳ੡͕ऴΘͬͨΒ্ͷεϨου͕ݱࡏͷεϨουʹͳΔ
35. ‣ Ҏ্͜Ε͚ͩɻ
    ‣ ਖ਼نදݱͷେ൒͸͜ΕͰදݱՄೳ
36. ਖ਼نදݱ͸Ͳ͏
 ίϯύΠϧ͞ΕΔ͔
37. ‣ ͲΜͳ෩ʹίϯύΠϧ͞ΕΔ͔঺հ
    ‣ ࠓ͔Βਖ਼نදݱͷਓؒ7.ʹͳͬͯ
 ҰݸҰݸ໋ྩΛղऍ͍͖ͯ͠·͠ΐ͏
38. B 0 char ‘a’ 1 match ‣ ؆୯
39. BCD 0 char ‘a’ 1 char ‘b’ 2 char ‘c’ 3 match ‣ ͜Ε΋؆୯
40.  " # 
    ࿈݁ ‣ ໋ྩྻΛ୯७ʹܨ͛ΒΕΔ
    ‣ ࠷ޙʹNBUDI໋ྩΛஔ͘ match " ͷ໋ྩྻ # ͷ໋ྩྻ
41. B 
    Φϓγϣϯ 0 split 1,2 1 char ‘a’ 2 match ‣ DIBS
    bB`ͷͱ͜Ζʹ͸͸ଞͷਖ਼نදݱͷ໋ྩྻ͕ೖΕΒΕΔ
    ‣ TQMJU໋ྩ͕؊ɻҰݸҰݸ௥͍ͬͯ͜͏
42. ͋͞ਓؒ7.ʹͳΖ͏ Thread PC SP Execution T1 0 split 1,2 aaa T2(PC=2)࡞੒ T1 1 char ‘a’ aaa Ϛον͢ΔͷͰSPΛ૿΍͢ T1 2 match aaa Ϛον׬ྃ ‣ จࣈྻ͕zBBBzͩͬͨ৔߹5ͰϚον׬ྃ
43. จࣈྻ͕zCCCzͩͬͨΒ Thread PC SP Execution T1 0 split 1,2 bbb T2(PC=2)࡞੒ T1 1 char ‘a’ bbb จࣈϚονࣦഊ: T1ফ͑Δ T2 2 match bbb Ϛον׬ྃ ‣ 5Ͱ͸จࣈϚονࣦഊ͢Δ͕5ͰNBUDI͕࣮ߦ͞ΕΔ
    ‣ ݁ՌϚον੒ޭ
44. BcC
    બ୒ 0 split 1,3 1 char ‘a’ 2 jmp 4 3 char ‘b’ 4 match ‣ DIBS
    bB`
    DIBS
    bC`ͷͱ͜Ζʹ͸͸೚ҙͷਖ਼نදݱͷ໋ ྩྻ͕ೖΕΒΕΔ
45. B 
    ݸҎ্܁Γฦ͠ 0 char ‘a’ 1 split 0, 2 2 match ‣ ܁Γฦ͠ͷϚονʹ΋TQMJU໋ྩ͕׆༂
    ‣ DIBS
    bB`ͷͱ͜Ζʹ͸೚ҙͷ໋ྩྻΛೖΕΒΕΔ
46. B 
    ݸҎ্܁Γฦ͠ 0 split 1,3 1 char ‘a’ 2 jmp 0 3 match ‣ DIBS
    bB`ͷͱ͜Ζʹ͸ʜ ҎԼུ
47. B 
    ඇᩦཉͳݸҎ্܁Γฦ͠ 0 split 3,1 1 char ‘a’ 2 jmp 0 3 match ‣ TQMJUͷҾ਺͕ٯʹͳͬͯΔ
48. 1)1Ͱ࣮૷ͯ͠ΈͨΒ ‣ 7.͚ͩͩͱߦ͙Β͍Ͱ࣮૷Ͱ͖ͨ
    ‣ IUUQCMPHBTJBMDPKQ
    ʹίʔυΛܝࡌ
    ‣ ؆୯ͳͷͰ࢓૊Έ͕Θ͔Ε͹୭Ͱ΋ॻ͚Δʂ
49. ·ͱΊ
50. ·ͱΊ ‣ ਖ਼نදݱΤϯδϯͷ࣮૷๏͸%'"࢖͏΍Γํͱ
 7.࢖͏΍Γํͷೋछྨʹେผ
    ‣ 7.ܕਖ਼نදݱΤϯδϯͷجຊ͸ࢸͬͯγϯϓϧ
    ‣ ໋ྩͭɺεϨουɺϨδελ͚ͭͩ
    ‣ γϯϓϧ͚ͩͲਖ਼نදݱΛ΄ͱΜͲදݱͰ͖Δ
    ‣ ࣮૷͕؆୯ͳͷͰॻ͍ͯΈΑ͏
51. ࠓճͷ࿩ͷݩωλ ‣ 3FHVMBS
    &YQSFTTJPO
    .BUDIJOH
    UIF
    7JSUVBM
    .BDIJOF
    "QQSPBDIͱ͍͏จॻ
    ‣ IUUQTXUDIDPNdSTDSFHFYQSFHFYQIUNM
    ‣ 7.ܕਖ਼نදݱΤϯδϯͷ࢓૊Έͱ
 ࣮૷ʹ͍ͭͯղઆ͞Ε͍ͯΔ
    ‣ ฏқͰΘ͔Γ΍͍͢ʂ
52. ͝ਗ਼ௌ͋Γ͕ͱ͏͍͟͝·ͨ͠ !BOBUPP
    CMPHBOBUPPKQ