Top-down parsing

The naive bottom-up parser of Section 5.2 never formed hypotheses about what it was looking for or used such hypotheses to decide its next move. It only ever checked rules to see if there was a legitimate way of putting together the pieces already to hand. That is why it encountered problems with rules that involved putting together 'empty space'. By contrast, a pure (left-to-right) top-down (depth-first) parser would have proceeded roughly as follows:

    I am looking for an S.

      What can an S consist of?

      An S can consist of an NP followed by a VP.

      So I need to look for an NP first.

        What can an NP consist of?

        There are no grammar rules expanding NP.

        There is a lexical entry listing 'nurses'

          as a member of the category NP.

        Is the first word in the string 'nurses'?

        No.

        There is a lexical entry listing 'MediCenter'

          as a member of the category NP.

        Is the first word in the string 'MediCenter'?

        Yes.

      I have found an NP consisting of the word 'MediCenter'.

      I now need to look for a VP.

***     What can a VP consist of?

        A VP can consist of a V.

        I now need to look for a V.

          What can a V consist of?

          There are no grammar rules expanding V.

          There is a lexical entry listing 'died'

            as a member of the category V.

          Is the next word in the string 'died'?

          No.

          There is a lexical entry listing 'employed'

            as a member of the category V.

          Is the next word in the string 'employed'?

          Yes.

        I have found a V consisting of the word 'employed'.

      I have found a VP consisting of a V

        consisting of the word 'employed'.

    I have found an S consisting of:

      an NP consisting of the word 'MediCenter'

      and a VP consisting of

      a V consisting of the word 'employed'.

    Have I reached the end of the string?

    No.

    Oh dear, I must have done something wrong.

    Try going back to *** and doing something different.

        I still need to look for a VP.

          What can a VP consist of?

          A VP can also consist of a V followed by an NP.

          I now need to look for a V.

            What can a V consist of?

            There are no grammar rules expanding V.

            There is a lexical entry listing 'died'

              as a member of the category V.

            Is the next word in the string 'died'?

            No.

            There is a lexical entry listing 'employed'

              as a member of the category V.

            Is the next word in the string 'employed'?

            Yes.

          I have found a V consisting of the word 'employed'.

        Now I need to look for an NP.

          What can an NP consist of?

          There are no grammar rules expanding NP.

          There is a lexical entry listing 'nurses'

            as a member of the category NP.

          Is the first word in the string 'nurses'?

          Yes.

        I have found an NP consisting of the word 'nurses'.

      I have found a VP consisting of:

        a V consisting of the word 'employed'

        followed by an NP consisting of the word 'nurses'.

    I have found an S consisting of:

      an NP consisting of the word 'MediCenter'

      and a VP consisting of

      a V consisting of the word 'employed'

      followed by an NP consisting of the word 'nurses'.

    Have I reached the end of the string?

    Yes.

    I have succeeded.

Figure 5.5 shows the search tree for top-down parsing of the example sentence 'MediCenter employed nurses'. In top-down recognition, a state can be characterized by a sequence of goals and a sequence of remaining words. In our tree, we separate the goals from the remaining words with a colon (:). Thus, d NP : e n describes the state of the recognizer when it is trying to find the word 'died' followed by an NP and when the remaining words are 'employed nurses'.

Top-down parsing does not have any problem with e-productions, but (when performed left to right) encounters trouble with rules that exhibit left recursion. Here is another way we could have rewritten our VP rules:

Rule {simple verb phrase}

    VP -> V.

Rule {complex verb phrase}

    VP -> VP NP.

but now the rules will in fact generate more strings. Of these rules, the second is left recursive in that the first symbol on the RHS is the same as the LHS. With left-recursive rules in a grammar, a left-to-right, top-down parser will get into an infinite loop if it makes the wrong choices, and if we are asking for all parses it will, of course, in the end have to try all possible choices:

I now need to look for a VP.

What can a VP consist of?

A VP can consist of a VP followed by an NP.

   I now need to look for a VP.

   What can a VP consist of?

   A VP can consist of a VP followed by an NP.

      I now need to look for a VP.

      What can a VP consist of?

      A VP can consist of a VP followed by an NP.

      ...

When we are using complex feature-based categories, left recursion also arises when the first category on the RHS of a rule is more general than the one on the LHS (see Chapter 7 for fuller discussion of the issues that features give rise to in parsing). Again, it is possible to transform a left-recursive grammar into an equivalent one with no left-recursive rules, and one that generates exactly the same set of strings (although it will not assign the same structures).

Exercise 5.3

Send us a comment.