Paper Info
Title
Backtracking non-deterministic recognizers
Abstract
Non-deterministic finite automata are used in a whole range of applications from scanners and editors to process algebra. Thompson's construction is an algorithm that will generate a non-deterministic finite automaton given a regular expression. A fresh look at this construction method is taken. It is specified and implemented using an attribute grammar, and using a scanner and parser generator, a non-deterministic-recognizer generator is built that generates a non-deterministic recognizer for a given regular expression. The recognizer uses a backtracking algorithm to determine whether a string matches the regular expression. The problem of pathological regular expressions, which are regular expressions that cause the recognizer to loop. is solved. The performance of the recognizer is compared with scanners generated by standard tools.
Year
Venue
Keywords
1995
JOURNAL OF PROGRAMMING LANGUAGES
NONDETERMINISTIC FINITE AUTOMATA,PROGRAM GENERATOR,RECOGNIZER
Field
DocType
Volume
Sociology,Theoretical computer science,Backtracking,Law
Journal
3
Issue
ISSN
Citations 
4.0
0963-9306
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Albert Nymeyer11069.98