org.stekikun.dolmen.tagged

Class Optimiser

java.lang.Object

org.stekikun.dolmen.tagged.Optimiser

public final class Optimiser
extends Object

This class implements optimisations of tagged regular exceptions in order to minimise the number of tags (which have a big impact on the complexity of the translation into a DFA).

The various optimisations remove tags whose positions in any successful matching can be deduced statically, with respect to either the start of the matched string, its end, or any other tag in the regular expression. Removed tags are recorded in an interpretation map, which for each such tag gives its relative position to some other marker.

Author:

Stéphane Lescuyer

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Optimiser.Allocated This structure represents the result of optimising a tagged regular expression: it packs together the resulting tagged expression, the list of Optimiser.IdentInfo for each possible bound variable in the original regular expression, and the overall number of different memory cells needed to store all markers at run-time.
static class	Optimiser.IdentInfo Structure which represents how an indentifier in a regular expression is realized in optimised tagged regular expressions, i.e. provides tag addresses for the start and end of the expression bound to the identifier, and whether it is optional or not.
static class	Optimiser.TagAddr The relative address of a tag, either with respect to some memory cell, i.e. some actual storage for a tag, or to the Optimiser.TagAddr.START or Optimiser.TagAddr.END of the input.
static class	Optimiser.TagKey Similar to TRegular.TagInfo, but without the semantic action.

Method Summary

Modifier and Type	Method and Description
Map<Optimiser.TagKey,Optimiser.TagAddr>	getTagEnvironment()
static Optimiser.Allocated	optimise(Regulars.VarsInfo varsInfo, boolean optimisation, TRegular regular)
protected TRegular	simpleBackward(TRegular r)
protected TRegular	simpleForward(TRegular r)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

getTagEnvironment

public Map<Optimiser.TagKey,Optimiser.TagAddr> getTagEnvironment()

Returns:

an unmodifiable view of the environment mapping tags that were optimised away by this instance to their relative addresses

simpleForward

protected TRegular simpleForward(TRegular r)

simpleBackward

protected TRegular simpleBackward(TRegular r)

optimise

public static Optimiser.Allocated optimise(Regulars.VarsInfo varsInfo,
                                           boolean optimisation,
                                           TRegular regular)

Parameters:

varsInfo - variable analysis for regular

optimisation - whether optimisation of tags with respect to the start or end of input should be applied

regular -

Returns:

an optimised tagged regular expression along with the environment that maps every binding's boundaries to locations relative to memory cells

See Also:

Optimiser.Allocated