{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T15:21:47Z","timestamp":1698074507429},"reference-count":13,"publisher":"Wiley","issue":"11","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":6207,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1989,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>General tools for the automatic generation of lexical analysers such as LEX<jats:sup>1<\/jats:sup> convert a specification consisting of a set of regular expressions into a deterministic finite automaton. The main algorithms involved are subset construction, state minimization and table compression. Even if these algorithms do not show their worst\u2010case time behaviour they are still quite expensive. This paper shows how to solve the problem in linear time for practical cases, thus resulting in a significant speed\u2010up. The idea is to combine the automaton introduced by Aho and Corasick<jats:sup>2<\/jats:sup> with the direct computation of an efficient table representation. Besides the algorithm we present experimental results of the scanner generator Rex<jats:sup>3<\/jats:sup> which uses this technique.<\/jats:p>","DOI":"10.1002\/spe.4380191106","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T20:57:14Z","timestamp":1163797034000},"page":"1089-1103","source":"Crossref","is-referenced-by-count":11,"title":["Efficient generation of lexical analysers"],"prefix":"10.1002","volume":"19","author":[{"given":"J.","family":"Grosch","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"LEX \u2014 a lexical analyzer generator","author":"Lesk M. E.","year":"1975"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_4_2","unstructured":"J.Grosch \u2018Rex \u2014 a scanner generator\u2019 Compiler Generation Report No. 5 GMD Forschungsstelle an der Universit\u00e4t Karlsruhe December1987."},{"key":"e_1_2_1_5_2","volume-title":"Flex \u2014 Manual Pages","author":"Paxson V.","year":"1988"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380160508"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1002\/j.1097-024X.1986.tb00011.x","article-title":"The automatic generation of fast lexical analysers","volume":"16","author":"Heuring V. P.","year":"1986","journal-title":"Software \u2014 Practice and Experience"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/15042.15051"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380170602"},{"key":"e_1_2_1_10_2","unstructured":"J.Grosch \u2018An Efficient Table\u2010Driven Scanner\u2019 Compiler Generation Report No. 1 GMD Forschungsstelle an der Universit\u00e4t Karlsruhe May1987."},{"key":"e_1_2_1_11_2","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho A. V.","year":"1986"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5192-7"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-96717-7"},{"key":"e_1_2_1_14_2","unstructured":"J.Grosch \u2018Selected examples of scanner specifications\u2019 Compiler Generation Report No. 7 GMD Forschungsstelle an der Universitat Karlsruhe March1988."}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380191106","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380191106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T01:01:32Z","timestamp":1697936492000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380191106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,11]]},"references-count":13,"journal-issue":{"issue":"11","published-print":{"date-parts":[[1989,11]]}},"alternative-id":["10.1002\/spe.4380191106"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380191106","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,11]]}}}