VLSI (Very Large Scale Integration) Architectures for Recognition of Context-Free Languages,
Two VLSI architectures are introduced for high speed recognition of general context-free languages based on the Cocke-Younger-Kasami algorithm and Earley's algorithm.
Abstract
Abstract : The speed of formal languages recognition is frequently considered to be important in many applications such as syntactic pattern recognition, artificial intelligence, natural language processing, syntax analysis of programming languages, pattern matching, etc. With the continuing advances in Very Large Scale Integration (VLSI) technology making circuitry smaller and faster, many processors can now be put together on a single chip and communicate with each other at on-chip speeds. This offers the opportunity in building low-cost, high-performance, special-purpose multiprocessor architectures to aid in the rapid solution of sophisticated language recognition problems. In this paper, two VLSI architectures are introduced for high speed recognition of general context-free languages. These languages are most commonly used in the mentioned areas and their recognition methods have been well studied. The recognition methods employed in this paper will be based on the Cocke-Younger-Kasami algorithm and Earley's algorithm. Multiprocessing and pipelining techniques are used in the architectures to execute the algorithm in parallel. (Author)