正規表現改善報告する回 / Regexp memoization progress report

RubyKaigi 2023 follow up( https://rhc.connpass.com/event/288535/) での発表資料です。

Transcript

1. ౻࿘େ໻
   !NBLF@OPX@KVTU
   
   
   ౔
   !
   3VCZ,BJHJ
   
   GPMMPX
   VQ ਖ਼نදݱվળใࠂ͢Δճ
2. લճͷ͋Β͢͡  IUUQTSVCZLBJHJPSHQSFTFOUBUJPOTNBLFOPXKVTUIUNMEBZ
3. લճͷ͋Β͢͡  ਖ਼نදݱϚονϯάΛΊͬͪΌ଎ͨ͘͠
4. લճͷ͋Β͢͡  ͔͠͠ɺਖ਼نදݱ͕଎͘ͳΔͨΊʹ͸੍͍͔ͭ͘໿͕
5. લճͷ͋Β͢͡  ੍໿ϑϦʔͳੈքΛΊͯ͟͠ ό Ϧ Ξ
6. ੍໿
   #FGPSF w ͜ΕΒͷػೳΛ࢖͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ 
 ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)
   ʮΞτϛοΫάϧʔϓʯ
   (?>foo) 
 ʮ৚݅෼ذʯ
   (?(<x>)yes|no)
   ʮඇแؚԋࢉࢠʯ
   (?~foo) 
 ʮޙํࢀরʯ
   (foo)\1 ʮ෦෼ࣜͷݺͼग़͠ʯ
   (?<x>foo)\g<x>
   w ͦͷଞɺಾͷ੍໿ͨͪ 
 ճ਺ࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍
   (fo{1,23}){42} 
 ۭจࣈྻʹϚον͢Δ͔΋͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ 
7. w ͜ΕΒͷػೳΛ࢖͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ 
 ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)
   ʮΞτϛοΫάϧʔϓʯ
   (?>foo) 
 ʮ৚݅෼ذʯ
   (?(<x>)yes|no)
   ʮඇแؚԋࢉࢠʯ
   (?~foo) 
 ʮޙํࢀরʯ
   (foo)\1 ʮ෦෼ࣜͷݺͼग़͠ʯ
   (?<x>foo)\g<x>
   w ͦͷଞɺಾͷ੍໿ͨͪ 
 ճ਺ࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍
   (fo{1,23}){42} 
 ۭจࣈྻʹϚον͢Δ͔΋͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍໿
   "GUFS 
8. w ͜ΕΒͷػೳΛ࢖͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ 
 ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)
   ʮΞτϛοΫάϧʔϓʯ
   (?>foo) 
 ʮ৚݅෼ذʯ
   (?(<x>)yes|no)
   ʮඇแؚԋࢉࢠʯ
   (?~foo) 
 ʮޙํࢀরʯ
   (foo)\1 ʮ෦෼ࣜͷݺͼग़͠ʯ
   (?<x>foo)\g<x>
   w ͦͷଞɺಾͷ੍໿ͨͪ 
 ճ਺ࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍
   (fo{1,23}){42} 
 ۭจࣈྻʹϚον͢Δ͔΋͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍໿
   "GUFS  ඍົʁ
9. w ͜ΕΒͷػೳΛ࢖͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ 
 ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)
   ʮΞτϛοΫάϧʔϓʯ
   (?>foo) 
 ʮ৚݅෼ذʯ
   (?(<x>)yes|no)
   ʮඇแؚԋࢉࢠʯ
   (?~foo) 
 ʮޙํࢀরʯ
   (foo)\1 ʮ෦෼ࣜͷݺͼग़͠ʯ
   (?<x>foo)\g<x>
   w ͦͷଞɺಾͷ੍໿ͨͪ 
 ճ਺ࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍
   (fo{1,23}){42} 
 ۭจࣈྻʹϚον͢Δ͔΋͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍໿
   "GUFS  ཧ࿦తʹແཧ ͋·Γ࢖ΘΕͯͳ͍
10. w ͜ΕΒͷػೳΛ࢖͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ 
 ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)
    ʮΞτϛοΫάϧʔϓʯ
    (?>foo) 
 ʮ৚݅෼ذʯ
    (?(<x>)yes|no)
    ʮඇแؚԋࢉࢠʯ
    (?~foo) 
 ʮޙํࢀরʯ
    (foo)\1 ʮ෦෼ࣜͷݺͼग़͠ʯ
    (?<x>foo)\g<x>
    w ͦͷଞɺಾͷ੍໿ͨͪ 
 ճ਺ࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍
    (fo{1,23}){42} 
 ۭจࣈྻʹϚον͢Δ͔΋͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍໿
    "GUFS  ཧ࿦తʹແཧ ͋·Γ࢖ΘΕͯͳ͍ ͦΜͳʹ
    ѱ͘ͳ͍ʁ
