Visualizing the McNaugthon-Yamada-Glushkov Construction

Once in a while I poke in my old Perl stuff to find something interesting. Luckily, this is usually the case.

Today, I found a script that draws an annotated syntax tree of a regular expression. The annotation shows the state sets calculated when applying the McNaugthon-Yamada-Glushkov algorithm to construct a finite automaton from the regular expression.

You can read about it in "Bruce W. Watson. Taxonomies and Toolkits of Regular Language
Algorithms. PhD thesis, Faculty of Computing Science Eindhoven
University of Technology, The Netherlands, 1995".

Here is an image:


I just thought about sharing this bit because there once was a thread about how we could improve marketing for Perl and one of the answers was to write (more) Perl applications.
So, here is one :)

Leave a comment

About Alex

user-pic I like Perl.