Vol.2018-SE-199 No.27
2018/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportߏจఆٛ‫ه‬ड़Λ༻͍ͨଟ‫ޠݴ‬ରԠίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͷ։ൃ੉ଜ ༤Ұ1,a)٢ా ଇ༟2ቐ Ըಬ3

Ҫ্ ࠀ࿠1֓ཁɿࣈ۟୯ҐͷίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͰ͋Δ CCFinder ͸ɼର৅ͷιʔείʔυͷࣈ۟ղੳΛߦͬ
͍ͯΔɽCCFinder ʹରԠ͢Δ‫ޠݴ‬Λ૿΍͢ʹ͸ͦͷ‫ޠݴ‬ͷࣈ۟ղੳΛ࣮૷͢Δඞཁ͕͋Δ͕ɼଟ͘ͷ‫ݴ‬‫ʹޠ‬ରͯ͠ 1 ͭͣͭࣈ۟ղੳΛ࣮૷͢Δͷ͸ɼίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͷ։ൃऀʹ֤‫΁ޠݴ‬ͷཧղ͕‫ٻ‬ΊΒΕɼखؒͷ͔͔Δ࡞‫͋Ͱۀ‬ΔɽίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͷ࢖༻ऀ͕ɼ৽ͨͳ‫ʹޠݴ‬༰қʹରԠͰ͖Δ࢓૊ΈΛ࡞Δ͜ͱͰɼ։ൃऀͷ࿑ྗΛ‫ݮ‬Β͢͜ͱ͕Ͱ͖Δɽຊ‫Ͱڀݚ‬͸ίʔυΫϩʔϯ‫ݕ‬ग़ʹ͓͚Δࣈ
۟ղੳʹඞཁͳ৘ใΛɼߏจղੳ‫ث‬ੜ੒‫ܥ‬ͷߏจఆٛϑΝΠϧ͔Βࣗಈతʹநग़͢Δख๏ΛఏҊ͢Δɽͦ
ͯ͠ɼͦͷख๏Λ༻͍ͯߏจఆٛ‫ه‬ड़ղੳϞδϡʔϧΛ։ൃ͠ɼ‫ط‬ଘͷίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͰ͋Δ
CCFinderSW ʹࣈ۟ղੳ৘ใΛ༩͑Δ͜ͱͰɼଟ‫ޠݴ‬ͷίʔυΫϩʔϯ‫ݕ‬ग़Λߦ͏࢓૊ΈΛ։ൃͨ͠ɽద
༻࣮‫Ͱݧ‬͸ɼߏจղੳ‫ث‬ੜ੒‫ܥ‬ͷ 1 ͭͰ͋Δ ANTLR ͷߏจఆٛϑΝΠϧ͔Βɼϓϩάϥϛϯά‫ޠݴ‬ͷίϝϯτ‫ه‬๏ͱ༧໿‫ޠ‬Λநग़͠ɼCCFinderSW Λ༻͍ͯίʔυΫϩʔϯ‫ݕ‬ग़Λߦ͍ɼఏҊख๏ͷ༗ޮੑΛ֬ೝͨ͠ɽΩʔϫʔυɿίʔυΫϩʔϯɼࣈ۟ղੳɼANTLR

A Tool for Multilingual Detection of Code Clones
Using Syntax Deﬁnitions
Yuichi Semura1,a)Norihiro Yoshida2

1. ͸͡Ίʹ

Eunjong Choi3

Katsuro Inoue1

ย·ͨ͸Ұக·ͨ͸ྨࣅ͢Δ͢΂ͯͷՕॴʹରͯ͠ಉҰͷमਖ਼Λߦ͏͔‫ݕ‬౼͢Δඞཁ͕͋Δ [4]ɽ͕ͨͬͯ͠ɼ։ൃ

ίʔυΫϩʔϯͱ͸ɼιʔείʔυதʹଘࡏ͢Δ‫ʹ͍ޓ‬ऀ͸ίʔυΫϩʔϯʹؔ͢Δ৘ใΛೝ͓ࣝͯ͘͠ඞཁ͕͋

Ұகɼ·ͨ͸ྨࣅͨ͠ίʔυยΛࢦ͠ɼओʹ‫ط‬ଘͷίʔυ

Δ͕ɼେ‫ن‬໛ͳιϑτ΢ΣΞʹ͓͍ͯ͸ɼίʔυΫϩʔϯยͷίϐʔΞϯυϖʔετʹΑͬͯੜ੒͞ΕΔ [3]ɽҰൠʹ͋ͨΔՕॴ͕๲େͳ਺ʹͳΔ͜ͱʹΑΓɼͦͷશͯΛೝతʹίʔυΫϩʔϯͷଘࡏ͸ɼιϑτ΢ΣΞอकΛࠔ೉ʹ͓ࣝͯ͘͜͠ͱ͸‫࣮ݱ‬తͰͳ͍ɽͦ͜Ͱɼ։ൃऀΛࢧԉ͍ͯ͢͠Δେ͖ͳཁҼͷ 1 ͭͱͯ͠‫͛ڍ‬ΒΕ͍ͯΔɽ͋Δ

ΔͨΊʹίʔυΫϩʔϯ‫ݕ‬ग़πʔϧ͕ఏҊ͞Ε͍ͯΔ [2]ɽίʔυยʹόά͕‫͔ͨͬͭݟ‬৔߹ɼͦͷίʔυยͷίʔυίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͷ 1 ͭͰ͋Δ CCFinder ͸ɼΫϩʔϯʹ΋όά͕‫·ؚ‬ΕΔՄೳੑ͕ߴ͍ɽͦͷͨΊɼ։

CɼC++ɼJavaɼCOBOLɼFortran ͷ‫͔ॻͰޠݴ‬Εͨιʔൃऀ͸͋Δίʔυยʹόά͕‫͔ͨͬͭݟ‬৔߹ɼͦͷίʔυείʔυ͔ΒίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δ͜ͱ͕ՄೳͰ͋Δ

1[6]ɽCCFinder Ͱ͸ࣈ۟୯ҐͷίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δ

2
3
a)

େࡕେֶ
Osaka University໊‫ݹ‬԰େֶ
Nagoya Universityಸྑઌ୺Պֶٕज़େֶӃେֶ
Nara Institute of Science and Technology
y-semura@ist.osaka-u.ac.jp

c 2018 Information Processing Society of JapanͨΊͷલॲཧͱͯ͠ɼιʔείʔυΛ‫ޠݴ‬ͷจ๏ʹԊͬͯࣈ۟୯Ґʹ෼ׂ͍ͯ͠Δɽ͜ͷॲཧ͸Ұൠతʹࣈ۟ղੳͱ
‫ݺ‬͹ΕΔ [13]ɽ·ͨ CCFinderX ͸ɼCCFinder ͷόʔδϣϯΞοϓͱͯ͠։ൃ͞ΕͨίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͰ͋1Vol.2018-SE-199 No.27
2018/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical ReportΓɼࣈ۟ղੳ෦ͷϢʔβʹΑΔมߋΛՄೳʹ͍ͯ͠Δ*1 ɽٛ‫ه‬ड़ղੳϞδϡʔϧΛ༻͍ͨίϝϯτͱ༧໿‫ޠ‬ͷநग़࣮͜Ε͸ίʔυΫϩʔϯ‫ݕ‬ग़Λߦ͍͍ͨ‫ʹޠݴ‬ରԠ͢Δࣈ‫ͱݧ‬ɼίʔυΫϩʔϯ‫ݕ‬ग़࣮‫ه͍ͯͭʹݧ‬ड़͢Δɽ6 ষͰ۟ղੳ෦ΛϢʔβ͕༻ҙ͢Δ͜ͱͰɼͦͷ‫ޠݴ‬ͷίʔυΫ

͸·ͱΊͱࠓ‫ޙ‬ͷ՝୊ʹ͍ͭͯड़΂Δɽϩʔϯ‫ݕ‬ग़͕ՄೳʹͳΔͱ͍͏͜ͱΛҙຯ͢Δɽ͔͠͠ɼ
͕ඞཁͰ͋ΔͨΊɼࣈ۟ղੳ෦ͷ࣮૷͸खؒͷ͔͔Δ࡞‫ۀ‬

2. ί ʔ υ Ϋ ϩ ʔ ϯ ‫ ݕ‬ग़ π ʔ ϧ:CCFinderX/CCFinderSW

Ͱ͋Δɽ͜ͷΑ͏ͳ৔߹ʹɼଟ͘ͷ‫ʹޠݴ‬ରԠͰ͖Δ؆୯ຊষͰ͸ຊ‫ڀݚ‬ͷഎ‫ͯ͠ͱܠ‬ɼίʔυΫϩʔϯ‫ݕ‬ग़πʔʹ࢓૊ΈΛ࢖͏͜ͱͰɼϢʔβͷखؒΛ‫ݮ‬Β͢͜ͱ͕ग़དྷϧͰ͋Δ CCFinderX ͱ CCFinderSW ʹ͍ͭͯͷઆ໌Λ

Δ [11]ɽ

ߦ͏ɽࣈ۟ղੳ෦Λ༻ҙ͢Δʹ͸ͦͷ‫ޠݴ‬ͷจ๏Λཧղ͢Δ͜ͱ

CCFinderX Ͱ͸ಛఆͷࣈ۟΍ͦͷ૊Έ߹Θͤʹ͍ͭͯɼίʔυΫϩʔϯͱ͸ɼιʔείʔυதʹଘࡏ͢Δ‫ʹ͍ޓ‬ਖ਼‫ن‬ԽॲཧΛߦ͍ͬͯΔɽ͜Ε͸ม਺໊΍ؔ਺໊ͳͲΛશҰகɼ·ͨ͸ྨࣅͨ͠ίʔυยΛࢦ͠ɼओʹ‫ط‬ଘͷίʔυͯಉҰͷࣈ۟ʹஔ͖‫͑׵‬ΔॲཧͰ͋Γɼ࣮༻తʹҙຯͷ͋ยͷίϐʔΞϯυϖʔετʹΑͬͯੜ੒͞ΕΔ [3]ɽҰൠΔίʔυΫϩʔϯ͚ͩΛ‫ݕ‬ग़͢ΔͨΊʹߦΘΕΔɽม਺໊తʹɼ‫ʹ͍ޓ‬ίʔυΫϩʔϯͱͳΔίʔυย͸Ϋϩʔϯϖ΍ؔ਺໊Ͱ࢖༻Ͱ͖Δࣈ۟͸ɺϓϩάϥϛϯά‫ʹޠݴ‬ΑͬΞͱ‫ݺ‬͹ΕΔɽίʔυΫϩʔϯʹීวతͳఆٛ͸ଘࡏ͠ͳͯઃఆ͕ҟͳΔͨΊʹɼ‫ʹޠݴ‬ΑͬͯผͷઃఆΛߦΘͳ͚͍ɽຊ࿦จͰ͸ίʔυΫϩʔϯͷఆٛͱͯ͠ҎԼͷ 2 ͭͷΕ͹ͳΒͳ͍ɽ

