language: en

Efficient Finite-State Approximation of Context Free Grammars

C.M. Rood
Computer Laboratory University of Cambridge
cmr1001@cl.cam.ac.uk

Abstract. 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.

1 THE APPROXIMATION