Optimization of Deterministic Finite Automaton Based Pattern Matching in Lexical Analysis of Compiler
Vaikunth Pai T · SSRN Electronic Journal · 2015
A compiler is a program that reads a program written in one language - the source language - and translates it into an equivalent program in another language - the target language. As an important part of this translation process, the compiler reports to its user the presence of errors in the source program. Conceptually, a compiler operates in phases, each of which transforms the source program from one representation to another. A phase is an independent task in the compilation process, which transforms the source program from one representation to another. The process of compilation starts with the first phase called lexical analysis. In this phase the input is scanned completely in order to identify the tokens. The token structures are recognized with the help of some diagrams. These diagrams are known as finite automata and to construct finite automata, regular expressions are used. These diagrams can be translated into a program for identifying tokens. The first goal of this research is to implement and optimize pattern matchers constructed from regular expressions for lexical phase of the compilation process. It will be suitable for inclusion in a Lex compiler because it constructs a DFA directly from a regular expression, without constructing an intermediate NFA along the way. The second goal of this research is to minimize the number of states of any DFA, so it can be used to reduce the size of a DFA-based pattern matcher.