λΠϓͷ෼ྨΛ༻͍Δ [10]ɽ

CCFinderSW [12] Ͱ͸ଟ‫ޠݴ‬ͷࣈ۟୯ҐͷίʔυΫϩʔ

λΠϓ 1 ɹϯ‫ݕ‬ग़Λ໨తͱͯ͠ɼϢʔβʹΑͬͯ༰қʹࣈ۟ղੳ෦ͷۭനɼλϒจࣈɼվߦ΍ίϝϯτͳͲΛআ͍ͯҰக͢มߋ͕ՄೳʹͳΔΑ͏ͳࣈ۟ղੳ‫ߏػ‬ΛఏҊ͍ͯ͠ΔɽࣈΔίʔυΫϩʔϯɽ۟ղੳ‫ߏػ‬ͷมߋՕॴΛɼओʹίϝϯτআ‫ڈ‬ͷϧʔϧͱஔ

λΠϓ 2 ɹ͖‫͕͑׵‬ඞཁͳࣈ۟ʹ‫ݶ‬ఆͨ͠ɽ͜ͷ࢓૊ΈʹΑͬͯϢʔ

λΠϓ 1 ͷ৚݅ʹՃ͑ͯɼϦςϥϧɼ‫ܕ‬ɼࣝผࢠΛআβʹΑΔࣈ۟ղੳ෦ͷίʔσΟϯάͷख͕ؒল͔Εɼ৽͍ͨͯҰக͢ΔίʔυΫϩʔϯɽͳ‫΁ޠݴ‬ͷରԠ͕༰қʹͳ͍ͬͯΔɽ
ߏจղੳ‫ث‬ੜ੒‫ܥ‬͸ɼࣈ۟ղੳ‫ث‬΍ߏจղੳ‫ث‬Λࣗಈతʹੜ੒͢ΔϓϩάϥϜͰ͋ΓɼύʔαδΣωϨʔλͱ΋‫ݺ‬͹ΕΔɽߏจղੳ‫ث‬ੜ੒‫ܥ‬͸ɼߏจఆٛ‫ه‬ड़Λ༻͍Δ͜

CCFinderX ͸ɼࣈ۟୯ҐͷίʔυΫϩʔϯΛ‫ݕ‬ग़͢Δ
πʔϧͰ͋ΔɽCCFinderX ͷಛ௃ͱͯ͠ҎԼͷΑ͏ͳ΋ͷ͕‫͛ڍ‬ΒΕΔɽ

• ม਺໊΍ؔ਺໊ͳͲͷࣈ۟ΛಉҰࣈ۟ʹஔ͖‫͑׵‬Δ͜

ͱͰࣈ۟ղੳ‫ث‬ɾߏจղੳ‫ث‬Λੜ੒͢Δ͜ͱ͕Ͱ͖ΔͨͱͰɼλΠϓ 2 ·ͰͷίʔυΫϩʔϯΛ‫ݕ‬ग़Ͱ͖Δɽ

Ίɼࣈ۟ղੳ‫ث‬ͷίʔσΟϯάͷखؒΛল͘͜ͱ͕Ͱ͖

• ਺ඦສߦ‫ن‬໛ͷγεςϜʹ΋࣮༻࣌ؒͰղੳՄೳͰ

Δɽ୅දతͳߏจղੳ‫ث‬ੜ੒‫ʹܥ‬ɼYacc [5] ΍ JavaCC*2 ɼ

ANTLR*3 ͳͲ͕͋Δɽຊ‫Ͱڀݚ‬͸ɼίʔυΫϩʔϯ‫ݕ‬ग़πʔϧΛଟ‫ʹޠݴ‬ରԠ
ͤ͞ΔͨΊʹɼࣈ۟ղੳʹඞཁͳ৘ใΛߏจղੳ‫ث‬ੜ੒‫ܥ‬ͷߏจఆٛϑΝΠϧ͔Βࣗಈతʹநग़͢Δํ๏ΛఏҊ͋͢Δɽ• ‫ޠݴ‬ґଘ෦෼ΛऔΓସ͑Δ͜ͱͰ͞·͟·ͳ‫ʹޠݴ‬ରԠ͍ͯ͠Δɽ

• ͖͍͠஋Λ༩͑Δ͜ͱͰɼࣈ۟਺͕͖͍͠஋ະຬͷίʔυΫϩʔϯΛ‫ݕ‬ग़͠ͳ͍Α͏ʹͰ͖Δɽ

Δɽ·ͨߏจղੳ‫ث‬ੜ੒‫ܥ‬ͷத͔Β ANTLR Λର৅ͱ͠

CCFinderX ͸ɼCCFinder ͷόʔδϣϯΞοϓͱͯ͠։

ͯɼANTLR Ͱ༻͍ΒΕΔߏจఆٛ‫ه‬ड़͔Βϓϩάϥϛϯ

ൃ͞ΕͨίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͰ͋Γɼࣈ۟ղੳ෦ͷά‫ޠݴ‬ͷίϝϯτ‫ه‬๏ͱ༧໿‫ޠ‬Λநग़͠ɼࣈ۟ղੳΛߦ͏ϢʔβʹΑΔมߋΛՄೳʹ͍ͯ͠Δɽ͜Ε͸ίʔυΫϩʔϞδϡʔϧΛ։ൃͨ͠ɽ͜ͷϞδϡʔϧʹΑͬͯग़ྗ͞Εϯ‫ݕ‬ग़Λߦ͍͍ͨ‫ʹޠݴ‬ରԠ͢Δࣈ۟ղੳ෦ΛϢʔβ͕༻ͨࣈ۟ղੳ৘ใΛ༻͍ͯɼCCFinderSW ͰίʔυΫϩʔϯҙ͢Δ͜ͱͰɼͦͷ‫ޠݴ‬ͷίʔυΫϩʔϯ‫ݕ‬ग़͕Մೳʹͳ‫ݕ‬ग़Λߦ͏ɽ

Δͱ͍͏͜ͱΛҙຯ͢Δɽ͔͠͠ɼࣈ۟ղੳ෦Λ༻ҙ͢ΔҎ߱ɼ2 ষͰ͸ຊ‫ڀݚ‬ͷഎ‫ͯ͠ͱܠ‬ɼίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͰ͋Δ CCFinderX ͱ CCFinderSW ͷઆ໌Λߦʹ͸‫ޠݴ‬ͷจ๏Λཧղ͢Δ͜ͱ͕ඞཁͰ͋Γɼࣈ۟ղੳ෦
ͷίʔσΟϯά͸खؒͷ͔͔Δ࡞‫͋Ͱۀ‬Δɽ

͏ɽ3 ষͰ͸ຊ‫Ͱڀݚ‬ର৅ͱͨ͠ߏจղੳ‫ث‬ੜ੒‫ܥ‬ͷ 1 ͭ

CCFinderSW ͸ɼCCFinderX ͱಉ༷ʹࣈ۟୯Ґͷίʔ

Ͱ͋Δ ANTLR ͷߏจఆٛ‫ه‬ड़ͷ‫͍ͯͭʹࣜܗ‬આ໌͠ɼ4υΫϩʔϯΛ‫ݕ‬ग़͢ΔπʔϧͰ͋Δ [12]ɽCCFinderSW ͸ষͰ͸ ANTLR ͷߏจఆٛϑΝΠϧ͔Β৘ใΛநग़͢Δ໾ଟ‫ޠݴ‬ରԠΛߦͬͨίʔυΫϩʔϯ‫ݕ‬ग़πʔϧͰ͋ΓɼࣈׂΛ୲͏Ϟδϡʔϧʹ͍ͭͯઆ໌Λߦ͏ɽ5 ষͰ͸ߏจఆ۟ղੳ෦ʹର৅‫ޠݴ‬ͷίϝϯτϧʔϧͱ༧໿‫ޠ‬Λೖྗ͢

*1
*2
*3

Δ͜ͱͰଟ͘ͷ‫ʹޠݴ‬ॊೈʹରԠͰ͖Δɽ͜ͷ࢓૊Έʹ
http://www.ccﬁnder.net/
https://javacc.org/
http://www.antlr.org/

c 2018 Information Processing Society of JapanΑͬͯϢʔβʹΑΔࣈ۟ղੳ෦ͷίʔσΟϯάͷख͕ؒল2

Vol.2018-SE-199 No.27
2018/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report

2.1 ίϝϯτআ‫ڈ‬䝋䞊䝇䝣䜯䜲䝹

&ŝŶĚĞƌ^t
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000^ƚĞƉϭ

^ƚĞƉϮ

^ƚĞƉϯ

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00Ꮠྃゎᯒ䝁䝯䞁䝖㝖ཤᏐྃศ๭㆑ูᏊุู

CCFinderSW ͷࣈ۟ղੳ෦Ͱ͸ɼ·ͣೖྗ͞Εͨιʔε䝁䝯䞁䝖䝹䞊䝹ண⣙ㄒίʔυ͔ΒίϝϯτΛআ‫͢ڈ‬Δɽ͜Ε͸ίʔυΫϩʔϯͷఆٛʹ‫͍ͯͮج‬ɼίʔυΫϩʔϯʹ͸ίϝϯτ΍ۭന͸‫ؚ‬·Εͳ͍ͨΊͰ͋ΔɽCCFinderSW ͷίϝϯτআ‫ڈ‬෦ͰᏐྃิ͸ɼϢʔβʹΑΔίϝϯτϧʔϧͷೖྗΛඞཁͱ͢Δɽআ

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000‫ڈ‬Մೳͳίϝϯτͷϧʔϧͱͯ͠ɼߦίϝϯτɼෳ਺ߦίኚ᥮ᚋ䛾Ꮠྃิ

ϧʔϧ͕༻ҙ͞Ε͍ͯΔɽϢʔβ͸ͦͷϧʔϧΛ΋ͱʹίኚ᥮ฎ⌮

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

䜽䝻䞊䞁᳨ฟ

