Double Parsing Approach to Build Finite State Automata from Regular Expressions

Abstract

The work described in this article is in the field of compilation. More precisely, it concerns the lexical analysis of a compiler or a translator in general. It can also be used in the search for patterns in texts or in any other system handling regular expressions. The goal is to build a finite state automaton from a regular expression. The construction of an automaton is accomplished in two distinct steps. The first step is a parser based on operator precedence. On receiving a regular expression as input, the parser outputs the corresponding postfix representation. The postfix expression obtained is transformed into the corresponding target finite state automaton in the second step. Experiments were carried out on several regular expressions in order to evaluate and validate our proposal. The results are conclusive and largely meet our expectations.