VLSI architecture for fast context-free language recognition (Earley's algorithm)
Y. P. Chiang, K. S. Fu · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1982
Earley's algorithm has been commonly used for the recognition of general context-free languages and usually has time complexity o(n/sup 3/). This paper presents a parallel Earley's algorithm in terms of x/sup */ operation. By restricting the input context-free grammar to be lamda-free, it is able to implement this parallel algorithm on a triangular shape VLSI system. This system has an efficient way of moving data around through fast buses, slow buses and INP bus. It is guaranteed that the right data will arrive at the right place at the right time. Simulation results showed that this system can recognize a string with length n in 2n+1 system unit times. 18 references.