Regular expression matching: Language concepts and efficient implementation
Eberhard Bertsch · 1980
This paper describes a parsing module that is to be used as an extension of string processing facilities in programming languages. The user interface is presented in the well-known framework of regular expressions. The implementation is sketched in sufficient detail for discussing problems of efficiency. In particular, a linear time bound can be established. The major novelty lies in the conceptual and implementational structure of parsing results. While preserving a tree-like outside appearance, the key data strucutre consists of easily accessed position tables.