Smap

Choose the version you want to view.

Current version:Version message:

Some free variables replaced by anonymous ones

Click on a tag to show all related programs.

curry functional list logic functional_pattern

Click on the badge to open the comment window for viewing and writing comments.

No comments yet.

Created by mh on April 10, 2014 (last modified on April 10, 2014)

0 users favorited this

Description: A program specifying the structure of regular expressions, their semantics and some matching operations

Source code (Latest version):

---------------------------------------------------------------------
-- Specifying regular expressions and their semantics.
-- 
-- This example is taken from:
-- S. Antoy, M. Antoy: Functional Logic Programming
-- Comm. of the ACM, 53(4), pp. 74-85
---------------------------------------------------------------------

-- A data type to represent regular expression over some alphabet
data RE a = Lit a
          | Alt  (RE a) (RE a)
          | Conc (RE a) (RE a)
          | Star (RE a)

-- Example: regular expression (a|b|c)
abc = Alt (Alt (Lit 'a') (Lit 'b')) (Lit 'c')

-- Example: regular expression (ab*)
abstar = Conc (Lit 'a') (Star (Lit 'b'))

-- Extend the language of regular expressions by standard abstractions,
-- here an operator denoting at least one or more occurrences:
plus re = Conc re (Star re)

-- The semantics of regular expressions can be defined as a nondeterministic
-- operation associating any word of the language defined by the regular
-- expression:
sem :: RE a -> [a]
sem (Lit c)    = [c]
sem (Alt  a b) = sem a ? sem b
sem (Conc a b) = sem a ++ sem b
sem (Star a)   = [] ? sem (Conc a (Star a))

-- Matching a string against a regular expression can be defined by
-- the following constraint:
match :: RE a -> [a] -> Success
match r s = sem r =:= s

-- A constraint similar to Unix's grep (i.e., whether a regular
-- expression is contained somewhere in a string) can be defined
-- as follows:
grep :: RE a -> [a] -> Success
grep r s = _ ++ sem r ++ _ =:= s

-- Examples:
goal1 = grep abc    "dbe"   --> success
goal2 = grep abstar "dabe"  --> success (finite evaluation!)

-- Extend grep to return the substring which starts with the
-- regular expression:
grepShow :: RE a -> [a] -> [a]
grepShow r s | xs ++ sem r ++ _ =:= s  = drop (length xs) s
   where xs free

-- Examples:
goal3 = grepShow abstar "dbabe"
goal4 = grepShow abc    "dbeaxce"

main = goal3

Options

Versions

2 versions

Tags

5 tags

Comments

0 comments »

Regular expressions

implemented in Curry