Non-Deterministic Recogniser: Generator Generator

摘要

Non-deterministic finite automata are used in applications, like scanners andeditors, that use pattern matching. Thompson's construction is an algorithm that will generate a non-deterministic finite automaton given a regular expression. The author takes a fresh look at this construction method. He specifies and implements it using an attribute grammar, and using a scanner and parser generator, he builds recognizer generators that can generate a recognizer for a given regular expression. The recognizer uses a backtracking algorithm to determine whether a string matches the regular expression. He also considers and solves the problem of regular expressions that cause the recognizer to loop.