Lexer algorithm

Multiple methods for processing regular expressions exist, having different capabilities and time/space requirements. Method used by Alpag is known as DFA (Deterministic Finite Automaton). Regular expression patterns defined by user are transformed into single deterministic finite automaton which is embedded in generated lexer. Analysis is performed by reading subsequent input characters and using them to walk the automaton.

The DFA algorithm has several advantages of which most important are:

• linear and very low cost of execution (at the expense of automaton precalculation which is done once during parser generation)
• stability due to lack of any data structure allocation/deallocation during processing.
• static structure of DFA which enables its multithreaded use

It also has some drawbacks:

• generated automaton can be large and occupy significant amount of memory
• regular expression patterns are limited to pure regular grammar. Certain features available in regular expression engines featuring other algorithms cannot be used with DFA. Examples of such features are ability to specify behavior for ambiguous regexes, or backreference matching.

DFA algorithm, with its speed and stability, seems to be optimal choice for lexers that are pre-calculated and permanently linked into target application.

The type of DFA implementation used by Alpag is known as table driven.

Major limitation of DFA method is potential large size of tables describing automaton. Alpag uses some simple yet effective methods for compressing DFA tables.