VERIFICATION DEVICE, VERIFICATION METHOD AND VERIFICATION PROGRAM
A verification device according to an embodiment includes a first determination unit and a second determination unit. The first determination unit determines whether a regular expression follows a syntax (for example, a syntax of a regular expression according to the Backus-Naur form) designated in advance. The second determination unit determines whether a condition (for example, real-world strong 1-unambiguity (RWS1U)) indicating that the processing time when the regular expression analyzes a character string is linear with respect to the length of the character string is satisfied.
1 . A verification device comprising:
processing circuitry configured to:
determine whether a regular expression follows a syntax designated in advance; and
determine whether a condition indicating that processing time when the regular expression analyzes a character string is linear with respect to a length of the character string is satisfied.
2 . The verification device according to claim 1 , wherein the processing circuitry is further configured to determine that the condition is satisfied when the regular expression satisfies RWS1U.
3 . The verification device according to claim 1 , wherein the processing circuitry is further configured to convert the regular expression subjected to removal of lookahead and addition of brackets into a nondeterministic finite automaton, and determines that the condition is satisfied in a case where there is no vertex on the nondeterministic finite automaton such that there are different paths that can reach a same character only through the brackets and transition of an empty character.
4 . A verification method executed by a verification device, the verification method comprising:
determining whether a regular expression follows a syntax designated in advance; and
determining whether a condition indicating that processing time when the regular expression analyzes a character string is linear with respect to a length of the character string is satisfied.
5 . A non-transitory computer-readable recording medium storing therein a verification program that causes a computer to execute a process comprising:
determining whether a regular expression follows a syntax designated in advance; and
determining whether a condition indicating that processing time when the regular expression analyzes a character string is linear with respect to a length of the character string is satisfied.