CYK algorithm question

CYK algorithm question

par Alexander Khalil Arwadi,
Nombre de réponses : 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?

En réponse à Alexander Khalil Arwadi

Re: CYK algorithm question

par 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.