parsingcontext-free-grammarcykearley-parser

simple CFG parser with epsilon transition

I have stumbled upon many different algorithms(CYK and Earley) to check whether or not a string is part of the CFL whose CFG is provided. I am looking for something simple to understand and implement. What I need to know is if the string is in the CFG or not. The CFG is given usually in the form of

S->S1 S2
S1->S1 a | a
S2->S2 b | b

The solution is supposed to accept epsilon transitions as well eg S1-> a | e

any ideas?

Solution

  • I found a really straight forward approach on this project

    https://code.google.com/p/cykparser/downloads/list

    Unlike other CYK parsers that go through unnecessary validation of the grammar. This parser is a really good proof of concept that just implements the CYK algorithm with basic grammar.

    The code is in python.