patternMinor
Bottom up chart parser adding active arc step
Viewed 0 times
arcactivechartparseraddingbottomstep
Problem
I am following Bottom up chart parsing algorithm from Natural Language Understanding book by James Allen. It is
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
This example shows dot is advanced. But step 3 says otherwise
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
This example shows dot is advanced. But step 3 says otherwise
Solution
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.
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.
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.
- 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.
Context
StackExchange Computer Science Q#104110, answer score: 2
Revisions (0)
No revisions yet.