PEGマシンのFPGA実装について
6
0
0
全文
(2) Vol.2016-ARC-221 No.6 2016/8/8. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. ຊߘͷߏ࣍ͷ௨ΓͰ͋Δɻୈ 2 અ PEG ʹ͍ͭͯ ड़Δɻ࣍ʹୈ 3 અɺୈ 4 અͰɺઃ͍ͯͭʹ࣮ͼٴܭ આ໌͢Δɻୈ 5 અͰੑೳධՁΛߦ͍ɺ࠷ʹޙୈ 6 અʹ݁. 3. ઃܭ PEG packrat parsing[12][2][6] ʹΑΓઢͰؒ࣌ܗղੳ ͢Δ͜ͱ͕Ͱ͖Δɻ͔͠͠ɺpackrat parsing େ͖ͳೖྗ. ͱࠓޙͷ՝Λड़Δɻ. ʹରͯ͠ലେͳϝϞϦ༰ྔΛ༻͢ΔɻͦͷͨΊɺେ͖ͳ ೖྗΛडཧ͢ΔͨΊɺMedeiros ࢯ͕ PEG ͷͨΊͷ Virtual. 2. ղੳදݱจ๏. Parsing Machine[5] ΛఏҊͨ͠ɻຊ͍༻ͰڀݚΔόʔνϟ. PEG A ← e ͱ͍͏ϧʔϧͷू߹Ͱ͋Γɺͦͷதʹ A ඇऴ߸هɺe ղੳද͋ͰݱΔɻղੳදݱද 1 ʹ. ϧϚγϯ Medeiros ࢯ͕ఏҊͨ͠όʔνϟϧϚγϯΛϕʔ εʹ͍ͯ͠Δɻ໋ྩηοτਤ 2 ͱͳΔɻ. Αͬͯද͞ΕΔɻ. ද 1 PEG ͷԋࢉࢠ ղੳදݱ. ҙຯ. ‘hoge’. จࣈϦςϥϧ. [a-zA-Z0-9]. จࣈΫϥε. .. ҙͷจࣈ. A. ඇऴ߸ه. (e). άϧʔϐϯά. e?. Φϓγϣϯ. e*. 0 ݸҎ্ͷ܁Γฦ͠. e+. 1 ճҎ্ͷ܁Γฦ͠. &e. ߠఆઌಡΈɹ. !e. ൱ఆઌಡΈ. ຊ͍༻ͰڀݚΔ໋ྩηοτ Medeios ࢯͷఏҊ໋ͨ͠. e1 e2. γʔέϯε. ྩηοτʹɺPEG ͷԋࢉࢠΛ࣮ߦ͢ΔͨΊͷಛԽ໋ྩΛ. e1 /e2. ༏ઌ͖બ. Ճ͍ͯ͠ΔɻಛԽ໋ྩͰɺΦϓγϣϯ໋ྩʢObyte,. ਤ 2 ໋ྩηοτ. Oset)ɺ0 ݸҎ্ͷ܁Γฦ໋͠ྩ (Rbyte, RsetʣͼٴઌಡΈ ໋ྩ (Nbyte, Nset, Nany) ͕͋Δɻ͜ΕΒͷ໋ྩɺ࣮ߦ. ‘abc’ · ͼٴͦΕͧΕ abc ͱҙͷจࣈʹϚον͢Δɻ [abc] ͷ߹ɺabc ͷ͍ͣΕ͔ 1 จࣈʹϚον͢Δɻe?, e*, e+ਖ਼نදͱݱಉ༷Ͱ͋Δ͕ɺPEG ͰͰ͖Δ͚ͩ. ͢Δ໋ྩΛ͠ݮɺ·ͨಛԽճ࿏ʹΑͬͯɺ࣮ߦޮΛ ্͛ΔͨΊʹ͋Δɻ ϝϞϦ༻ྔΛ͢ݮΔͨΊɺ໋ྩͷϫʔυ 16bit ʹ. ͍จࣈྻΛϚονͤ͞Δɻe1 e2 ॱ࣍ʹ e1 ɺe2 ΛධՁ͠ɺ. ऩΊͨɻୈ 15 Ϗοτ͔Βୈ 11 Ϗοτ·ͰɺΦϖϨʔ. ͲͪΒ͔͕ࣦഊͨ͠߹ɺ࠷ॳͷҐஔʹόοΫτϥοΫ͢. γϣϯϑΟʔϧυʢOp ϑΟʔϧυʣͰ͋Γɺ໋֤ྩʹରԠ. Δɻ༏ઌ͖બ (e1 /e2 ) ·ͣ e1 ΛධՁ͠ɺࣦ͠ഊ͠. ͨ͠ίʔυׂ͕ΓৼΒΕΔɻୈ 10 Ϗοτ͔Βୈ 0 Ϗοτ. ͨ߹ e2 ΛධՁ͢Δɻ·ͨɺ!e Ͱ e ͕ࣦഊ͢Δ࣌ʹ. ·Ͱ໋ྩͷରσʔλͱͳΓɺ໋ྩʹΑͬͯ͜ͷσʔλ. ޭ͠ɺe ͕ޭͨ࣌͠ʹࣦഊ͢Δɻ. ͷҙຯ͕ҟͳΔɻରσʔλͷҙຯද 2 ʹࣔ͢ͱ͓ΓͰ. ਤ 1 ࢛ଇԋࢉΛද͢ PEG ͷྫͰ͋ΔɻPEG ͷԋࢉࢠ ඇৗʹ୯७Ͱɺ࠶ؼతߏΛॲཧ͢Δͷʹ༏Ε͍ͯΔɻ. ͋Δɻ໋ྩͷόΠτίʔυͷੜߏจղੳϓϥοτϗʔ Ϝ Nez[10] Λ༻͍ͯ͠Δɻ. ·ͨɺࣈ۟ղੳߏͼٴจղੳΛ͚Δඞཁ͕͋Δଞͷࣜܗ. ද 2 ରσʔλͷҙຯ. จ๏ͱҧͬͯɺPEG Ͱɺࣈ۟ղੳΛಉ࣌ʹߦ͏͜ͱ͕Ͱ ͖Δɻ. ໋ྩ. Byte/Obyte/Rbyte/Nbyte Set/Oset/Rset/Nset Call/Alt/Jump. ରσʔλͷҙຯ จࣈ. Set ςʔϒϧͷΠϯσοΫε ໋ྩΞυϨε. 4. ࣮ ਤ 1 PEG ྫ. 4.1 શମਤ શମͷγεςϜਤ 3 ʹࣔ͢ͱ͓ΓͰ͋Δɻϗετͱͷ ௨৴ Ubuntu OS ͱ FPGA ͷ௨৴͕Մೳʹͨ͠ɺXillybus. ⓒ 2016 Information Processing Society of Japan. 2.
(3) Vol.2016-ARC-221 No.6 2016/8/8. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. ͕ࣾఏ͍ͯ͠ڙΔ Xillybus IP ίΞΛ༻͍Δɻ·ͨɺϝΠ. 4.2 PEGVM ͷಈ࡞. ϯϝϞϦ FPGA ʹࡌ͍ͯ͠ΔϒϩοΫϝϞϦͰ࣮. PEGVM ͷಈ࡞ɺ໋ྩϑΣονɺจࣈσʔλಡΈࠐ. ͢ΔɻγεςϜͷಈ࡞Ͱɺ·ͣϗετ͔Β໋ྩྻͷόΠ. Έɺ໋ྩσίʔυɺͼٴԋࢉɾσʔλసૹΛߦ͏໋ྩ࣮ߦ. τίʔυΛड͚औΓɺϝϞϦʹҰ࣌తʹอଘ͢Δɻ࣍ʹจ. ͱ͍ͬͨҰ࿈ͷॲཧͷ܁Γฦ͠Ͱ͋ΓɺͦΕΒʹରԠͨ͠. ࣈྻΛϗετ͔Βड͚औΓɺղੳΛߦ͍ɺ݁ՌΛϗετʹ. FɺDɺE ͱ͍͏̏ͭͷঢ়ଶ͕͋ΔɻҰൠతʹɺ໋ྩϑΣο. ฦ͢ɻ. ν໋ྩ͕֨ೲ͞Ε͍ͯΔϝϞϦΞυϨεͷઃఆɺϝϞϦ σʔλϨδελͷಡΈࠐΈɺ໋ྩϨδελͷసૹͷ̏ ͭͷಈ࡞Ͱߏ͞ΕΔɻ͔͠͠ɺຊ࣮Ͱ FPGA ʹ ࡌ͍ͯ͠Δ BlockRAM ΛϝϞϦͱͯ͠༻͢ΔͨΊɺ໋ ྩϑΣον 1 ΫϩοΫαΠΫϧͰ࣮ߦͨ͠ɻ࣮ࡍʹɺϝ ϞϦΞυϨεࣄલʹઃఆ͓͖ͯ͠ɺಡΈग़͠৴߸͕͋Δ ߹ɺσʔλΛϝϞϦσʔλϨδελΛ௨ͣ͞ɺ໋ྩ Ϩδελʹసૹ͞ΕΔɻD ঢ়ଶ 1 ΫϩοΫαΠΫϧͰ࣮ ߦ͞ΕΔɻE ঢ়ଶجຊతʹ 1 ΫϩοΫαΠΫϧͰ࣮ߦ͞ ΕΔ͕ɺRbyteɺRset ྩ໋ذͷ߹ྫ֎Ͱ͋Γɺ۩ ମతʹ 4.3 અͰઆ໌͢Δɻ ੍ޚ৴߸ੜճ࿏ͷׂɺ੍ޚ৴߸Λద࣌ੜͯ͠ɺ ਤ 3 શମγεςϜ. ֤ճ࿏ʹ͑Δ͜ͱͰ͋Δɻঢ়ଶ FɺDɺE ʹରͯ͠ɺ3 ͭ ͷϑϦοϓϑϩοϓ͕ྻʹଓ͞Ε͍ͯΔɻ·ͣલͷ໋. ·ͨɺPEG ʹಛԽͨ͠ Virtual Machine(PEGVM) ͷશ ମਤਤ 4 ͱͳΔɻPEGVM ʹɺॻ͖ػ͑ೳ͖ͭϓϩ άϥϜϨδελʢPR) ͕͋ΔɻPR ࣍ʹ࣮ߦ໋͖͢ྩ ͕֨ೲ͞ΕͨϝϞϦΞυϨεΛࢦఆ͢ΔɻϓϩάϜͷ࣮ߦ ʹैͬͯॱ࣍ʹΠϯΫϦϝϯτ͞Εɺͨͩ͠ɺྩ໋ذ ׂΓࠐΈ͕࣮ߦ͞Εͨ߹ɺذઌͷΞυϨε͕ PR ʹॻ ͖ࠐ·ΕΔɻ·ͨɺReturn ελοΫͱ Fail ελοΫ͕͋ ΓɺͦΕͧΕͷελοΫ͕ελοΫϙΠϯλΛ͍࣋ͬͯΔɻ ελοΫϙΠϯλɺΠϯΫϦϝϯλͱσΟΫϦϝϯλΛ. ྩͷ࣮ߦ͕ޭͨ͠߹ɺঢ়ଶ F ʹର͢ΔϑϦοϓϑϩο ϓʹϑΣονىಈ৴߸ͷϋΠϨϕϧ͕औΓࠐ·ΕΔɻͦ ͷΫϩοΫͷؒɺϝϞϦͷಡΈग़͠৴߸ΛϋΠϨϕϧʹ ͢Δɻͦͷ࣍ͷΫϩοΫͷ্ཱ͕ͪΓͰɺঢ়ଶ D ʹର͢Δ ϑϦοϓϑϩοϓʹϋΠϨϕϧ͕औΓࠐ·Εɺঢ়ଶ F ʹ ର͢ΔϑϦοϓϑϩοϓͷग़ྗϩʔϨϕϧʹͳΔɻͦ ͷΫϩοΫͷؒɺIR ͕͍࣋ͬͯΔ໋ྩσʔλ͕σίʔυ͞ ΕΔɻಉ༷ʹͯ͠ɺͦͷ࣍ͷΫϩοΫαΠΫϧͰɺ໋ྩ ࣮ߦͷͨΊͷ৴߸ΛϋΠϨϕϧʹͯ͠ɺ໋ྩΛ࣮ߦ͢Δɻ ͦͯ͠ɺ࣍ͷΫϩοΫ͔Β৽ͨͳ໋ྩϑΣονΛ࣮ߦ͢Δɻ. ͓࣋ͬͯΓɺ৴߸ʹΑͬͯΠϯΫϦϝϯτσΟΫϦϝ ϯτ͕ద࣮࣌ߦ͞ΕΔɻଞʹɺ໋ྩΛղಡ͢Δσίʔμ ͦΕͧΕͷ໋ྩʹಛԽ໋ͨ͠ྩ༻ճ࿏͕͋Δɻ·ͨɺϝϞ Ϧ͔ΒಡΈࠐΜ໋ͩྩσʔλɺFIFO ͔Βड͚औͬͨจࣈ σʔλͦΕͧΕ໋ྩϨδελʢIRʣ ɺจࣈϨδελʢTRʣ ʹҰ࣌తʹอଘ͞ΕΔɻ. 4.3 ໋֤ྩͷ࣮ߦ 4.3.1 جຊ໋ྩ Byte ໋ྩ࣮ߦͷλΠϜνϟʔτਤ 5a ʹࣔ͢ɻF ঢ়ଶͰ ɺΫϩοΫͷ্ཱ͕ͪΓͰ໋ྩಡΈࠐΈ৴߸ͷ read ist ৴߸͕ϋΠϨϕϧʹͳΓɺ໋ྩ͕֨ೲ͞ΕΔϝϞϦʹΞΫ ηε͠ɺσʔλΛ IR ʹసૹ͞ΕΔɻΞΫηεΞυϨε. PR ͔Βసૹ͞ΕͨΞυϨεͰ͋Δɻಉ࣌ʹจࣈಡΈࠐΈ ৴߸ read text ৴߸ϋΠϨϕϧʹͳΓɺFIFO ͔Β 1 จ ࣈΛಡΈग़͠ɺTR ʹసૹ͞ΕΔɻ ࣍ͷΫϩοΫαΠΫϧͷ্ཱ͕ͪΓͰɺIR ͱ TR ͷσʔ λཱ͕֬͞Εɺ͜ͷΫϩοΫαΠΫϧͰ IR ͷσʔλ͕σ ίʔυ͞ΕɺͲͷ໋ྩΛ࣮ߦ͢Δ͔͕ܾ·Δɻࠓճ Byte ໋ྩ༻ճ࿏͕࣮ߦ͞ΕΔ͜ͱʹͳΔɻಉΫϩοΫαΠΫϧ ͰɺPR ΠϯΫϦϝϯτ͞ΕɺϝϞϦΞΫηε༻Ϩδε λͷ addr ʹσʔλ͕సૹ͞ΕΔɻ ਤ 4 Virtual Machine ͷશମਤ. ࣍ͷΫϩοΫαΠΫϧͷ্ཱ͕ͪΓͰɺByte ໋ྩ༻ճ ࿏ͷτϦΨʔͰ͋Δ Byte r ͕ϋΠϨϕϧʹͳΓɺByte ໋ ྩ༻ճ࿏͕࣮ߦ͞ΕΔɻIR ͕͍࣋ͬͯΔจࣈσʔλͱ TR. ⓒ 2016 Information Processing Society of Japan. 3.
(4) Vol.2016-ARC-221 No.6 2016/8/8. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. ͷจࣈσʔλ͕Ұக͢ΔͳΒɺmatch ৴߸͕ϋΠϨϕϧ. จࣈফඅ৴߸Λ͍࣋ͬͯΔͱ͜Ζ͕ҧ͏ɻΦϓγϣϯ໋ྩ. ʹͳΓɺҰக͠ͳ͚Εɺfail ৴߸͕ϋΠϨϕϧʹͳΔɻ. Ϛονޭͨ͠߹ɺจࣈফඅ৴߸͕ϋΠϨϕϧʹͳΓɺ. match ৴߸ ͼٴfail ৴߸ɺ੍ޚ৴߸ੜճ࿏ͷೖྗͰ. จࣈΛফඅ͢ΔɻҰํɺϚονࣦഊͨ͠߹ɺจࣈΛফඅ. ͋Γɺmatch ৴߸͕ϋΠϨϕϧͰ͋Εɺ࣍ͷΫϩοΫ͔. ͠ͳ͍͕ɺFail ॲཧ͕͜ىΒͣɺ࣍ͷ໋ྩʹਐΉɻઌಡΈ. Β৽ͨͳ໋ྩϑΣονΛ࣮ߦ͢ΔΑ͏ʹ੍ޚ৴߸͕ੜ͞. ໋ྩʢNByte, NSet) ͷ࣮ߦ Byte,Set ໋ྩͷ࣮ߦͱྨࣅ. ΕΔɻҰํɺfail ৴߸͕ϋΠϨϕϧͷ߹ɺFail ॲཧΛ࣮. ͢Δ͕ɺ͜ΕΒͷ໋ྩͰจࣈΛফඅ͠ͳ͍ɻ. ߦ͢Δ੍ޚ৴߸͕ੜ͞ΕΔɻFail ॲཧͰɺFail ελο Ϋ͔ΒσʔλΛϙοϓΞοϓ͠ɺͦͷσʔλΛ PR ʹసૹ ͠ɺ࣍ͷ໋ྩΞυϨεʹઃఆ͞ΕΔɻ. 4.3.3 ྩ໋ذ ʹྩ໋ذɺJump ໋ྩ͕͋ΔɻJump ໋ྩ࣮ߦͷλΠ Ϝνϟʔτਤ 6 ʹࣔ͢ͱ͓ΓͰ͋ΔɻE ঢ়ଶͰɺσίʔ υͨ݁͠ՌɺJump ໋ྩͷ࣮ߦͷτϦΨʔͰ͋Δ Jump r ͕ ϋΠϨϕϧʹͳΓɺPR ͷτϦΨʔͰ͋Δ PR lat ৴߸ϋ ΠϨϕϧʹͳΔɻ͜ͷͱ͖ɺΠϯΫϦϝϯτ৴߸ͷ PR inc ϩʔϨϕϧͰ͋ΔͨΊɺδϟϯϓઌͷΞυϨεΛ࣋ͬͯ ͍Δ PC data in ͷ͕ PR ͷʹஔ͖͑ΒΕΔɻ࣍ͷ ΫϩοΫαΠΫϧͰɺϝϞϦΞυϨεϨδελ addr ʹগ ͠Εͯ PR ͷ͕औΓࠐ·ΕΔɻ·ͨɺ࣍ͷΫϩοΫα ΠΫϧͷ্ཱ͕ͪΓͰ৽ͨͳ໋ྩϑΣον͕࢝·Δɻ. (a) Byte. (b) Rbyte. ਤ 5 Byte ໋ྩ ͼٴRbyte ໋ྩ࣮ߦͷλΠϜνϟʔτ. Byte ໋ྩɺIR Λ͍࣋ͬͯΔ̍จࣈͷσʔλͱ TR ͷ จࣈσʔλΛൺֱ͢Δͷʹରͯ͠ɺSet ໋ྩ TR ͷจࣈ͕ ෳͷจࣈͷதͷͲΕ͔ͱҰக͢Δ͔ΛධՁ͢Δ໋ྩͰ͋ ΔɻSet ໋ྩΛ࣮ߦ͢ΔͨΊʹɺSet ςʔϒϧΛ͏ɻSet ςʔϒϧෳͷ 256 Ϗοτྻ͔ΒͳΔɻ256 Ϗοτྻʹɺ. ASCII දͷ n ൪ͷจࣈͱϚονͤ͞ΔͳΒɺn Ϗοτ Λ’1’ ʹ͠ɺϚονͤ͞ͳ͍ͳΒɺ’0’ ʹ͢ΔɻSet ςʔϒ ϧ໋ྩͷόΠτίʔυͱಉ࣌ʹੜ͞Ε͍ͯΔɻ͜ͷΑ ͏ʹͯ͠ɺ༩͑ΒΕͨจࣈΛ Set ςʔϒϧʹরΒ͠߹Θͤ. ਤ 6 Jump ໋ྩ࣮ߦͷλΠϜνϟʔτ. ͯɺରԠͨ͠Ϗοτͷ͕’1’ Ͱ͋ΕϚονޭɺ’0’ Ͱ͋ΕϚονࣦഊͱͳΔɻ. 4.3.4 ελοΫૢ࡞໋ྩ ελοΫૢ࡞໋ྩʹɺCallɺAltɺReturnɺSucc ͕͋Δɻ. 4.3.2 ಛԽ໋ྩ. Non-Terminal Λͼݺग़໋͢ྩ͕ Call ໋ྩͰ͋ΓɺͦΕΛ. ಛԽ໋ྩ Rbyte ͷ࣮ߦͰɺF ঢ়ଶɺD ঢ়ଶ Byte ໋. ͼݺग़ͨ͠ϓϩάϥϜ࣮ߦ੍ޚΛฦ͢ͷ͕ Return ໋ྩͰ. ྩͱಉ༷Ͱ͋Δɻͦͷ༷ࢠਤ 5b ʹࣔ͢ͱ͓ΓͰ͋Δɻ. ͋ΔɻCall ໋ྩɺϓϩάϥϜϨδελ PR ͷΛ Return. Ex ঢ়ଶͰɺIR ͕͍࣋ͬͯΔ໋ྩͷରσʔλͱ TR ͷ. ελοΫʹϓογϡμϯͯ͠ୀආͤ͞ɺNon-Terminal ͷ. จࣈσʔλ͕Ұகͨ͠߹ɺnext txt ৴߸͕ϋΠϨϕϧ. ઌ಄൪Ͱ͋ΔΞυϨεΛ PR ʹసૹ͢ΔɻCall ໋ྩͷ࣮. ͱͳΔɻ͜ͷ߹ɺ࣍ͷΫϩοΫαΠΫϧͷ্ཱ͕ͪΓͰ. ߦ Jump ໋ྩͱࣅ͓ͯΓɺͨͩ͠৽ͨͳΞυϨεΛ PR. จࣈಡΈࠐΈ৴߸ͷ read txt ͕ϋΠϨϕϧͱͳΓɺFIFO. ʹసૹ͢Δͱಉ࣌ʹɺReturn ελοΫʹϓογϡμϯ. ͔Β 1 จࣈΛಡΈग़͢ɻ࣍ͷΫϩοΫαΠΫϧͰɺIR ͷ. Λߦ͏ɻ. ͍࣋ͬͯΔ໋ྩͷରσʔλͱ৽ͨͳ TR ͷจࣈσʔλΛ. Return ໋ྩɺCall ໋ྩʹΑͬͯελοΫʹୀආͨ͠. ൺֱ͢ΔɻҰக͢Εɺ·ͨ FIFO ͔Β৽ͨͳจࣈΛಡΈ. Non-Terminal ͔ΒͷΓ൪ΛϙοϓΞοϓͯ͠ PR . ࠐ·ΕΔɻIR ͷ͍࣋ͬͯΔ໋ྩͷରσʔλͱ TR ͷจ. సૹ͢Δɻ͜ΕʹΑͬͯɺNon-Terminal Λͼݺग़ͨ͠ϓ. ࣈσʔλ͕Ұக͠ͳ͘ͳΔ·Ͱɺ͜ͷॲཧ͕܁Γฦ͞ΕΔɻ. ϩάϥϜ࣮ߦ੍͕ޚฦ͞ΕΔɻReturn ໋ྩ࣮ߦͷλΠ. Ұக͠ͳ͍߹ɺnext ist ৴߸͕ϋΠϨϕϧͱͳΓɺ࣍ͷ. Ϝνϟʔτਤ 7 ʹࣔ͢ͱ͓ΓͰ͋Δɻ. ΫϩοΫ͔Β৽ͨͳ໋ྩϑΣονΛ࣮ߦ͢Δɻ Φϓγϣϯ໋ྩʢObyte, Oset) ಉ༷ʹ࣮ߦ͞ΕΔ͕ɺ. ⓒ 2016 Information Processing Society of Japan. E1 ঢ়ଶͷΫϩοΫαΠΫϧͷ্ཱ͕ͪΓͰɺReturn ໋ ྩ࣮ߦͷτϦΨʔͰ͋Δ Return r ৴߸͕ϋΠϨϕϧʹͳ. 4.
(5) Vol.2016-ARC-221 No.6 2016/8/8. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. ຊମͷ࣮Ͱ༻͍ͨϦιʔε༻ྔද 3 ʹࣔ͢ͱ͓ΓͰ ͋Δɻ ද 3 Ϧιʔε༻ྔ Ϧιʔεɹ. ༻ (%). ༻ྔɹ. ར༻Մೳɹ. LUT. 323. 17600. 1.84. FF. 196. 35200. 0.56. ϩδοΫηϧɹ. 565. 28000. 2.02. Ͱ࣌ݱɺ࢛ଇԋࢉΛද͢ͳͲͷ؆୯ͳ PEG ʹର͠ ͯɺਖ਼͘͠ಈ࡞͢Δ͜ͱ͕֬ೝͰ͖ͨɻද 3 ʹͨ͠ࡌهϦ ιʔε PEG ϑΝΠϧͼٴจࣈྻͷෳࡶʹґଘ͠ͳ͍ɻ ਤ 7 Return ໋ྩ࣮ߦͷλΠϜνϟʔτ. ͨͩ͠ɺBlockRAM ͷ༻ྔ PEG ϑΝΠϧͼٴจࣈྻ ͷෳࡶʹґଘ͢Δɻ. ΔɻಉΫϩοΫαΠΫϧͰ Return ελοΫͷಡΈग़͠৴ ߸ read stk ͕ϋΠϨϕϧʹͳΓɺσʔλ͕ data stk Ϩδ ελʹసૹ͞ΕΔɻ࣍ͷΫϩοΫαΠΫϧͰ PR ͷॻ͖ ͑σʔλ PC data in ʹগ͠Εͯ data stk ͷσʔλ͕औ Γࠐ·ΕΔɻ࣍ͷΫϩοΫαΠΫϧͷ্ཱ͕ͪΓͰ PR ͷ ৽ͨͳΞυϨεཱ͕֬͠ɺগ͠Ε໋ͯྩΞυϨεͷ addr Ϩδελʹసૹ͞ΕΔɻ͜ͷ࣌Ͱ Return ελοΫ͔Β ϙοϓΞοϓͨ͠ΞυϨε࣍ͷ໋ྩΛࢦ͢Α͏ʹͳΔɻ ࣍ʹ৽ͨͳ໋ྩϑΣον͕࢝·Δɻ ҰํɺPEG ͰɺόοΫτϥοΫ͕͋Δ [9], [11]ɻόο ΫτϥοΫɺબࢶͷதͰϚον͕ࣦഊͨ͠߹ɺલͷ ঢ়ଶʹΓɺผͷબࢶΛධՁ͢ΔΈͰ͋Δɻબ͕ ͋Δ߹ɺબࢶΛධՁ͢ΔલʹɺόΫτϥοΫ͕͜ىΔ. BlockRAM ɺ໋ྩྻྖҬɺελοΫྖҬɺSet ςʔϒ ϧͰΘΕ͍ͯΔɻ໋ྩྻྖҬ ͼٴSet ςʔϒϧʹ༻͍Β ΕΔϝϞϦྔ PEG ϑΝΠϧʹґଘ͢Δɻྫ͑ɺਤ 1 ʹ࢛ࣔ͢ଇԋࢉΛද͢ PEG ͷ߹ɺ4 ͭͷϧʔϧ͔Β 34 ͷ໋ྩ͕ੜ͞ΕΔɻҰͭͷ໋ྩ 16bit Ͱ͋ΔͨΊɺ໋ ྩྻྖҬʹ 34×16bit ͕ΘΕ͍ͯΔɻ·ͨɺSet ςʔϒ ϧʹ 3 ྻ͕ඞཁͰ͋Γɺͭ·Γ 3×256bit ͕ΘΕ͍ͯΔɻ ໋ྩྻྖҬ ͼٴSet ςʔϒϧͰΘΕΔ BlockRAM ߹ Ͱܭ1312bit ͱͳΓɺࡌ͞Εͨ 240KByte BlockRAM ͷ. 0.068%Ͱ͋Δɻ ҰํɺελοΫʹΘΕΔϝϞϦྔจࣈྻͷ͞ߏ ʹґଘ͢ΔͨΊɺͲͷఔͷϝϞϦΛ֬อ͢ΕΑ͍͔ ࠓޙͷ՝ͱͳΔɻ. ͱ͖ͷΓઌΛ Fail ελοΫʹϓογϡμϯ͢Δɻ͜ͷ ૢ࡞Λߦ͏ͷ Alt ໋ྩͰ͋Δɻ ·ͨɺͲ͔͜ͰϚον͕ࣦഊͨ͠߹ɺόοΫτϥοΫ ͕͜ىΔɻ͜ͷͱ͖ɺFail ॲཧ͕ߦΘΕɺFail ελοΫ͔ ΒϙοϓΞοϓ͞ΕͨΞυϨεΛ PR ʹసૹ͞Εɺ࣍ʹ࣮ ߦ͞ΕΔ໋ྩͷΞυϨεʹͳΔɻҰํɺແࣄʹϚονͰ͖ ͨ߹ɺଞͷબࢶΛධՁ͢Δඞཁ͕ͳ͘ͳΔͨΊɺFail ελοΫʹอଘͨ͠ΞυϨε͕আ͞ڈΕΔɻ͜ͷૢ࡞Λߦ ͏ͷ Succ ໋ྩͰ͋Δɻ. Alt ໋ྩͱ Succ ໋ྩͷಈ࡞ Call ໋ྩɺReturn ໋ྩͱ ࣅ͍ͯΔ͕ɺ྆ऀͷҧ͍ Alt ໋ྩͱ Succ ໋ྩ͕ελο ΫΛૢ࡞͢Δ͚ͩͰɺPR ʹσʔλΛసૹ͠ͳ͍Ͱ͋Δɻ. 6. ·ͱΊ ຊߘͰɺղੳදݱจ๏ʢPEGʣʹಛԽͨ͠ Virtual Ma-. chine ʹ͍ͭͯड़ͨɻඞཁ࠷খݶͷճ࿏͚ͩࡌ͠ɺ·ͨ PEG ԋࢉࢠʹಛԽͨ͠ճ࿏ʹΑΓɺίϯύΫτ͔ͭޮ ͕Α͍ϚονϯάϚγϯ͕࣮͖ͨͰݱɻVirtual Machine ຊମ͕ඇৗʹখ͍ͨ͞Ίɺಉ͡ FPGA ʹෳͷ Virtual. Machine ΛࡌͤɺฒྻͰಈ࡞ͤ͞Δ͜ͱʹΑͬͯɺߴ͍ε ϧʔϓοτͷϚονϯάϚγϯ͕ظͰ͖Δɻ Ͱ࣌ݱɺ࢛ଇԋࢉΛද͢ͳͲͷ؆୯ͳ PEG ϑΝΠ ϧʹରͯ͠ਖ਼͘͠ಈ࡞Ͱ͖ͨɻελοΫʹΘΕΔϝϞϦ ͷੵݟɺͼٴΑΓෳࡶͳσʔλߏΛॲཧͰ͖ΔΑ͏ʹճ ࿏Λ֦ு͢Δͷࠓޙͷ՝ͱͳΔɻ. 5. ੑೳධՁ ຊͰڀݚɺXilinx ࣾͷ Zynq xc7z010-1clg400c Λࡌ. ࢀߟจݙ. ͨ͠ Zynq-7000 ධՁϘʔυͰ࣮ͨ͠ɻ·ͨɺVHDL ʹΑ. [1]. Δ RLT هड़Ͱߦ͍ɺཧ߹ஔઢɺγϛϡϨʔγϣ. [2]. ϯͳͲʹ Vivado Suite Design 2015.3 Λ༻͍͍ͯΔɻΫ ϩοΫप 125MHz Ͱ͋Δɻ ϗετͱͷΠϯλʔϑΣʔεΛআ͍ͨ Virtual Machine. ⓒ 2016 Information Processing Society of Japan. [3]. Ford, B.: Parsing expression grammars: A recognitionbasedsyntactic foundation. In Proc. of POPL04, 2004. Ford, B.: Packrat Parsing and Parsing Expression Grammars Pages.http://bford.info/packrat/ Sidhu, R. and Prasanna, V.K.: Fast Regular Expression Matching using FPGAs. In Proc. of FCCM01, 2001.. 5.
(6) ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. [4]. [5] [6] [7]. [8]. [9]. [10] [11]. [12]. Vol.2016-ARC-221 No.6 2016/8/8. Yang, Y.E., Jiang, W. and Prasanna, V.K.: Compact Architecture for High Throughput Regular Expression Matching on FPGA. In Proc. of ANCS08, pp. 30-39, 2008. Medeiros, S. and Ierusalimschy, R.: A Parsing Machine for PEGs. In Proc. of DLS08, 2008. Kuramitsu, K.: Packrat Parsing with Elastic Sliding Window. In IPSJ Programming Meeting, 2014. Yamagaki, N., Sidhu, R. and Kamiya, S.: Highspeed regular expression matching engine using multicharacter nfa. In Proc. of FPL 08, 2008. Lin, C.H., Jiang, C.P. and Chang, S.C.: Optimization of Pattern Matching Circuits for Regular Expression on FPGA. In Proc. of IEEE TVLSI06, 2006. Aho, A. V., and Ullman, J. D.: The Theory of Parsing, Translation and Compiling, Vol. I,ʠParsingʡ. Prentice Hall, 1972. Kuramitsu, K.: Nez: practical open grammar language. In Proc. of ACM SPLASH/Onward 2016, 2016. Birman, A., and Ullman, J. D.: Parsing algorithms with backtrack. Information and Control 23, pp. 1âĂŞ34, 1973. Ford, B.: Packrat parsing: simple, powerful, lazy, linear time. In Proc.of ICFP02, pp. 36-47, 2002.. ⓒ 2016 Information Processing Society of Japan. 6.
(7)
関連したドキュメント
Gamma function; Beta function; Riemann-Liouville Fractional deriva- tive; Hypergeometric functions; Fox H-function; Generating functions; Mellin transform; Integral representations..
Its layer-to-layer transfer matrix is a polynomial of two spectral parameters, it may be re- garded in terms of quantum groups both as a sum of sl(N) transfer matrices of a chain
In this lecture, we aim at presenting a certain linear operator which is defined by means of the Hadamard product (or convolu- tion) with a generalized hypergeometric function and
It can be shown that cubic graphs with arbitrarily large girth exist (see Theorem 3.2) and so there is a well-defined integer µ 0 (g), the smallest number of vertices for which a
The key point is the concept of a Hamiltonian system, which, contrary to the usual approach, is not re- lated with a single Lagrangian, but rather with an Euler–Lagrange form
By employing the theory of topological degree, M -matrix and Lypunov functional, We have obtained some sufficient con- ditions ensuring the existence, uniqueness and global
In this work, we have applied Feng’s first-integral method to the two-component generalization of the reduced Ostrovsky equation, and found some new traveling wave solutions,
Thus, we use the results both to prove existence and uniqueness of exponentially asymptotically stable periodic orbits and to determine a part of their basin of attraction.. Let
