Catalogue of Artificial Intelligence Techniques
Keywords: backtracking, backtracking parser, breadth-first search, parsing, pseudo-parallel parser
Categories: Natural Language
Author(s): Henry Thompson
Amounts to a Depth-first Search of the tree of alternatives which arise in the parsing process. Clearest in the context of Top-down parsing of a Context-free Grammar. Suppose our grammar includes the following rules:
Suppose that in the course of analysing a string we are trying to find an , which leads us to look for a , which we find. A choice then confronts us--do we look now for an following the , or do we rather look for a at the same place we found the ? Given the possibility of ambiguity, either or both course may succeed. The first choice, which leads to a backtracking parser, is depth-first. The second choice, which leads to a pseudo-parallel parser, is Breadth-first. If the candidate string was in fact ambiguous, in the depth-first case we would find in that order, whereas in the breadth-first case we would find .
- Gazdar, G. and Mellish, C., Natural Language Processing in Prolog: An Introduction to Computational Linguistics
, Addison-Wesley , 1989.