ϝϯτɼߦશମίϝϯτɼෳ਺ߦશମίϝϯτͷ 4 छྨͷϝϯτϧʔϧΛ‫ه‬ड़ͨ͠ϑΝΠϧΛ࡞੒͠ɼ࣮ߦ࣌ʹೖྗͱͯͦ͠ͷϑΝΠϧΛ CCFinderSW ʹ༩͑Δɽ

䜽䝻䞊䞁᝟ሗ

^ƚĞƉϰ

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00ฟຊᩚᙧฎ⌮

2.2 ࣈ۟෼ׂ
ίϝϯτআ‫ڈ‬Λߦͬͨ‫ޙ‬͸ࣈ۟෼ׂΛߦ͏ɽࣈ۟෼ׂͰ

䜽䝻䞊䞁䝨䜰᝟ሗਤ 1

CCFinderSW ͷ֓ཁ

Fig. 1 An overview of CCFinderSW࢖ΘΕΔϧʔϧ͸ҎԼͷ௨ΓͰ͋Δɽ൪߸͕খ͍͞ϧʔϧ΄Ͳ༏ઌ͞ΕΔɽ( 1 ) จࣈɼจࣈྻϦςϥϧ͸ 1 ࣈ۟ͱ͢Δɽ
( 2 ) ۭനͱվߦͷલ‫۟ࣈͰޙ‬Λ෼ׂ͢Δɽ
( 3 ) ‫߸ه‬͸ 1 จࣈͣͭͰ෼ׂ͢Δɽ‫͕߸ه‬ෳ਺จࣈͰ 1 ͭͷҙຯΛද͢৔߹Ͱ΋ɼ1 จࣈͰ 1 ࣈ۟ͱ͢Δɽ͔Εɼ৽ͨͳ‫΁ޠݴ‬ͷରԠ͕༰қʹͳ͍ͬͯΔɽ͜͜Ͱɼ

( 4 ) ͦΕҎ֎ͷ࿈ଓͨ͠ӳ਺ࣈྻ͸ 1 ࣈ۟ͱ͢Δɽ

CCFinderSW ͷॲཧ֓ཁʹ͍ͭͯ‫ه‬ड़͢Δɽ4 ͭͷ Stepʹ෼͚ΒΕɼ֤ Step ͷৄࡉΛઆ໌͢Δɽ

Step 1:ࣈ۟ղੳ ɹ

2.3 ࣝผࢠ൑ผɾม‫ॲ׵‬ཧࣝผࢠ൑ผͰ͸ࣈ۟෼ׂͰӳ਺ࣈྻͱͯ͠෼ׂ͞ΕͨιʔείʔυΛϓϩάϥϛϯά‫ޠݴ‬ͷจ๏ʹԊͬͯࣈࣈ͕۟ɼࣝผࢠ͔༧໿‫͔ޠ‬Λ൑ఆ͢Δ΋ͷͰ͋Δɽ͜Ε͸۟ྻʹม‫͢׵‬Δɽͦͷࡍɼۭനͱίϝϯτ͸‫ػ‬ೳʹӨ

Step 2 ͷม‫ॲ׵‬ཧͷͨΊʹߦΘΕΔɽ༧໿‫ޠ‬͸ม਺໊΍ؔ‫͍ͳ͠ڹ‬ͷͰແࢹ͞ΕΔɽࣈ۟ղੳ͸ίϝϯτআ‫ڈ‬ɼ਺໊ʹ࢖༻Ͱ͖ͳ͍จࣈྻͷ͜ͱΛࢦ͠ɼϓϩάϥϛϯά

ࣈ۟෼ׂɼࣝผࢠ൑ผͱ͍ͬͨॲཧ͕ߦΘΕ͍ͯΔɽ

‫ʹޠݴ‬Αͬͯҟͳ͍ͬͯΔɽϢʔβ͸༧໿‫ޠ‬ҰཡΛ‫ه‬ड़͠ೖྗ͞Εͨίϝϯτϧʔϧ͸ίϝϯτআ‫͞༻࢖Ͱڈ‬ͨϑΝΠϧΛ࡞੒͠ɼ࣮ߦ࣌ʹೖྗͱͯͦ͠ͷϑΝΠϧΛ

Εɼ༧໿‫ޠ‬Ұཡ͸ࣝผࢠ൑ผͰ࢖༻͞ΕΔɽ

༩͑Δɽ

Step 2:ม‫ॲ׵‬ཧ ɹม‫ॲ׵‬ཧ͸ɼ࣮༻తʹҙຯͷ͋ΔίʔυΫϩʔϯ͚ͩΛ෼ׂ͞Εͨࣈ۟ྻ͔Β࣮༻తʹҙຯͷ͋ΔίʔυΫ‫ݕ‬ग़͢ΔͨΊʹߦΘΕΔɽ͜Ε͸ࣈ۟ղੳͰࣝผࢠͱ൑ผ

ϩʔϯ͚ͩΛ‫ݕ‬ग़͢ΔͨΊͷม‫׵‬Λߦ͏ɽ͜Ε͸ม਺͞Εͨม਺໊΍ؔ਺໊ͳͲΛɼશͯಉҰͷࣈ۟ʹஔ͖‫͑׵‬໊΍ؔ਺໊ͳͲΛશͯಉҰͷࣈ۟ʹஔ͖‫͑׵‬ΔॲཧͰ

ΔॲཧͰ͋Δɽ͋Δɽ

Step 3:Ϋϩʔϯ‫ݕ‬ग़ ɹ

2.4 CCFinderSW ͷ໰୊఺ม‫͞׵‬Εͨࣈ۟ྻΛɼൺֱ͠ίʔυΫϩʔϯΛ‫ݕ‬ग़͢

CCFinderSW ͸ೖྗͱͯ͠ίϝϯτϧʔϧͱ༧໿‫ޠ‬ͷΔɽ͜ͷൺֱʹ͸ N-gram Λ༻͍ͨΞϧΰϦζϜΛ࠾ೖྗ͕ඞཁͰ͋Δ͕ɼ৽ͨͳ‫ʹޠݴ‬ରԠ͢Δʹ͸ίϝϯτ༻͍ͯ͠Δɽ

ϧʔϧΛ‫ه‬ड़͢ΔϑΝΠϧͱ༧໿‫ޠ‬ͷҰཡΛ‫ه‬ड़͢ΔϑΝ

Step 4:ग़ྗ੔‫ॲܗ‬ཧ ɹ

Πϧͷ 2 ͭΛϢʔβ͕࡞੒͠ͳ͚Ε͹ͳΒͳ͍ɽίϝϯτ࠷‫ʹޙ‬ग़ྗ੔‫ॲܗ‬ཧΛߦ͍ɼ‫ݕ‬ग़͞ΕͨΫϩʔϯϖΞϧʔϧΛ‫ه‬ड़͢ΔϑΝΠϧʹ͸ಠࣗͷจ๏͕ଘࡏ͠ɼϢʔʹ͍ͭͯɼ΋ͱͷιʔείʔυͰͲͷϑΝΠϧʹଘࡏβ͸ͦΕΛཧղ͢Δඞཁ͕͋Δɽ·ͨશͯͷ༧໿‫ޠ‬Λ‫ه‬ड़͢Δ͔ɼߦ൪߸ͱྻ൪߸͕ग़ྗ͞ΕΔɽͨ͠ϑΝΠϧΛ༻ҙ͢Δ͜ͱ͸ඇৗʹखؒͰ͋Δɽ͜ΕΒҎ߱ɼStep 1 ͷৄࡉͱͯ͠ 2.1 અͰίϝϯτআ‫͍ͭʹڈ‬
ͯɼ2.2 અͰࣈ۟෼ׂʹ͍ͭͯͷৄࡉΛઆ໌͢Δɽ2.3 અͰ͸ɼStep 1 ͷࣝผࢠ൑ผͱɾStep 2 ͷม‫ॲ׵‬ཧʹ͍ͭͯ‫ه‬
ड़͢Δɽ2.4 અͰ͸‫ࡏݱ‬ͷ CCFinderSW ͷ໰୊఺ʹ͍ͭͯઆ໌͢Δɽ

c 2018 Information Processing Society of JapanͷϢʔβʹΑΔखؒΛܰ‫ͤ͞ݮ‬ΔͨΊͷ࢓૊Έ͕ඞཁͰ͋Δɽ

3. ߏจղੳ‫ث‬ੜ੒‫ܥ‬ɿANTLRߏจղੳ‫ث‬ੜ੒‫ܥ‬͸ɼࣈ۟ղੳ‫ث‬΍ߏจղੳ‫ث‬Λࣗಈత

3

Vol.2018-SE-199 No.27
2018/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportʹੜ੒͢ΔϓϩάϥϜͰ͋ΓɼύʔαδΣωϨʔλͱ΋‫ݺ‬ද 1͹ΕΔɽߏจղੳ‫ث‬ੜ੒‫ܥ‬͸ɼߏจఆٛ‫ه‬ड़Λ༻͍Δ͜ͱ

Table 1 Main tokens used in ANTLRANTLR Ͱ࢖༻͞ΕΔओཁͳࣈ۟

Ͱࣈ۟ղੳ‫ث‬ɾߏจղੳ‫ث‬Λੜ੒͢Δ͜ͱ͕Ͱ͖ΔͨΊɼࣈ۟ղੳ‫ث‬ͷίʔσΟϯάͷखؒΛল͘͜ͱ͕Ͱ͖Δɽ୅
දతͳߏจղੳ‫ث‬ੜ੒‫ʹܥ‬ɼYacc ΍ JavaCCɼANTLR ͳ
Ͳ͕͋Δɽ

ࣈ۟

‘Ϧςϥϧ’[จࣈू߹]

આ໌จࣈɼ·ͨ͸จࣈྻʹϚον͢Δɽ
ࢦఆ͞ΕͨจࣈͷͲΕ͔ 1 ͭʹϚον͢Δɽa-z ͷΑ͏ʹॻ͘͜ͱͰൣғΛࢦఆ͢Δ͜ͱ΋Մೳɽਖ਼‫ن‬ߏจղੳ‫ث‬ੜ੒‫ܥ‬ͷ 1 ͭͰ͋Δ ANTLR ͸ɼߏจ໦ͷද‫͞༻࢖Ͱݱ‬ΕΔ΋ͷͱಉ༷ɽߏஙɾ୳ࡧ͕Մೳͳߏจղੳ‫ث‬Λੜ੒͢ΔɽTwitter Ͱͷ.

