check-cfg-ambiguity 0.0.0.1 → 0.0.0.2
raw patch · 6 files changed
+92/−44 lines, 6 filesdep +QuickCheckdep +doctestdep ~basedep ~containersPVP ok
version bump matches the API change (PVP)
Dependencies added: QuickCheck, doctest
Dependency ranges changed: base, containers
API changes (from Hackage documentation)
Files
- ChangeLog +1/−0
- CheckCFGAmbiguity.hs +51/−32
- README +0/−3
- README.md +3/−0
- check-cfg-ambiguity.cabal +34/−9
- doctests.hs +3/−0
ChangeLog view
@@ -0,0 +1,1 @@+0.0.0.2: Changed versions of dependencies
CheckCFGAmbiguity.hs view
@@ -1,12 +1,19 @@+-- <ghc2021+-> {-# LANGUAGE Haskell2010 #-}+{-# LANGUAGE EmptyCase, PostfixOperators, TupleSections, NamedFieldPuns, BangPatterns, BinaryLiterals, HexFloatLiterals, NumericUnderscores, GADTSyntax, RankNTypes, TypeApplications, PolyKinds, ExistentialQuantification, TypeOperators, ConstraintKinds, ExplicitForAll, KindSignatures, NamedWildCards, ScopedTypeVariables, FlexibleContexts, FlexibleInstances, MultiParamTypeClasses, ConstrainedClassMethods, InstanceSigs, TypeSynonymInstances, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveTraversable, StandaloneDeriving, EmptyDataDeriving, DeriveLift, DeriveGeneric #-}+-- Deleted GeneralisedNewtypeDeriving, because it is not compatible with Safe+-- Deleted ImportQualifiedPost, StandaloneKindSignatures, because they are not supported in ghc 8.8.1+{-# LANGUAGE MonoLocalBinds #-}+-- </ghc2021+->+ {-# LANGUAGE LambdaCase #-}-{-# LANGUAGE ScopedTypeVariables #-} {- | (I assume you have read description at https://hackage.haskell.org/package/check-cfg-ambiguity .) Example. Let's check grammar of expressions of form @1 + (2 + 3)@ for ambiguity. +>>> import CheckCFGAmbiguity >>> import qualified Data.Map as M >>> :{ checkAmbiguity (M.fromList [@@ -18,7 +25,7 @@ :} SeemsUnambiguous -}-module CheckCFGAmbiguity (TerminalOrNonterminal(..), checkAmbiguity, Result(..)) where+module CheckCFGAmbiguity (TerminalOrNonterminal(..), checkAmbiguity, Result(..) {- $Earley -}) where import qualified Data.Map import qualified Data.Set@@ -27,18 +34,15 @@ import Data.Foldable(for_) import Data.Maybe(fromJust, catMaybes) import Data.List(find)---- For package "base" before 4.11.0.0-infixl 1 <&>-(<&>) :: (Functor f) => f a -> (a -> b) -> f b-a <&> b = fmap b a+import Data.Functor((<&>))+import Control.Monad(when) data TerminalOrNonterminal t n = T t | N n deriving (Eq, Ord, Show) -- We always create values of this type using "toGrammar", thus we enforce that all RHS nonterminals appear in LHS -- It is okey to have nonterminals (i. e. nonterminals present in LHS) without productions -- Order of productions for single nonterminal is not important. But I use list anyway, not multiset-data Grammar t n = Grammar (Data.Map.Map n [[TerminalOrNonterminal t n]]) deriving (Eq, Ord, Show)+newtype Grammar t n = Grammar (Data.Map.Map n [[TerminalOrNonterminal t n]]) deriving (Eq, Ord, Show) toGrammar :: (Ord n) => Data.Map.Map n [[TerminalOrNonterminal t n]] -> Maybe (Grammar t n) toGrammar g = if all (\prods -> all (\prod -> all (\case {@@ -48,11 +52,6 @@ then Just (Grammar g) else Nothing --- $--- prop> isJust $ toGrammar $ Data.Map.fromList [("a", [[N "b"]]), ("b", [[N "a"]])]--- prop> isJust $ toGrammar $ Data.Map.fromList [("a", [[N "b"]]), ("b", [[]])]--- prop> isNothing $ toGrammar $ Data.Map.fromList [("a", [[N "b"]]), ("b", [[N "c", N "a"]])]- {- $setup >>> :set -XHaskell2010 >>> :set -XScopedTypeVariables@@ -70,6 +69,12 @@ :} -} +-- $+-- prop> isJust $ toGrammar $ Data.Map.fromList [("a", [[N "b"]]), ("b", [[N "a"]])]+-- prop> isJust $ toGrammar $ Data.Map.fromList [("a", [[N "b"]]), ("b", [[]])]+-- prop> isJust $ toGrammar $ Data.Map.fromList [("a", [[N "b"]]), ("b", [])]+-- prop> isNothing $ toGrammar $ Data.Map.fromList [("a", [[N "b"]]), ("b", [[N "c", N "a"]])]+ {- $ >>> :{ conv [@@ -114,26 +119,18 @@ while $ do { do { currWordsV <- readSTRef currWords;- writeSTRef currWords [];- for_ currWordsV $ \word -> do {- let { (before, after) = break (\case { N _ -> True; T _ -> False; }) word };- case after of {- [] -> return ();- (N nn):rest -> for_ (fromJust $ Data.Map.lookup nn g) $ \prod -> do {- let { newWord = before ++ prod ++ rest };- do {- allWordsV <- readSTRef allWords;- if Data.Set.member newWord allWordsV- then writeSTRef collision True- else return ();- writeSTRef allWords $ Data.Set.insert newWord allWordsV;- };- currWordsV2 <- readSTRef currWords;- writeSTRef currWords $ newWord:currWordsV2;- };- _ -> error "Impossible";- };+ writeSTRef currWords $ concat $ currWordsV <&> \word -> let {+ (before, after) = break (\case { N _ -> True; T _ -> False; }) word;+ } in case after of {+ [] -> [];+ (N nn):rest -> (fromJust $ Data.Map.lookup nn g) <&> \prod -> before ++ prod ++ rest;+ _ -> error "Impossible"; };+ currWordsV2 <- readSTRef currWords;+ allWordsV <- readSTRef allWords;+ let { allWordsV2 = Data.Set.union allWordsV (Data.Set.fromList currWordsV2); };+ writeSTRef allWords allWordsV2;+ when (Data.Set.size allWordsV2 /= Data.Set.size allWordsV + length currWordsV2) $ writeSTRef collision True; }; iV <- readSTRef i; writeSTRef i (iV + 1);@@ -285,6 +282,18 @@ } {- $+>>> checkAmbiguity (conv2 [("start", [])]) "start" 1+SeemsUnambiguous++>>> checkAmbiguity (conv2 [("start", [])]) "start" 0+WrongCount++>>> checkAmbiguity (conv2 [("start", [])]) "start" (-1)+WrongCount++>>> checkAmbiguity (Data.Map.fromList [("start", [[N "a"]])]) "start" 10+NTNotFound+ >>> :{ let { g :: Data.Map.Map String [[TerminalOrNonterminal String String]] = Data.Map.fromList [("start", [])];@@ -425,5 +434,15 @@ ("t999", ["t1000"]) ]) "t0" 15 :}+Ambiguous+-}++{- $Earley+The following two grammars are from https://github.com/ollef/Earley/issues/54++>>> checkAmbiguity (Data.Map.fromList [("r1", [[T "A"], [N "r1"]])]) "r1" 10+Ambiguous++>>> checkAmbiguity (Data.Map.fromList [("r1", [[N "r1"], [T "A"]])]) "r1" 10 Ambiguous -}
− README
@@ -1,3 +0,0 @@-See https://hackage.haskell.org/package/check-cfg-ambiguity--You don't need to be registered on SourceHut to create bug report
+ README.md view
@@ -0,0 +1,3 @@+See https://hackage.haskell.org/package/check-cfg-ambiguity++You don't need to be registered on SourceHut to create bug report.
check-cfg-ambiguity.cabal view
@@ -1,25 +1,50 @@-cabal-version: >= 1.10+cabal-version: 3.0 name: check-cfg-ambiguity-version: 0.0.0.1+version: 0.0.0.2 synopsis: Checks context free grammar for ambiguity using brute force up to given limit description: Checks context free grammar for ambiguity using brute force up to given limit.- .+ It is impossible to check arbitrary context free grammar for ambiguity on a Turing machine. So we provide you brute force algorithm up to a limit.- .+ You can also use function "upTo" from package "Earley-0.13.0.1" for the same purpose, but it can freeze on infinitely ambiguous grammars: https://github.com/ollef/Earley/issues/54 . So I decided to write and publish this package.- .++ See also: https://mail.haskell.org/pipermail/haskell-cafe/2021-May/134006.html+ You don't need to be registered on SourceHut to create bug report.-license: BSD3++ If you think that this software is not needed or existing software already subsumes its functionality, please, tell me that, I will not be offended.+license: BSD-3-Clause license-file: LICENSE maintainer: Askar Safin <safinaskar@mail.ru> category: Parsing build-type: Simple-extra-source-files: README ChangeLog+extra-source-files: README.md ChangeLog source-repository head type: git location: https://git.sr.ht/~safinaskar/check-cfg-ambiguity library exposed-modules: CheckCFGAmbiguity- build-depends: base >= 4.9.1 && < 4.17, containers >= 0.5.7 && < 0.7+ -- base 4.13 removed Monad.fail, so "before base 4.13 there was nothing"+ build-depends:+ -- CI-BOUNDS-BEGIN+ base >= 4.13.0.0 && <= 4.17.0.0,+ containers >= 0.6.2.1 && <= 0.6.6+ -- CI-BOUNDS-END default-language: Haskell2010- ghc-options: -Wall+ ghc-options: -Wall -Wincomplete-patterns -Wincomplete-uni-patterns -Wmissing-export-lists -Wredundant-constraints -Wcompat -Wincomplete-record-updates -Wpartial-fields -Wunused-type-patterns -Wimplicit-lift++-- When following links below, keep in mind that "doctest" and "docspec" are two different words. Also keep in mind that "cabal-doctest" is not the only way to integrate cabal and doctest+-- I use simple way of cabal/doctest integration, described in https://github.com/sol/doctest/blob/d5b10128403663f7dc581477c7c7eb28a6f26f5a/README.markdown in section "Cabal integration"+-- Alternative way is to use "cabal-doctest" ( https://hackage.haskell.org/package/cabal-doctest-1.0.8 ), i. e. to write custom Setup.hs. But this requires boilerplate. Also, this can cause problems: https://github.com/ekmett/distributive/pull/53 , https://github.com/ekmett/distributive/issues/37+-- Another alternative way is not to integrate doctest and cabal at all and simply run "doctest" or "cabal-doctest" from continuous integration directly. But this will require us to specify all dependencies for tests in CI scripts. This is ugly+-- Note that author of cabal-doctest doesn't use this program anymore: https://github.com/ekmett/distributive/pull/53#issuecomment-744024619+-- So, we choose that way from doctest's README+-- To make it work "cabal v2-build" should write environment files. See https://stackoverflow.com/a/58027909 and https://github.com/ekmett/comonad/pull/58/commits/264f9057ea37cbffeb83744ff667ead4aa0f456a#diff-73f8a010e9b95aa9fe944c316576b12c2ec961272d428e38721112ecb1c1a98bR205 (note: this link shows how to run cabal-docspec, not cabal-doctest)+-- On docspec: the author doesn't think docspec is "useful for others": https://github.com/ekmett/distributive/pull/60#discussion_r549900441++test-suite doctests+ type: exitcode-stdio-1.0+ ghc-options: -threaded+ main-is: doctests.hs+ build-depends: base, doctest == 0.20.1, QuickCheck == 2.14.2+ default-language: Haskell2010
+ doctests.hs view
@@ -0,0 +1,3 @@+{-# LANGUAGE Haskell2010 #-}+import Test.DocTest+main = doctest ["CheckCFGAmbiguity.hs"]