HaLeX 1.2.4 → 1.2.5
raw patch · 6 files changed
+388/−8 lines, 6 filesdep +HUnitdep +QuickCheck
Dependencies added: HUnit, QuickCheck
Files
- HaLeX.cabal +7/−6
- HaLeX_lib/Language/HaLex/Sentences.hs +162/−0
- HaLeX_lib/Language/HaLex/Test_HaLex.hs +136/−0
- HaLeX_lib/Language/HaLex/Test_HaLex_Quickcheck.hs +81/−0
- INSTALL +1/−1
- README.md +1/−1
HaLeX.cabal view
@@ -1,6 +1,6 @@ name: HaLeX-version: 1.2.4-synopsis: HaLeX enables modelling, manipulation and animation of regular languages+version: 1.2.5+synopsis: HaLeX enables modelling, manipulation and visualization of regular languages description: This library was developed in the context of a programming methodology course for undergraduate students, and as a consequence, it was defined mainly for educational purposes. Indeed, it provides a clear, efficient and concise way to define, to understand@@ -11,7 +11,7 @@ license: PublicDomain license-file: LICENSE author: João Saraiva-maintainer: João Saraiva <jas@di.uminho.pt>+maintainer: João Saraiva <saraiva@di.uminho.pt> homepage: http://www.di.uminho.pt/~jas/Research/HaLeX/HaLeX.html tested-with: GHC==6.8.2@@ -21,17 +21,18 @@ extra-source-files: scripts/Make_Animation, scripts/faAnim.lefty, example/real, example/real_dfa.hs, example/real_ndfa.hs, example/GenMDfa.hs Library- build-depends: base>4 && <5, mtl+ build-depends: base>4 && <5, mtl, HUnit, QuickCheck extensions: FlexibleContexts, FlexibleInstances, MultiParamTypeClasses ghc-options: -Wall hs-source-dirs: HaLeX_lib- Exposed-modules: Language.HaLex.RegExpAsDiGraph, Language.HaLex.Ndfa, Language.HaLex.Dfa2MDfa, Language.HaLex.Minimize,+ exposed-modules: Language.HaLex.RegExpAsDiGraph, Language.HaLex.Ndfa, Language.HaLex.Dfa2MDfa, Language.HaLex.Minimize, Language.HaLex.Examples.Real, Language.HaLex.Examples.Robot, Language.HaLex.RegExpParser, Language.HaLex.FaClasses, Language.HaLex.RegExp, Language.HaLex.Dfa, Language.HaLex.DfaMonad, Language.HaLex.Fa2RegExp, Language.HaLex.Parser, Language.HaLex.RegExp2Fa, Language.HaLex.FaAsDiGraph,- Language.HaLex.FaOperations, Language.HaLex.Util, Language.HaLex.Equivalence+ Language.HaLex.FaOperations, Language.HaLex.Util, Language.HaLex.Equivalence,+ Language.HaLex.Sentences, Language.HaLex.Test_HaLex, Language.HaLex.Test_HaLex_Quickcheck Executable halex main-is: halex.hs
+ HaLeX_lib/Language/HaLex/Sentences.hs view
@@ -0,0 +1,162 @@+-----------------------------------------------------------------------------+-- |+-- Module : Language.HaLex.Sentences+-- Copyright : (c) João Saraiva 2017+-- License : LGPL+--+-- Maintainer : jas@di.uminho.pt+-- Stability : provisional+-- Portability : portable+--+-- Generation of sentences for (regular) languages defined via+-- Regular Expressions and Finite Autumata+--+-----------------------------------------------------------------------------++module Language.HaLex.Sentences ( sentencesRegExp+ , sentencesNdfa+ , sentencesDfa+ , onePathDfa+ ) where++import Language.HaLex.Dfa+import Language.HaLex.Ndfa+import Language.HaLex.RegExp+import Language.HaLex.RegExp2Fa+import Language.HaLex.RegExpParser+import Language.HaLex.FaOperations+import Language.HaLex.Minimize+import Data.Maybe+import Data.List++-----------------------------------------------------------------------------+-- * Generating Sentence+++-- | Generates a set of sentences of the language defined by a given+-- Regular Expression++sentencesRegExp :: Ord sy => RegExp sy -> [[sy]]+sentencesRegExp = sentencesDfa . regExp2Dfa++-- | Generates a set of sentences of the language defined by a given+-- NonDerterministic Finite Automaton++sentencesNdfa :: (Ord sy , Ord st) => Ndfa st sy -> [[sy]]+sentencesNdfa = sentencesDfa . minimizeDfa . ndfa2dfa +++-- | Generates a set of sentences of the language defined by a given+-- Deterministic Finite Automaton.+-- +-- It computes a set of paths starting from the start state and ending+-- in an accepting state, which include all transitions/edges of the+-- automaton.+--+-- This function does not computes the smallest set (of paths/sentebces),+-- as computed by the "Chinese Postman Problem"+--+-- Function written by MSc student José Nuno Macedo (72424)+-- in the context of the 2016/17 edition of the course +-- "Analysis and Testing of Software", MIEI, Univ. Minho.+--++sentencesDfa :: (Ord st, Eq sy, Ord sy) => Dfa st sy -> [[sy]]+sentencesDfa = nub . sentencesDfa'++-- | This auxiliar function uses the transition table computed from the+-- given automaton to generate a finite set of sentences the the+-- language.++sentencesDfa' :: (Ord st, Ord sy) => Dfa st sy -> [[sy]]+sentencesDfa' d = sentences d tt tt+ where tt = transitionTableDfa d++-- | This function generates all paths (corresponding to valid sentences+-- of the language) that cover all transitions of the finite automaton. +-- The transition table serves two purposes when calling this function:+-- - to know the transitions of the automaton+-- - to serve has the state recording all transitions not used (yet)+-- (in the begining this list should be the full transition+-- table of the dfa, and the function terminates when this+-- list is empty: no more tarnsitions need to be covered)++sentences :: (Ord st, Ord sy)+ => Dfa st sy -- ^ Automaton+ -> [(st, sy, st)] -- ^ Dfa's Transition Table+ -> [(st, sy, st)] -- ^ Table with transitions to be used+ -> [[sy]] -- ^ List of sentences++sentences _ _ [] = []+sentences d@(Dfa _ _ s z _) tt mustUse = sys ++ rec_call+ where+ -- First, we compute all paths from the start state to each state+ -- in the set of final sates. Each path produces the list of+ -- transitions that need to be used and the sentence formed by+ -- that path+ + (newMustUses, sys) = unzip [onePath tt mustUse [] fs' s | fs' <- z ]++ -- The lists of transitions to be used (produced by each path)+ -- is merged into a sinle list of transitions still to be used++ newMustUse = foldr1 intersect newMustUses++ -- Recursive call with the new list os transitions still to be used.+ -- note that if the new transitions (to be used) are the same to the+ -- received ones, no progress was made. Thus no (non-finishing)+ -- recursive call is performed.++ rec_call = if newMustUse == mustUse+ then []+ else (sentences d tt newMustUse)+++-- | This function computes one path from a given start state to a given final+-- state. The function does not repeat transitions. This function+-- "walks backwards": it starts from the final state back to the start one.+--+-- It receives the Dfa's transition table (tt), the table with the+-- transitions that Can Be Used (cbu), the labels of the transitions used+-- thus far (sys), the final state (ft), the start state (st).+-- It returns a pair:+-- the transitions that were not used in this path +-- the list of labels used in the path+++onePath :: (Eq sy, Eq st)+ => [(st, sy, st)] -- ^ Dfa's Transition Table+ -> [(st, sy, st)] -- ^ Table with transitions to be used+ -> [sy] -- ^ list of labels (used so far) + -> st -- ^ final state+ -> st -- ^ start state+ -> ([(st, sy, st)] , [sy]) ++onePath tt cbu sys ft st+ | ft == st = (cbu, sys)+ | otherwise = onePath tt (delete k cbu) (symbol:sys) before_f st+ -- at each recursive call it performs a backwards step+ -- the new final state is the origin of the chosen transition+ -- (where the previous final state (ft) is the destination).+ -- The transition used is deleted from can be used.+ -- The initial state (st) and trans. table (tt) do not change.+ where + -- computing the lists of transitions with the final state (ft)+ -- as destination: both for the trans. table and the can be used+ -- transitions+ + priorityList = filter (\(a,_,c) -> c == ft) cbu+ p2 = filter (\(a, _, c) -> a /= c && c == ft) tt++ -- selects the transition from the computed lsits, prefering+ -- the transitions coming from the can be used trable.++ k@(before_f, symbol, _) = head $ priorityList ++ p2+++-- | This function computes one sentence of the language defined by+-- a deterministic fininte automaton++onePathDfa :: (Ord st, Ord sy) => Dfa st sy -> [sy]+onePathDfa dfa@(Dfa v q s z d) = snd $ onePath ttdfa ttdfa [] (head z) s + where ttdfa = transitionTableDfa dfa
+ HaLeX_lib/Language/HaLex/Test_HaLex.hs view
@@ -0,0 +1,136 @@+-----------------------------------------------------------------------------+-- |+-- Module : Language.HaLex.Sentences+-- Copyright : (c) João Saraiva 2017+-- License : LGPL+--+-- Maintainer : jas@di.uminho.pt+-- Stability : provisional+-- Portability : portable+--+-- Generation of sentences of the (regular) languages defined via+-- Regular Expressions and Finite Autumata+--+-----------------------------------------------------------------------------++module Language.HaLex.Test_HaLex ( test_size_fa+ , test_gen_sentences+ ) where++import Language.HaLex.Dfa+import Language.HaLex.Ndfa+import Language.HaLex.RegExp+import Language.HaLex.RegExp2Fa+import Language.HaLex.RegExpParser+import Language.HaLex.FaOperations+import Language.HaLex.Minimize+import Language.HaLex.Sentences+import Language.HaLex.FaClasses++import Data.Maybe+import Data.List++import Test.HUnit++++-----------------------------------------------------------------------------+-- * Generic functions to test regular expressions and finite automata+++-- | Test the size of finite automata+-- The size (ie number of states) of a minimized dfa is always+-- less of equal than the size of an equivalent ndfa or dfa.++test_size_fa :: (Ord st, Ord sy, Show st, Show sy)+ => Ndfa st sy -> Test+test_size_fa ndfa = TestList [ sizeFa dfa_min <= sizeFa dfa ~?= True+ , sizeFa dfa_min <= sizeFa ndfa ~?= True+ ]+ where dfa = ndfa2dfa ndfa+ dfa_min = minimizeDfa dfa+++-- | Test the acceptance of generated sentences+-- The accpetance functions for 'RegExp', 'Ndfa' and 'Dfa' should+-- accept all sentences of the language of an equivalent reg. exp.++test_gen_sentences :: (Ord sy, Show sy) => RegExp sy -> Test++test_gen_sentences re =+ TestList [ and (map (matches' re) sentences_re) ~?= True+ , and (map (accept ndfa) sentences_re) ~?= True+ , and (map (accept dfa) sentences_re) ~?= True+ , and (map (accept dfa_min) sentences_re) ~?= True+ ]+ where sentences_re = sentencesRegExp re+ ndfa = regExp2Ndfa re+ dfa = ndfa2dfa ndfa+ dfa_min = minimizeDfa dfa++++-----------------------------------------------------------------------------+-- * Examples++++re = fromJust $ parseRegExp "('+'|'-')?[0-9]*('.'?)[0-9]+"+++re'' = fromJust $ parseRegExp "a[^a]*a"+++ndfa = regExp2Ndfa re+dfa = ndfa2dfa ndfa+dfa_int = beautifyDfa dfa++dfa_min = minimizeDfa dfa_int+dfa_min' = beautifyDfa dfa_min+++test_acceptNdfa = TestList [ ndfaaccept ndfa "109" ~?= True+ , ndfaaccept ndfa "+13" ~?= True+ , ndfaaccept ndfa "-13.4" ~?= True+ , ndfaaccept ndfa "-.15" ~?= True+ , ndfaaccept ndfa "+0.123" ~?= True+ , ndfaaccept ndfa "-.2.3" ~?= False+ , ndfaaccept ndfa "" ~?= False+ ]++test_acceptDfa = TestList [ dfaaccept dfa "109" ~?= True+ , dfaaccept dfa "+13" ~?= True+ , dfaaccept dfa "-13.4" ~?= True+ , dfaaccept dfa "-.15" ~?= True+ , dfaaccept dfa "+0.123" ~?= True+ , dfaaccept dfa "-.2.3" ~?= False+ , dfaaccept dfa "" ~?= False+ ]++test_acceptDfamin = TestList [ dfaaccept dfa_min "109" ~?= True+ , dfaaccept dfa_min "+13" ~?= True+ , dfaaccept dfa_min "-13.4" ~?= True+ , dfaaccept dfa_min "-.15" ~?= True+ , dfaaccept dfa_min "+0.123" ~?= True+ , dfaaccept dfa_min "-.2.3" ~?= False+ , dfaaccept dfa_min "" ~?= False+ ]+++dfaToHaskell = toHaskell dfa_int "Dfa_RE"+++re' = fromJust $ parseRegExp "[a-z][a-z]*"++++main = do runTestTT test_acceptNdfa+ runTestTT test_acceptDfa+ runTestTT test_acceptDfamin+ runTestTT $ test_size_fa (regExp2Ndfa re)+ runTestTT $ test_size_fa (regExp2Ndfa re')+ runTestTT $ test_gen_sentences re+ runTestTT $ test_gen_sentences re'+++
+ HaLeX_lib/Language/HaLex/Test_HaLex_Quickcheck.hs view
@@ -0,0 +1,81 @@+{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}+-----------------------------------------------------------------------------+-- |+-- Module : Language.HaLex.Sentences+-- Copyright : (c) João Saraiva 2017+-- License : LGPL+--+-- Maintainer : jas@di.uminho.pt+-- Stability : provisional+-- Portability : portable+--+-- Generation of sentences of the (regular) languages defined via+-- Regular Expressions and Finite Autumata+--+-----------------------------------------------------------------------------++module Language.HaLex.Test_HaLex_Quickcheck where++import Language.HaLex.Dfa+import Language.HaLex.Ndfa+import Language.HaLex.RegExp+import Language.HaLex.RegExp2Fa+import Language.HaLex.RegExpParser+import Language.HaLex.FaOperations+import Language.HaLex.Minimize+import Language.HaLex.Sentences+import Language.HaLex.FaClasses++import Test.QuickCheck+import Data.Char+import Control.Monad++++instance Arbitrary (RegExp Char) where+ arbitrary = sized genRegExp+++genRegExp :: Integral n => n -> Gen (RegExp Char)++genRegExp size+ | size>0 = frequency [(13, genLiteral)+ ,(10, genThen)+ ,(4 , genPlus)+ ,(2 , genDigits) + ,(1 , return Epsilon)+ ]+ | otherwise = return Epsilon+ where+ genLiteral = do c <- elements "aeiouAEIOU-_+-*/\\" -- arbitrary+ return (Literal c)+ genDigits = return digRegExp + genThen = do re1 <- genRegExp (size `div` 2)+ re2 <- genRegExp (size `div` 2)+ return (Then re1 re2)+ genPlus = do re <- genRegExp (size `div` 2)+ return (OneOrMore re)+++-- digRegExp :: RegExp+digRegExp :: RegExp Char+digRegExp = foldr1 Or (map (\x -> Literal (intToDigit x)) [0..9])++digRegExp' = foldr (\l r -> Or (Literal (intToDigit l))+ r) Empty [0..9]+++genRegExp' size+ | size>0 = oneof [genThen , genPlus , genLiteral , return Epsilon ]+ | otherwise = return Epsilon+ where+ genLiteral = do c <- elements "aeiouAEIOU-_+-*/\\" -- arbitrary+ return (Literal c)+ genThen = do re1 <- genRegExp' (size `div` 2)+ re2 <- genRegExp' (size `div` 2)+ return (Then re1 re2)+ genPlus = do re <- genRegExp' (size `div` 2)+ return (OneOrMore re)++exRegExp = sample (arbitrary :: Gen (RegExp Char))+
INSTALL view
@@ -12,7 +12,7 @@ jas@di.uminho.pt -Version: 1.2.4 (January, 2017)+Version: 1.2.5 (January, 2017) - halex batch tool
README.md view
@@ -15,7 +15,7 @@ saraiva@di.uminho.pt -Version: 1.2.4 (January, 2017)+Version: 1.2.5 (January, 2017) 1- What is HaleX