‫ࡧݕ‬ΫΤϦͷղੳʹ͸ ANTLR ͕࠾༻͞ΕΔͳͲ޿͘࢖˜x೚ҙͷҰจࣈʹϚον͢Δx Ͱ‫ه‬ड़͞Ε͍ͯΔू߹ʹϚον͠ͳ͍೚ҙͷҰจࣈʹϚον͢Δɽ x ͸ 1 จࣈͷϦςϥϧ΍จࣈू߹༻͞Ε͍ͯͯ [7]ɼ2018 ೥‫ࡏݱ‬΋։ൃ͕ਐΊΒΕ͍ͯΔͨ

͕ࢦఆ͞ΕΔɽຊߘͰ͸ NOT ԋࢉࢠͱ‫Ϳݺ‬Ίɼର৅ͱͯ͠બ୒ͨ͠ɽANTLR ͕ߏจղੳ‫ث‬Λੜ੒͢ΔλʔήοτͱͳΔ‫ޠݴ‬͸ C++ɼJavaɼPythonɼGo ͳͲ͕͋ΔɽຊষͰ͸ɼຊ‫ڀݚ‬Λߦ͏ʹ͋ͨͬͯඞཁͱͳͬͨ ANTLRx*x ͷ 0 ճҎ্ͷ‫܁‬Γฦ͠ʹϚον͢Δɽ

x?

x ͷ 0 ճɼ·ͨ͸ 1 ճͷग़‫ʹݱ‬Ϛον͢Δɽ

x*?

x ͷ 0 ճҎ্ͷ࠷୹ͷ‫܁‬Γฦ͠ʹϚον͢Δɽ

x|yx ·ͨ͸ y ʹϚον͢Δɽ

ͷߏจఆٛ‫ه‬ड़ͷจ๏ͱɼௐࠪΛߦͬͨϑΝΠϧʹଟ͘࠾༻͞Ε͍ͯͨද‫ํݱ‬๏ʹ͍ͭͯઆ໌͢Δɽ

ANTLR Ͱߏจఆٛ‫ه‬ड़ͷྫͱͯ͠ɼ࢛ଇԋࢉࣜΛද͢ίϚϯυΛࢦఆͯ͠ಛఆͷૢ࡞Λࢪ͢͜ͱ΋Ͱ͖Δɽ

΋ͷΛ‫͢ࡌܝ‬Δɽ·ͣ 1 ߦ໨ʹɼgrammar จ๏໊ͱॻ

ίϚϯυ͸ ϧʔϧ໊ : ϧʔϧϒϩοΫ − >ίϚϯυ; ͷ͘͜ͱͰɼ͜ͷϑΝΠϧ͕ද͢จ๏ͷ໊લΛએ‫͢ݴ‬Δɽ2

Α͏ʹ‫ه‬ड़͢Δɽ ຊߘʹඞཁͳίϚϯυͷछྨ͸ 2 ͭͰ͋ߦ໨Ҏ߱͸จ๏Λߏ੒͢Δϧʔϧʹ͍ͭͯ‫ه‬ड़͍ͯ͠Δɽ

Δɽ1 ͭ໨͸ skip Ͱ͋Δɽskip Λࢦఆ͞Εͨࣈ۟͸ɼࣈ۟

ANTLR ͷจ๏Λఆٛ͢Δϧʔϧʹ͸ɼࣈ۟ղੳϧʔϧͱղੳʹΑͬͯಡΈඈ͹͞ΕΔɽ2 ͭ໨͸ channel ίϚϯυߏจղੳϧʔϧͷ 2 ͕ͭଘࡏ͢Δɽ࢛ଇԋࢉࣜΛද͢ߏจఆٛϑΝΠϧͰ͋Δɽchannel(x) ͷΑ͏ʹ‫ه‬ड़͠ɼx ʹ͸͋Β͔͡Ίఆ ٛ͞Εͨ channel ໊͕ೖΔɽchannel ίϚϯυ͸ࣈ۟Λ͋

grammar Prog;

Δ channel ʹ౉͢ɽྫ͑͹ίϚϯυΛ channel(HIDDEN)

prog: expr;

ͱࢦఆ͢ΔͱɼHIDDEN ʹ౉͢ɽಛʹ channel(HIDDEN)

expr: term ( ( ’+’ | ’-’ ) term )*;͸ skip ͱࣅͨಇ͖Λ͍ͯͯ͠ɼ͜ͷίϚϯυΛࢦఆ͞Εͨ

term: factor ( ( ’*’ | ’/’ ) factor )*;ࣈ۟͸ Parser ʹΑͬͯແࢹ͞ΕΔ [9]ɽfactor: INT | ’(’ expr ’)’;

4. ߏจఆٛ‫ه‬ड़ղੳϞδϡʔϧͷ։ൃ

INT : [0-9]+;
WS: [ \t\r\n]+ -> skip;ຊ‫Ͱڀݚ‬͸ɼࣈ۟ղੳʹඞཁͳ৘ใΛɼߏจղੳ‫ث‬ੜ੒‫ܥ‬ ͷߏจఆٛ‫ه‬ड़ϑΝΠϧ͔Βࣗಈతʹநग़͢Δํ๏ΛఏҊ͢Δɽͦͯ͠ߏจղੳ‫ث‬ੜ੒‫ܥ‬ͷத͔Β ANTLR Λର৅ͱϧʔϧͷ‫ه‬ड़๏͸ɼϧʔϧ໊ : ϧʔϧϒϩοΫ ; ͱͳͯ͠ɼANTLR Ͱ༻͍ΒΕΔߏจఆٛ‫ه‬ड़Λղੳ͠ϓϩάΓɼ͜ͷΑ͏ͳϧʔϧ͕ 1 ͭͷϑΝΠϧʹෳ਺ఆٛ͞ΕΔ
͜ͱͱͳΔɽࣈ۟ղੳϧʔϧͷϧʔϧ໊͸େจࣈ͔Β࢝·ϥϛϯά‫ޠݴ‬ͷίϝϯτ‫ه‬๏ͱ༧໿‫ޠ‬Λநग़͢ΔϞδϡʔΓɼߏจղੳϧʔϧͷϧʔϧ໊͸খจࣈ͔Β࢝·Δɽຊ‫ݚ‬ϧΛ։ൃͨ͠ɽ͜ͷϞδϡʔϧʹΑͬͯग़ྗ͞Εͨࣈ۟ղ‫ߏͰڀ‬จղੳϧʔϧʹ͍ͭͯ͸΄ͱΜͲ࢖༻͠ͳ͍ͨΊɼੳʹඞཁͳ৘ใΛ༻͍ͯɼCCFinderSW ͰίʔυΫϩʔϯຊߘͰ͸ࣈ۟ղੳϧʔϧʹ͓͍ͯͷΈઆ໌͢Δɽ‫ݕ‬ग़Λߦ͏ɽຊষͰ͸৽ͨʹ։ൃͨ͠ߏจఆٛ‫ه‬ड़ղੳ͢ANTLR Ͱ༻͍ΒΕΔࣈ۟ղੳϧʔϧͰͷࣈ۟ද‫ͭʹݱ‬ΔϞδϡʔϧͱ CCFinderSW ͷมߋ఺ʹ͍ͭͯड़΂Δɽ

͍ͯɼANTLR ͷ։ൃऀʹΑΔυΩϡϝϯτ [8] ͕ଘࡏ͢

ਤ 2 ͸৽ͨʹ։ൃΛߦͬͨߏจఆٛ‫ه‬ड़ղੳϞδϡʔϧΔɽͦͷத͔Βຊߘʹඞཁͳ΋ͷΛൈਮ͠ɼද 1 ʹࣔ͠ͱ CCFinderSW ͷؔ܎Λදͨ͠΋ͷͰ͋Δɽຊ‫৽Ͱڀݚ‬ͨɽઌʹ࢛ࣔͨ͠ଇԋࢉࣜΛද͢ϑΝΠϧͷதͰ͸ɼࣈ۟ͨʹ։ൃͨ͠෦෼͸ਤ 2 ͷΦϨϯδ৭ͰϋΠϥΠτ͞Εͨղੳϧʔϧͱͯ͠ ‘INT’ ͱ ‘WS’ ͕ଘࡏ͢Δɽ ‘INT’ ͸਺෦෼Ͱ͋Γɼ‫ط‬ଘͷ CCFinderSW ʹ‫·ؚ‬ΕΔ෦෼͸੨৭ͰࣈྻΛද͍ͯͯ͠ɼ‘WS’ ͸ۭനͱλϒจࣈͱվߦΛද͠ϋΠϥΠτ͞Εͨ෦෼Ͱ͋Δɽߏจఆٛ‫ه‬ड़ղੳϞδϡʔ

͍ͯΔɽ

ϧ͸ɼANTLR ͷߏจఆٛ‫ه‬ड़͔ΒίϝϯτΛද͢ਖ਼‫ن‬ද࣍ʹɼANTLR Ͱ࢖༻͞ΕΔίϚϯυͱ͍͏‫ػ‬ೳʹ͍ͭ‫ͱݱ‬༧໿‫ޠ‬Λநग़͢Δ΋ͷͰ͋Δɽ·ͨ CCFinderSW ͷ

ͯઆ໌͢ΔɽANTLR ͸ࣈ۟ղੳϧʔϧΛ༻͍ͯιʔεࣈ۟ղੳ෦Λ֦ுͯ͠ɼίϝϯτΛද͢ਖ਼‫ن‬ද‫ݱ‬Λ༻͍ͯίʔυதͰग़‫͢ݱ‬Δࣈ۟Λఆٛ͢Δ͕ɼͦΕͧΕͷࣈ۟ʹίϝϯτআ‫ڈ‬Λߦ͏‫ػ‬ೳΛ௥Ճͨ͠ɽ͜ΕʹΑͬͯɼࣈ۟
෼ׂҎ߱ͷॲཧΛैདྷͷ CCFinderSW ͱಉ͡ྲྀΕͰιʔc 2018 Information Processing Society of Japan

4

Vol.2018-SE-199 No.27
2018/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report䝋䞊䝇䝣䜯䜲䝹

ᵓᩥᐃ⩏グ㏙ઃ͚ɼͦͷ͏ͪͷগͳ͘ͱ΋ 1 ͭʹ౰ͯ͸·Δ͜ͱͰίϝϯτʹؔ͢ΔϧʔϧͰ͋Δͱࣝผ͢Δɽͦͷ 4 ͭͷ൑அ‫ج‬ᵓᩥᐃ⩏グ㏙ゎᯒ䝰䝆䝳䞊䝹&ŝŶĚĞƌ^tṇつ⾲⌧䜢⏝䛔䛯䝁䝯䞁䝖㝖ཤ
Ꮠྃศ๭㆑ูᏊุู^ƚĞƉϭ
^ƚĞƉϮ

