0
$\begingroup$

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)?

$\endgroup$
2
  • 1
    $\begingroup$ What is your actual goal? Is your goal to parse a string (determine whether it is in a context-free language), or to construct a single parse tree if it is in the language, or to construct a representation of all possible parse trees, or something else? Can you edit your question to clarify what you are trying to achieve? Rather than asking about a specific algorithm ("I want a variant of CYK") it would be better to specify the task (the inputs and outputs you wantt from the algorithm) and then discuss what's missing from CYK to make it suitable for your need. $\endgroup$
    – D.W.
    Jan 11, 2023 at 8:26
  • $\begingroup$ I am a researcher trying to improve upon parsing algorithms with the aim of using them in different aspects such as possibly improving its runtime or using it for error correction etc. I have not yet found improvements to CYK, hence asking the community. $\endgroup$ Jan 11, 2023 at 23:15

1 Answer 1

1
$\begingroup$

If you want to build a representation of all parse trees, I think a GLR (Tomita) parser is a better fit than something based on CYK. A GLR parser outputs a compact representation of the set of all parse trees, and does not require transformation to CNF.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.