Though facing the fear that someone might not like my question but does somebody know a useful tool to either
a context-free grammar automatically ?
I need to resolve a rather long chain of left-recursion in my grammar.
So far I've tried this algorithm and this tool. But both are only applicable for smaller grammars and provide practically unusable results (1000's of rules).
During my research I found two excellent tools for dealing with CFG's I want to share here (since I am sure they will help others as they helped me):
This application removes left-corner cycles from a context-free grammar to make it more acceptable for LL parsers. Of course, this can change the associativity of operators in the language, and this does not resolve problems with first sets, follow sets, and nullable symbols.
Allows the user to specify a context-free grammar (either using a GUI or text-only). Demonstrates standard context-free grammar normalization algorithms:
- reduced form
- Chomsky normal form
- strict Chomsky normal form
- epsilon-free form
- chain-rule-free form
- Greibach normal form
In addition, the CYK algorithm can be used on sCNF grammars to parse a word and generate a parse tree in case the world is generated by the grammar.
Here is another automated tool.
