# 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:

$X\to Q,R,S\mathrm{.}\phantom{\rule{0ex}{0ex}}X\to U,V,W\mathrm{.}$

Suppose that in the course of analysing a string we are trying to find an $X$, which leads us to look for a $Q$, which we find. A choice then confronts us--do we look now for an $R$ following the $Q$, or do we rather look for a $U$ at the same place we found the $Q$? 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 $QRS{X}_{1}UVW{X}_{2}$ in that order, whereas in the breadth-first case we would find $QURVSW{X}_{1}{X}_{2}$.

### References:

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

### Comments:

No comments.