Thursday, December 13, 2007

Approximating context-free grammars with regular grammars.

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.

No comments: