Got a version of the Mohri and Nederhof algorithm working with SWI-prolog. The prolog source (attached here) is from Implementation of Regular Approximation of Context-Free Grammars Through Transformation by Tapani Raiko at Helsinki University of Technology.
Raiko explains how to use the program in his write-up.
A similar idea is implemented by Tanaka Akira in abnf converter. It's a ruby program to convert Augmented BNF to Regexp.