I am a researcher starting to work on the field of parsing and recognition of languages.
As part of my background research, I am reading up on CYK. I understand that it requires the grammar to be in CNF. This however, is restrictive, as it forces the grammar to be restructured to remove $\epsilon$ rules from arbitrary nonterminals (allowing it only on the start symbol). The problem with this is that, when transforming the CYK recognizer to a CYK parser, a naive parse tree generation algorithm simply extracting the parse tree from the chart produces a parse tree that has a different structure from the original grammar before conversion to CNF. The main difference is that such a parse forest is finite in size, with no possibility of infinite recursion due to epsilon rules.
Hence, one may ask; can CYK parser be modified such that the restriction of CNF format on the grammar be relaxed, such that we can use arbitrary context-free grammars? It is fairly trivial to modify the CYK such that the other restrictions such as (1) either one terminal symbol or (2) two nonterminal symbols on a production rule is relaxed. However, arbitrary epsilons on rules is slightly harder because adding them likely changes the algorithm structure a little bit (one needs to pre-compute nullable nonterminals, handle nullable nonterminals in subparse checks etc.).
So, my question is, are there any updates to CYK that allows epsilon rule to be used as production rule for arbitrary nonterminals (not just the start symbol)?
