Catherine Rood (University of Cambridge)
This paper introduces a novel method for constructing finite--state machines recognising context free (CF) grammars. The method utilizes the idea of a path through a finite--state machine (FSM). Certain paths form the basis for an unfolding process which is applied to the LR(0) characteristic finite--state machine (CFSM) corresponding to the grammar. The next section discusses the approximation algorithm, including this unfolding process, in more detail, and section 3 introduces the concept of an unfolding criterion. Section 4 proves the soundness of the approximation method, and its exactness to arbitrary, fixed recursive depths. Section 5 presents initial computational figures resulting from an implementation of the method. A variation of the method that is more computationally feasible is discussed. The final section compares the method with existing research on finite--state approximation of CF grammars, and presents preliminary conclusions regarding the method.