Need help to solve the function haskell regex manipulation function

user_17460873 0
Viewed 77

The definition

firsts :: RE sym -> [sym]
firsts = undefined

The RE data

data RE sym -- sym is type of alphabet symbols
    = RSym sym  -- match single symbol
    | REps  -- match empty string
    | RZero  -- match nothing
    | RStar (RE sym)  -- choice
    | RPlus (RE sym)  -- concatenation
    | RAlt (RE sym) (RE sym) -- 0+ repetition
    | RSeq (RE sym) (RE sym) -- 1+ repetition
    deriving (Show)

The Alphabet used in regex

data Alphabet = A | B | C deriving (Show, Eq)

firsts re returns a list containing every symbol that occurs first in some string in the language for re. For example, if re represents "A(C|B)|BC", then the strings in its language are AB, AC, and BC. In this case, firsts re might return [A,B].

Note that the type signature does not include Eq sym or Ord sym. This means that your code will be unable to sort or remove duplicates from the list of symbols it returns. The requirements your code must satisfy are:

  1. the list returned must be finite (even if the language is infinite!)
  2. every symbol in the list must be the first symbol in some string in the language
  3. for every string in the language, its first symbol must occur in the list Individual symbols may occur in any order, and may be duplicated any finite number of times.
nsregularexpression automata regular-language haskell regex
1 Answers

The idea is to analyze the regular expression, not produce all possible strings for that regular expression. For example the RSym sym clearly has sym as first (and only) character whereas REps has no start characters.

It thus means that you should define a function that aims to find the initial characters. You thus implement such function like:

firsts :: RE sym -> [sym]
firsts (RSym sym) = [sym]
firsts REps = []
firsts RZero = …
firsts (RStar sub) = …
firsts (RPlus sub) = …
firsts (RAlt sub1 sub2) = …
firsts (RSeq sub1 sub2) = …

where sub and sub1 and sub2 are sub-regexes. You will thus for some of these regular expressions have to make recursive calls to find out the first characters of the subregex(es).

For (RSeq sub1 sub2) you will need to make a helper function matchEmpty :: RE sym -> Bool that checks if the regular expression matches with the empty string. If that is the case then the first characters of sub2 can be the first characters of the regex whereas if sub1 does not match with the empty string, then that is impossible.

user_675790
Related