Myths and facts about the efficient implementation of finite automata and lexical analysis Export

@incollection{citeulike:6081298, abstract = {Finite automata and their application in lexical analysis play an important role in many parts of computer science and particularly in compiler constructions. We measured 12 scanners using different implementation strategies and found that the execution time differed by a factor of 74. Our analysis of the algorithms as well as run-time statistics on cache misses and instruction frequency reveals substantive differences in code locality and certain kinds of overhead typical for specific implementation strategies. Some of the traditional statements on writing fast scanners could not be confirmed. Finally, we suggest an improved scanner generator.}, author = {Brouwer, Klaus and Gellerich, Wolfgang and Ploedereder, Erhard}, citeulike-article-id = {6081298}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/BFb0026419}, citeulike-linkout-1 = {http://www.springerlink.com/content/m57r53x7320wm465}, doi = {10.1007/BFb0026419}, journal = {Compiler Construction}, keywords = {application, automaton, comparison, formallanguage, recognition, study, survey}, pages = {1--15}, posted-at = {2009-11-06 17:08:04}, priority = {0}, title = {Myths and facts about the efficient implementation of finite automata and lexical analysis}, url = {http://dx.doi.org/10.1007/BFb0026419}, year = {1998} }

TY - CHAP ID - citeulike:6081298 L3 - citeulike-article-id:6081298 N2 - Finite automata and their application in lexical analysis play an important role in many parts of computer science and particularly in compiler constructions. We measured 12 scanners using different implementation strategies and found that the execution time differed by a factor of 74. Our analysis of the algorithms as well as run-time statistics on cache misses and instruction frequency reveals substantive differences in code locality and certain kinds of overhead typical for specific implementation strategies. Some of the traditional statements on writing fast scanners could not be confirmed. Finally, we suggest an improved scanner generator. JF - Compiler Construction EP - 15 TI - Myths and facts about the efficient implementation of finite automata and lexical analysis SP - 1 KW - application KW - automaton KW - comparison KW - formallanguage KW - recognition KW - study KW - survey AU - Brouwer, Klaus AU - Gellerich, Wolfgang AU - Ploedereder, Erhard PY - 1998/// UR - http://dx.doi.org/10.1007/BFb0026419 ER -