Info

There exist numerous grammar inference methods, that use sets of both positive and negative examples as an algorithm input. The origin of these examples could be very diverse - from real-life data to manually crafted data. Both categories have their advantages and disadvantages.
Real-life data, as learning sets, promise the greatest performance in industrial applications if grammars are inferred properly. However, due to an imperfection of measurement equipment, some examples could include errors. Moreover, some of the phenomena, that are expressed through those data cannot be covered with formal language theory methods.

On the opposite side are sets for manually crafted grammars. Despite many advantages, such as possessing full knowledge about them or the certainty that the examples are error-free, they also create some issues - creating a grammar of given complexity with positive and negative learning sets is a difficult and time-consuming task.

Our iterative method of generating artificial context-free grammars allows the creation of a consistent context-free grammar of given parameters automatically, with positive and negative example sets. The algorithm consists of several steps. Firstly, a grammar of given parameters is generated using our original approach. Then it used to generate proper positive and negative sets.

The tool was presented at conferences and in papers given below:

Unold, O., Culer, Ł., Kaczmarek, A. (2018). Iterative method of generating artificial context-free grammars. The 14th International Conference on Grammatical Inference (ICGI 2018, Wrocław)

Additional materials:

For more detailed information about system please look at materials given below.

ICGI 2018 presentation

Contact

If you want to report a bug or have any suggestions don't hesitate to contact us - we would be grateful for any feedback.

Olgierd Unold

webpage: http://olgierd.unold.staff.iiar.pwr.wroc.pl/
e-mail: olgierd{dot}unold{at}pwr.edu.pl

Agnieszka Kaczmarek

e-mail: agnieszka{dot}kaczmarek{at}pwr.edu.pl

Łukasz Culer

webpage: http://lukasz.culer.staff.iiar.pwr.wroc.pl/
e-mail: lukasz{dot}culer{at}pwr.edu.pl

Credits

This tool was created thanks to papers given below:

[1] SAKAKIBARA, Yasubumi; KONDO, Mitsuhiro. GA-based learning of context-free grammars using tabular representations. In: ICML. 1999. p. 354-360.
[2] MAYER, Mikaël; HAMZA, Jad. Optimal test sets for context-free languages. arXiv preprint arXiv:1611.06703, 2016.
[3] YOUNGER, Daniel H. Recognition and parsing of context-free languages in time n3. Information and control, 1967, 10.2: 189-208.
[4] STARKIE, Bradford; COSTE, François; VAN ZAANEN, Menno. The Omphalos context-free grammar learning competition. In: International Colloquium on Grammatical Inference. Springer, Berlin, Heidelberg, 2004. p. 16-27.