Page 1 of 1

Granny [left recursion killer for grammars] [script]

Posted: Sat Jan 03, 2009 3:22 pm
by Vincent
the source code distribution
(7.77 KiB) Downloaded 937 times

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:

  • 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 :sweat
Language: Objective Caml License: GNU GPL OS: Any