Efficient generation of lexical analysers
1989; Wiley; Volume: 19; Issue: 11 Linguagem: Inglês
10.1002/spe.4380191106
ISSN1097-024X
Autores Tópico(s)Formal Methods in Verification
ResumoAbstract General tools for the automatic generation of lexical analysers such as LEX 1 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‐case 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‐up. The idea is to combine the automaton introduced by Aho and Corasick 2 with the direct computation of an efficient table representation. Besides the algorithm we present experimental results of the scanner generator Rex 3 which uses this technique.
Referência(s)