CYK algorithm question

CYK algorithm question

by Alexander Khalil Arwadi -
Number of replies: 1

What happens if the we can't reach S (or a top level category non-terminal) at the top of the chart? What will the parser output?

In reply to Alexander Khalil Arwadi

Re: CYK algorithm question

by Jean-Cédric Chappelier -

Well... it's up to you (to design your tool to fit your needs): recognizer or analyzer ? and if an analyzer: shipping the whole chart or all the parse trees?

If it's a recognizer, then the output should certainly be "no".
If it's an analyzer outputting the list of parse trees (exponential complexity, then, in the general case): empty list
If it's analyzer outputting a chart: then its chart, whatever it contains; which then may let you later do some "reconstructive correction" from the pieces you might found lower in the chart.