/dsl-CYK-algorithm

This proyect is an implementation of the cyk algorithm but using a Domain Specific Languaje

Primary LanguageJava

dsl-CYK-algorithm instructions

Word: abbbabaa

G = ({a, b}, {S, A, B, E, C, X, Y, Z}, P, S)

With Productions P as:
A -> a | YE | XC
B -> b | XE | YZ
C -> AA
E -> YB | XA
S -> YB | XA | *
X -> b
Y -> a
Z -> BB

Applying CYK-Algorithm:

+-------+-------+-------+-------+-------+-------+-------+-------+
| a     | b     | b     | b     | a     | b     | a     | a     |
+-------+-------+-------+-------+-------+-------+-------+-------+
| A,Y   | B,X   | B,X   | B,X   | A,Y   | B,X   | A,Y   | A,Y   |
+-------+-------+-------+-------+-------+-------+-------+-------+
| E,S   | Z     | Z     | E,S   | E,S   | E,S   | C     |
+-------+-------+-------+-------+-------+-------+-------+
| B     | -     | B     | B     | A     | A     |
+-------+-------+-------+-------+-------+-------+
| Z     | Z     | Z     | E,S   | C     |
+-------+-------+-------+-------+-------+
| B     | -     | B     | A     |
+-------+-------+-------+-------+
| Z     | Z     | E,S   |
+-------+-------+-------+
| B     | B     |
+-------+-------+
| E,S   |
+-------+
The word abbbabaa is an element of the CFG G and can be derived from it.

Note: In order to help you runing this proyect please use the following link and download the pluging for xtext

  • Xtext plugin
  • Folow the steps for installing the plugin in your eclipse IDE

STEPS:

  1. Download this repository and open it as a workspace

  2. Once you have it, please go to the proyect org.xtext.cyk *and open de the file * MyFNC.xtext locaded here: image

  3. Rigth click on the file MyFNC.xtext and select Run as -> Generate xtext artifacts image image

  4. Rigth click on the file GenerateMyFNC.mwe2 and select Run as -> 1 MWE2 WorkFlow image image

  5. Rigth click on the proyect org.xtext.cyk and select Run as -> Eclipse aplication it will open a new Eclipse IDE image image

  6. On that new IDE create a new Java proyect, then at the folder src create a new file with the extention .fnc

  7. In your new file .fnc write your grammar as in the following pic you can paste it from the file test.txt image

  8. For writing the word that you'd like to test with the cyk algorithm , first write the reserved word Check enclose in quotation marks the string that you want to taste image

  9. Finally check the folder src-gen and you will find the output in the file result.txt image