gll 0.2.0.1 → 0.2.0.2

raw patch · 3 files changed

+34/−8 lines, 3 files

Files

• gll.cabal +9/−8
• src/GLL/Combinators/Memoisation.hs +24/−0
• src/GLL/Parser.hs +1/−0

@@ -3,7 +3,7 @@  -- The name of the package. name:                gll-version:             0.2.0.1+version:             0.2.0.2 synopsis:            GLL parser with simple combinator interface  license:             BSD3 license-file:        LICENSE@@ -18,26 +18,26 @@         GLL is a parser combinator library for writing generalised parsers.         The parsers can correspond to arbitrary context-free grammar, accepting          both non-determinism and (left-) recursion.-        The underlying parsing algorithm is GLL (Scott and Johnstone 2013)-+        The underlying parsing algorithm is GLL (Scott and Johnstone 2013).+        .         The library provides an interface in Control.Applicative style (although no         instance of Applicative is given). -        Users can add arbitrary semantic with the <$> combinator. -+        Users can add arbitrary semantic to the parser. +        .         There are 4 top-level functions: parse, parseString, parseWithOptions         and parseStringWithOptions. They all return a list of semantic results,         one for each derivation. In the case that infinite derivations are possible         only 'good parse trees' are accepted (Ridge 2014).-+        .         Function parse relies on a builtin Token datatype. User-defined token-types          are currently not supported. parseString enables parsing character strings.         The user is granted GLL.Combinators.Options to specify certain disambiguation         rules.-+        .         GLL.Combinators.MemInterface is a memoised version of the library.         Parsers are no longer pure functions and must be built inside the IO monad,         providing fresh memo-tables to each memo'ed non-terminal.-+        .         See UnitTests and MemTests for examples of using both version of         the library. @@ -50,6 +50,7 @@     exposed-modules :     GLL.Combinators.Interface                         , GLL.Combinators.MemInterface                         , GLL.Combinators.Options+                        , GLL.Combinators.Memoisation                         , UnitTests                         , MemTests     other-modules   :   GLL.Types.Abstract

@@ -0,0 +1,24 @@+module GLL.Combinators.Memoisation where++import              Data.IORef+import qualified    Data.IntMap     as IM++-- | use <::=> to enforce using parse context (to handle left-recursion)+type MemoTable a = IM.IntMap (IM.IntMap a)+type MemoRef a   = IORef (MemoTable a)++memLookup :: (Int, Int) -> MemoTable a -> Maybe a+memLookup (l,r) = maybe Nothing look' . IM.lookup l+ where  look' = maybe Nothing Just . IM.lookup r ++memInsert :: (Int, Int) -> a -> MemoTable a -> MemoTable a+memInsert (l,r) as = IM.alter add' l+ where  add' mm = case mm of+                    Nothing -> Just $ IM.singleton r as+                    Just m  -> Just $ IM.insert r as m++-- create a new memo-table to use with the memo function+newMemoTable :: IO (MemoRef a)+newMemoTable = newIORef IM.empty++

@@ -151,6 +151,7 @@         case mnext of             Nothing            -> return () -- no continuation             Just (next,sppf)   -> pRhs next sppf+     pLhs (bigx, i, gn) = do          let     alts  =  [  (Slot bigx [] beta, i, gn) | (Alt bigx beta) <- altsOf bigx                          ,  select (input A.! i) beta bigx