CYK Parser
Introduction
How
to Run CYK Parser
In the previous version of JFLAP, user had to rely on brute force parser to check whether certain string is accepted by the grammar or not. Unfortunately, brute force parser could take quite long time to parse the input. To improve efficiency in parsing, CYK Parser has been implemented in new version of JFLAP.
CYK Parser transforms the given grammar into CNF form and performs CYK parsing algorithm to check the string's membership in the grammar.
We will begin by entering a new grammar. You can either enter the grammar (shown below) or load the file grammarForCYK.jff.
Then you can click on Input, followed by CYK Parse. After clicking CYK Parse, you should see a window that is very similar to Brute Force Parse window.
Now you can input a string and to check its membership in the grammar. Enter the string “aabbb”. Immediately, you will see the answer on the panel telling you that the string is accepted.
Since the string is accepted by the grammar, you can try to see which productions were applied to achieve our input string by clicking STEP button. You can also Click on Derivation Table to see which production rule has been applied to the input string. After clicking one STEP button, your window should look like one of these :
After clicking STEP until the end, you will see either entire tree or derivation table of how the input string has been accepted by the grammar.
CYK Parse works so much faster than traditional Brute Force Parse. You can see the remarkable difference in speed, if you try to parse input string as “aaaabbbbb” with the same grammar in Brute Force Parse. It would probably take long time to get the result. However, CYK Parse will immediately tell you that the string is accepted by the grammar.
*NOTE: You can also perform multi-run with CYK Parser as you did with Brute Force Parser.
This concludes our brief tutorial on CYK Parsing. Thanks for reading!
