NTABWRD6X3E4M6TVAJVYWDS2P4NTLZDWBGCLCGFT5MEL3R2QBSNQC
3GHXO275SGZZSJ3S257MHVJHQSZGJ4OFMIE5FLP3J5ZQTS7WLWFAC
4THINMV4MX66Z4Y52WLGNXM47QYU3Q5NP4DFQBLFJ7JQ3FZONNNAC
U6I2FUUXVA6YPCDTWG6YRAPZONOOEQDPC55M2ASOPGR4YUT6H53AC
7YWAKRCSER4YX74DMLVXBXINQX6THDK3GYZFMMCCQGSBZN6H5UGQC
Y2IUROGFTA2S36WITVZPGR5XXO2OWWDPDHHM4QRGTKAQ3QDCRFXQC
G66Q553SEOS33IMFNC35Q6AGKFWXAJBP2TFPN2LRLAURFCGSOCZQC
5GF73GZXJXBUC2OVVLBGTLWDKSBA73SUOWVP3OSJWSCRW3WEKDWAC
SSIBGHOHPSNPZ2CF652OJTNJDPVRKKXNQAMC4346GDWC72IRADTAC
RTRQE7TUHKS5XI3ETGEHIEZ7VCPI2RL46PNY6YZWEHX2GO56W7DQC
KPGBRXJOHTJ2FM7X7PH26SNBXOKWRUQU6FVQAACX6A5LO75LKWLQC
Z76JVGG72BEI4JFDB2GKKUVZE66SRNDKYHAK26FSCFZ7K4DI562AC
PCJW5NAOLUWGKEXPKG6P2CEIVFRP3H4B2L3QVID7SO2XLAA5IBVAC
TDF6PHBBP3E72UHEV6SZCEV77P5SMERMKQQWBW3W2LHSP6IUIUWQC
/\abc
abab
\ cbbccababbbbcaabacaaaccacacccabacccccbca
/\/\/ acaabbbabccacacabbbccccabaccbbaabcbcaccb
\ abbcbcabbcbccbccaabbacacccccabbbbbbbabab
\ cbcacaabccbaaaccbccaaaacaaccaccaabcababb
\ bbbacabbaaccaabcccabaacababccccbcbbcacbc
/\/\/ cbbbcbbacbbcbabccccbbbaaaaabbccaccccbbac
/\/\/ bbaabaacacbabbacccacaaacbaabccabcccccaab
/\/\/ bcaaabcbbacabcbbabacbcccbaabaabcccabbacb
/\/\/ bbabbaccbbaccabbbbcccabbbaaaaabcaccbcaaa
/\/\/ acbaaabbbacccaaccbaacabbcbbbbcbbcbbacaba
/\/\/ bcacbbaacbbbacbcbabaccbcbccaaacbcbbabbaa
/\/\/ cbbcbbbcabaabcaaabcbacaaaaabaccacbacbbba
/\/\/ babcacbaabbcbcbbccacccbccabacbcabccaaabb
/\/\/ caacacaaaccbcbbbbbabbbccbbbbbbaacabbabca
\ cacaccabcacacabcacacaabbabaaabbcaaababac
\cababacbbcaabccaaabaabcbacccaccbcacacaaa
/bcaababbbbbcccacbccaacaccabcaaababbccccc
/\/\/ bcaaabbbacacbccaaabcacabcbbbcabaaabbbccb
/\/\/ bcaccbcbabcaccbaacbbbbaaaacbabbabacbabaa
/\/\/ acbcbcacccaaaacacacbbcabcaaaacaacaabacca
/ abcbabccabaacababaccbbcacbacacaccccaabcb
/\/\/ cbbcaaacccccccaaaccbacbabcbbcbbccbcabcaa
/ accbabaabaaccaacaababcbccbcbbaccabaacaaa
/\/\/ cbbabaaabaaccaabcaccabacbaacccbbcccaabac
/\/\/ aacabcbccbbaccabaacbaacbbbcaccaacccbaaba
/ abababcabbcaaaccaaacacaabbbcaaaaababcbac
/ accabccbaccabbcbbabcbbaccbcccbcabacbabab
/\/\/ caacbbacbacaaaacaccaaaccbaccacbaaaaaaaca
/\/\/ bcccabccbacbaacbbcacbccacbbccbacccbcbaab
/ aacccbbabbbbacccccaabcaaacbcababbccacaab
/\abcdef
ab|cde
\ bbfdfffedccabcfeaceb
\ dbaaeaaaedfcdebfadfe
\ bafdefaabfeeebabddda
/\/\/ eccdcacaaffddedfcfde
\ bcbffbdecedabbbacfee
\ ebadfebcdffdabcebafb
\eaabdbebafeeaacedfdd
/eabbdcffbbbccbafffee
/\/\/ cbbecaafebdecdfaebfd
/\/\/ fbdeeacaacfdeeddbbda
/ edbcdbabdcbedebbebca
/\/\/ ddfeaadceeefdbeecfed
/\/\/ baedafcdafdbebcaaadd
/\/\/ aebdaecaadcacbddfecd
/\/\/ ebcfadcdbdcdccffddde
/ faaaaefedceabbffaeaf
/ cdeecfcdacfbefffdfac
/\/\/ bbbcceffedcbdbffdcfd
/ ffeeabecbfdcbeedebba
/\/\/ dbebffadccdfaaddbebc
/\/\/ fcbbceaafeebcbedfbfe
/ ddaacdedeecfadbbdebe
/\/\/ fdbacacfeffcdcbdeeef
/ cccbadebcfabefdabdff
\ cbcecbfccbedcfabdebe
/\/\/ caddffccccfffbdffbed
/\/\/ aadeacecbacccecdbbbe
/\/\/ bccbffffdecfefeaccba
\ afefacfdbdbcdecebbad
\ ebefabdfecaffbccbfed
/\/\/ ffdddbbdfffdccbbddda
/\/\/ bbfdbeccaccafaafddfb
/\/\/ dddefddfbdeeffddcacd
/\/\/ fcdddcefbfebefdfdfdf
\ cccaeaccccbabdbeceaa
/\/\/ dbbcadaaaebcfcbaddba
/\/\/ bdfdfdebcebcbccebfaa
\ eeadeababebbbfbdfdec
\ dfaabbfecfafcaeaaafd
\bafcebcbabecafacbfba
/\abcd
a*bc*(ab)+
/\/\/ bacbbcdaccabbcaddabc
/\/\/ aadbcbadbbbbdbaaacaa
/\/\/ cadcacccbdabccbdcbcd
\ abaadbdbabbabdcaadba
/\/\/ dbdbacaccdccabccbacd
/\/\/ adcacbaccccbbbdbbbdb
/\/\/ bbdacaccbdccddabacdc
\ ddcbaabdcbabdabddbdc
/\/\/ cbacbcbaaddbcaaabccd
/\/\/ adbcdbacbbaccbcadbdd
/\/\/ cbaaaaccadcbdadcbaac
/\/\/ bcdbdbdacaccacaacddd
/\/\/ acdabdcbacbbbccdbcda
/\/\/ abbcbcaacbbccbdcbcbc
/\/\/ ccabadbccccbacdbaddb
/\/\/ baabadbcbcbdcaccaaaa
\ bdacaababdbbcaccadaa
\ ccababdbabbacbcbdddd
\ ddcaaaabdbcddbabaddd
\bdbadbaacdbbcbbbbabd
/\/\/ acbbccbbdacbddabdcad
/ccaddccbbbacbdadbaba
/ cbcdababbdbdbaacbcda
/\/\/ cddcbacdaacbbbdddbbc
/\/\/ bcbaabcccaddaaabbacd
/\/\/ ddbacdccccdadbdcacdc
/\/\/ bcdbdcaaacdaddabccbd
/ bddcdbabbacdbacdddab
/\/\/ bbaaabbcaacdbbccddaa
/\/\/ cadddddbdabaddaaacdc
/\/\/ ccccbdddcdacdbaabcac
/\/\/ acdbcdadabdbbcbcdacb
/\/\/ cadabacbbdcabcdadcca
/\/\/ ddbcbadddacaaaacbada
/ babddaaabbbacdccbaac
/ dabaaccabababcdcbbad
/\/\/ cdbcbbbcadcddaccdbca
/\/\/ aaadcacdcabaabaadbcb
/ bcabbddbbbcbacacaddc
/\/\/ dbadaddcaaaaaaadaaba
/\abcde
a+.+b?a+.+b+
/\/\/ dabcbbbcaacaeaccdddd
\ acadedbecccbaaeeccdb
\ ebdacbadabdbbcddceac
\ dbeceaeeaacceeabecbd
\ beabcadcadeaedbedcce
/\/\/ cebeadbacceceeccdaea
/\/\/ cbddedeabdbcddbbbebd
/\/\/ eebcbeeddbedcdbddcae
\ badeaddeaadaaeacdabe
\ebbedbebdeaebeebaaeb
/\/\/ bdeedcbaabeacecaeeaa
/cdeccaebaaacceebbcca
/ eeadabdabacabeaeddce
/\/\/ debdbbbcbeddbbdecead
/ bebcdeeacabeabdedcbc
/ beacbcbaaaaacaabcaee
/ ceeaebccecaedbcbebbc
/ dcaabaabedadbddccbab
/\/\/ eedcbcdcbcebcdaadade
/ cceeddbeaeecececdabb
/\/\/ ecceccedbebcaaedddcc
\ dcabdabdacaceeaceeeb
/\/\/ eeeebdecbdaededcecba
\ aaaaaacccdedcacceecb
/\/\/ eccebcdddbccdecbdccd
\ dbbdeddcccabadbedaee
\ bdedcbaebaeedacdedcb
\ abebbedaadacaeceebaa
\ cbaedcecbacbdcbbcbeb
\dbdcbedacccbaeddbbda
/\/\/ debbbecdacccbcbecccd
/ccbbbabbbbbacbbdaaab
/ cecaeabdccaabbbbccba
/ bcadaeaeccdebcddddca
/\/\/ dbbbbdacbdcedebaecdc
/ cdcbeeeaeeaacdaccbbe
/ ebcdadbdbddaeaaddacb
/ adcdebdcabebcddcbbeb
/\/\/ ddcccbcbdecebadbbdca
/ bcbadeebebdccecaedeb
/\abcde
abcd*|cba(abc)+|(abc)+(bdb)(abc)?|a.b.c.d|(((abc)+)+)+
\ acabecdabeaecadcaaaededabeccdeddbedcdeabcacdddeeecdeccdbbaae
/\/\/ acebaebaabeaaacebdcceabbdbeeebcacecedbbadaadccdaadccdbbaedcd
/\/\/ eacaddcadacbeebbbcdedadcccdadaaaadeebdcdcbbedeebdbecaddcebdb
/\/\/ cbbaabbdcccaacbbeaaebcbdebcddecbbceddcdeebddabaaeeedacbebedd
\ bacbabcedeebcbecbdebaabbeaeecacbcbddecdabdcedcdeddddbdaadecd
\ dbceebcbbbecbcbdeebcaceadeadbcadeebeeeebadecadbbadbccddacdac
/\/\/ beacdecbbedececdcbdddbceebdbddbeeceaaadeacbababdcbecabdaaadb
\ cdbabcecbeecceeebaecdedbdeaacaeadebdbbcadaaeccecdaccedaebcba
\ ebbdcbddddaddebabebddacdddccccaeadbdbdabceabcdecceecbceaeeac
/\/\/ cbedaeeeecaacbccbcdacacbcbdbacccbadeaadabdbeacbeadeaabbcdcae
\cbbccdccaacaaaddeabadaeabcacbcacbecebbcdaebebaedeebbaedaddee
/\/\/ aeadcbcaeeaebaeddabaeecbbacabbabbcaebbebbaccaedaabdadcbddbce
/\/\/ eadbeeabebeedbddddeebdeedbbbadeccddbdeeecdccdcecbcddecaacbca
/cededdacedbccabcedeeabbbcebaeabddebbbebbecaadcdaaaccededbddb
/\/\/ dcbcecbbecececaebdbdccbcdaebbedecadeebebbdcbadacbaedbbcacacb
/\/\/ dabeacedddeaaaacebdbdcabebecabddabeaeecbabbdcaccbbebaecebeac
/\/\/ dadbedbbaabeeddcabdcededecdaaedeecbdddbecacdedecebccdcdadeed
/\/\/ dababbeaedbccceaabdddacdcddcbcbdeaacbebeaaaddeeaeaeadceededd
/\/\/ debbbbebddedcaeeabebbdaeebaddaeadaceabddcbeaacbbbdadeecccedb
/\/\/ acdbbdeccdacdbdaabaaebcaaeebcacbcecbacbddbaaaabaadbccdbacddd
/\/\/ adbeaacbbeeccacbcceccccdeeecbbdeedabbadaaebbadbeecdbecdabbeb
/ cdabdcadbeaddaeeddabadbdacbcabaedcbcedabcbbbceccbaecccbcccde
/\/\/ caaebbdbeedbbdddcdbecbddcaecabbedbbcbaeccecaedbdadacdcdabedd
/ bcbaeabcbaacbdbddcdabecdcbcbeccdcebbeddbdcecbcdaaeeccabdecce
/\/\/ cadeadaebceadbdbccaaecbebdcbdaaddabdeeaebdbeaabbeebebebbdcee
/\/\/ acadcbcbacabdbbeebdbaaebebddcbbbabdeccccbcacbcbebcbdcceeacde
/ ecdeeaccdecccbccceaebddceaeebdbdbabdeecaeeecadabcdaedddeaebc
/ cebdeacdeabdeeabdbbcabcedebabbcddebdcedabaccdadbcebbdeddeacc
/ ccbbcbdbccacecdeaeedcbcddacaabccdebeadbebeaaaababceeecdcdcad
/\/\/ cebcebdcbccbceddaaaecccacecedbdacabaceabdadcceabebadcdbcdccd
/\/\/ ecaeaedebabdeeeaeaeacdbebcadabdeeadbdbddacbeaedcacbcbdbedaae
/\/\/ bcdcaccaecdeacecbeeebbabddebbeddecbbedbebedbbbbacebdcedddaac
/\/\/ dededdaceaaacebadabbdbebececbcbdbcdbdbecaeadedcccbecceaeccca
/\/\/ ceebaebdbaebebdcbaeacddedddcecccccacdaccbcadaadacecbbaabbbdb
/\/\/ dbdaddeacbbadcbdccbbccebbceaeedccddcaeedbecdaaeacaedbcdddebc
/ ddceeebeccdcabbabbcaebdeeccddbddaaedaddcaaeeebaeabcdcecdabcd
\ dadbbaceabcecbdbdebccceadbeecddacebaebecbbdaadcddbebbddeabdc
/\/\/ ebaacbbbedcbedaaaabdabeeaeadadeeeaeeabaadcbecabaabeeaceebdbb
/\/\/ aeeabddabdecbacdaeaddadbadadedaccaddddeadedbdbeeeabeedcecded
\ acbcbccddaececdeadcabeecedcabceeecbaadcceccdcbdacccacbcbeaae
/\/\/ edbcbdceedcebdbdbaadbeacedbcdaaedcedaeecdeaebabdcbbdcdbdeabe
/\/\/ bbdcccbabeccacdcbdaadaeeadcadedbacdcacddcdabeddacdcebdedbbba
/\/\/ bddaaeeeacedeaeadbdcaedbcbaedbcccbabbabaddeeabbcceaecbdaaaed
/\/\/ bdedaedaadceaabedaedaecbaaddbebcbaceebaedabdcaddccadbaabddbb
/\/\/ ddeeaaedaebbcdeaaccbccaadcdccdcbbdbdcaabdecdcbbebcccebdaebdc
/\/\/ aebabababdbdacadddbcaddccebabddccdcdaeeeadceaceaecaedabecbea
/\/\/ eababebaeddeadbbbbaacaeeceeacecedcdddbcadbcedddcaaacebdccdde
/\/\/ bccaeaebebecadaedeacebcdccbcaaadcdddcaaaeebdcabbbddebcddeeae
\ cbcacebabcbbdcaedaebcbacadeebaeecbbcecddabebacecdeceecaebded
\ cbacdcdecdacaadbbcceabcedbaeecedceddcadbebceddebaeeadcebcede
\ aaeeaebedebcdccedcecaabaceaacbcadaedaabccdabceeecccaedebecac
\ cdaaeabdbcbceebcbdabaeaaecacaebaceedebedacadadabaaaabccececb
/\/\/ caeedccdcaddaeeedbbacbeeecdabdbeebdccaadebdededbbebbbcbedbcc
\bbaebdbecdddabbbaabcbaeccedbbbcebbcacdaceeaaecdadaeceadadaaa
/eabbaaccabdbabcecdeaceabbaccebceabcdbdaccecedbcdcabdddcbdcda
/\/\/ eaadddbcbacbdeebacdbedaecdadcecebbddbdacdcababdecdcacccabdbb
/ ceaaaabdbadabdabcbeacdccadbedbdcbedebaaacbebecebbacbbdeeacdb
/\/\/ ddcbabdcebddecedadacdbbeceadcebaeacebcdddcbeacbecccebebacccd
/\/\/ bebccdbddcbeedbedddddcbccaeabaceecaaedbdceacebedeaedcdcdcbbd
/\/\/ dbdeedacaccaecebedbaeaaabadbbddaeeeeebdeccecaaabbbaceabaaccb
/\/\/ cdbdbcbeaddeedbcaacbdbeabaadbdbeeaaccacaeeaaccacabdbaebddcbe
/\/\/ adddccbcedeeeeadcbecebedeaaaabadcbaadebaeabbdaccbdbadeeccbed
/\/\/ ceaddadecacdadadbdadcbebdaddecbbaaebaecbccebbeaacabbcedeabad
/\/\/ bdbbbeadcaeabeacceeacbaabaedabbcbeeddbddadedcbbbeadeebedbadd
/ aeacebbaaeeeccdebccaaabceebacdeeccebebdaeddbdedacbdeceeecabe
/\/\/ edbccdabeceedcccabdcdccbbdacaeebeaccbbbbbaeaabdddccddebacbae
/ aeaabaedabceccbeaecbdbaadddaaaebececdeaabeacaacdadadaadccbdb
/\/\/ bdcceaacbddaccacbcaacdceecbdaecadccbaccedbaceaaaecaaccccaddd
/ abceeababeececccbbeaeebedbeaeebeddbebcaaaeacdbedbadabbbabbcb
/\/\/ aedaeecdcddedeaecaaacababadccacdccacccbbebbedacaaeadebedbddc
/ adbbabddbdbbdbcbcaebcceacdeeeabcccbabccabcdababebbcadcbcedec
/\/\/ dbeddbdceacabaeabeadedcebcdcecdecbababacecebeddcbacbacaedabb
/ ecbeebadcbeccabbbdacdcabaeadaebbdbbbddeeddadeacbdcedceeccced
/\/\/ debbcdbcbaceecedbbbabebdaacedebadbdbbbcebebecdacdecacdebeede
\ beceaababcedeeabbdacaddaceccebacbdebceacddbabebabccabaeaccae
\ ddadaacdaacbbcbbcdbedebdaeaddcadacbdceadbacbdbeabceadcbedbed
\ ebeccaccccbacaabcbbcabcdbcdcdaeaddbaddaecbabdbdabaecdacadeee
\ aebbbecddddbaeccdaabdddaabaadeeeecbadabaeebcedccabcdddbcaeec
/\/\/ beaeceaceadceccedebbeeecababdbbaadaeebdcbdeedacebbcdbbaacecc
/\/\/ eeedcaadacdcebcbcbbeaabaedaadbdeedbccbcaccbeeaedebcebbbaecbb
/\/\/ ceedceeddedbdbadbbaaecdcedabecccabaaeccecaadbdecbdecbeabedea
/\/\/ baaeceedadeeabeebecccdbabdaecaaccceedcbcddbebabdbbdeadccbebd
/\/\/ dceaeecdaaeeaccacaacdeaaecddedaaeccccccabdbdaabeadccbabdcdca
\ eeccdbcdbeeccabcdcabdeadaaadbdadaddeddadcbdadaddbcacbcaadecd
/\/\/ eeddedecabedcbeacecbbcedbccededcdaeaaacecedbbacddedccbceadbb
\ ddbabacbaabbbacdeabcbdededcddacdeebaddcbddadcaccbeebaadddeae
/\/\/ adccaddedeebcdcdebaadecccdbbcbbcbbdbeaddcaadadcdaccdbcbccdcd
/\/\/ ccaaebddeccbeebbebccbaebdbdcddeeeadddadbbdeadbaaeaebebcbdbaa
/\/\/ acbdbdacbcadebbaabebeecddcdcddeabdcedebabeeceaeebcecddcbcdcb
\eaedbeabccaadbaaedacecdbcbeaebeadbacebadaeeeabcaebbbecbeddbe
/edccaeeabcaeaddeeebbabbdabadabeeccbdeeeaacaceddacdddeaecedde
/ ccaaebbcddbdedbaeedcdecedeadceccbaebdcbecededbbeecdceaebdeee
/\/\/ dcbadcacaedccccbdcaccccedbabddeaedddbdbcbcdcecbdcabaecbdbbdc
/\/\/ eabdeeecdaceeeacacabbadccebaaaaacaceadedebeeedbddceababbadeb
/\/\/ eacdceeeebedcaaadcadbcbeebaaaaedcccabbdecececebdbdaddbdbacea
/\/\/ eecbeeebecdbebcacbebdbdbccaecdbdbeaacddeecdecabbdbeeadddebdd
/ bdcadbecaeabccbebdcdccbdebabaabbcbebaeadecdababaadddaaaababd
/\/\/ dbdbdacebcaaaeebdbadedcdceaeaebecececcdcbeeedbaebceebbebeabd
/ dccddeedaededbadcdaaaabdcaaaecaabebcdbabccabcebadbebbebddbcb
/\/\/ cdddedacaeeabaccecccbaabbeecbbabdacdbccdcaaddbcdacecbeeadbca
/\abc
abab
\ cbbccababbbbcaabacaaaccacacccabacccccbca
/\/\/ acaabbbabccacacabbbccccabaccbbaabcbcaccb
\ abbcbcabbcbccbccaabbacacccccabbbbbbbabab
\ cbcacaabccbaaaccbccaaaacaaccaccaabcababb
\ bbbacabbaaccaabcccabaacababccccbcbbcacbc
/\/\/ cbbbcbbacbbcbabccccbbbaaaaabbccaccccbbac
/\/\/ bbaabaacacbabbacccacaaacbaabccabcccccaab
/\/\/ bcaaabcbbacabcbbabacbcccbaabaabcccabbacb
/\/\/ bbabbaccbbaccabbbbcccabbbaaaaabcaccbcaaa
/\/\/ acbaaabbbacccaaccbaacabbcbbbbcbbcbbacaba
/\/\/ bcacbbaacbbbacbcbabaccbcbccaaacbcbbabbaa
/\/\/ cbbcbbbcabaabcaaabcbacaaaaabaccacbacbbba
/\/\/ babcacbaabbcbcbbccacccbccabacbcabccaaabb
/\/\/ caacacaaaccbcbbbbbabbbccbbbbbbaacabbabca
\ cacaccabcacacabcacacaabbabaaabbcaaababac
\cababacbbcaabccaaabaabcbacccaccbcacacaaa
/bcaababbbbbcccacbccaacaccabcaaababbccccc
/\/\/ bcaaabbbacacbccaaabcacabcbbbcabaaabbbccb
/\/\/ bcaccbcbabcaccbaacbbbbaaaacbabbabacbabaa
/\/\/ acbcbcacccaaaacacacbbcabcaaaacaacaabacca
/ abcbabccabaacababaccbbcacbacacaccccaabcb
/\/\/ cbbcaaacccccccaaaccbacbabcbbcbbccbcabcaa
/ accbabaabaaccaacaababcbccbcbbaccabaacaaa
/\/\/ cbbabaaabaaccaabcaccabacbaacccbbcccaabac
/\/\/ aacabcbccbbaccabaacbaacbbbcaccaacccbaaba
/ abababcabbcaaaccaaacacaabbbcaaaaababcbac
/ accabccbaccabbcbbabcbbaccbcccbcabacbabab
/\/\/ caacbbacbacaaaacaccaaaccbaccacbaaaaaaaca
/\/\/ bcccabccbacbaacbbcacbccacbbccbacccbcbaab
/ aacccbbabbbbacccccaabcaaacbcababbccacaab
/\abcdef
ab|cde
\ bbfdfffedccabcfeaceb
\ dbaaeaaaedfcdebfadfe
\ bafdefaabfeeebabddda
/\/\/ eccdcacaaffddedfcfde
\ bcbffbdecedabbbacfee
\ ebadfebcdffdabcebafb
\eaabdbebafeeaacedfdd
/eabbdcffbbbccbafffee
/\/\/ cbbecaafebdecdfaebfd
/\/\/ fbdeeacaacfdeeddbbda
/ edbcdbabdcbedebbebca
/\/\/ ddfeaadceeefdbeecfed
/\/\/ baedafcdafdbebcaaadd
/\/\/ aebdaecaadcacbddfecd
/\/\/ ebcfadcdbdcdccffddde
/ faaaaefedceabbffaeaf
/ cdeecfcdacfbefffdfac
/\/\/ bbbcceffedcbdbffdcfd
/ ffeeabecbfdcbeedebba
/\/\/ dbebffadccdfaaddbebc
/\/\/ fcbbceaafeebcbedfbfe
/ ddaacdedeecfadbbdebe
/\/\/ fdbacacfeffcdcbdeeef
/ cccbadebcfabefdabdff
\ cbcecbfccbedcfabdebe
/\/\/ caddffccccfffbdffbed
/\/\/ aadeacecbacccecdbbbe
/\/\/ bccbffffdecfefeaccba
\ afefacfdbdbcdecebbad
\ ebefabdfecaffbccbfed
/\/\/ ffdddbbdfffdccbbddda
/\/\/ bbfdbeccaccafaafddfb
/\/\/ dddefddfbdeeffddcacd
/\/\/ fcdddcefbfebefdfdfdf
\ cccaeaccccbabdbeceaa
/\/\/ dbbcadaaaebcfcbaddba
/\/\/ bdfdfdebcebcbccebfaa
\ eeadeababebbbfbdfdec
\ dfaabbfecfafcaeaaafd
\bafcebcbabecafacbfba
/\abcd
a*bc*(ab)+
/\/\/ bacbbcdaccabbcaddabc
/\/\/ aadbcbadbbbbdbaaacaa
/\/\/ cadcacccbdabccbdcbcd
\ abaadbdbabbabdcaadba
/\/\/ dbdbacaccdccabccbacd
/\/\/ adcacbaccccbbbdbbbdb
/\/\/ bbdacaccbdccddabacdc
\ ddcbaabdcbabdabddbdc
/\/\/ cbacbcbaaddbcaaabccd
/\/\/ adbcdbacbbaccbcadbdd
/\/\/ cbaaaaccadcbdadcbaac
/\/\/ bcdbdbdacaccacaacddd
/\/\/ acdabdcbacbbbccdbcda
/\/\/ abbcbcaacbbccbdcbcbc
/\/\/ ccabadbccccbacdbaddb
/\/\/ baabadbcbcbdcaccaaaa
\ bdacaababdbbcaccadaa
\ ccababdbabbacbcbdddd
\ ddcaaaabdbcddbabaddd
\bdbadbaacdbbcbbbbabd
/\/\/ acbbccbbdacbddabdcad
/ccaddccbbbacbdadbaba
/ cbcdababbdbdbaacbcda
/\/\/ cddcbacdaacbbbdddbbc
/\/\/ bcbaabcccaddaaabbacd
/\/\/ ddbacdccccdadbdcacdc
/\/\/ bcdbdcaaacdaddabccbd
/ bddcdbabbacdbacdddab
/\/\/ bbaaabbcaacdbbccddaa
/\/\/ cadddddbdabaddaaacdc
/\/\/ ccccbdddcdacdbaabcac
/\/\/ acdbcdadabdbbcbcdacb
/\/\/ cadabacbbdcabcdadcca
/\/\/ ddbcbadddacaaaacbada
/ babddaaabbbacdccbaac
/ dabaaccabababcdcbbad
/\/\/ cdbcbbbcadcddaccdbca
/\/\/ aaadcacdcabaabaadbcb
/ bcabbddbbbcbacacaddc
/\/\/ dbadaddcaaaaaaadaaba
/\abcde
a+.+b?a+.+b+
/\/\/ dabcbbbcaacaeaccdddd
\ acadedbecccbaaeeccdb
\ ebdacbadabdbbcddceac
\ dbeceaeeaacceeabecbd
\ beabcadcadeaedbedcce
/\/\/ cebeadbacceceeccdaea
/\/\/ cbddedeabdbcddbbbebd
/\/\/ eebcbeeddbedcdbddcae
\ badeaddeaadaaeacdabe
\ebbedbebdeaebeebaaeb
/\/\/ bdeedcbaabeacecaeeaa
/cdeccaebaaacceebbcca
/ eeadabdabacabeaeddce
/\/\/ debdbbbcbeddbbdecead
/ bebcdeeacabeabdedcbc
/ beacbcbaaaaacaabcaee
/ ceeaebccecaedbcbebbc
/ dcaabaabedadbddccbab
/\/\/ eedcbcdcbcebcdaadade
/ cceeddbeaeecececdabb
/\/\/ ecceccedbebcaaedddcc
\ dcabdabdacaceeaceeeb
/\/\/ eeeebdecbdaededcecba
\ aaaaaacccdedcacceecb
/\/\/ eccebcdddbccdecbdccd
\ dbbdeddcccabadbedaee
\ bdedcbaebaeedacdedcb
\ abebbedaadacaeceebaa
\ cbaedcecbacbdcbbcbeb
\dbdcbedacccbaeddbbda
/\/\/ debbbecdacccbcbecccd
/ccbbbabbbbbacbbdaaab
/ cecaeabdccaabbbbccba
/ bcadaeaeccdebcddddca
/\/\/ dbbbbdacbdcedebaecdc
/ cdcbeeeaeeaacdaccbbe
/ ebcdadbdbddaeaaddacb
/ adcdebdcabebcddcbbeb
/\/\/ ddcccbcbdecebadbbdca
/ bcbadeebebdccecaedeb
/\abcde
abcd*|cba(abc)+|(abc)+(bdb)(abc)?|a.b.c.d|(((abc)+)+)+
\ acabecdabeaecadcaaaededabeccdeddbedcdeabcacdddeeecdeccdbbaae
/\/\/ acebaebaabeaaacebdcceabbdbeeebcacecedbbadaadccdaadccdbbaedcd
/\/\/ eacaddcadacbeebbbcdedadcccdadaaaadeebdcdcbbedeebdbecaddcebdb
/\/\/ cbbaabbdcccaacbbeaaebcbdebcddecbbceddcdeebddabaaeeedacbebedd
\ bacbabcedeebcbecbdebaabbeaeecacbcbddecdabdcedcdeddddbdaadecd
\ dbceebcbbbecbcbdeebcaceadeadbcadeebeeeebadecadbbadbccddacdac
/\/\/ beacdecbbedececdcbdddbceebdbddbeeceaaadeacbababdcbecabdaaadb
\ cdbabcecbeecceeebaecdedbdeaacaeadebdbbcadaaeccecdaccedaebcba
\ ebbdcbddddaddebabebddacdddccccaeadbdbdabceabcdecceecbceaeeac
/\/\/ cbedaeeeecaacbccbcdacacbcbdbacccbadeaadabdbeacbeadeaabbcdcae
\cbbccdccaacaaaddeabadaeabcacbcacbecebbcdaebebaedeebbaedaddee
/\/\/ aeadcbcaeeaebaeddabaeecbbacabbabbcaebbebbaccaedaabdadcbddbce
/\/\/ eadbeeabebeedbddddeebdeedbbbadeccddbdeeecdccdcecbcddecaacbca
/cededdacedbccabcedeeabbbcebaeabddebbbebbecaadcdaaaccededbddb
/\/\/ dcbcecbbecececaebdbdccbcdaebbedecadeebebbdcbadacbaedbbcacacb
/\/\/ dabeacedddeaaaacebdbdcabebecabddabeaeecbabbdcaccbbebaecebeac
/\/\/ dadbedbbaabeeddcabdcededecdaaedeecbdddbecacdedecebccdcdadeed
/\/\/ dababbeaedbccceaabdddacdcddcbcbdeaacbebeaaaddeeaeaeadceededd
/\/\/ debbbbebddedcaeeabebbdaeebaddaeadaceabddcbeaacbbbdadeecccedb
/\/\/ acdbbdeccdacdbdaabaaebcaaeebcacbcecbacbddbaaaabaadbccdbacddd
/\/\/ adbeaacbbeeccacbcceccccdeeecbbdeedabbadaaebbadbeecdbecdabbeb
/ cdabdcadbeaddaeeddabadbdacbcabaedcbcedabcbbbceccbaecccbcccde
/\/\/ caaebbdbeedbbdddcdbecbddcaecabbedbbcbaeccecaedbdadacdcdabedd
/ bcbaeabcbaacbdbddcdabecdcbcbeccdcebbeddbdcecbcdaaeeccabdecce
/\/\/ cadeadaebceadbdbccaaecbebdcbdaaddabdeeaebdbeaabbeebebebbdcee
/\/\/ acadcbcbacabdbbeebdbaaebebddcbbbabdeccccbcacbcbebcbdcceeacde
/ ecdeeaccdecccbccceaebddceaeebdbdbabdeecaeeecadabcdaedddeaebc
/ cebdeacdeabdeeabdbbcabcedebabbcddebdcedabaccdadbcebbdeddeacc
/ ccbbcbdbccacecdeaeedcbcddacaabccdebeadbebeaaaababceeecdcdcad
/\/\/ cebcebdcbccbceddaaaecccacecedbdacabaceabdadcceabebadcdbcdccd
/\/\/ ecaeaedebabdeeeaeaeacdbebcadabdeeadbdbddacbeaedcacbcbdbedaae
/\/\/ bcdcaccaecdeacecbeeebbabddebbeddecbbedbebedbbbbacebdcedddaac
/\/\/ dededdaceaaacebadabbdbebececbcbdbcdbdbecaeadedcccbecceaeccca
/\/\/ ceebaebdbaebebdcbaeacddedddcecccccacdaccbcadaadacecbbaabbbdb
/\/\/ dbdaddeacbbadcbdccbbccebbceaeedccddcaeedbecdaaeacaedbcdddebc
/ ddceeebeccdcabbabbcaebdeeccddbddaaedaddcaaeeebaeabcdcecdabcd
\ dadbbaceabcecbdbdebccceadbeecddacebaebecbbdaadcddbebbddeabdc
/\/\/ ebaacbbbedcbedaaaabdabeeaeadadeeeaeeabaadcbecabaabeeaceebdbb
/\/\/ aeeabddabdecbacdaeaddadbadadedaccaddddeadedbdbeeeabeedcecded
\ acbcbccddaececdeadcabeecedcabceeecbaadcceccdcbdacccacbcbeaae
/\/\/ edbcbdceedcebdbdbaadbeacedbcdaaedcedaeecdeaebabdcbbdcdbdeabe
/\/\/ bbdcccbabeccacdcbdaadaeeadcadedbacdcacddcdabeddacdcebdedbbba
/\/\/ bddaaeeeacedeaeadbdcaedbcbaedbcccbabbabaddeeabbcceaecbdaaaed
/\/\/ bdedaedaadceaabedaedaecbaaddbebcbaceebaedabdcaddccadbaabddbb
/\/\/ ddeeaaedaebbcdeaaccbccaadcdccdcbbdbdcaabdecdcbbebcccebdaebdc
/\/\/ aebabababdbdacadddbcaddccebabddccdcdaeeeadceaceaecaedabecbea
/\/\/ eababebaeddeadbbbbaacaeeceeacecedcdddbcadbcedddcaaacebdccdde
/\/\/ bccaeaebebecadaedeacebcdccbcaaadcdddcaaaeebdcabbbddebcddeeae
\ cbcacebabcbbdcaedaebcbacadeebaeecbbcecddabebacecdeceecaebded
\ cbacdcdecdacaadbbcceabcedbaeecedceddcadbebceddebaeeadcebcede
\ aaeeaebedebcdccedcecaabaceaacbcadaedaabccdabceeecccaedebecac
\ cdaaeabdbcbceebcbdabaeaaecacaebaceedebedacadadabaaaabccececb
/\/\/ caeedccdcaddaeeedbbacbeeecdabdbeebdccaadebdededbbebbbcbedbcc
\bbaebdbecdddabbbaabcbaeccedbbbcebbcacdaceeaaecdadaeceadadaaa
/eabbaaccabdbabcecdeaceabbaccebceabcdbdaccecedbcdcabdddcbdcda
/\/\/ eaadddbcbacbdeebacdbedaecdadcecebbddbdacdcababdecdcacccabdbb
/ ceaaaabdbadabdabcbeacdccadbedbdcbedebaaacbebecebbacbbdeeacdb
/\/\/ ddcbabdcebddecedadacdbbeceadcebaeacebcdddcbeacbecccebebacccd
/\/\/ bebccdbddcbeedbedddddcbccaeabaceecaaedbdceacebedeaedcdcdcbbd
/\/\/ dbdeedacaccaecebedbaeaaabadbbddaeeeeebdeccecaaabbbaceabaaccb
/\/\/ cdbdbcbeaddeedbcaacbdbeabaadbdbeeaaccacaeeaaccacabdbaebddcbe
/\/\/ adddccbcedeeeeadcbecebedeaaaabadcbaadebaeabbdaccbdbadeeccbed
/\/\/ ceaddadecacdadadbdadcbebdaddecbbaaebaecbccebbeaacabbcedeabad
/\/\/ bdbbbeadcaeabeacceeacbaabaedabbcbeeddbddadedcbbbeadeebedbadd
/ aeacebbaaeeeccdebccaaabceebacdeeccebebdaeddbdedacbdeceeecabe
/\/\/ edbccdabeceedcccabdcdccbbdacaeebeaccbbbbbaeaabdddccddebacbae
/ aeaabaedabceccbeaecbdbaadddaaaebececdeaabeacaacdadadaadccbdb
/\/\/ bdcceaacbddaccacbcaacdceecbdaecadccbaccedbaceaaaecaaccccaddd
/ abceeababeececccbbeaeebedbeaeebeddbebcaaaeacdbedbadabbbabbcb
/\/\/ aedaeecdcddedeaecaaacababadccacdccacccbbebbedacaaeadebedbddc
/ adbbabddbdbbdbcbcaebcceacdeeeabcccbabccabcdababebbcadcbcedec
/\/\/ dbeddbdceacabaeabeadedcebcdcecdecbababacecebeddcbacbacaedabb
/ ecbeebadcbeccabbbdacdcabaeadaebbdbbbddeeddadeacbdcedceeccced
/\/\/ debbcdbcbaceecedbbbabebdaacedebadbdbbbcebebecdacdecacdebeede
\ beceaababcedeeabbdacaddaceccebacbdebceacddbabebabccabaeaccae
\ ddadaacdaacbbcbbcdbedebdaeaddcadacbdceadbacbdbeabceadcbedbed
\ ebeccaccccbacaabcbbcabcdbcdcdaeaddbaddaecbabdbdabaecdacadeee
\ aebbbecddddbaeccdaabdddaabaadeeeecbadabaeebcedccabcdddbcaeec
/\/\/ beaeceaceadceccedebbeeecababdbbaadaeebdcbdeedacebbcdbbaacecc
/\/\/ eeedcaadacdcebcbcbbeaabaedaadbdeedbccbcaccbeeaedebcebbbaecbb
/\/\/ ceedceeddedbdbadbbaaecdcedabecccabaaeccecaadbdecbdecbeabedea
/\/\/ baaeceedadeeabeebecccdbabdaecaaccceedcbcddbebabdbbdeadccbebd
/\/\/ dceaeecdaaeeaccacaacdeaaecddedaaeccccccabdbdaabeadccbabdcdca
\ eeccdbcdbeeccabcdcabdeadaaadbdadaddeddadcbdadaddbcacbcaadecd
/\/\/ eeddedecabedcbeacecbbcedbccededcdaeaaacecedbbacddedccbceadbb
\ ddbabacbaabbbacdeabcbdededcddacdeebaddcbddadcaccbeebaadddeae
/\/\/ adccaddedeebcdcdebaadecccdbbcbbcbbdbeaddcaadadcdaccdbcbccdcd
/\/\/ ccaaebddeccbeebbebccbaebdbdcddeeeadddadbbdeadbaaeaebebcbdbaa
/\/\/ acbdbdacbcadebbaabebeecddcdcddeabdcedebabeeceaeebcecddcbcdcb
\eaedbeabccaadbaaedacecdbcbeaebeadbacebadaeeeabcaebbbecbeddbe
/edccaeeabcaeaddeeebbabbdabadabeeccbdeeeaacaceddacdddeaecedde
/ ccaaebbcddbdedbaeedcdecedeadceccbaebdcbecededbbeecdceaebdeee
/\/\/ dcbadcacaedccccbdcaccccedbabddeaedddbdbcbcdcecbdcabaecbdbbdc
/\/\/ eabdeeecdaceeeacacabbadccebaaaaacaceadedebeeedbddceababbadeb
/\/\/ eacdceeeebedcaaadcadbcbeebaaaaedcccabbdecececebdbdaddbdbacea
/\/\/ eecbeeebecdbebcacbebdbdbccaecdbdbeaacddeecdecabbdbeeadddebdd
/ bdcadbecaeabccbebdcdccbdebabaabbcbebaeadecdababaadddaaaababd
/\/\/ dbdbdacebcaaaeebdbadedcdceaeaebecececcdcbeeedbaebceebbebeabd
/ dccddeedaededbadcdaaaabdcaaaecaabebcdbabccabcebadbebbebddbcb
/\/\/ cdddedacaeeabaccecccbaabbeecbbabdacdbccdcaaddbcdacecbeeadbca
mod tokenizer {
#[derive(Debug, PartialEq, Eq)]
pub enum Token {
Char(u8), // A-Z a-z
Dot, // .
Alt, // |
Star, // *
Plus, // +
Quest, // ?
Lpar, // (
Rpar, // )
}
#[derive(Debug, PartialEq)]
pub enum TokenError {
NotAccepted(u8),
Miscellaneous(String),
}
pub fn map(input: u8) -> Result<Token, TokenError> {
if input.is_ascii() {
Ok(match input {
b'.' => Token::Dot,
b'|' => Token::Alt,
b'*' => Token::Star,
b'+' => Token::Plus,
b'?' => Token::Quest,
b'(' => Token::Lpar,
b')' => Token::Rpar,
x => Token::Char(x)
})
} else {
Err(TokenError::NotAccepted(input))
}
}
pub fn scan(input: &[u8]) -> Result<Vec<Token>, (TokenError, usize)> {
input
.iter()
.cloned()
.enumerate()
.map(|(pos, inp)| map(inp).map_err(|err| (err, pos)))
.collect()
}
#[cfg(test)]
mod tests {
use super::{map, Token};
#[test]
fn match_dot() {
assert_eq!(map(b'.'), Ok(Token::Dot))
}
#[test]
fn match_alternation() {
assert_eq!(map(b'|'), Ok(Token::Alt))
}
#[test]
fn match_star() {
assert_eq!(map(b'*'), Ok(Token::Star))
}
#[test]
fn match_plus() {
assert_eq!(map(b'+'), Ok(Token::Plus))
}
#[test]
fn match_question() {
assert_eq!(map(b'?'), Ok(Token::Quest))
}
#[test]
fn match_left_parenthesis() {
assert_eq!(map(b'('), Ok(Token::Lpar))
}
#[test]
fn match_right_parenthesis() {
assert_eq!(map(b')'), Ok(Token::Rpar))
}
#[test]
fn match_ascii() {
assert_eq!(map(b'a'), Ok(Token::Char(b'a')))
}
}
}
mod tokenizer {
#[derive(Debug, PartialEq, Eq)]
pub enum Token {
Char(u8), // A-Z a-z
Dot, // .
Alt, // |
Star, // *
Plus, // +
Quest, // ?
Lpar, // (
Rpar, // )
}
#[derive(Debug, PartialEq)]
pub enum TokenError {
NotAccepted(u8),
Miscellaneous(String),
}
pub fn map(input: u8) -> Result<Token, TokenError> {
if input.is_ascii() {
Ok(match input {
b'.' => Token::Dot,
b'|' => Token::Alt,
b'*' => Token::Star,
b'+' => Token::Plus,
b'?' => Token::Quest,
b'(' => Token::Lpar,
b')' => Token::Rpar,
x => Token::Char(x)
})
} else {
Err(TokenError::NotAccepted(input))
}
}
pub fn scan(input: &[u8]) -> Result<Vec<(Token, usize)>, (TokenError, usize)> {
input
.iter()
.cloned()
.enumerate()
.map(|(pos, inp)| map(inp)
.map(|tok| (tok, pos))
.map_err(|err| (err, pos)))
.collect()
}
#[cfg(test)]
mod tests {
use super::{map, Token};
#[test]
fn match_dot() {
assert_eq!(map(b'.'), Ok(Token::Dot))
}
#[test]
fn match_alternation() {
assert_eq!(map(b'|'), Ok(Token::Alt))
}
#[test]
fn match_star() {
assert_eq!(map(b'*'), Ok(Token::Star))
}
#[test]
fn match_plus() {
assert_eq!(map(b'+'), Ok(Token::Plus))
}
#[test]
fn match_question() {
assert_eq!(map(b'?'), Ok(Token::Quest))
}
#[test]
fn match_left_parenthesis() {
assert_eq!(map(b'('), Ok(Token::Lpar))
}
#[test]
fn match_right_parenthesis() {
assert_eq!(map(b')'), Ok(Token::Rpar))
}
#[test]
fn match_ascii() {
assert_eq!(map(b'a'), Ok(Token::Char(b'a')))
}
}
}
pub enum Expr {
Conc(Box<Expr>, Box<Expr>),
Alt(Box<Expr>, Box<Expr>),
Star(Box<Expr>),
Quest(Box<Expr>),
Char(u8),
Dot
}
pub enum ParseError {
TokenError((tokenizer::TokenError, usize)),
UnexpectedEnd
}
type Result = std::result::Result<Expr, ParseError>;
pub fn parse(input: &[u8]) -> Result {
let mut tokens = tokenizer::scan(input)
.map_err(|x| ParseError::TokenError(x))?
.into_iter()
.peekable();
parse_expr(&mut tokens)
}
fn parse_expr(tokens: &mut Peekable<IntoIter<(Token, usize)>>) -> Result {
let left = parse_term(tokens)?;
parse_expr_inner(tokens, left)
}
fn parse_expr_inner(tokens: &mut Peekable<IntoIter<(Token, usize)>>, left: Expr) -> Result {
if matches!(tokens.peek(), Some((Token::Alt, _))) {
let _ = tokens.next().unwrap();
let right = parse_term(tokens)?;
let expr = Expr::Alt(Box::new(left), Box::new(right));
}
fn parse_term(tokens: &mut Peekable<IntoIter<(Token, usize)>>) -> Result {
let left = parse_factor(tokens)?;
parse_term_inner(tokens, left)
}
fn parse_term_inner(tokens: &mut Peekable<IntoIter<(Token, usize)>>, left: Expr) -> Result {
if matches!(tokens.peek(), Some((Token::Char(_), _)) | Some((Token::Dot, _))) {
let right = parse_factor(tokens)?;
let expr = Expr::Conc(Box::new(left), Box::new(right));
parse_term_inner(tokens, expr)
} else {
Ok(left)
}
}
fn parse_factor(tokens: &mut Peekable<IntoIter<(Token, usize)>>) -> Result {
match tokens.next() {
Some((Token::Star, _)) => {
Ok(Expr::Star(()))
}
_ => Err(ParseError::UnexpectedEnd)
}
}
#[cfg(test)]
mod tests {
use crate::parser::{parse, Expr};
#[test]
fn parse_ascii() {
assert_eq!(parse(b"a"), Ok(Expr::Char(b'b')))
}
#[test]
fn parse_dot() {
assert_eq!(parse(b"."), Ok(Expr::Dot))
}
#[test]
fn parse_concatenation() {
assert_eq!(parse(b"ab"), Ok(Expr::Conc(Box::new(Expr::Char(b'a')), Box::new(Expr::Char(b'b')))));
}
#[test]
fn parse_alternation() {
assert_eq!(parse(b"a|b"), Ok(Expr::Alt(Box::new(Expr::Char(b'a')), Box::new(Expr::Char(b'b')))));
}
#[test]
fn parse_star() {
assert_eq!(parse(b"a*"), Ok(Expr::Star(Box::new(Expr::Char(b'a')))))
}
#[test]
fn parse_plus() {
assert_eq!(
parse(b"a+"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Star(
Box::new(Expr::Char(b'a')))))))
}
#[test]
fn parse_question() {
assert_eq!(parse(b"a?"), Ok(Expr::Quest(Box::new(Expr::Char(b'a')))))
}
#[test]
fn parse_star_before_concatenation() {
assert_eq!(
parse(b"ab*"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Star(
Box::new(Expr::Char(b'b')))
))
)
)
}
#[test]
fn parse_quest_before_concatenation() {
assert_eq!(
parse(b"ab*"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Quest(
Box::new(Expr::Char(b'b')))
))
)
)
}
#[test]
fn parse_plus_before_concatenation() {
assert_eq!(
parse(b"ab+"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Quest(
Box::new(Expr::Char(b'b')))
))
)
)
}
#[test]
fn no_star_after_alternation() {
assert!(matches!(
parse(b"|*"),
Err(_)
))
}
#[test]
fn no_plus_after_alternation() {
assert!(matches!(
parse(b"|+"),
Err(_)
))
}
#[test]
fn no_quest_after_alternation() {
assert!(matches!(
parse(b"|?"),
Err(_)
))
}
Err(_)
))
}
#[test]
fn no_lone_star() {
assert!(matches!(
parse(b"*"),
Err(_)
))
}
#[test]
fn no_lone_plus() {
assert!(matches!(
parse(b"+"),
Err(_)
))
}
#[test]
fn no_lone_question() {
assert!(matches!(
parse(b"?"),
}
parse_expr_inner(tokens, expr)
} else {
Ok(left)
}
#[derive(Debug, PartialEq)]
#[derive(Debug, PartialEq)]
use std::{iter::Peekable, vec::IntoIter};
use tokenizer::Token;
fn main() {
println!("Hello, world!");
}
[package]
name = "lab2"
version = "0.1.0"
edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
.git
.DS_Store
# Added by cargo
/target
/\abcde
abcd*|cba(abc)+|(abc)+(bdb)(abc)?|a.b.c.d|(((abc)+)+)+
\ acabecdabeaecadcaaaededabeccdeddbedcdeabcacdddeeecdeccdbbaae
/\/\/ acebaebaabeaaacebdcceabbdbeeebcacecedbbadaadccdaadccdbbaedcd
/\/\/ eacaddcadacbeebbbcdedadcccdadaaaadeebdcdcbbedeebdbecaddcebdb
/\/\/ cbbaabbdcccaacbbeaaebcbdebcddecbbceddcdeebddabaaeeedacbebedd
\ bacbabcedeebcbecbdebaabbeaeecacbcbddecdabdcedcdeddddbdaadecd
\ dbceebcbbbecbcbdeebcaceadeadbcadeebeeeebadecadbbadbccddacdac
/\/\/ beacdecbbedececdcbdddbceebdbddbeeceaaadeacbababdcbecabdaaadb
\ cdbabcecbeecceeebaecdedbdeaacaeadebdbbcadaaeccecdaccedaebcba
\ ebbdcbddddaddebabebddacdddccccaeadbdbdabceabcdecceecbceaeeac
/\/\/ cbedaeeeecaacbccbcdacacbcbdbacccbadeaadabdbeacbeadeaabbcdcae
\cbbccdccaacaaaddeabadaeabcacbcacbecebbcdaebebaedeebbaedaddee
/\/\/ aeadcbcaeeaebaeddabaeecbbacabbabbcaebbebbaccaedaabdadcbddbce
/\/\/ eadbeeabebeedbddddeebdeedbbbadeccddbdeeecdccdcecbcddecaacbca
/cededdacedbccabcedeeabbbcebaeabddebbbebbecaadcdaaaccededbddb
/\/\/ dcbcecbbecececaebdbdccbcdaebbedecadeebebbdcbadacbaedbbcacacb
/\/\/ dabeacedddeaaaacebdbdcabebecabddabeaeecbabbdcaccbbebaecebeac
/\/\/ dadbedbbaabeeddcabdcededecdaaedeecbdddbecacdedecebccdcdadeed
/\/\/ dababbeaedbccceaabdddacdcddcbcbdeaacbebeaaaddeeaeaeadceededd
/\/\/ debbbbebddedcaeeabebbdaeebaddaeadaceabddcbeaacbbbdadeecccedb
/\/\/ acdbbdeccdacdbdaabaaebcaaeebcacbcecbacbddbaaaabaadbccdbacddd
/\/\/ adbeaacbbeeccacbcceccccdeeecbbdeedabbadaaebbadbeecdbecdabbeb
/ cdabdcadbeaddaeeddabadbdacbcabaedcbcedabcbbbceccbaecccbcccde
/\/\/ caaebbdbeedbbdddcdbecbddcaecabbedbbcbaeccecaedbdadacdcdabedd
/ bcbaeabcbaacbdbddcdabecdcbcbeccdcebbeddbdcecbcdaaeeccabdecce
/\/\/ cadeadaebceadbdbccaaecbebdcbdaaddabdeeaebdbeaabbeebebebbdcee
/\/\/ acadcbcbacabdbbeebdbaaebebddcbbbabdeccccbcacbcbebcbdcceeacde
/ ecdeeaccdecccbccceaebddceaeebdbdbabdeecaeeecadabcdaedddeaebc
/ cebdeacdeabdeeabdbbcabcedebabbcddebdcedabaccdadbcebbdeddeacc
/ ccbbcbdbccacecdeaeedcbcddacaabccdebeadbebeaaaababceeecdcdcad
/\/\/ cebcebdcbccbceddaaaecccacecedbdacabaceabdadcceabebadcdbcdccd
/\/\/ ecaeaedebabdeeeaeaeacdbebcadabdeeadbdbddacbeaedcacbcbdbedaae
/\/\/ bcdcaccaecdeacecbeeebbabddebbeddecbbedbebedbbbbacebdcedddaac
/\/\/ dededdaceaaacebadabbdbebececbcbdbcdbdbecaeadedcccbecceaeccca
/\/\/ ceebaebdbaebebdcbaeacddedddcecccccacdaccbcadaadacecbbaabbbdb
/\/\/ dbdaddeacbbadcbdccbbccebbceaeedccddcaeedbecdaaeacaedbcdddebc
/ ddceeebeccdcabbabbcaebdeeccddbddaaedaddcaaeeebaeabcdcecdabcd
\ dadbbaceabcecbdbdebccceadbeecddacebaebecbbdaadcddbebbddeabdc
/\/\/ ebaacbbbedcbedaaaabdabeeaeadadeeeaeeabaadcbecabaabeeaceebdbb
/\/\/ aeeabddabdecbacdaeaddadbadadedaccaddddeadedbdbeeeabeedcecded
\ acbcbccddaececdeadcabeecedcabceeecbaadcceccdcbdacccacbcbeaae
/\/\/ edbcbdceedcebdbdbaadbeacedbcdaaedcedaeecdeaebabdcbbdcdbdeabe
/\/\/ bbdcccbabeccacdcbdaadaeeadcadedbacdcacddcdabeddacdcebdedbbba
/\/\/ bddaaeeeacedeaeadbdcaedbcbaedbcccbabbabaddeeabbcceaecbdaaaed
/\/\/ bdedaedaadceaabedaedaecbaaddbebcbaceebaedabdcaddccadbaabddbb
/\/\/ ddeeaaedaebbcdeaaccbccaadcdccdcbbdbdcaabdecdcbbebcccebdaebdc
/\/\/ aebabababdbdacadddbcaddccebabddccdcdaeeeadceaceaecaedabecbea
/\/\/ eababebaeddeadbbbbaacaeeceeacecedcdddbcadbcedddcaaacebdccdde
/\/\/ bccaeaebebecadaedeacebcdccbcaaadcdddcaaaeebdcabbbddebcddeeae
\ cbcacebabcbbdcaedaebcbacadeebaeecbbcecddabebacecdeceecaebded
\ cbacdcdecdacaadbbcceabcedbaeecedceddcadbebceddebaeeadcebcede
\ aaeeaebedebcdccedcecaabaceaacbcadaedaabccdabceeecccaedebecac
\ cdaaeabdbcbceebcbdabaeaaecacaebaceedebedacadadabaaaabccececb
/\/\/ caeedccdcaddaeeedbbacbeeecdabdbeebdccaadebdededbbebbbcbedbcc
\bbaebdbecdddabbbaabcbaeccedbbbcebbcacdaceeaaecdadaeceadadaaa
/eabbaaccabdbabcecdeaceabbaccebceabcdbdaccecedbcdcabdddcbdcda
/\/\/ eaadddbcbacbdeebacdbedaecdadcecebbddbdacdcababdecdcacccabdbb
/ ceaaaabdbadabdabcbeacdccadbedbdcbedebaaacbebecebbacbbdeeacdb
/\/\/ ddcbabdcebddecedadacdbbeceadcebaeacebcdddcbeacbecccebebacccd
/\/\/ bebccdbddcbeedbedddddcbccaeabaceecaaedbdceacebedeaedcdcdcbbd
/\/\/ dbdeedacaccaecebedbaeaaabadbbddaeeeeebdeccecaaabbbaceabaaccb
/\/\/ cdbdbcbeaddeedbcaacbdbeabaadbdbeeaaccacaeeaaccacabdbaebddcbe
/\/\/ adddccbcedeeeeadcbecebedeaaaabadcbaadebaeabbdaccbdbadeeccbed
/\/\/ ceaddadecacdadadbdadcbebdaddecbbaaebaecbccebbeaacabbcedeabad
/\/\/ bdbbbeadcaeabeacceeacbaabaedabbcbeeddbddadedcbbbeadeebedbadd
/ aeacebbaaeeeccdebccaaabceebacdeeccebebdaeddbdedacbdeceeecabe
/\/\/ edbccdabeceedcccabdcdccbbdacaeebeaccbbbbbaeaabdddccddebacbae
/ aeaabaedabceccbeaecbdbaadddaaaebececdeaabeacaacdadadaadccbdb
/\/\/ bdcceaacbddaccacbcaacdceecbdaecadccbaccedbaceaaaecaaccccaddd
/ abceeababeececccbbeaeebedbeaeebeddbebcaaaeacdbedbadabbbabbcb
/\/\/ aedaeecdcddedeaecaaacababadccacdccacccbbebbedacaaeadebedbddc
/ adbbabddbdbbdbcbcaebcceacdeeeabcccbabccabcdababebbcadcbcedec
/\/\/ dbeddbdceacabaeabeadedcebcdcecdecbababacecebeddcbacbacaedabb
/ ecbeebadcbeccabbbdacdcabaeadaebbdbbbddeeddadeacbdcedceeccced
/\/\/ debbcdbcbaceecedbbbabebdaacedebadbdbbbcebebecdacdecacdebeede
\ beceaababcedeeabbdacaddaceccebacbdebceacddbabebabccabaeaccae
\ ddadaacdaacbbcbbcdbedebdaeaddcadacbdceadbacbdbeabceadcbedbed
\ ebeccaccccbacaabcbbcabcdbcdcdaeaddbaddaecbabdbdabaecdacadeee
\ aebbbecddddbaeccdaabdddaabaadeeeecbadabaeebcedccabcdddbcaeec
/\/\/ beaeceaceadceccedebbeeecababdbbaadaeebdcbdeedacebbcdbbaacecc
/\/\/ eeedcaadacdcebcbcbbeaabaedaadbdeedbccbcaccbeeaedebcebbbaecbb
/\/\/ ceedceeddedbdbadbbaaecdcedabecccabaaeccecaadbdecbdecbeabedea
/\/\/ baaeceedadeeabeebecccdbabdaecaaccceedcbcddbebabdbbdeadccbebd
/\/\/ dceaeecdaaeeaccacaacdeaaecddedaaeccccccabdbdaabeadccbabdcdca
\ eeccdbcdbeeccabcdcabdeadaaadbdadaddeddadcbdadaddbcacbcaadecd
/\/\/ eeddedecabedcbeacecbbcedbccededcdaeaaacecedbbacddedccbceadbb
\ ddbabacbaabbbacdeabcbdededcddacdeebaddcbddadcaccbeebaadddeae
/\/\/ adccaddedeebcdcdebaadecccdbbcbbcbbdbeaddcaadadcdaccdbcbccdcd
/\/\/ ccaaebddeccbeebbebccbaebdbdcddeeeadddadbbdeadbaaeaebebcbdbaa
/\/\/ acbdbdacbcadebbaabebeecddcdcddeabdcedebabeeceaeebcecddcbcdcb
\eaedbeabccaadbaaedacecdbcbeaebeadbacebadaeeeabcaebbbecbeddbe
/edccaeeabcaeaddeeebbabbdabadabeeccbdeeeaacaceddacdddeaecedde
/ ccaaebbcddbdedbaeedcdecedeadceccbaebdcbecededbbeecdceaebdeee
/\/\/ dcbadcacaedccccbdcaccccedbabddeaedddbdbcbcdcecbdcabaecbdbbdc
/\/\/ eabdeeecdaceeeacacabbadccebaaaaacaceadedebeeedbddceababbadeb
/\/\/ eacdceeeebedcaaadcadbcbeebaaaaedcccabbdecececebdbdaddbdbacea
/\/\/ eecbeeebecdbebcacbebdbdbccaecdbdbeaacddeecdecabbdbeeadddebdd
/ bdcadbecaeabccbebdcdccbdebabaabbcbebaeadecdababaadddaaaababd
/\/\/ dbdbdacebcaaaeebdbadedcdceaeaebecececcdcbeeedbaebceebbebeabd
/ dccddeedaededbadcdaaaabdcaaaecaabebcdbabccabcebadbebbebddbcb
/\/\/ cdddedacaeeabaccecccbaabbeecbbabdacdbccdcaaddbcdacecbeeadbca
/\abcde
a+.+b?a+.+b+
/\/\/ dabcbbbcaacaeaccdddd
\ acadedbecccbaaeeccdb
\ ebdacbadabdbbcddceac
\ dbeceaeeaacceeabecbd
\ beabcadcadeaedbedcce
/\/\/ cebeadbacceceeccdaea
/\/\/ cbddedeabdbcddbbbebd
/\/\/ eebcbeeddbedcdbddcae
\ badeaddeaadaaeacdabe
\ebbedbebdeaebeebaaeb
/\/\/ bdeedcbaabeacecaeeaa
/cdeccaebaaacceebbcca
/ eeadabdabacabeaeddce
/\/\/ debdbbbcbeddbbdecead
/ bebcdeeacabeabdedcbc
/ beacbcbaaaaacaabcaee
/ ceeaebccecaedbcbebbc
/ dcaabaabedadbddccbab
/\/\/ eedcbcdcbcebcdaadade
/ cceeddbeaeecececdabb
/\/\/ ecceccedbebcaaedddcc
\ dcabdabdacaceeaceeeb
/\/\/ eeeebdecbdaededcecba
\ aaaaaacccdedcacceecb
/\/\/ eccebcdddbccdecbdccd
\ dbbdeddcccabadbedaee
\ bdedcbaebaeedacdedcb
\ abebbedaadacaeceebaa
\ cbaedcecbacbdcbbcbeb
\dbdcbedacccbaeddbbda
/\/\/ debbbecdacccbcbecccd
/ccbbbabbbbbacbbdaaab
/ cecaeabdccaabbbbccba
/ bcadaeaeccdebcddddca
/\/\/ dbbbbdacbdcedebaecdc
/ cdcbeeeaeeaacdaccbbe
/ ebcdadbdbddaeaaddacb
/ adcdebdcabebcddcbbeb
/\/\/ ddcccbcbdecebadbbdca
/ bcbadeebebdccecaedeb
/\abcd
a*bc*(ab)+
/\/\/ bacbbcdaccabbcaddabc
/\/\/ aadbcbadbbbbdbaaacaa
/\/\/ cadcacccbdabccbdcbcd
\ abaadbdbabbabdcaadba
/\/\/ dbdbacaccdccabccbacd
/\/\/ adcacbaccccbbbdbbbdb
/\/\/ bbdacaccbdccddabacdc
\ ddcbaabdcbabdabddbdc
/\/\/ cbacbcbaaddbcaaabccd
/\/\/ adbcdbacbbaccbcadbdd
/\/\/ cbaaaaccadcbdadcbaac
/\/\/ bcdbdbdacaccacaacddd
/\/\/ acdabdcbacbbbccdbcda
/\/\/ abbcbcaacbbccbdcbcbc
/\/\/ ccabadbccccbacdbaddb
/\/\/ baabadbcbcbdcaccaaaa
\ bdacaababdbbcaccadaa
\ ccababdbabbacbcbdddd
\ ddcaaaabdbcddbabaddd
\bdbadbaacdbbcbbbbabd
/\/\/ acbbccbbdacbddabdcad
/ccaddccbbbacbdadbaba
/ cbcdababbdbdbaacbcda
/\/\/ cddcbacdaacbbbdddbbc
/\/\/ bcbaabcccaddaaabbacd
/\/\/ ddbacdccccdadbdcacdc
/\/\/ bcdbdcaaacdaddabccbd
/ bddcdbabbacdbacdddab
/\/\/ bbaaabbcaacdbbccddaa
/\/\/ cadddddbdabaddaaacdc
/\/\/ ccccbdddcdacdbaabcac
/\/\/ acdbcdadabdbbcbcdacb
/\/\/ cadabacbbdcabcdadcca
/\/\/ ddbcbadddacaaaacbada
/ babddaaabbbacdccbaac
/ dabaaccabababcdcbbad
/\/\/ cdbcbbbcadcddaccdbca
/\/\/ aaadcacdcabaabaadbcb
/ bcabbddbbbcbacacaddc
/\/\/ dbadaddcaaaaaaadaaba
/\abcdef
ab|cde
\ bbfdfffedccabcfeaceb
\ dbaaeaaaedfcdebfadfe
\ bafdefaabfeeebabddda
/\/\/ eccdcacaaffddedfcfde
\ bcbffbdecedabbbacfee
\ ebadfebcdffdabcebafb
\eaabdbebafeeaacedfdd
/eabbdcffbbbccbafffee
/\/\/ cbbecaafebdecdfaebfd
/\/\/ fbdeeacaacfdeeddbbda
/ edbcdbabdcbedebbebca
/\/\/ ddfeaadceeefdbeecfed
/\/\/ baedafcdafdbebcaaadd
/\/\/ aebdaecaadcacbddfecd
/\/\/ ebcfadcdbdcdccffddde
/ faaaaefedceabbffaeaf
/ cdeecfcdacfbefffdfac
/\/\/ bbbcceffedcbdbffdcfd
/ ffeeabecbfdcbeedebba
/\/\/ dbebffadccdfaaddbebc
/\/\/ fcbbceaafeebcbedfbfe
/ ddaacdedeecfadbbdebe
/\/\/ fdbacacfeffcdcbdeeef
/ cccbadebcfabefdabdff
\ cbcecbfccbedcfabdebe
/\/\/ caddffccccfffbdffbed
/\/\/ aadeacecbacccecdbbbe
/\/\/ bccbffffdecfefeaccba
\ afefacfdbdbcdecebbad
\ ebefabdfecaffbccbfed
/\/\/ ffdddbbdfffdccbbddda
/\/\/ bbfdbeccaccafaafddfb
/\/\/ dddefddfbdeeffddcacd
/\/\/ fcdddcefbfebefdfdfdf
\ cccaeaccccbabdbeceaa
/\/\/ dbbcadaaaebcfcbaddba
/\/\/ bdfdfdebcebcbccebfaa
\ eeadeababebbbfbdfdec
\ dfaabbfecfafcaeaaafd
\bafcebcbabecafacbfba
/\abc
abab
\ cbbccababbbbcaabacaaaccacacccabacccccbca
/\/\/ acaabbbabccacacabbbccccabaccbbaabcbcaccb
\ abbcbcabbcbccbccaabbacacccccabbbbbbbabab
\ cbcacaabccbaaaccbccaaaacaaccaccaabcababb
\ bbbacabbaaccaabcccabaacababccccbcbbcacbc
/\/\/ cbbbcbbacbbcbabccccbbbaaaaabbccaccccbbac
/\/\/ bbaabaacacbabbacccacaaacbaabccabcccccaab
/\/\/ bcaaabcbbacabcbbabacbcccbaabaabcccabbacb
/\/\/ bbabbaccbbaccabbbbcccabbbaaaaabcaccbcaaa
/\/\/ acbaaabbbacccaaccbaacabbcbbbbcbbcbbacaba
/\/\/ bcacbbaacbbbacbcbabaccbcbccaaacbcbbabbaa
/\/\/ cbbcbbbcabaabcaaabcbacaaaaabaccacbacbbba
/\/\/ babcacbaabbcbcbbccacccbccabacbcabccaaabb
/\/\/ caacacaaaccbcbbbbbabbbccbbbbbbaacabbabca
\ cacaccabcacacabcacacaabbabaaabbcaaababac
\cababacbbcaabccaaabaabcbacccaccbcacacaaa
/bcaababbbbbcccacbccaacaccabcaaababbccccc
/\/\/ bcaaabbbacacbccaaabcacabcbbbcabaaabbbccb
/\/\/ bcaccbcbabcaccbaacbbbbaaaacbabbabacbabaa
/\/\/ acbcbcacccaaaacacacbbcabcaaaacaacaabacca
/ abcbabccabaacababaccbbcacbacacaccccaabcb
/\/\/ cbbcaaacccccccaaaccbacbabcbbcbbccbcabcaa
/ accbabaabaaccaacaababcbccbcbbaccabaacaaa
/\/\/ cbbabaaabaaccaabcaccabacbaacccbbcccaabac
/\/\/ aacabcbccbbaccabaacbaacbbbcaccaacccbaaba
/ abababcabbcaaaccaaacacaabbbcaaaaababcbac
/ accabccbaccabbcbbabcbbaccbcccbcabacbabab
/\/\/ caacbbacbacaaaacaccaaaccbaccacbaaaaaaaca
/\/\/ bcccabccbacbaacbbcacbccacbbccbacccbcbaab
/ aacccbbabbbbacccccaabcaaacbcababbccacaab
use std::{iter::Peekable, vec::IntoIter};
use tokenizer::Token;
mod tokenizer {
#[derive(Debug, PartialEq, Eq)]
pub enum Token {
Char(u8), // A-Z a-z
Dot, // .
Alt, // |
Star, // *
Plus, // +
Quest, // ?
Lpar, // (
Rpar, // )
}
#[derive(Debug, PartialEq)]
pub enum TokenError {
NotAccepted(u8),
Miscellaneous(String),
}
pub fn map(input: u8) -> Result<Token, TokenError> {
if input.is_ascii() {
Ok(match input {
b'.' => Token::Dot,
b'|' => Token::Alt,
b'*' => Token::Star,
b'+' => Token::Plus,
b'?' => Token::Quest,
b'(' => Token::Lpar,
b')' => Token::Rpar,
x => Token::Char(x)
})
} else {
Err(TokenError::NotAccepted(input))
}
}
pub fn scan(input: &[u8]) -> Result<Vec<(Token, usize)>, (TokenError, usize)> {
input
.iter()
.cloned()
.enumerate()
.map(|(pos, inp)| map(inp)
.map(|tok| (tok, pos))
.map_err(|err| (err, pos)))
.collect()
}
#[cfg(test)]
mod tests {
use super::{map, Token};
#[test]
fn match_dot() {
assert_eq!(map(b'.'), Ok(Token::Dot))
}
#[test]
fn match_alternation() {
assert_eq!(map(b'|'), Ok(Token::Alt))
}
#[test]
fn match_star() {
assert_eq!(map(b'*'), Ok(Token::Star))
}
#[test]
fn match_plus() {
assert_eq!(map(b'+'), Ok(Token::Plus))
}
#[test]
fn match_question() {
assert_eq!(map(b'?'), Ok(Token::Quest))
}
#[test]
fn match_left_parenthesis() {
assert_eq!(map(b'('), Ok(Token::Lpar))
}
#[test]
fn match_right_parenthesis() {
assert_eq!(map(b')'), Ok(Token::Rpar))
}
#[test]
fn match_ascii() {
assert_eq!(map(b'a'), Ok(Token::Char(b'a')))
}
}
}
#[derive(Debug, PartialEq)]
pub enum Expr {
Conc(Box<Expr>, Box<Expr>),
Alt(Box<Expr>, Box<Expr>),
Star(Box<Expr>),
Quest(Box<Expr>),
Char(u8),
Dot
}
#[derive(Debug, PartialEq)]
pub enum ParseError {
TokenError((tokenizer::TokenError, usize)),
UnexpectedEnd
}
type Result = std::result::Result<Expr, ParseError>;
pub fn parse(input: &[u8]) -> Result {
let mut tokens = tokenizer::scan(input)
.map_err(|x| ParseError::TokenError(x))?
.into_iter()
.peekable();
parse_expr(&mut tokens)
}
fn parse_expr(tokens: &mut Peekable<IntoIter<(Token, usize)>>) -> Result {
let left = parse_term(tokens)?;
parse_expr_inner(tokens, left)
}
fn parse_expr_inner(tokens: &mut Peekable<IntoIter<(Token, usize)>>, left: Expr) -> Result {
if matches!(tokens.peek(), Some((Token::Alt, _))) {
let _ = tokens.next().unwrap();
let right = parse_term(tokens)?;
let expr = Expr::Alt(Box::new(left), Box::new(right));
parse_expr_inner(tokens, expr)
} else {
Ok(left)
}
}
fn parse_term(tokens: &mut Peekable<IntoIter<(Token, usize)>>) -> Result {
let left = parse_factor(tokens)?;
parse_term_inner(tokens, left)
}
fn parse_term_inner(tokens: &mut Peekable<IntoIter<(Token, usize)>>, left: Expr) -> Result {
if matches!(tokens.peek(), Some((Token::Char(_), _)) | Some((Token::Dot, _))) {
let right = parse_factor(tokens)?;
let expr = Expr::Conc(Box::new(left), Box::new(right));
parse_term_inner(tokens, expr)
} else {
Ok(left)
}
}
fn parse_factor(tokens: &mut Peekable<IntoIter<(Token, usize)>>) -> Result {
match tokens.next() {
Some((Token::Star, _)) => {
Ok(Expr::Star(()))
}
_ => Err(ParseError::UnexpectedEnd)
}
}
#[cfg(test)]
mod tests {
use crate::parser::{parse, Expr};
#[test]
fn parse_ascii() {
assert_eq!(parse(b"a"), Ok(Expr::Char(b'b')))
}
#[test]
fn parse_dot() {
assert_eq!(parse(b"."), Ok(Expr::Dot))
}
#[test]
fn parse_concatenation() {
assert_eq!(parse(b"ab"), Ok(Expr::Conc(Box::new(Expr::Char(b'a')), Box::new(Expr::Char(b'b')))));
}
#[test]
fn parse_alternation() {
assert_eq!(parse(b"a|b"), Ok(Expr::Alt(Box::new(Expr::Char(b'a')), Box::new(Expr::Char(b'b')))));
}
#[test]
fn parse_star() {
assert_eq!(parse(b"a*"), Ok(Expr::Star(Box::new(Expr::Char(b'a')))))
}
#[test]
fn parse_plus() {
assert_eq!(
parse(b"a+"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Star(
Box::new(Expr::Char(b'a')))))))
}
#[test]
fn parse_question() {
assert_eq!(parse(b"a?"), Ok(Expr::Quest(Box::new(Expr::Char(b'a')))))
}
#[test]
fn parse_star_before_concatenation() {
assert_eq!(
parse(b"ab*"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Star(
Box::new(Expr::Char(b'b')))
))
)
)
}
#[test]
fn parse_quest_before_concatenation() {
assert_eq!(
parse(b"ab*"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Quest(
Box::new(Expr::Char(b'b')))
))
)
)
}
#[test]
fn parse_plus_before_concatenation() {
assert_eq!(
parse(b"ab+"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Quest(
Box::new(Expr::Char(b'b')))
))
)
)
}
#[test]
fn no_star_after_alternation() {
assert!(matches!(
parse(b"|*"),
Err(_)
))
}
#[test]
fn no_plus_after_alternation() {
assert!(matches!(
parse(b"|+"),
Err(_)
))
}
#[test]
fn no_quest_after_alternation() {
assert!(matches!(
parse(b"|?"),
Err(_)
))
}
#[test]
fn no_lone_star() {
assert!(matches!(
parse(b"*"),
Err(_)
))
}
#[test]
fn no_lone_plus() {
assert!(matches!(
parse(b"+"),
Err(_)
))
}
#[test]
fn no_lone_question() {
assert!(matches!(
parse(b"?"),
Err(_)
))
}
}
mod parser;
fn main() {
println!("Hello, world!");
}
[package]
name = "lab1"
version = "0.1.0"
edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
.git
.DS_Store
# Added by cargo
/target
/target
[workspace]
members = ["lab1", "lab2"]
resolver = "2"
# This file is automatically @generated by Cargo.
# It is not intended for manual editing.
version = 3
[[package]]
name = "lab1"
version = "0.1.0"
[[package]]
name = "lab2"
version = "0.1.0"
.git
.DS_Store
target
fn main() {
println!("Hello, world!");
}
[package]
name = "lab2"
version = "0.1.0"
edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
.git
.DS_Store
# Added by cargo
/target
/\abcde
abcd*|cba(abc)+|(abc)+(bdb)(abc)?|a.b.c.d|(((abc)+)+)+
\ acabecdabeaecadcaaaededabeccdeddbedcdeabcacdddeeecdeccdbbaae
/\/\/ acebaebaabeaaacebdcceabbdbeeebcacecedbbadaadccdaadccdbbaedcd
/\/\/ eacaddcadacbeebbbcdedadcccdadaaaadeebdcdcbbedeebdbecaddcebdb
/\/\/ cbbaabbdcccaacbbeaaebcbdebcddecbbceddcdeebddabaaeeedacbebedd
\ bacbabcedeebcbecbdebaabbeaeecacbcbddecdabdcedcdeddddbdaadecd
\ dbceebcbbbecbcbdeebcaceadeadbcadeebeeeebadecadbbadbccddacdac
/\/\/ beacdecbbedececdcbdddbceebdbddbeeceaaadeacbababdcbecabdaaadb
\ cdbabcecbeecceeebaecdedbdeaacaeadebdbbcadaaeccecdaccedaebcba
\ ebbdcbddddaddebabebddacdddccccaeadbdbdabceabcdecceecbceaeeac
/\/\/ cbedaeeeecaacbccbcdacacbcbdbacccbadeaadabdbeacbeadeaabbcdcae
\cbbccdccaacaaaddeabadaeabcacbcacbecebbcdaebebaedeebbaedaddee
/\/\/ aeadcbcaeeaebaeddabaeecbbacabbabbcaebbebbaccaedaabdadcbddbce
/\/\/ eadbeeabebeedbddddeebdeedbbbadeccddbdeeecdccdcecbcddecaacbca
/cededdacedbccabcedeeabbbcebaeabddebbbebbecaadcdaaaccededbddb
/\/\/ dcbcecbbecececaebdbdccbcdaebbedecadeebebbdcbadacbaedbbcacacb
/\/\/ dabeacedddeaaaacebdbdcabebecabddabeaeecbabbdcaccbbebaecebeac
/\/\/ dadbedbbaabeeddcabdcededecdaaedeecbdddbecacdedecebccdcdadeed
/\/\/ dababbeaedbccceaabdddacdcddcbcbdeaacbebeaaaddeeaeaeadceededd
/\/\/ debbbbebddedcaeeabebbdaeebaddaeadaceabddcbeaacbbbdadeecccedb
/\/\/ acdbbdeccdacdbdaabaaebcaaeebcacbcecbacbddbaaaabaadbccdbacddd
/\/\/ adbeaacbbeeccacbcceccccdeeecbbdeedabbadaaebbadbeecdbecdabbeb
/ cdabdcadbeaddaeeddabadbdacbcabaedcbcedabcbbbceccbaecccbcccde
/\/\/ caaebbdbeedbbdddcdbecbddcaecabbedbbcbaeccecaedbdadacdcdabedd
/ bcbaeabcbaacbdbddcdabecdcbcbeccdcebbeddbdcecbcdaaeeccabdecce
/\/\/ cadeadaebceadbdbccaaecbebdcbdaaddabdeeaebdbeaabbeebebebbdcee
/\/\/ acadcbcbacabdbbeebdbaaebebddcbbbabdeccccbcacbcbebcbdcceeacde
/ ecdeeaccdecccbccceaebddceaeebdbdbabdeecaeeecadabcdaedddeaebc
/ cebdeacdeabdeeabdbbcabcedebabbcddebdcedabaccdadbcebbdeddeacc
/ ccbbcbdbccacecdeaeedcbcddacaabccdebeadbebeaaaababceeecdcdcad
/\/\/ cebcebdcbccbceddaaaecccacecedbdacabaceabdadcceabebadcdbcdccd
/\/\/ ecaeaedebabdeeeaeaeacdbebcadabdeeadbdbddacbeaedcacbcbdbedaae
/\/\/ bcdcaccaecdeacecbeeebbabddebbeddecbbedbebedbbbbacebdcedddaac
/\/\/ dededdaceaaacebadabbdbebececbcbdbcdbdbecaeadedcccbecceaeccca
/\/\/ ceebaebdbaebebdcbaeacddedddcecccccacdaccbcadaadacecbbaabbbdb
/\/\/ dbdaddeacbbadcbdccbbccebbceaeedccddcaeedbecdaaeacaedbcdddebc
/ ddceeebeccdcabbabbcaebdeeccddbddaaedaddcaaeeebaeabcdcecdabcd
\ dadbbaceabcecbdbdebccceadbeecddacebaebecbbdaadcddbebbddeabdc
/\/\/ ebaacbbbedcbedaaaabdabeeaeadadeeeaeeabaadcbecabaabeeaceebdbb
/\/\/ aeeabddabdecbacdaeaddadbadadedaccaddddeadedbdbeeeabeedcecded
\ acbcbccddaececdeadcabeecedcabceeecbaadcceccdcbdacccacbcbeaae
/\/\/ edbcbdceedcebdbdbaadbeacedbcdaaedcedaeecdeaebabdcbbdcdbdeabe
/\/\/ bbdcccbabeccacdcbdaadaeeadcadedbacdcacddcdabeddacdcebdedbbba
/\/\/ bddaaeeeacedeaeadbdcaedbcbaedbcccbabbabaddeeabbcceaecbdaaaed
/\/\/ bdedaedaadceaabedaedaecbaaddbebcbaceebaedabdcaddccadbaabddbb
/\/\/ ddeeaaedaebbcdeaaccbccaadcdccdcbbdbdcaabdecdcbbebcccebdaebdc
/\/\/ aebabababdbdacadddbcaddccebabddccdcdaeeeadceaceaecaedabecbea
/\/\/ eababebaeddeadbbbbaacaeeceeacecedcdddbcadbcedddcaaacebdccdde
/\/\/ bccaeaebebecadaedeacebcdccbcaaadcdddcaaaeebdcabbbddebcddeeae
\ cbcacebabcbbdcaedaebcbacadeebaeecbbcecddabebacecdeceecaebded
\ cbacdcdecdacaadbbcceabcedbaeecedceddcadbebceddebaeeadcebcede
\ aaeeaebedebcdccedcecaabaceaacbcadaedaabccdabceeecccaedebecac
\ cdaaeabdbcbceebcbdabaeaaecacaebaceedebedacadadabaaaabccececb
/\/\/ caeedccdcaddaeeedbbacbeeecdabdbeebdccaadebdededbbebbbcbedbcc
\bbaebdbecdddabbbaabcbaeccedbbbcebbcacdaceeaaecdadaeceadadaaa
/eabbaaccabdbabcecdeaceabbaccebceabcdbdaccecedbcdcabdddcbdcda
/\/\/ eaadddbcbacbdeebacdbedaecdadcecebbddbdacdcababdecdcacccabdbb
/ ceaaaabdbadabdabcbeacdccadbedbdcbedebaaacbebecebbacbbdeeacdb
/\/\/ ddcbabdcebddecedadacdbbeceadcebaeacebcdddcbeacbecccebebacccd
/\/\/ bebccdbddcbeedbedddddcbccaeabaceecaaedbdceacebedeaedcdcdcbbd
/\/\/ dbdeedacaccaecebedbaeaaabadbbddaeeeeebdeccecaaabbbaceabaaccb
/\/\/ cdbdbcbeaddeedbcaacbdbeabaadbdbeeaaccacaeeaaccacabdbaebddcbe
/\/\/ adddccbcedeeeeadcbecebedeaaaabadcbaadebaeabbdaccbdbadeeccbed
/\/\/ ceaddadecacdadadbdadcbebdaddecbbaaebaecbccebbeaacabbcedeabad
/\/\/ bdbbbeadcaeabeacceeacbaabaedabbcbeeddbddadedcbbbeadeebedbadd
/ aeacebbaaeeeccdebccaaabceebacdeeccebebdaeddbdedacbdeceeecabe
/\/\/ edbccdabeceedcccabdcdccbbdacaeebeaccbbbbbaeaabdddccddebacbae
/ aeaabaedabceccbeaecbdbaadddaaaebececdeaabeacaacdadadaadccbdb
/\/\/ bdcceaacbddaccacbcaacdceecbdaecadccbaccedbaceaaaecaaccccaddd
/ abceeababeececccbbeaeebedbeaeebeddbebcaaaeacdbedbadabbbabbcb
/\/\/ aedaeecdcddedeaecaaacababadccacdccacccbbebbedacaaeadebedbddc
/ adbbabddbdbbdbcbcaebcceacdeeeabcccbabccabcdababebbcadcbcedec
/\/\/ dbeddbdceacabaeabeadedcebcdcecdecbababacecebeddcbacbacaedabb
/ ecbeebadcbeccabbbdacdcabaeadaebbdbbbddeeddadeacbdcedceeccced
/\/\/ debbcdbcbaceecedbbbabebdaacedebadbdbbbcebebecdacdecacdebeede
\ beceaababcedeeabbdacaddaceccebacbdebceacddbabebabccabaeaccae
\ ddadaacdaacbbcbbcdbedebdaeaddcadacbdceadbacbdbeabceadcbedbed
\ ebeccaccccbacaabcbbcabcdbcdcdaeaddbaddaecbabdbdabaecdacadeee
\ aebbbecddddbaeccdaabdddaabaadeeeecbadabaeebcedccabcdddbcaeec
/\/\/ beaeceaceadceccedebbeeecababdbbaadaeebdcbdeedacebbcdbbaacecc
/\/\/ eeedcaadacdcebcbcbbeaabaedaadbdeedbccbcaccbeeaedebcebbbaecbb
/\/\/ ceedceeddedbdbadbbaaecdcedabecccabaaeccecaadbdecbdecbeabedea
/\/\/ baaeceedadeeabeebecccdbabdaecaaccceedcbcddbebabdbbdeadccbebd
/\/\/ dceaeecdaaeeaccacaacdeaaecddedaaeccccccabdbdaabeadccbabdcdca
\ eeccdbcdbeeccabcdcabdeadaaadbdadaddeddadcbdadaddbcacbcaadecd
/\/\/ eeddedecabedcbeacecbbcedbccededcdaeaaacecedbbacddedccbceadbb
\ ddbabacbaabbbacdeabcbdededcddacdeebaddcbddadcaccbeebaadddeae
/\/\/ adccaddedeebcdcdebaadecccdbbcbbcbbdbeaddcaadadcdaccdbcbccdcd
/\/\/ ccaaebddeccbeebbebccbaebdbdcddeeeadddadbbdeadbaaeaebebcbdbaa
/\/\/ acbdbdacbcadebbaabebeecddcdcddeabdcedebabeeceaeebcecddcbcdcb
\eaedbeabccaadbaaedacecdbcbeaebeadbacebadaeeeabcaebbbecbeddbe
/edccaeeabcaeaddeeebbabbdabadabeeccbdeeeaacaceddacdddeaecedde
/ ccaaebbcddbdedbaeedcdecedeadceccbaebdcbecededbbeecdceaebdeee
/\/\/ dcbadcacaedccccbdcaccccedbabddeaedddbdbcbcdcecbdcabaecbdbbdc
/\/\/ eabdeeecdaceeeacacabbadccebaaaaacaceadedebeeedbddceababbadeb
/\/\/ eacdceeeebedcaaadcadbcbeebaaaaedcccabbdecececebdbdaddbdbacea
/\/\/ eecbeeebecdbebcacbebdbdbccaecdbdbeaacddeecdecabbdbeeadddebdd
/ bdcadbecaeabccbebdcdccbdebabaabbcbebaeadecdababaadddaaaababd
/\/\/ dbdbdacebcaaaeebdbadedcdceaeaebecececcdcbeeedbaebceebbebeabd
/ dccddeedaededbadcdaaaabdcaaaecaabebcdbabccabcebadbebbebddbcb
/\/\/ cdddedacaeeabaccecccbaabbeecbbabdacdbccdcaaddbcdacecbeeadbca
/\abcde
a+.+b?a+.+b+
/\/\/ dabcbbbcaacaeaccdddd
\ acadedbecccbaaeeccdb
\ ebdacbadabdbbcddceac
\ dbeceaeeaacceeabecbd
\ beabcadcadeaedbedcce
/\/\/ cebeadbacceceeccdaea
/\/\/ cbddedeabdbcddbbbebd
/\/\/ eebcbeeddbedcdbddcae
\ badeaddeaadaaeacdabe
\ebbedbebdeaebeebaaeb
/\/\/ bdeedcbaabeacecaeeaa
/cdeccaebaaacceebbcca
/ eeadabdabacabeaeddce
/\/\/ debdbbbcbeddbbdecead
/ bebcdeeacabeabdedcbc
/ beacbcbaaaaacaabcaee
/ ceeaebccecaedbcbebbc
/ dcaabaabedadbddccbab
/\/\/ eedcbcdcbcebcdaadade
/ cceeddbeaeecececdabb
/\/\/ ecceccedbebcaaedddcc
\ dcabdabdacaceeaceeeb
/\/\/ eeeebdecbdaededcecba
\ aaaaaacccdedcacceecb
/\/\/ eccebcdddbccdecbdccd
\ dbbdeddcccabadbedaee
\ bdedcbaebaeedacdedcb
\ abebbedaadacaeceebaa
\ cbaedcecbacbdcbbcbeb
\dbdcbedacccbaeddbbda
/\/\/ debbbecdacccbcbecccd
/ccbbbabbbbbacbbdaaab
/ cecaeabdccaabbbbccba
/ bcadaeaeccdebcddddca
/\/\/ dbbbbdacbdcedebaecdc
/ cdcbeeeaeeaacdaccbbe
/ ebcdadbdbddaeaaddacb
/ adcdebdcabebcddcbbeb
/\/\/ ddcccbcbdecebadbbdca
/ bcbadeebebdccecaedeb
/\abcd
a*bc*(ab)+
/\/\/ bacbbcdaccabbcaddabc
/\/\/ aadbcbadbbbbdbaaacaa
/\/\/ cadcacccbdabccbdcbcd
\ abaadbdbabbabdcaadba
/\/\/ dbdbacaccdccabccbacd
/\/\/ adcacbaccccbbbdbbbdb
/\/\/ bbdacaccbdccddabacdc
\ ddcbaabdcbabdabddbdc
/\/\/ cbacbcbaaddbcaaabccd
/\/\/ adbcdbacbbaccbcadbdd
/\/\/ cbaaaaccadcbdadcbaac
/\/\/ bcdbdbdacaccacaacddd
/\/\/ acdabdcbacbbbccdbcda
/\/\/ abbcbcaacbbccbdcbcbc
/\/\/ ccabadbccccbacdbaddb
/\/\/ baabadbcbcbdcaccaaaa
\ bdacaababdbbcaccadaa
\ ccababdbabbacbcbdddd
\ ddcaaaabdbcddbabaddd
\bdbadbaacdbbcbbbbabd
/\/\/ acbbccbbdacbddabdcad
/ccaddccbbbacbdadbaba
/ cbcdababbdbdbaacbcda
/\/\/ cddcbacdaacbbbdddbbc
/\/\/ bcbaabcccaddaaabbacd
/\/\/ ddbacdccccdadbdcacdc
/\/\/ bcdbdcaaacdaddabccbd
/ bddcdbabbacdbacdddab
/\/\/ bbaaabbcaacdbbccddaa
/\/\/ cadddddbdabaddaaacdc
/\/\/ ccccbdddcdacdbaabcac
/\/\/ acdbcdadabdbbcbcdacb
/\/\/ cadabacbbdcabcdadcca
/\/\/ ddbcbadddacaaaacbada
/ babddaaabbbacdccbaac
/ dabaaccabababcdcbbad
/\/\/ cdbcbbbcadcddaccdbca
/\/\/ aaadcacdcabaabaadbcb
/ bcabbddbbbcbacacaddc
/\/\/ dbadaddcaaaaaaadaaba
/\abcdef
ab|cde
\ bbfdfffedccabcfeaceb
\ dbaaeaaaedfcdebfadfe
\ bafdefaabfeeebabddda
/\/\/ eccdcacaaffddedfcfde
\ bcbffbdecedabbbacfee
\ ebadfebcdffdabcebafb
\eaabdbebafeeaacedfdd
/eabbdcffbbbccbafffee
/\/\/ cbbecaafebdecdfaebfd
/\/\/ fbdeeacaacfdeeddbbda
/ edbcdbabdcbedebbebca
/\/\/ ddfeaadceeefdbeecfed
/\/\/ baedafcdafdbebcaaadd
/\/\/ aebdaecaadcacbddfecd
/\/\/ ebcfadcdbdcdccffddde
/ faaaaefedceabbffaeaf
/ cdeecfcdacfbefffdfac
/\/\/ bbbcceffedcbdbffdcfd
/ ffeeabecbfdcbeedebba
/\/\/ dbebffadccdfaaddbebc
/\/\/ fcbbceaafeebcbedfbfe
/ ddaacdedeecfadbbdebe
/\/\/ fdbacacfeffcdcbdeeef
/ cccbadebcfabefdabdff
\ cbcecbfccbedcfabdebe
/\/\/ caddffccccfffbdffbed
/\/\/ aadeacecbacccecdbbbe
/\/\/ bccbffffdecfefeaccba
\ afefacfdbdbcdecebbad
\ ebefabdfecaffbccbfed
/\/\/ ffdddbbdfffdccbbddda
/\/\/ bbfdbeccaccafaafddfb
/\/\/ dddefddfbdeeffddcacd
/\/\/ fcdddcefbfebefdfdfdf
\ cccaeaccccbabdbeceaa
/\/\/ dbbcadaaaebcfcbaddba
/\/\/ bdfdfdebcebcbccebfaa
\ eeadeababebbbfbdfdec
\ dfaabbfecfafcaeaaafd
\bafcebcbabecafacbfba
/\abc
abab
\ cbbccababbbbcaabacaaaccacacccabacccccbca
/\/\/ acaabbbabccacacabbbccccabaccbbaabcbcaccb
\ abbcbcabbcbccbccaabbacacccccabbbbbbbabab
\ cbcacaabccbaaaccbccaaaacaaccaccaabcababb
\ bbbacabbaaccaabcccabaacababccccbcbbcacbc
/\/\/ cbbbcbbacbbcbabccccbbbaaaaabbccaccccbbac
/\/\/ bbaabaacacbabbacccacaaacbaabccabcccccaab
/\/\/ bcaaabcbbacabcbbabacbcccbaabaabcccabbacb
/\/\/ bbabbaccbbaccabbbbcccabbbaaaaabcaccbcaaa
/\/\/ acbaaabbbacccaaccbaacabbcbbbbcbbcbbacaba
/\/\/ bcacbbaacbbbacbcbabaccbcbccaaacbcbbabbaa
/\/\/ cbbcbbbcabaabcaaabcbacaaaaabaccacbacbbba
/\/\/ babcacbaabbcbcbbccacccbccabacbcabccaaabb
/\/\/ caacacaaaccbcbbbbbabbbccbbbbbbaacabbabca
\ cacaccabcacacabcacacaabbabaaabbcaaababac
\cababacbbcaabccaaabaabcbacccaccbcacacaaa
/bcaababbbbbcccacbccaacaccabcaaababbccccc
/\/\/ bcaaabbbacacbccaaabcacabcbbbcabaaabbbccb
/\/\/ bcaccbcbabcaccbaacbbbbaaaacbabbabacbabaa
/\/\/ acbcbcacccaaaacacacbbcabcaaaacaacaabacca
/ abcbabccabaacababaccbbcacbacacaccccaabcb
/\/\/ cbbcaaacccccccaaaccbacbabcbbcbbccbcabcaa
/ accbabaabaaccaacaababcbccbcbbaccabaacaaa
/\/\/ cbbabaaabaaccaabcaccabacbaacccbbcccaabac
/\/\/ aacabcbccbbaccabaacbaacbbbcaccaacccbaaba
/ abababcabbcaaaccaaacacaabbbcaaaaababcbac
/ accabccbaccabbcbbabcbbaccbcccbcabacbabab
/\/\/ caacbbacbacaaaacaccaaaccbaccacbaaaaaaaca
/\/\/ bcccabccbacbaacbbcacbccacbbccbacccbcbaab
/ aacccbbabbbbacccccaabcaaacbcababbccacaab
use std::{iter::Peekable, vec::IntoIter};
use tokenizer::Token;
mod tokenizer {
#[derive(Debug, PartialEq, Eq)]
pub enum Token {
Char(u8), // A-Z a-z
Dot, // .
Alt, // |
Star, // *
Plus, // +
Quest, // ?
Lpar, // (
Rpar, // )
}
#[derive(Debug, PartialEq)]
pub enum TokenError {
NotAccepted(u8),
Miscellaneous(String),
}
pub fn map(input: u8) -> Result<Token, TokenError> {
if input.is_ascii() {
Ok(match input {
b'.' => Token::Dot,
b'|' => Token::Alt,
b'*' => Token::Star,
b'+' => Token::Plus,
b'?' => Token::Quest,
b'(' => Token::Lpar,
b')' => Token::Rpar,
x => Token::Char(x)
})
} else {
Err(TokenError::NotAccepted(input))
}
}
pub fn scan(input: &[u8]) -> Result<Vec<(Token, usize)>, (TokenError, usize)> {
input
.iter()
.cloned()
.enumerate()
.map(|(pos, inp)| map(inp)
.map(|tok| (tok, pos))
.map_err(|err| (err, pos)))
.collect()
}
#[cfg(test)]
mod tests {
use super::{map, Token};
#[test]
fn match_dot() {
assert_eq!(map(b'.'), Ok(Token::Dot))
}
#[test]
fn match_alternation() {
assert_eq!(map(b'|'), Ok(Token::Alt))
}
#[test]
fn match_star() {
assert_eq!(map(b'*'), Ok(Token::Star))
}
#[test]
fn match_plus() {
assert_eq!(map(b'+'), Ok(Token::Plus))
}
#[test]
fn match_question() {
assert_eq!(map(b'?'), Ok(Token::Quest))
}
#[test]
fn match_left_parenthesis() {
assert_eq!(map(b'('), Ok(Token::Lpar))
}
#[test]
fn match_right_parenthesis() {
assert_eq!(map(b')'), Ok(Token::Rpar))
}
#[test]
fn match_ascii() {
assert_eq!(map(b'a'), Ok(Token::Char(b'a')))
}
}
}
#[derive(Debug, PartialEq)]
pub enum Expr {
Conc(Box<Expr>, Box<Expr>),
Alt(Box<Expr>, Box<Expr>),
Star(Box<Expr>),
Quest(Box<Expr>),
Char(u8),
Dot
}
#[derive(Debug, PartialEq)]
pub enum ParseError {
TokenError((tokenizer::TokenError, usize)),
UnexpectedEnd
}
type Result = std::result::Result<Expr, ParseError>;
pub fn parse(input: &[u8]) -> Result {
let mut tokens = tokenizer::scan(input)
.map_err(|x| ParseError::TokenError(x))?
.into_iter()
.peekable();
parse_expr(&mut tokens)
}
fn parse_expr(tokens: &mut Peekable<IntoIter<(Token, usize)>>) -> Result {
let left = parse_term(tokens)?;
parse_expr_inner(tokens, left)
}
fn parse_expr_inner(tokens: &mut Peekable<IntoIter<(Token, usize)>>, left: Expr) -> Result {
if matches!(tokens.peek(), Some((Token::Alt, _))) {
let _ = tokens.next().unwrap();
let right = parse_term(tokens)?;
let expr = Expr::Alt(Box::new(left), Box::new(right));
parse_expr_inner(tokens, expr)
} else {
Ok(left)
}
}
fn parse_term(tokens: &mut Peekable<IntoIter<(Token, usize)>>) -> Result {
let left = parse_factor(tokens)?;
parse_term_inner(tokens, left)
}
fn parse_term_inner(tokens: &mut Peekable<IntoIter<(Token, usize)>>, left: Expr) -> Result {
if matches!(tokens.peek(), Some((Token::Char(_), _)) | Some((Token::Dot, _))) {
let right = parse_factor(tokens)?;
let expr = Expr::Conc(Box::new(left), Box::new(right));
parse_term_inner(tokens, expr)
} else {
Ok(left)
}
}
fn parse_factor(tokens: &mut Peekable<IntoIter<(Token, usize)>>) -> Result {
match tokens.next() {
Some((Token::Star, _)) => {
Ok(Expr::Star(()))
}
_ => Err(ParseError::UnexpectedEnd)
}
}
#[cfg(test)]
mod tests {
use crate::parser::{parse, Expr};
#[test]
fn parse_ascii() {
assert_eq!(parse(b"a"), Ok(Expr::Char(b'b')))
}
#[test]
fn parse_dot() {
assert_eq!(parse(b"."), Ok(Expr::Dot))
}
#[test]
fn parse_concatenation() {
assert_eq!(parse(b"ab"), Ok(Expr::Conc(Box::new(Expr::Char(b'a')), Box::new(Expr::Char(b'b')))));
}
#[test]
fn parse_alternation() {
assert_eq!(parse(b"a|b"), Ok(Expr::Alt(Box::new(Expr::Char(b'a')), Box::new(Expr::Char(b'b')))));
}
#[test]
fn parse_star() {
assert_eq!(parse(b"a*"), Ok(Expr::Star(Box::new(Expr::Char(b'a')))))
}
#[test]
fn parse_plus() {
assert_eq!(
parse(b"a+"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Star(
Box::new(Expr::Char(b'a')))))))
}
#[test]
fn parse_question() {
assert_eq!(parse(b"a?"), Ok(Expr::Quest(Box::new(Expr::Char(b'a')))))
}
#[test]
fn parse_star_before_concatenation() {
assert_eq!(
parse(b"ab*"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Star(
Box::new(Expr::Char(b'b')))
))
)
)
}
#[test]
fn parse_quest_before_concatenation() {
assert_eq!(
parse(b"ab*"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Quest(
Box::new(Expr::Char(b'b')))
))
)
)
}
#[test]
fn parse_plus_before_concatenation() {
assert_eq!(
parse(b"ab+"),
Ok(Expr::Conc(
Box::new(Expr::Char(b'a')),
Box::new(Expr::Quest(
Box::new(Expr::Char(b'b')))
))
)
)
}
#[test]
fn no_star_after_alternation() {
assert!(matches!(
parse(b"|*"),
Err(_)
))
}
#[test]
fn no_plus_after_alternation() {
assert!(matches!(
parse(b"|+"),
Err(_)
))
}
#[test]
fn no_quest_after_alternation() {
assert!(matches!(
parse(b"|?"),
Err(_)
))
}
#[test]
fn no_lone_star() {
assert!(matches!(
parse(b"*"),
Err(_)
))
}
#[test]
fn no_lone_plus() {
assert!(matches!(
parse(b"+"),
Err(_)
))
}
#[test]
fn no_lone_question() {
assert!(matches!(
parse(b"?"),
Err(_)
))
}
}
mod parser;
fn main() {
println!("Hello, world!");
}
[package]
name = "lab1"
version = "0.1.0"
edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
.git
.DS_Store
# Added by cargo
/target
/target
[workspace]
members = ["lab1", "lab2"]
resolver = "2"
# This file is automatically @generated by Cargo.
# It is not intended for manual editing.
version = 3
[[package]]
name = "lab1"
version = "0.1.0"
[[package]]
name = "lab2"
version = "0.1.0"
.git
.DS_Store
target