In one assignment, I was given a grammar with left recursions which I needed to parse with an LL(k) parser.
Rather than applying the left-recursion elimination algorithm by hand, I wrote this small script to do the job for me [I'm notoriously lazy]. Grammars are to be described using the data structure directly in the source code, and the script generates the new, left-recursion-free grammar in a readable form, either plain text or LaTeX.
Example granny LaTeX output:
Notes:
- The LaTeX output depends on my old LaTeX package
- This script is provided as-is, in the hope it might be useful to someone, but it is not user-friendly in the least : there is no user's manual or help page, and some knowledge of OCaml and Languages Theory is required to understand, use and extend it.
- Thought: If I had time, I would write a full program implementing all common algorithms on automata and context-free grammars, complete with a natural description language as input and LaTeX output; you could go from (regular) grammar to automaton, minimise it, go back to a grammar, kill left recs, try out different algorithms to eliminate left recs and see which is best etc etc. I could not find any program doing all that on the internet. This would be fun to write but I don't have the time
