A technique for converting NFA's and DFA's to regular expressions in Lex
Gregory Safko · Rowan Digitals Works (Rowan University) · 2002
In the design and creation of compilers, a compiler-writer is called upon to make assumptions and declarations about how their language's syntax performs and behaves. Lex is a software tool used to create grammar rules. A flat file is read as input to lex, and the corresponding C code is output. However, in order to properly format the flat file, the compiler-writer creates the lex expression either on a "hunch," or based on some given set of criteria. Among these criteria are: case sensitivity, the introduction of special characters and symbols, the handling of a space character, and the handling of escape sequence characters, namely the tab, new-line, and carriage return symbols. Lex can create the code to perform such verification, but it is up to the compiler-writer to provide lex with the rules. Sometimes the rules can be seen more easily diagrammatically through an NFA or a DFA. Once the FA is created, it is just a matter of extracting the rules from the diagram. The following technique can be employed to create lex rules from the Finite Automata.