Regular Expressions and Automata using Miranda.
(Full text available)
In these notes Miranda is used as a vehicle to introduce regular expressions, pattern matching, and their implementations by means of non-deterministic and deterministic automata. As part of the material, we give an implementation of the ideas, contained in a set of files. References to this material are scattered through the text. The files can be obtained by following the instructions in medskip noindent tt http://www.ukc.ac.uk/computer_science/Miranda_craft/regExp.html medskip noindent This material is based on the treatment of the subject in `the Dragon book', but provides full implementations rather than their pseudo-code versions of the algorithms. The material gives an illustration of many of the features of Miranda, including polymorphism (the states of an NFA can be represented by objects of any type); modularisation (the system is split across a number of modules); higher-order functions (used in finding limits of processes, for example) and other features.
- Depositors only (login required):