SLR INFERENCE - AN INFERENCE SYSTEM FOR FIXED-MODE LOGIC PROGRAMS, BASED ON SLR PARSING

Definite-clause grammars (DCGs) generalize context-free grammars in su ch a way that Prolog can be used as a parser in the presence of contex t-sensitive information. Prolog's proof procedure, however, is based o n backtracking, which may be a source of inefficiency. Parsers for con text-free grammars that use backtracking, for instance, were soon repl aced by more efficient methods, such as LR parsers. This suggests inco rporating the principles underlying LR parsing into a parser for gramm ars with context-sensitive information. We present a technique that ap plies a transformation to the program/grammar by adding leaves to the proof/parse trees and placing the contextual information in such leave s. An inference system is then easily obtained from an LR parser, sinc e only the parts dealing with terminals (which appear at the leaves) m ust be modified. Although our method is restricted to programs with fi xed modes, it may be preferable to DCGs under Prolog for some programs . (C) Elsevier Science Inc., 1998.