Efficient Parsing of Fixed-Mode DCGs

Manuel Vilares Ferro
Miguel Angel Alonso Pardo
David Cabrero Souto

in Proc. of FORMAL GRAMMAR'97, Aix-en-Provence, France, 1997.


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.

Manuel Vilares Ferro / vilares@dc.fi.udc.es
Miguel Angel Alonso Pardo / alonso@dc.fi.udc.es
David Cabrero Souto / cabrero@dc.fi.udc.es