Download Paper - STS

5.3 Back End
For starters, this is accomplished by inducing the first phase of the transformation
process with a call to the Transform function, whenever a new regular expression object
is constructed in the process of applying one of the methods mentioned above. Another
means to that end works one step ahead: Before even the constructor for creating
instances of the Concatenation class is called, checking whether any of the two regular
expressions that will be passed as arguments to the constructor are equal to the empty
set constant, avoids a lot of unnecessary computations.
The result is that the time and space requirements are effectively reduced. Also, it
becomes easier to comprehend the whole process of converting a control flow graph to a
regular expression.
A slight improvement of this result is achieved when the second phase of the transformation process is performed on the resulting regular expression, during which certain
sub-expressions are replaced by more concise expressions using the plus and optional
operators. As far as the weakening rules are concerned, they are applied lastly, once the
construction process is finished.
55