|Objective:||Because of its efficiency and relative simplicity of implementation, the chart parsing algorithm is popular for practical NLP applications. The goal of this module is to teach you the fundamental chart parsing algorithm and its useful variations. You will implement the chart parsing algorithm in Common Lisp, test it on a variety of cases, and analyze its efficiency in terms of the number of parse operations carried out on each sentence.|
Allen, James (1995). Natural Language Understanding (Redwood City, CA: Benjamin/Cummings), pp. 53-60 (Section 3.4).
Copies of this material will be available in the LTI Lab (CyH 277).
bottom-up-chart. Note that your function must implement two of the variations that are mentioned briefly by Allen: breadth-first vs. depth-first search, and exhaustive search vs. earliest answer.
chart.lisp, and be sure to include a statement which loads the given code (see above).
(run-tests 'bottom-up-chart)to see whether your implementation behaves as desired. The test code file defines a series of tests and the testing function
chart-questions.txt, answer the following questions:
(bottom-up-chart '(the man holds the water in the large can) 'dfs t) (bottom-up-chart '(the man holds the water in the large can) 'bfs t) (bottom-up-chart '(the man holds the water in the large can) 'dfs nil)You should get three different answers; what are the parse trees printed in each case?
NP V NP PP, the PP is a child of the object NP rather than the V.) How would you set the
ngets larger for sentences of the form
(NP V NP PP1 PP2 ... PPn), how would you characterize the difference in the number of parse operations for
(quitmode = NIL)vs.
(quitmode = T)?
chart-questions.txt) by copying them to the directory corresponding to your userid under: