Efficient Parsing of Fixed-Mode DCGs

In this paper we describe an efficient parsing model for monotonous fixed-mode DCGs, including traversing of cyclic terms. The algorithm can be viewed as an extension of the classic push-down automaton model in dynamic programming along with the incorporation of a mechanism for detecting and traversing cyclic trees. Details of implementation and experimental tests are described. Experimental results show the performance of our approach.

Keywords: Definite Clause Grammar, Dynamic Programming, Logical Push-Down Automaton, Cyclic Term.