An abstract machine theory for formal language parsers

Summary The usual data necessary for any abstract machine theory is given in categorical terminology. In these terms, an abstract machine theory for formal language parsers is developed, exposing the essential nature of any left-to-right parsing scheme. A weak classification of all parsers for a given language is developed and the usual notions of initial machine, reachable machine and minimal machine apply. Minimality is an extremely weak notion in this theory, although it is equivalent to a simple form of immediate error detection for parsers. Remarks on the construction of parsing procedures are given.Research supported in part by grant GJ-1171 from the National Science Foundation.