I am following Bottom up chart parsing algorithm from Natural Language Understanding book by James Allen. It is

enter image description here

I couldn't understand the 3rd step. I thought that when active arc is added the dot is advanced. But dot is indroduced in the third step. The example says that

enter image description here

This example shows dot is advanced. But step 3 says otherwise

  • 1
    $\begingroup$ It looks like few users have access to that book. Can you provide a link that shows several page or even a whole chapter? $\endgroup$ – John L. Feb 25 '19 at 12:47
  • 1
    $\begingroup$ @Apass.Jack 1995 $\endgroup$ – user5507 Mar 2 '19 at 2:00

You have spotted a typo in that book.

The dot $\circ$ in step 3 of figure 3.11 should be after constituency C. To be explicit and precise, step 3 should be stated as the following.

  1. For each rule in the grammar of form X $\to$ C X$_1$ ... X$_n$, add an active arc of form X $\to$ C $\circ$ X $_1$ ... X$_n$ from position P$_1$ to P$_2$.

As you have observed, all examples following figure 3.11 show clearly that the dot $\circ$ are placed after constituency C.

This can also be verified by the statement a few lines below.

Notice that active arcs are never removed from the chart.

We can check that we cannot, indeed, find any instance of an active arc in all of section 3, chapter 3 of the book that starts with a $\circ$.

There is also a rule that for each active arc from position $a$ to $b$, the symbols before the $\circ$ should correspond to the terminals between those positions inclusively. That rule also implies that a dot $\circ$ cannot be at the very front of an active arc.

By the way, that books is written so clearly that I have to say that glaring typo is an almost reverse testimonial.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.