Page 228 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes The sequence of items corresponding to the sample parse of ‘they sh’ above begins:
0. <[.S], [they fish]>
1. < [S .NP VP], [they fish]>
2. < [S .NP VP], [NP .they], [they fish]>

3. < [S .NP VP], [NP .fish], [they fish]>
4. < [S .NP VP], [NP they.], [ fish]>
5. < [S [NP they] .VP], [ fish]>
6. < [S [NP they] .VP], [VP .Vi], [ fish]>

7. < [S [NP they] .VP], [VP .Vt NP], [ fish]>
etc.
Notice that both 2 and 3 were produced from 1, but that 3 was discarded because none of the
actions applied to it. The order in which new items are processed can be varied in order to give
depth first or breadth first search behaviour. Depending on the search strategy followed, the top
down algorithm may go into a loop when certain types of rule are found in the grammar. For
example, if we added rules for more complex types of NP, we would encounter ‘left recursion’
of the category NP:
NP -> NP ‘s N:possessive NPs like [[John] ‘s sister]
Now from an item like:
< S -> .NP VP ....>

we would produce one like
< NP -> .NP ‘s N ....>
and this would in turn produce another
< NP -> .NP ‘s N ....>

and so on. There are two solutions: either rewrite the grammar to eliminate left recursion,
which is always possible in principle, or add an extra step to the algorithm to check for repeated
items. Some grammars will potentially send any sound and complete parsing algorithm into a
loop: namely, those that contain cycles of the form A -> ...... -> A, where some symbol exhaustively
dominates itself. This is not necessarily a bug in the parsing algorithms: such grammars will
assign an infinite set of parse trees to any structure containing an A. Under these circumstances,
the parser is merely trying to do what it is supposed to do and find all possible parses.

12.3.2 Bottom Up Parsing

The operation of a bottom up algorithm for CFG can be illustrated by the following sequence of
operations for ‘they sh’: Structure Input so far remaining
[they fish]

[NP they] [fish]
[NP they][Vi fish] []
[NP they][Vp [Vi fish]] []

[S [NP they][Vp [Vi fish]]] []

222 LOVELY PROFESSIONAL UNIVERSITY