org.stekikun.dolmen.syntax

Class Regulars

java.lang.Object

org.stekikun.dolmen.syntax.Regulars

public abstract class Regulars
extends Object

This class contains various utility methods about regular expressions.

Author:

Stéphane Lescuyer

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Regulars.MatchResult The result of a successful match of a regular expression against some input string
static class	Regulars.VarsInfo Gathers information about the nature of various bindings in a regular expression.

Method Summary

Modifier and Type	Method and Description
static Iterable<Regulars.MatchResult>	allMatches(Regular regular, String input)
static Iterable<Regulars.MatchResult>	allMatches(Regular regular, String input, boolean strict)
static Regulars.VarsInfo	analyseVars(Regular regular)
static @Nullable CSet	asCSet(Regular reg) A regular expression corresponds to a character set if it is either a character set, or an alternation of expression which correspond to a character set.
static boolean	equal(Regular r1, Regular r2) This is not an equivalence test between regular regular expressions, in the sense that it can return false on two different regular expressions which would otherwise recognize the same language.
static CSet	first(Regular regular)
static @Nullable Map<String,String>	matches(Regular regular, String input)
static @Nullable Map<String,String>	matches(Regular regular, String input, boolean strict)
static Map<CSet,Regular>	project(Regular regular, CSet first) The projection of a regular expression on a character set provides regular expressions for all character in the set, with the following meaning: a string s with first character c matches the regular expression r if and only if s.substring(1) matches the projection of r on the character c.
static Regular	removeNestedBindings(Regular r) Note that nested bindings with the same name are useless because if the regular expression matches some string, the last match bound for some name will always be the outermost binding with that name.
static Regular	removeNestedBindings2(Regular r) Note that nested bindings with the same name are useless because if the regular expression matches some string, the last match bound for some name will always be the outermost binding with that name.
static Iterable<String>	witnesses(Regular regular)

Methods inherited from class java.lang.Object

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

Method Detail

equal

public static boolean equal(Regular r1,
                            Regular r2)

This is not an equivalence test between regular regular expressions, in the sense that it can return false on two different regular expressions which would otherwise recognize the same language.

Parameters:

r1 -

r2 -

Returns:

true if and only if the two given regular expressions are structurally equal

removeNestedBindings

public static Regular removeNestedBindings(Regular r)

Note that nested bindings with the same name are useless because if the regular expression matches some string, the last match bound for some name will always be the outermost binding with that name.

Parameters:

r -

Returns:

a regular expression matching the same language as r but where bindings which appear nested below a binding with the same name have been removed

removeNestedBindings2

public static Regular removeNestedBindings2(Regular r)

Note that nested bindings with the same name are useless because if the regular expression matches some string, the last match bound for some name will always be the outermost binding with that name.

Parameters:

r -

Returns:

a regular expression matching the same language as r but where bindings which appear nested below a binding with the same name have been removed

analyseVars

public static Regulars.VarsInfo analyseVars(Regular regular)

Parameters:

regular -

Returns:

a Regulars.VarsInfo structure describing the nature of the various bound names appearing in the given regular expression

allMatches

public static Iterable<Regulars.MatchResult> allMatches(Regular regular,
                                                        String input,
                                                        boolean strict)

Parameters:

regular -

input -

strict - if set, nothing can be matched after EOF; if not set, empty strings can still match after EOF

Returns:

an iterable of all potential match results of the regular expression regular and a prefix of input

allMatches

public static Iterable<Regulars.MatchResult> allMatches(Regular regular,
                                                        String input)

Parameters:

regular -

input -

Returns:

allMatches(regular, input, true)

matches

public static @Nullable Map<String,String> matches(Regular regular,
                                                   String input,
                                                   boolean strict)

Parameters:

regular -

input -

strict - if set, nothing can be matched after EOF; if not set, empty strings can still match after EOF

Returns:

null if regular does not match the full input string, or the map of bound substrings if a match was found

matches

public static @Nullable Map<String,String> matches(Regular regular,
                                                   String input)

Parameters:

regular -

input -

Returns:

matches(regular, input, true)

witnesses

public static Iterable<String> witnesses(Regular regular)

Parameters:

regular -

Returns:

an iterable view of potential matching strings for the given regular expression

first

public static CSet first(Regular regular)

Parameters:

regular -

Returns:

the set of characters that can start a (non-empty) match of the given regular expression

asCSet

public static @Nullable CSet asCSet(Regular reg)

A regular expression corresponds to a character set if it is either a character set, or an alternation of expression which correspond to a character set. Binding regular expressions never correspond to character sets.

Parameters:

reg -

Returns:

the character set that the given regular expression corresponds to and returns null if reg does not correspond to a character set.

project

public static Map<CSet,Regular> project(Regular regular,
                                        CSet first)

The projection of a regular expression on a character set provides regular expressions for all character in the set, with the following meaning: a string s with first character c matches the regular expression r if and only if s.substring(1) matches the projection of r on the character c.

This method returns a map which groups together all characters for which the projection is the same: it associates various character sets to their common corresponding projection of the given regular expression. The map has the following properties:

• it does not contain empty character sets
• characters which cannot start a match of regular, or which do not belong to first, are not mapped at all
• all the keys are pairwise disjoint character sets

Important: The description of a projection only holds when considering non-strict matching (cf matches(Regular, String, boolean)). Indeed projecting the Kleene star of a regexp that ends with EOF does not preserve the semantics unless it is allowed to match the empty string after EOF.

Parameters:

regular -

first -

Returns:

the projection map of regular on the given character set