䝁䝯䞁䝖䜢⾲䛩
ṇつ⾲⌧Εͨ 4 ͭͷϧʔϧ͸શͯ C ‫ޠݴ‬ͷෳ਺ߦίϝϯτʹ૬౰͢Δද‫͋Ͱݱ‬Δɽ( 1 ) ϧʔϧ໊ʹ Comment ΍ COMMENT ͳͲͷจࣈ͕‫ؚ‬·Ε͍ͯΔɽ

ண⣙ㄒ୍ぴ

ኚ᥮ฎ⌮

^ƚĞƉϯ͕ϰ 䜽䝻䞊䞁᳨ฟ䞉ฟຊ䜽䝻䞊䞁䝨䜰᝟ሗਤ 2४ͱͦΕΒʹ౰ͯ͸·ΔϧʔϧͷྫΛҎԼʹࣔ͢ɽྫࣔ͞

ߏจఆٛ‫ه‬ड़ղੳϞδϡʔϧͱ CCFinderSW

Fig. 2 An anaylsis module for syntax deﬁnition and CCFinderSWεϑΝΠϧΛѻ͏͜ͱ͕Ͱ͖ΔɽCCFinderSW ͱߏจఆ( 2 ) ίϚϯυͷ skip ͕‫ݺ‬͹Ε͍ͯΔɽ( 3 ) ίϚϯυͷ channel(HIDDEN) ͕‫ݺ‬͹Ε͍ͯΔɽ( 4 ) ίϚϯυͷ channel ͕‫ݺ‬͹Ε͍ͯͯɼchannel ໊ʹComment ΍ COMMENT ͳͲͷจࣈ͕‫·ؚ‬Ε͍ͯΔɽίϝϯτͷఆٛྫ
Comment:’/*’.*?’*/’;
Block1: ’/*’.*?’*/’ -> skip;
Block2: ’/*’.*?’*/’ -> channel(HIDDEN);
Block3: ’/*’.*?’*/’ -> channel(BComment);ٛ‫ه‬ड़ղੳϞδϡʔϧΛ߹ΘͤΔͱɼιʔεϑΝΠϧͱߏ

Step B બͼग़͞Εͨίϝϯτʹؔ͢ΔϧʔϧΛ࠶‫ؼ‬จఆٛ‫ه‬ड़Λೖྗͱͯ͠༩͑Δ͜ͱͰΫϩʔϯϖΞ৘ใ͕తʹৄࡉԽ͢Δɽ3 અͰ࢛ࣔͨ͠ଇԋࢉࣜΛද͢ߏจఆٛग़ྗ͞ΕΔ͜ͱʹͳΔɽ

ϑΝΠϧͷྫͰ͸ɼterm ͱ͍͏໊લͷϧʔϧͷதͰ factorຊ‫Ͱڀݚ‬։ൃͨ͠ߏจఆٛ‫ه‬ड़ղੳϞδϡʔϧ͸ɼ·ͣͱ͍͏ϧʔϧ͕ຒΊࠐ·Ε͍ͯΔɽ͜ͷΑ͏ʹϧʔϧͷத

ANTLR ͷߏจఆٛ‫ه‬ड़Λߏจղੳͯ͠ߏจ໦Λੜ੒ͯ͠Ͱଞͷϧʔϧ͕ࢀর͞Ε͍ͯΔ৔߹͸ɼStep C Ͱਖ਼‫ن‬ද‫ݱ‬͍Δɽ͜ͷߏจղੳʹ͸ɼJava ‫Ͱޠݴ‬ಈ࡞͢Δߏจղੳ‫ث‬ʹม‫͢׵‬ΔͨΊʹࢀরઌϧʔϧͷ಺༰Λ࠶‫ؼ‬తʹ୅ೖ͠ɼΛ ANTLR Ͱੜ੒ͯ͠૊ΈࠐΜͩɽৄࡉԽΛߦ͏ɽ

Ҏ߱ɼ4.1 અͰ͸ίϝϯτ‫ه‬ड़ϧʔϧͷਖ਼‫ن‬ද‫΁ݱ‬ͷม

Step C ৄࡉԽ͞ΕͨϧʔϧΛ Java Ͱ࢖༻͞ΕΔΑ͏‫͍ͯͭʹ׵‬આ໌͠ɼ4.2 અͰ͸༧໿‫ޠ‬Ұཡͷਖ਼‫ن‬ද‫΁ݱ‬ͷͳਖ਼‫ن‬ද‫ʹݱ‬ม‫͢׵‬Δɽ͜Ε͸ຊ‫Ͱڀݚ‬ͷϞδϡʔϧ͕ม‫͍ͯͭʹ׵‬આ໌͢Δɽ

Java Ͱ։ൃ͞Ε͍ͯΔ͜ͱͰɼANTLR Ͱ࢖༻͞ΕΔද‫ݱ‬ͱ͸෦෼తʹҟͳ͍ͬͯΔͨΊͰ͋ΔɽJava Ͱ༻͍ΒΕ

4.1 ίϝϯτ‫ه‬ड़ϧʔϧͷਖ਼‫ن‬ද‫΁ݱ‬ͷม‫׵‬Δਖ਼‫ن‬ද‫ ͱݱ‬ANTLR ͷߏจఆٛͰ࢖༻͞ΕΔද‫ݱ‬ͷҧ͍ຊઅͰ͸ ANTLR ͷߏจఆٛ‫ه‬ड़͔ΒɼίϝϯτΛද͢Ͱɼม‫͕׵‬ඞཁͳ΋ͷ͸ 3 ͭ͋Δɽ1 ͭ໨͸γϯάϧΫΥʔਖ਼‫ن‬ද‫ݱ‬ͷநग़ํ๏ʹ͍ͭͯड़΂Δɽ·ͣਖ਼‫ن‬ද‫Ͱݱ‬நग़ςʔγϣϯͰ͋ΔɽANTLR ͷߏจఆٛ‫ه‬ड़Ͱ͸ɼର৅‫ݴ‬

͢Δཧ༝ͱͯ͠͸ɼANTLR ͷߏจఆٛ‫ه‬ड़͸ਖ਼‫ن‬ද‫ͱݱ‬‫ʹޠ‬ग़‫͢ݱ‬Δ࣮ࡍͷϦςϥϧΛγϯάϧΫΥʔςʔγϣϯ͍ۙද‫͕͞ݱ‬Ε͓ͯΓɼม‫׵‬ՄೳͰ͋Δ͔ΒͰ͋Δɽ·ͨͰғΜͰ‫ه‬ड़͢Δɽਖ਼‫ن‬ද‫Ͱݱ‬͸͜ͷγϯάϧΫΥʔςʔ

CCFinderSW Ͱ࠾༻͞Ε͍ͯͨίϝϯτϧʔϧͷ෼ྨҎγϣϯ͸ෆཁͰ͋ΔͨΊআ‫͢ڈ‬Δɽ2 ͭ໨͸ NOT ԋࢉࢠ֎ͷίϝϯτϧʔϧʹ΋ɼ෯޿͘ରԠग़དྷΔՄೳੑ͕͋Δ

Ͱ͋ΔɽANTLR ͷߏจఆٛ‫ه‬ड़Ͱ͸ɼ͋Δಛఆͷจࣈू͔ΒͰ͋Δɽ

߹ʹϚον͠ͳ͍ू߹Λදͨ͢Ίʹઌ಄ʹɼNOT ԋࢉࢠਖ਼‫ن‬ද‫ݱ‬ͷநग़͸ҎԼͷ 4 ͭͷ Step ʹ෼͚ΒΕΔɽͷ໾ׂΛ͢Δ ‘˜’ Λ͚ͭΔɽ ͜ͷ NOT ԋࢉࢠʹ௚઀తʹ

Step A શͯͷϧʔϧͷத͔Βίϝϯτʹؔ͢Δͱߟ͑

૬౰͢Δ΋ͷ͸ਖ਼‫ن‬ද‫ʹݱ‬͸ଘࡏ͠ͳ͍ͨΊɼਖ਼‫ن‬ද‫ݱ‬ͷΒΕΔϧʔϧΛબͼͩ͢ɽ

Step B ͦΕͧΕͷϧʔϧͷதͰɼผͷϧʔϧΛࢀর͠
͍ͯΔ෦෼Λ࠶‫ؼ‬తʹৄࡉԽ͢Δɽ

Step C ৄࡉԽ͞ΕͨϧʔϧΛ Java Ͱ࢖༻͞ΕΔਖ਼‫ن‬ද‫ʹݱ‬ม‫͢׵‬Δɽ

Step D ੜ੒͞Εͨਖ਼‫ن‬ද‫ݱ‬Λશͯ݁߹ͯ͠ 1 ͭͷද‫ݱ‬ʹ͢Δɽ
֤ Step ͷৄࡉ͸ҎԼͷͱ͓ΓͰ͋Δɽ

Step A ·ͣɼશͯͷϧʔϧͷத͔Βίϝϯτʹؔ͢Δ൱ఆతઌಡΈΛ༻͍ͯಉ౳ͷද‫ʹݱ‬ม‫͢׵‬Δɽ3 ͭ໨͸೚
ҙͷ 1 จࣈΛද͢ ‘.’ Ͱ͋ΔɽANTLR ͷߏจఆٛ‫ه‬ड़Ͱ͸͜ͷ ‘.’ ͸೚ҙͷ 1 จࣈΛද͢ͷʹର͠ɼJava Ͱ࢖༻͞ΕΔਖ਼‫ن‬ද‫Ͱݱ‬͸վߦҎ֎ͷ೚ҙͷ 1 จࣈΛද͠ɼఆ͕ٛ
ͦΕͧΕͰҟͳ͍ͬͯΔɽ͜ͷఆٛͷࠩҟΛຒΊΔͨΊɼߏจఆٛ‫ه‬ड़Ͱ༻͍ΒΕΔ ‘.’ Λਖ਼‫ن‬ද‫Ͱݱ‬ͷಉ౳ͷද‫ݱ‬Ͱ͋Δ ‘[\s\S]’ ʹม‫͢׵‬Δ͜ͱͰରԠ͍ͯ͠Δɽ

