Parsing as Resolution
M. Vilares Ferro
J. Graña Gil
Abstract
A general context-free parsing algoritm based on logical dynamic programming
techniques is described. The analyzer takes a general class of context-free
grammar as drivers, and any finite string as input. In an empirical comparison,
the new system appears to be superior to the others context-free analysers
(as for example the SDF system), and comparable to the standard generators
of deterministic parsers (as for example YACC, the standard generator of compilers
in UNIX) when the input string is not ambiguous.
Key words: Context-Free Parsing, Dynamic Programming, Horn Clauses,
Earley Deduction, Definite Clause Programs, Logical Push-Down Automata.
This work was totally supported by the Eureka Software Factory project.
Manuel Vilares Ferro /
vilares@dc.fi.udc.es
Jorge Graña Gil /
grana@dc.fi.udc.es