Deductive Parsing Discussion
Item Semantics
[X, Il, Ir, i, j] -> the tree rooted in X with left subtree given by the item reference Il and right subtree given by the item reference Ir, licensing the substring w_i ... w_(i+j) is a tree licensed by the the grammar.
Axioms
[X, ~, ~, i, 0] s/t X |-> w_i
Inference Rules
| [X, Il, Ir, i, j] [Y, Jl, Jr, i+j+1, k] | s/t Z |-> X Y |
| [Z, [X, Il, Ir, i, j], [Y, Jl, Jr, i+j+1, k], i, i+j+1+k] |
Goal
[S, Il, Ir, 0, |w|]
Questions
- What is the maximum number of items given |G| and |w|?
- What is the complexity?
- What is the new complexity if we pack the item references in lists, e.g. [X, Tl, Tr, i, j] where Tl and Tr refer to lists of items rather than individual items?
- Compare the charts of the parse forest representation to the and/or graph described in the Lang
Posted by kellyia at June 9, 2004 02:27 PM