Page 230 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes framework (any grammar containing them can in principle be converted to one, usually much
larger, recognizing the same language which does not) but they are practically very useful in
describing, for example, movement phenomena, in a reasonably concise way. Bottom up parsers
find instances of such rules applied at every possible point in the input which can lead to much
wasted effort. A better parsing algorithm than either pure top down or pure bottom up can be
got by combining features of both. Operating bottom up means that the process is guided by
what is actually in the input, rather than what the grammar predicts might be there (which will
give a very large number of possibilities for a realistic grammar and lexicon). But imposing
some top down constraints means that we can use what we have already found, with our
knowledge about possible grammatical structures, to guide the search for what follows.
One such combined algorithm is the following. It is a member of the family of ‘left-corner’
parsing algorithms, since it begins at the left corner of the constituent it is trying to build, when
viewed pictorially:

Mother
/\
/\
‘Left Corner’ ......

It is also a ‘predictive’ parser, in that it uses grammatical knowledge to predict what should
come next, given what it has found already.
To describe this left-corner predictive parsing algorithm we extend our notion of an ‘item’ to be:

<CurrentConstituent, RemainingInput, MotherCatSought,
DaughtersFound, DaughtersSought, StackOfIncompleteConstituents>
There are four operations creating new items from old:

‘Shift’ is as before, taking the next word from RemainingInput and making it (suitably
labelled) the CurrentConstituent.
‘Predict’ finds a rule whose leftmost daughter matches the CurrentConstituent, and then
fills the MotherCatSought, DaughtersFound, and DaughtersSought fields of the new item
as appropriate, copying these parts of the old item onto the StackOfIncompleteConstituents.

‘Match’ applies when the CurrentConstituent is the next item in DaughtersSought: the
new item has a null CurrentConstituent, and undergoes appropriate changes to the two
Daughters fields.

‘Reduce’ applies when there are no more DaughtersSought and creates an item with a new
CurrentConstituent built from the MotherCatSought and the DaughtersFound, popping
the most recent StackOfIncompleteConstituents entry to form the new Mother and
Daughters fields.
With the Predict operation defined as above the algorithm will be sound and complete. However,
it will derive no benefit from the top down information it carries, for that is not yet being used
to constrain parsing hypotheses. What we need to do is to check that the mother categories on
the rules found by Predict can be a ‘left corner’ of the current MotherCatSought, i.e. can be the
leftmost daughter of some tree dominated by the MotherCat. This information can be calculated
from the grammar fairly easily: we will not show how to do this here but for the grammar given
above the ‘left-corner-of’ relation is:

<NP,S>
<Aux,VP>

224 LOVELY PROFESSIONAL UNIVERSITY