Granny [left recursion killer for grammars] [script]

Some of the small programs I wrote on my spare time. They are Free Software, and written mostly in OCaml.
User avatar
Posts: 3041
Joined: Fri Apr 07, 2006 12:10 pm
Location: Schtroumpf

Granny [left recursion killer for grammars] [script]

Postby Vincent » Sat Jan 03, 2009 3:22 pm

the source code distribution
(7.77 KiB) Downloaded 800 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
a typical grammar with left recursions, direct and indirect, and the corresponding granny LaTeX output.
{ Vincent Hugot }

Return to “Programs”

Who is online

Users browsing this forum: Bing [Bot] and 15 guests