11. ͜Ε·ͰͷϝϞԽ w ී௨ͷਖ਼نදݱͷ৔߹ɺ 
 ʮ͋Δঢ়ଶʹ͋ΔҐஔ͔ΒͷϚονͰࣦഊͨ͠ʯͱ͍͏৘ใΛه࿥͢Ε͹0,
    w ϝϞԽςʔϒϧͷܕ 
 memo: (State, Int) -> (NoMemo | Failure) w ઌಡΈɾޙಡΈ͕͋Δ৔߹ɺΞτϛοΫάϧʔϓ͕͋Δ৔߹͸ʁ 
12. ઌಡΈɾޙಡΈͷϝϞԽ w ઌಡΈɾޙಡΈ෦෼͸Ϛονϯάࣦഊ͍ͯ͠ͳͯ͘΋ɺ 
 ʮ͋Δঢ়ଶɾ͋ΔҐஔʯʹ΋͏Ұ౓౸ୡ͢ΔՄೳੑ͕͋Δ 
 ྫ
    /a*?(?=a*)z/
    w ʮઌಡΈɾޙಡΈ෦෼ͷϚονϯάʹ੒ޭͨ͠ʯͱ͍͏৘ใΛ 
 ϝϞԽςʔϒϧʹه࿥͢Δඞཁ͕͋Δ
    w ϝϞԽςʔϒϧͷܕ 
 memo: (State, Int) -> (NoMemo | Success | Failure) 
13. ΞτϛοΫά ϧʔϓͷϝϞԽ w ΞτϛοΫά ϧʔϓͷ৔߹ɺ 
 ΞτϛοΫά ϧʔϓͷதͰͷࣦഊͱɺ֎ଆͰͷࣦഊΛ۠ผ͠ͳ͚Ε͹͍͚ͳ͍ ֎ଆͰࣦഊͨ͠৔߹ɺΞτϛοΫά ϧʔϓͷதͷόοΫτϥοΫ͸ 

    লུ͠ͳ͚Ε͹͍͚ͳ͍
    w ϝϞԽςʔϒϧͷܕ 
 memo: (State, Int) -> 
 (NoMemo | Success | AtomicFailure | Failure) 
14. ࣮૷ͷमਖ਼఺ w ࣮ࡍͷϝϞԽςʔϒϧ͸CJU഑ྻͳͷͰɺ 
 ઌಡΈɾޙಡΈɾΞτϛοΫά ϧʔϓ಺ͷঢ়ଶʹରͯ͠͸ 
 CJU࢖ͬͯϝϞԽ͢ΔΑ͏ʹͨ͠
    w ͜Ε·Ͱ͸ʮ͋Δঢ়ଶʹ͋ΔҐஔͰ౸ୡͨ͠ʯͱ͍͏৘ใΛه࿥͍͕ͯͨ͠ɺ 
 ʮ͋Δঢ়ଶʹ͋ΔҐஔ͔ΒͷϚονʹࣦഊͨ͠ʯͱ͍͏৘ใʹ͢ΔͨΊɺ 
 όοΫτϥοΫதʹϝϞԽςʔϒϧΛߋ৽͢ΔΑ͏ʹͨ͠  IUUQTHJUIVCDPNSVCZSVCZQVMM
15. ݱࡏͷ੍໿ w ͜ΕΒͷػೳΛ࢖͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ 
 ʮ৚݅෼ذʯ
    (?(<x>)yes|no)
    ʮඇแؚԋࢉࢠʯ
    (?~foo) 
 ʮޙํࢀরʯ
    (foo)\1 ʮ෦෼ࣜͷݺͼग़͠ʯ
    (?<x>foo)\g<x>
    w ͦͷଞɺಾͷ੍໿ͨͪ 
 ճ਺ࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍
    (fo{1,23}){42} 
 ઌಡΈɾޙಡΈͱΞτϛοΫά ϧʔϓ͕ωετͰ͖ͳ͍ 
 ઌಡΈɾޙಡΈɾΞτϛοΫά ϧʔϓͷதͰΩϟϓνϟ͸࢖͑ͳ͍ 
16. ΏΔ΅ w ੍໿ʹ͔͔Βͳ͍͔Ͳ͏͔Λ
    Regexp.linear_time?
    ͰνΣοΫͰ͖·͢
    w ͜ΕΛ࢖ͬͯɺϓϩάϥϜதͷਖ਼نදݱ੍͕໿ʹ͔͔Βͳ͍͔νΣοΫ͢Δ 
 3VCPDPQ
    ϓϥάΠϯΛ࡞ͬͯɺϝϯςφϯεͯ͘͠ΕΔਓΛืू͍ͯ͠·͢  SVCZKQ
    4MBDLͷSFHFYQνϟϯωϧʹͯ