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:

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 .



Add Comment

No comments.