# Automatic generation of efficient lexical processors using finite state techniques

@article{Johnson1968AutomaticGO, title={Automatic generation of efficient lexical processors using finite state techniques}, author={W. Johnson and James H. Porter and Stephanie I. Ackley and D. Ross}, journal={Commun. ACM}, year={1968}, volume={11}, pages={805-813} }

The practical application of the theory of finite-state automata to automatically generate lexical processors is dealt with in this tutorial article by the use of the AED RWORD system, developed at M.I.T. as part of the AED-1 system. This system accepts as input descriptions of the multicharacter items or of words allowable in a language given in terms of a subset of regular expressions. The output of the system is a lexical processor which reads a string of characters and combines them into… Expand

#### 57 Citations

Constructing a finite automaton for a given regular expression

- Computer Science
- SIGA
- 1980

A closer look at the algorithms involved in this process reveals that as far as its computational complexity is concerned the most crucial step is the construction of the nondeterminLstic automaton, which may be of time complexity O(n 2n). Expand

Design of a microprogrammed lexical microprocessor

- Computer Science
- MICRO 8
- 1975

The design of a lexical processor is presented, which is vertically microprogrammed for easier programming, and could be implemented as a microprocessor to be a member of a multi-microprocessor system for high-level languages. Expand

Program control via transition matrices—a novel application of micro-programming

- SIGMINI '76
- 1976

A micro-coded implementation of a particularly rich concept—the transition matrix (TM) is described, which permits TM-oriented decision-making techniques to be utilized in virtually any task that can be described by means of a transition matrix. Expand

A Language Independent Scanner Generator

- Computer Science
- 2008

A methodology for scanner generation that supports automatic generation of off the shelf scanners from specifications that is convenient because the user operates with meaningful constructs and no programming is required. Expand

On the look-ahead problem in lexical analysis

- Computer Science
- Acta Informatica
- 2005

A new lexical analyzer makes use of the suffix finite automata to identify tokens and it can detect lexical errors at an earlier time than traditional lexical Analyzers. Expand

A VLSI design for the parallel finite state automaton and its performance evaluation as a hardware scanner

- Computer Science
- International Journal of Computer & Information Sciences
- 2004

A hardware architecture and VLSI design of the parallel finite state model and the performance evaluation of the proposed architecture as a special purpose hardware recognizer device capable of performing pattern matching and text retrieval operations is presented. Expand

A Portable Syntax Analyzer for Microcomputers

- Computer Science
- Comput. Lang.
- 1985

The classical tools of high-level language analysis have been adapted so that a machine independent analyzer is provided and each phase consists of a number of table-based modules that lead to storage minimization as well as system reliability and maintainability. Expand

Construction of a Minimal Deterministic Finite Automaton from a Regular Expression

- Computer Science
- 2011

The main advantage of the minimal DFA construction algorithm is its minimal intermediate memory requirements and hence, the reduced time complexity. Expand

Myths and Facts about the Efficient Implementation of Finite Automata and Lexical Analysis

- Computer Science
- CC
- 1998

Analysis of the algorithms as well as run-time statistics on cache misses and instruction frequency reveals substantive differences in code locality and certain kinds of overhead typical for specific implementation strategies. Expand

Parsing with Neural and Finite Automata Networks: A Graph Grammar Approach

- Computer Science
- 2011

A twofold investigation on the use of graph grammar as it explores an attempt to use both aspects of graph grammars (to generate a valid language and to parse a language for its validity) for parsing with (i) neural networks and (ii) finite automata networks. Expand

#### References

SHOWING 1-10 OF 27 REFERENCES

AN ALGORITHMIC THEORY OF LANGUAGE

- Computer Science
- 1962

The Algorithmic Theory of Language takes the view that processing algorithms define classes of language and elements are considered to be elements with attractive and repulsive properties which cause them to link together to form linguistic structures. Expand

On Formalisms for Turing Machines

- Computer Science
- JACM
- 1965

Turing's original quintuple formalism for an abstract computing machine is compared with the quadruple approach of Post and with some new alterr~atives, and some new alternative deft-nitions are introduced. Expand

Automatic-programming-language translation through syntactical analysis

- Computer Science
- CACM
- 1962

The methods and techniques described in the present discussion represent the interpretation and partial development of a concept originally due to E. T. Dickinson and are presented as a tutorial exposition of syntax-directe(1 autoInatie-progranuning-language translation with samples from aspeets of ALGOL. Expand

A generalized technique for symbol manipulation and numerical calculation

- Computer Science
- CACM
- 1961

An unusual use of index registers is described which provides a computer technique that appears to include all known symbol manipulation techniques as simple subcases and is ideally suited to both symbolic and numerical operations. Expand

A new hierarchy of elementary functions

- Mathematics
- 1969

0. Introduction. Let C be the class of all functions on nonnegative integers into nonnegative integers for which there is a mechanical procedure for obtaining the values from the arguments. Such… Expand

Regular Expressions and State Graphs for Automata

- Mathematics, Computer Science
- IRE Trans. Electron. Comput.
- 1960

Algorithms are presented for 1) converting a state graph describing the behavior of an automaton to a regular expression describing the behavior of the same automaton (section 2), and 2) for… Expand

Design of a separable transition-diagram compiler

- Computer Science
- CACM
- 1963

A COBOL compiler design is presented which is compact enough to permit rapid, one-pass compilation of a large subset of COBOL on a moderately large computer. Versions of the same compiler for smaller… Expand

The AED approach to generalized computer-aided design

- Computer Science
- ACM '67
- 1967

This paper has been written in response to a request for an up-to-date broad view of the approach to computer-aided design taken by the M.I.T. Computer-Aided Design Project. Included in the… Expand

Translator writing systems

- Computer Science
- CACM
- 1968

A critical review of recent efforts to automate the writing of translators of programming languages is presented and various approaches to automating the postsyntactic aspects of translator writing are discussed. Expand

Simulation in the theory of computing systems

- 1968