4

Though facing the fear that someone might not like my question but does somebody know a useful tool to either

  • resolve left recursion or to
  • simplify

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).

3

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.

1

Here is another automated tool.

  • Easy input format
  • Better output format
  • Also supports multi-letter symbols
  • What happens if the link you provided changes? How would your answer still be valid? You should use the link only as a reference and include as much information as possible. – rrirower Jan 25 '17 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.