Step D ੜ੒͞Εͨਖ਼‫ن‬ද‫ݱ‬Λશͯ݁߹ͯ͠ 1 ͭͷද‫͢ʹݱ‬ΔɽStep C Ͱੜ੒͞Εͨਖ਼‫ن‬ද‫ݱ‬ͷશͯͷ࿦ཧ࿨ͱߟ͑ΒΕΔϧʔϧΛબͼग़͢ɽ͜Εʹ͸൑அ‫ج‬४Λ 4 ͭ

c 2018 Information Processing Society of Japan

5

Vol.2018-SE-199 No.27
2018/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Report

Step α67(3$%&RPPHQW&67$57 "&(1'&67$57b b

/&RPPHQW'6/$6+f>僊U僊Q@ &(1'b b

Step β'6/$6+bb

Step δ

67(3&

Step γ Ͱม‫͞׵‬Εͨਖ਼‫ن‬ද‫Ͱݱ‬ɼӳࣈྻΛද͍ͯ͠Δ΋ͷΛબग़͢Δɽ

 ">僊U僊Q@ >僊V僊6@

Step 

67(3'

Step α Ͱநग़͞ΕͨϦςϥϧͱ Step δ Ͱબग़͞Εͨਖ਼‫ن‬ද‫ݱ‬Λશͯ݁߹ͯ͠ 1 ͭͷද‫͢ʹݱ‬Δɽ僊 >僊V僊6@ "僊 e ">僊U僊Q@ >僊V僊6@

ਤ 3

Step β ͰৄࡉԽ͞ΕͨϧʔϧΛ Java Ͱ࢖༻͞ΕΔਖ਼‫ن‬ද‫ʹݱ‬ม‫͢׵‬Δɽ

/&RPPHQW  f>僊U僊Q@ 僊 >僊V僊6@ "僊 શͯͷϧʔϧͰɼผͷϧʔϧΛࢀর͍ͯ͠Δ෦෼Λ࠶‫ؼ‬తʹৄࡉԽ͢Δɽ

Step γ67(3%%&RPPHQW   "  શͯͷϧʔϧͰɼग़‫͍ͯ͠ݱ‬ΔϦςϥϧͷ͏ͪӳࣈྻʹҰக͢Δ΋ͷΛநग़͢Δɽ

Step α ͸ɼϧʔϧϒϩοΫʹग़‫͢ݱ‬ΔϦςϥϧͷ͏ͪӳίϝϯτ‫ه‬ड़ϧʔϧͷਖ਼‫ن‬ද‫΁ݱ‬ͷม‫ྫ׵‬ࣈྻʹҰக͢Δ΋ͷΛશͯநग़͠༧໿‫͋Ͱޠ‬ΔͱΈͳ͢ɽ

Fig. 3 An example of transformating comment rules into a

Step β ͸ 4.1 અͰઆ໌ͨ͠ίϝϯτநग़ͷ Step A ͱಉ༷

regular expression

Ͱ͋ΓɼStep γ ͸ίϝϯτநग़ͷ Step C ͱಉ༷Ͱ͋ΔɽΛͱΔɽ͜Ε͸ɼશͯͷਖ਼‫ن‬ද‫ݱ‬Λؒʹ ‘|’ Λ‫ڬ‬ΜͰ݁߹͢

Step δ ͸ Step γ Ͱੜ੒͞Εͨਖ਼‫ن‬ද‫͕ݱ‬ɼӳࣈྻΛද͠

Δ͜ͱͰߦΘΕΔɽ͜ͷ Step D Λऴ͑ͨ࣌఺Ͱɼίϝϯ͍ͯΔ΋ͷΛબͼग़͢ɽStep  ͸ίϝϯτநग़ͷ Step Dτ‫ه‬ड़ϧʔϧͷਖ਼‫ن‬ද‫ݱ‬ͷม‫͕׵‬ऴྃ͢Δɽ

ͱಉ༷ʹ ‘|’ Λ༻͍ͨ݁߹Λߦ͏ɽ

ਤ 3 ͸ɼҎ্ͷίϝϯτ‫ه‬ड़ϧʔϧͷਖ਼‫ن‬ද‫΁ݱ‬ͷม‫׵‬

Step α ͱ Step δ Ͱ͸ɼ༧໿‫ޠ‬͸ӳࣈྻͰ͋Δͱ͍͏લྫͰ͋Δɽ·ͣ Step A Ͱ BComment ͱ LComment ͱఏʹ‫͍͍ͯͮج‬Δɽຊ‫ڀݚ‬ͷௐࠪͰ͸༧໿‫·ؚʹޠ‬ΕΔจ

͍͏ 2 ͭͷίϝϯτΛද͢ͱߟ͑ΒΕΔϧʔϧΛબ୒͢ࣈͱͯ͠ӳࣈྻҎ֎ʹɼ‘ ’ ΍ ‘@’ ͳͲͷ‫߸ه‬΋‫·ؚ‬ΕΔ

Δɽ࣍ʹ Step B Ͱ͸બ୒͞ΕͨϧʔϧͷৄࡉԽΛߦ͏ɽ͜ͱ͕͋ͬͨͨΊɼϞδϡʔϧʹநग़͍ͨ͠༧໿‫·ؚʹޠ‬

BComment Ͱ͸ CST ART ͱ CEN D ͱ͍͏ଞͷϧʔϧΕΔจࣈΛࢦఆ͢Δ‫ػ‬ೳΛ࣮૷ͨ͠ɽ

΁ͷࢀর͕͋ΔͨΊɼࢀরઌͷϧʔϧΛ୅ೖͯ͠ଞͷϧʔ

5. ద༻࣮‫ݧ‬ϧ໊͕‫·ؚ‬Εͳ͍ද‫͢ʹݱ‬ΔɽStep C Ͱ͸ਖ਼‫ن‬ද‫Ͱݱ‬ͷಉ౳ͷද‫ʹݱ‬ม‫͠׵‬ɼ࠷‫ ʹޙ‬Step D Ͱੜ੒͞ΕͨશͯͷຊষͰ͸ɼ։ൃͨ͠ߏจఆٛ‫ه‬ड़ղੳϞδϡʔϧͷ༗༻ਖ਼‫ن‬ද‫ݱ‬Λ݁߹͢ΔɽੑΛ֬ೝ͢ΔͨΊʹߦͬͨ 2 ͭͷద༻࣮‫͍ͯͭʹݧ‬આ໌͢Δɽ

4.2 ༧໿‫ޠ‬Ұཡͷਖ਼‫ن‬ද‫΁ݱ‬ͷม‫׵‬ຊઅͰ͸ ANTLR ͷߏจఆٛ‫ه‬ड़͔Βɼ༧໿‫ޠ‬Ұཡͷந

5.1 ίϝϯτͱ༧໿‫ޠ‬ͷநग़࣮‫ݧ‬ग़ํ๏ʹ͍ͭͯड़΂Δɽຊ‫Ͱڀݚ‬։ൃͨ͠ϞδϡʔϧΛ༻͍ͯɼͲͷఔ౓ͷߏจຊπʔϧΛ։ൃ͢ΔࡍʹɼANTLR ͷߏจఆٛ‫ه‬ड़಺Ͱͷ༧໿‫ޠ‬ͷ‫ه‬ड़๏Λௐࠪͨ݁͠Ռɼେ͖͘෼͚ͯ 2 छྨͷఆٛ‫ه‬ड़ϑΝΠϧʹ͓͍ͯίϝϯτͱ༧໿‫ޠ‬ͷ৘ใ͕நग़ՄೳͰ͋Δ͔Λ࣮ࣔ͢‫ݧ‬Λߦͬͨɽ‫ه‬ड़๏͕͋ͬͨɽҎԼʹ 2 छྨͷ‫ه‬ड़๏ʹ͍ͭͯɼwhile࣮‫ݧ‬ͷର৅ͱͳΔϑΝΠϧ͸ Github ͷϦϙδτϦͰ͋Δ grammars-v4*4 Λ࢖༻ͨ͠ɽ͜ͷϦϙδτϦ͸ ANTLRͱ͍͏༧໿‫ޠ‬Λ༻͍ͯྫࣔ͢Δɽ༧໿‫ޠ‬ͷද‫ྫه‬ ͷจ๏ϑΝΠϧΛूΊͨ΋ͷͰ͋Γɼ໿ 150 छྨͷจ๏

WHILE:’while’;ϑΝΠϧ͕‫·ؚ‬Ε͍ͯΔɽANTLR ͷ։ൃऀͰ͋Δ Parr

WHILE:[wW][hH][iI][lL][eE];΋‫ؚ‬Ίͯɼ170 ਓҎ্ͷߩ‫͕ऀݙ‬ଘࡏ͠ɼ‫Ͱࡏݱ‬΋ߋ৽͕จࣈͱখจࣈͷͲͪΒͰ΋Ϛονϯά͢Δ͜ͱΛ‫ه͢ڐ‬ड़ϧ͔Βίϝϯτͱ༧໿‫͑ߟͱޠ‬ΒΕΔఆٛʹ͍ͭͯ͋Β͔

๏Ͱ͋Δɽ1 ͭ໨ͷ‫ه‬ड़๏ͷӈล΋ਖ਼‫ن‬ද‫͑ߟͯ͠ͱݱ‬Β͡Ί‫ه‬࿥͓͖ͯ͠ɼߏจఆٛ‫ه‬ड़ղੳϞδϡʔϧ͕ίϝϯ

͑ΔͨΊɼ༧໿‫ޠ‬Ұཡ΋ίϝϯτϧʔϧͱಉ༷ʹਖ਼‫ن‬ද‫ݱ‬τͱ༧໿‫͍ͯͭʹޠ‬ͷ৘ใΛநग़Ͱ͖Δ͔Ͳ͏͔൑ఆͨ͠ɽ ଓ͚ΒΕ͍ͯΔɽ࣮‫ͨ͠༻࢖Ͱݧ‬ϦϙδτϦͷεφοϓ
γϣοτ͸ 2017 ೥ 12 ݄ 14 ೔࣌఺ͷ΋ͷͰ͋Δɽ
1 ͭ໨ͷ‫ه‬ड़๏Ͱ͸ɼW HILE ͱ͍͏ϧʔϧ໊ʹ while·ͣຊ‫Ͱڀݚ‬͸ɼϦϙδτϦʹ‫·ؚ‬Ε͍ͯΔ 154 छྨͷͱ͍͏୯‫͕ޠ‬ඥ෇͚ΒΕ͍ͯΔɽ͜ͷ‫ه‬ड़๏͸࠷΋޿͘࢖จ๏ʹ͍ͭͯௐࠪΛߦͬͨɽͦͷத͔ΒɼGithub ͷ AdΘΕ͍ͯΔ΋ͷͰ͋ͬͨɽͦͯ͠ 2 ͭ໨ͷ‫ه‬ड़๏Ͱ͸ɼਖ਼vanced Code Search*5 ͷ‫ࡧݕ‬ର৅ʹొ࿥͞Ε͍ͯΔ 43 ‫ݴ‬‫ن‬ද‫͞༻࢖Ͱݱ‬ΕΔΑ͏ͳจࣈΫϥεΛ༻͍ͨॻ͖ํ͕͞
‫ޠ‬Λ࣮‫ݧ‬ର৅ͱͨ͠ɽ࣍ʹͦͷ 43 ‫ޠݴ‬ͷߏจఆٛϑΝΠΕ͍ͯΔɽ͜Ε͸ while ʹ‫·ؚ‬ΕΔ 5 จࣈͷͦΕͧΕʹେͰੜ੒͢Δ͜ͱʹͨ͠ɽ༧໿‫ޠ‬Ұཡͷநग़͸ҎԼͷ 5 ͭͷStep ʹ෼͚ΒΕΔɽ

c 2018 Information Processing Society of Japan


*4
*5

https://github.com/antlr/grammars-v4
https://github.com/search/advanced

6Vol.2018-SE-199 No.27
2018/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportຊ‫͚͓ʹڀݚ‬Δ༧໿‫ޠ‬ͷఆٛʹ͍ͭͯ‫ه‬ड़͢ΔɽҰൠతʹ༧໿‫ͱޠ‬͸ɼม਺໊΍ؔ਺໊ʹ࢖༻Ͱ͖ͳ͍จࣈྻͷ͜ͱΛࢦ͠ɼͦΕͧΕͷϓϩάϥϛϯά‫ʹޠݴ‬ΑͬͯఆΊΒද 2ίϝϯτͱ༧໿‫ޠ‬ͷநग़݁Ռ

Table 2 Result of the extraction of comments and reservedwords

Ε͍ͯΔɽҰํɼϓϩάϥϛϯά‫͚͓ʹޠݴ‬ΔΩʔϫʔυ

‫ޠݴ‬

ίϝϯτ

༧໿‫ޠ‬

ͱ͸ɼ͋Δϓϩάϥϛϯά‫͞༻࢖Ͱޠݴ‬ΕΔಛผͳҙຯΛ

agc

˓

˓

antlrv4

˓

˓

apex

˓

˓

asm6502˓˓ͯ΋༧໿‫Ͱޠ‬͸ͳ͍จࣈྻ͕ଘࡏ͠ɼͦ΋ͦ΋༧໿‫͕ޠ‬ଘ

aspectj˓˓ࡏ͠ͳ͍‫ޠݴ‬΋ଘࡏ͢Δɽྫͱͯ͠ɼ࣮‫ݧ‬ର৅‫ޠݴ‬ͷ 1 ͭbrainf*ckʷ

ఆٛͳ͠Ͱ͋Δ Fortran ʹ͸༧໿‫ޠ‬͸ଘࡏͤͣɼΩʔϫʔυ΋ม਺

c

˓

˓

໊ʹ࢖༻Ͱ͖Δɽ͜ͷ࣮‫Ͱݧ‬͸ɼ֤‫͞༻࢖Ͱޠݴ‬ΕΔΩʔ

clojure˓˓ϫʔυ͕ͦͷ··༧໿‫ͳʹޠ‬Δͱఆ࣮ٛͯ͠‫ݧ‬Λߦͬͨɽcobol85˓˓

ද 2 ͸ɼ֤‫ޠݴ‬ͷߏจఆٛϑΝΠϧʹରͯ͠ίϝϯτͱ

cool

˓

˓

cpp14

˓

˓

csharp˓˓࣋ͭจࣈྻͷ͜ͱΛࢦ͢ɽ༧໿‫ͱޠ‬Ωʔϫʔυ͸ࣅ௨ͬͨଘࡏͱ‫ݴ‬ΘΕ͍ͯΔ͕ɼ‫ʹޠݴ‬Αͬͯ͸ΩʔϫʔυͰ͋ͬ༧໿‫͍ͯͭʹޠ‬ͷ৘ใΛநग़݁ՌΛࣔͨ͠΋ͷͰ͋Δɽ֤‫ʹޠݴ‬ର͠ɼϞδϡʔϧ͕ίϝϯτͱ༧໿‫ޠ‬ͷ৘ใ͕நग़

css3

˓

ʷ

Մೳ͔Ͳ͏͔Λ͍ࣔͯ͠Δɽ˓͸நग़Մೳɼʷ͸நग़ෆՄ

ecmascript

˓

˓

ೳΛࣔ͠ɼ
ʮఆٛͳ͠ʯ͸จ๏ϑΝΠϧʹίϝϯτͱ༧໿‫ޠ‬

erlang˓˓Β͖͠‫ه‬ड़͕ͳ͔ͬͨ͜ͱΛ͍ࣔͯ͠Δɽ݁Ռɼϓϩάϥ

fortran77˓˓ϛϯά‫ޠݴ‬ͷจ๏Λද͢ 43 ͷߏจఆٛ‫ه‬ड़ϑΝΠϧͷ͏golang˓˓ͪɼίϝϯτ͸ 93 ˋɼ༧໿‫ޠ‬͸ 97 ˋͷϑΝΠϧ͔Βநग़

html

˓

ఆٛͳ͠

idl

˓

˓

͢Δ͜ͱ͕Ͱ͖ͨɽ

java9

˓

˓

kotlin˓˓brainf*ck ίϝϯτ৘ใͷநग़͕Ͱ͖ͳ͍ɽbrainf*ck ͸

lua

ʷ

˓

೉ղϓϩάϥϛϯά‫͋Ͱޠݴ‬Γɼಛఆͷ 8 จࣈͷΈmodelica˓˓ιʔείʔυ͕‫ه‬ड़͞ΕɼͦΕҎ֎ͷจࣈ͕ແࢹ͞Εɼ

modula2˓˓ίϝϯτͱΈͳ͞ΕΔͱ͍͏ಛघͳจ๏Λ࣋ͭ΋ͷͰ

objective-c˓˓

pascal˓˓˓࣍ʹɼʷͱͳͬͨཧ༝ʹ͍ͭͯͦΕͧΕ‫ه‬ड़͢Δɽ

͋ͬͨɽ

php

˓

plsql

˓

˓

prologఆٛͳ͠ఆٛͳ͠

protobuf3

˓˓

python3˓˓lua ίϝϯτ৘ใͷநग़͕Ͱ͖ͳ͍ɽlua ʹ༻͍ΒΕΔί

r

˓

ఆٛͳ͠

ϝϯτ‫ߏ͕߸ه‬จఆٛϑΝΠϧͷதͰෳࡶʹఆٛ͞Ε

rexx

ʷ

˓

css ༧໿‫ޠ‬৘ใͷநग़͕Ͱ͖ͳ͍ɽcss ͷߏจఆٛϑΝΠϧͷதͰ͸ɼநग़͍ͨ͠༧໿‫ޠ‬ͷதʹվߦ͕‫·ؚ‬ΕΔ͜ͱΛ‫͢ڐ‬Α͏ͳ‫ه‬ड़͕͞Ε͍ͯΔͳͲɼಛघͳॻ͖
ํ͕͞Ε͍ͯΔͨΊநग़ෆՄೳͱ൑அͨ͠ɽ

scala

˓

˓

rexx ίϝϯτ৘ใͷநग़͕Ͱ͖ͳ͍ɽߏจఆٛϑΝΠϧ

smalltalk˓˓ͰωετΛ‫͢ڐ‬ෳ਺ߦίϝϯτͷఆ͕ٛɼ2 ͭͷϧʔ

smtlibv2

˓˓

swift3

˓

˓

vba

˓

˓

verilog2001

˓

˓

vhdl

˓

˓

visualbasic6˓˓

webidl˓˓͓ͯΓɼਖ਼‫ن‬ද‫Ͱݱ‬ͷநग़͸ෆՄೳͱ൑அͨ͠ɽ

ϧΛϧʔϓ͢Δ͜ͱͰද‫͞ݱ‬Ε͍ͯΔͨΊɼଞͷ‫ޠݴ‬ͷߏจఆٛϑΝΠϧͱ͸ҧͬͨಛघͳॻ͖ํ͕͞Εͯ
͍ΔͨΊɼநग़͸ෆՄೳͱ൑அͨ͠ɽ

5.2 ίʔυΫϩʔϯ‫ݕ‬ग़࣮‫ݧ‬ຊઅͰ͸ ANTLR ͷߏจఆٛ‫ه‬ड़͔Βநग़ͨ͠ίϝϯτʹ૬౰͢Δਖ਼‫ن‬ද‫ͱݱ‬༧໿‫ޠ‬ҰཡΛɼίʔυΫϩʔϯ‫ݕ‬ग़ͨΊɼλΠϓ 1 ͷίʔυΫϩʔϯͱ͍͑Δɽ࣍ʹίϐʔͷ΁ద༻ՄೳͰ͋Δ͜ͱΛ֬ೝ͢ΔͨΊʹߦ࣮ͬͨ‫͍ͭʹݧ‬ιʔείʔυʹରͯ͠ɼద੾ͳՕॴʹίϝϯτΛ௥Ճͯͯ͠‫ه‬ड़͢Δɽม਺໊Λॻ͖‫͑׵‬Δɽ͜ͷΑ͏ͳॲཧʹΑͬͯɼखಈͰλ࣮‫ݧ‬ͷखॱʹ͍ͭͯઆ໌͢Δɽ·ͣɼ͋Δ‫ޠݴ‬ͷιʔεΠϓ 2 ͷίʔυΫϩʔϯΛ࡞੒͢Δɽ࠷‫ʹޙ‬ɼ͜ͷΦϦδίʔυΛ 1 ͭ༻ҙ͠ɼͦͷιʔείʔυͷίϐʔΛಉ࣌φϧͱίϐʔ͞ΕͨϑΝΠϧͱɼߏจఆٛ‫ه‬ड़ϑΝΠϧ͔ʹ࡞੒͢Δɽ͜ͷ࣌఺Ͱ͸ 2 ͭͷιʔείʔυ͸ಉҰͷΒநग़ͨ͠৘ใΛೖྗͱͯ͠ CCFinderSW ʹ౉͠ɼίʔc 2018 Information Processing Society of Japan

7

Vol.2018-SE-199 No.27
2018/7/20

৘ใॲཧֶձ‫ڀݚ‬ใࠂ
IPSJ SIG Technical Reportද 3ίʔυΫϩʔϯ‫ݕ‬ग़ͷ݁Ռ

Table 3 Result of code clone detection‫ޠݴ‬ίʔυΫϩʔϯ‫ݕ‬ग़ࠓ‫ޙ‬ͷ՝୊ͱͯ͠ߏจఆٛϑΝΠϧ͔Βίϝϯτϧʔϧͱ߹ΘͤͯจࣈྻϦςϥϧͷ৘ใ΋औಘ͠ɼଟ͘ͷίϝϯτϧʔϧʹରԠग़དྷΔΑ͏ͳ‫ʹࣜܗ‬ม‫ͯ͠׵‬ɼίϝϯτআc˓‫͑ߦ͕ڈ‬ΔΑ͏ʹ CCFinderSW Λ֦ு͢Δ͜ͱ͕ඞཁͰ

cpp14

˓

͋Δɽ

csharp˓golang

˓

java9

˓

python3˓ఆ͸ߦΘΕ͍ͯͳ͍ɽࠓ‫ޙ‬ͷ՝୊ͱͯ͠ɼநग़͞ΕͨΩʔsmalltalk˓ϫʔυ͕༧໿‫͋Ͱޠ‬Δ͔൑ఆ͢Δ͜ͱ͕‫͛ڍ‬ΒΕΔɽ

vhdl

˓

visualbasic6˓ຊ‫Ͱڀݚ‬։ൃͨ͠ϞδϡʔϧͰநग़͞ΕΔจࣈྻ͸ϓϩάϥϛϯά‫ޠݴ‬ͷΩʔϫʔυͰ͋Γɼ༧໿‫͔͏Ͳ͔ޠ‬ͷ൑ँࣙ ຊ‫ڀݚ‬͸ JSPS Պ‫ݚ‬අ JP25220003, JP18H04094,

JP16K16034 ͷॿ੒Λड͚ͨɽυΫϩʔϯ‫ݕ‬ग़Λߦ͍ɼλΠϓ 2 ͷίʔυΫϩʔϯͱͯ͠ࢀߟจ‫ݙ‬‫ݕ‬ग़͞ΕΔ͜ͱΛ֬ೝ͢Δɽ

[1]
[2]

ຊ࣮‫ݧ‬ͷର৅ͱͯ͠ 9 ‫ޠݴ‬Λબग़ͨ͠ɽ͜ͷ‫ޠݴ‬͸ 5.1
અͷ࣮‫Ͱݧ‬ίϝϯτͱ༧໿‫ޠ‬ͷͲͪΒ΋நग़Մೳͱͳͬͨ
‫ޠݴ‬ͷ͏ͪɼม਺໊ͷมߋͱίϝϯτͷ௥Ճ͕े෼ʹՄೳ

[3]ͱߟ͑ΒΕͨ΋ͷΛෳ਺બ୒ͨ͠ɽ
ίʔυΫϩʔϯ‫ݕ‬ग़ͷ݁ՌΛද 3 ʹࣔͨ͠ɽશͯͷ‫ޠݴ‬[4]ʹ͓͍ͯλΠϓ 2 ͷίʔυΫϩʔϯͷ‫ݕ‬ग़͕ՄೳͰ͋Δ͜
ͱ͕֬ೝͰ͖ͨɽ

6. ·ͱΊͱࠓ‫ޙ‬ͷ՝୊

[5]
[6]

ຊ‫Ͱڀݚ‬͸ίʔυΫϩʔϯ‫ݕ‬ग़ʹ͓͚Δࣈ۟ղੳʹඞཁͳ৘ใΛɼߏจղੳ‫ث‬ੜ੒‫ܥ‬ͷߏจఆٛϑΝΠϧ͔Βࣗಈతʹநग़͢Δख๏ΛఏҊͨ͠ɽͦͯ͠ɼͦͷख๏Λ༻͍ͯ[7]ߏจఆٛ‫ه‬ड़ղੳϞδϡʔϧΛ։ൃ͠ɼ‫ط‬ଘͷίʔυΫ[8]ϩʔϯ‫ݕ‬ग़πʔϧͰ͋Δ CCFinderSW ʹࣈ۟ղੳ৘ใΛ
༩͑Δ͜ͱͰɼଟ‫ޠݴ‬ͷίʔυΫϩʔϯ‫ݕ‬ग़Λߦ͏࢓૊ΈΛ։ൃͨ͠ɽ։ൃͨ͠Ϟδϡʔϧͷద༻࣮‫Ͱݧ‬͸ɼϓϩά

[9]
[10]

ϥϛϯά‫ޠݴ‬ͷจ๏Λද͢ 43 ͷߏจఆٛ‫ه‬ड़ϑΝΠϧͷ͏ͪɼίϝϯτ͸ 93 ˋɼ༧໿‫ޠ‬͸ 97 ˋ͔Βநग़Ͱ͖ͨ͜ͱ
Λࣔͨ͠ɽͦͯ͠நग़ͨ͠৘ใΛೖྗͱͯ͠ CCFinderSW[11]

ʹ༩͑Δ͜ͱͰɼ9 ‫͍͓ͯʹޠݴ‬λΠϓ 2 ͷίʔυΫϩʔϯͷ‫ݕ‬ग़͕ՄೳͰ͋Δ͜ͱ͕֬ೝͨ͠ɽ
ߏจఆٛ‫ه‬ड़͸ର৅ͱͳΔϓϩάϥϛϯά‫ޠݴ‬ͷจ๏

[12]ʹґଘ͢Δ͕ɼॻ͖खʹ΋ґଘ͢Δɽͭ·Γɼಉ͡จ๏Ͱ
͋ͬͯ΋ෳ਺ͷ‫ه‬ड़๏Ͱද‫͢ݱ‬Δ͜ͱ͕Ͱ͖Δɽຊ‫Ͱڀݚ‬ͷ։ൃ͸ɼߏจఆٛ‫ه‬ड़ͷௐࠪʹ͓͍ͯଟ͘ଘࡏͨ͠‫ه‬ड़๏ʹରͯ͠ߦΘΕͨ΋ͷͰ͋Δɽ৽ͨͳ‫ه‬ड़๏ʹରԠ͢ΔͨΊʹ͸ɼϞδϡʔϧΛ֦ு͠ͳ͚Ε͹ͳΒͳ͍ɽ

[13]Friedl, J. E.: Mastering regular expressions (2002).
ං‫ޙ‬๕थɼೇຊਅೋɼҪ্ࠀ࿠ɿίʔυΫϩʔϯ‫ݕ‬ग़ͱͦͷؔ࿈ٕज़ɼిࢠ৘ใ௨৴ֶձ࿦จࢽɼVol. J91-D, No. 6,
pp. 1465–1481 (2008).
Ҫ্ࠀ࿠ɼਆ୩೥༸ɼೇຊਅೋɿίʔυΫϩʔϯ‫ݕ‬ग़๏ɼίϯϐϡʔλιϑτ΢ΣΞɼVol. 18, No. 5, pp. 47–54(2001).
ං‫ޙ‬๕थɼਆ୩೥༸ɼೇຊਅೋɼҪ্ࠀ࿠ɿίʔυΫϩʔϯΛର৅ͱͨ͠ϦϑΝΫλϦϯάࢧԉ‫ڥ؀‬ɼిࢠ৘ใ௨৴
ֶձ࿦จࢽɼVol. Vol.J88-D-I, No. 2, pp. 186–195 (2005).
Johnson, S. C.: Yacc: Yet another compiler-compiler,
Vol. 32, Bell Laboratories Murray Hill, NJ (1975).
Kamiya, T., Kusumoto, S. and Inoue, K.: CCFinder: amultilinguistic token-based code clone detection system
for large scale source code, IEEE Transactions on Software Engineering, Vol. 28, No. 7, pp. 654–670 (2002).
Parr, T.: About The ANTLR Parser Generator,
http://www.antlr.org/about.html.
Parr, T.: antlr4/index.md at master antlr/antlr4,
https://github.com/antlr/antlr4/blob/master/doc/index.md.
Parr, T.: The deﬁnitive ANTLR 4 reference (2013).
Roy, C. K., Cordy, J. R. and Koschke, R.: Comparison and evaluation of code clone detection techniques
and tools: A qualitative approach, Science of Computer
Programming, Vol. 74, No. 7, pp. 470–495 (2009).
Sakamoto, K., Shimojo, K., Takasawa, R., Washizaki,
H. and Fukazawa, Y.: OCCF: A framework for developing test coverage measurement tools supporting multiple
programming languages, Proc. of ICST 2013, IEEE, pp.
422–430 (2013).
Semura, Y., Yoshida, N., Choi, E. and Inoue, K.:
CCFinderSW: Clone Detection Tool with Flexible Multilingual Tokenization, Proc. of APSEC 2017, IEEE, pp.
654–659 (2017).
২ాହ࢜ɼਆ୩೥༸ɼೇຊਅೋɼҪ্ࠀ࿠ɿΫϩʔϯ‫ݕ‬ग़πʔϧΛ༻͍ͨιʔείʔυ෼ੳπʔϧͷࢼ࡞ɼిࢠ৘
ใ௨৴ֶձٕज़‫ڀݚ‬ใࠂɼVol. 101, No. 240, pp. 17–24(2001).

CCFinderSW Ͱͷίϝϯτআ‫ڈ‬Λɼίϝϯτʹ૬౰͢Δਖ਼‫ن‬ද‫ݱ‬Λ༻͍Δ͜ͱͰߦ͕ͬͨɼ‫ࡏݱ‬ͷํ๏Ͱ͸‫׬‬શʹίϝϯτΛ࡟আ͢Δ͜ͱ͸Ͱ͖ͳ͍ɽ͜Ε͸γϯάϧ
ΫΥʔςʔγϣϯ΍μϒϧΫΥʔςʔγϣϯΛ༻͍ͨจࣈྻϦςϥϧʹΑΔྫ֎ʹରԠͯ͠ͳ͍ͨΊͰ͋Δɽ͜ͷΑ͏ͳ໰୊ʹରॲ͠Α͏ͱ͢Δͱɼਖ਼‫ن‬ද‫͕ݱ‬ෳࡶʹͳΔͨΊ [1]ɼਖ਼‫ن‬ද‫Ͱݱ‬ͷίϝϯτ࡟আ͸ආ͚ͨ΄͏͕Α͍ɽc 2018 Information Processing Society of Japan

8