Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

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:

XQ,R,S.XU,V,W.

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 QRSX1UVWX2 in that order, whereas in the breadth-first case we would find QURVSWX1X2.


References:


Comments:

Add Comment

No comments.