# Catalogue of Artificial Intelligence Techniques

## Depth-first Parsing

**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 .

### References:

- Gazdar, G. and Mellish, C.,
*Natural Language Processing in Prolog: An Introduction to Computational Linguistics*, Addison-Wesley , 1989.

### Comments:

No comments.