Earley 0.10.0 → 0.10.0.1

raw patch · 6 files changed

+184/−16 lines, 6 filesnew-uploaderPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• CHANGELOG.md +11/−0
• Earley.cabal +5/−3
• README.md +144/−0
• Text/Earley/Grammar.hs +12/−10
• Text/Earley/Internal.hs +11/−2
• examples/Words.hs +1/−1

@@ -0,0 +1,11 @@+# 0.10++- Remove `Args`, and use `Results` instead+- Make `parser` function not take input directly+- Remove redundant type parameter to `Grammar`.++# 0.9++- Optimise handling of nullable non-terminals+- Pass a record of arguments in the parse routine+- Add support for consecutive mixfix holes

@@ -1,5 +1,5 @@ name:                Earley-version:             0.10.0+version:             0.10.0.1 synopsis:            Parsing all context-free grammars using Earley's algorithm. description:         See <https://www.github.com/ollef/Earley> for more                      information and@@ -21,6 +21,10 @@                      GHC == 7.10.1,                      GHC == 7.10.2 +extra-source-files:+                      README.md+                      CHANGELOG.md+ Flag Examples   Description: "Build examples"   Default:     False@@ -37,9 +41,7 @@                        Text.Earley.Internal,                        Text.Earley.Mixfix,                        Text.Earley.Parser-  -- other-modules:   build-depends:       base >=4.7 && <4.9, ListLike >=4.1-  -- hs-source-dirs:   default-language:    Haskell2010   ghc-options:         -Wall                        -funbox-strict-fields

@@ -0,0 +1,144 @@+Earley [![Build Status](https://travis-ci.org/ollef/Earley.svg?branch=master)](https://travis-ci.org/ollef/Earley) [![Hackage](https://img.shields.io/hackage/v/Earley.svg)](https://hackage.haskell.org/package/Earley)+======++[Go to the API documentation on Hackage.](https://hackage.haskell.org/package/Earley)++This (Text.Earley) is a library consisting of two main parts:++1. Text.Earley.Grammar:+   An embedded context-free grammar (CFG) domain-specific language (DSL) with+   semantic action specification in applicative style.++   An example of a typical expression grammar working on an input tokenised+   into strings is the following:++   ```haskell+      expr :: Grammar r (Prod r String String Expr)+      expr = mdo+        x1 <- rule $ Add <$> x1 <* namedSymbol "+" <*> x2+                  <|> x2+                  <?> "sum"+        x2 <- rule $ Mul <$> x2 <* namedSymbol "*" <*> x3+                  <|> x3+                  <?> "product"+        x3 <- rule $ Var <$> (satisfy ident <?> "identifier")+                  <|> namedSymbol "(" *> x1 <* namedSymbol ")"+        return x1+        where+          ident (x:_) = isAlpha x+          ident _     = False+   ```++2. Text.Earley.Parser:+   An implementation of (a modification of) the Earley parsing algorithm.++   To invoke the parser on the above grammar, run e.g. (here using `words` as a+   stupid tokeniser):++   ```haskell+      fullParses (parser expr) $ words "a + b * ( c + d )"+      = ( [Add (Var "a") (Mul (Var "b") (Add (Var "c") (Var "d")))]+        , Report {...}+        )+   ```++   Note that we get a list of all the possible parses (though in this case+   there is only one).++   Another invocation, which shows the error reporting capabilities (giving the+   last position that the parser reached and what it expected at that point),+   is the following:++   ```haskell+      fullParses (parser expr) $ words "a +"+      = ( []+        , Report { position   = 2+                 , expected   = ["(","identifier","product"]+                 , unconsumed = []+                 }+        )+   ```++Text.Earley.Mixfix additionally includes helper functionality for creating+parsers for expressions with mixfix identifiers in the style of Agda.++How do I write grammars?+------------------------++As hinted at above, the grammars are written inside `Grammar`, which is a+`Monad` and `MonadFix`.  For the library to be able to tame the recursion in+the grammars, we have to use the `rule` function whenever a production is+recursive.++Whenever you would write e.g.+```haskell+...+p = foo <|> bar <*> p+...+```+in a conventional combinator parser library, you instead write the following:+```haskell+grammar = mdo+  ...+  p <- rule $ foo <|> bar <*> p+  ...+```++Apart from making it possible to do recursion (even left-recursion), `rule`s+have an additional benefit: they control where work is shared, by the rule that+any `rule` is only ever expanded once per position in the input string. If a+`rule` is encountered more than once at a position, the work is shared.++Compared to parser generators and combinator libraries+------------------------------------------------------++This library differs from the main methods that are used to write parsers in+the Haskell ecosystem:++* Compared to parser generators (YACC, Happy, etc.) it requires very little+  pre-processing of the grammar. It also allows you to stay in the host+  language for both grammar and parser, i.e. there is no use of a separate+  tool. This also means that you are free to use the abstraction facilities of+  Haskell when writing a grammar. Currently the library requires a linear+  traversal of the grammar's rules before use, which is usually fast enough to+  do at run time, but precludes infinite grammars.++* The grammar language is similar to that of many parser combinators (Parsec,+  Attoparsec, parallel parsing processes, etc.), providing an applicative+  interface, but the parser gracefully handles all finite CFGs, including those+  with left-recursion. On the other hand, its productions are not monadic+  meaning that it does not support context-sensitive or infinite grammars,+  which are supported by many parser combinator libraries.++  Note: The `Grammar` type is a `Monad` (used to provide observable sharing)+  but it lives a layer above productions. It cannot be used to decide what+  production to use depending on the result of a previous production, i.e. it+  does not give us monadic parsing.++The parsing algorithm+---------------------++The parsing algorithm that this library uses is based on [Earley's parsing+algorithm](https://en.wikipedia.org/wiki/Earley_parser).  The algorithm has+been modified to produce online parse results, to give good error messages, and+to allow garbage collection of the item sets. Essentially, instead of storing a+sequence of sets of items like in the original algorithm, the modified+algorithm just stores pointers back to sets of reachable items.++The worst-case run time performance of the Earley parsing algorithm is cubic in+the length of the input, but for large classes of grammars it is linear. It+should however be noted that this library will likely be slower than most+parser generators and parser combinator libraries.++The parser implements an optimisation similar to that presented in Joop M.I.M+Leo's paper *A general context-free parsing algorithm running in linear time on+every LR(k) grammar without using lookahead*, which removes indirections in+sequences of non-ambiguous backpointers between item sets.++For more in-depth information about the internals of the library, there are+[implementation notes](docs/implementation.md) currently being written.++Contact+-------++Olle Fredriksson - https://github.com/ollef

@@ -23,14 +23,16 @@ -- -- @a@: The return type of the production. ----- @t@: The type of the terminals that the production operates on.+-- @t@ for terminal: The type of the terminals that the production operates+-- on. ----- @e@: The type of names, used for example to report expected tokens.+-- @e@ for expected: The type of names, used for example to report expected+-- tokens. ----- @r@: The type of a non-terminal. This plays a role similar to the @s@ in the---      type @ST s a@.  Since the 'parser' function expects the @r@ to be---      universally quantified, there is not much to do with this parameter---      other than leaving it universally quantified.+-- @r@ for rule: The type of a non-terminal. This plays a role similar to the+-- @s@ in the type @ST s a@.  Since the 'parser' function expects the @r@ to be+-- universally quantified, there is not much to do with this parameter other+-- than leaving it universally quantified. -- -- As an example, @'Prod' r 'String' 'Char' 'Int'@ is the type of a production that -- returns an 'Int', operates on (lists of) characters and reports 'String'@@ -109,10 +111,10 @@ -- -- @a@: The return type of the grammar (often a 'Prod'). ----- @r@: The type of a non-terminal. This plays a role similar to the @s@ in the---      type @ST s a@.  Since the 'parser' function expects the @r@ to be---      universally quantified, there is not much to do with this parameter---      other than leaving it universally quantified.+-- @r@ for rule: The type of a non-terminal. This plays a role similar to the+-- @s@ in the type @ST s a@.  Since the 'parser' function expects the @r@ to be+-- universally quantified, there is not much to do with this parameter other+-- than leaving it universally quantified. -- -- Most of the functionality of 'Grammar's is obtained through its instances, -- e.g.  'Monad' and 'MonadFix'. Note that GHC has syntactic sugar for

@@ -35,6 +35,14 @@ newtype Results s a = Results { unResults :: ST s [a] }   deriving Functor +lazyResults :: ST s [a] -> ST s (Results s a)+lazyResults stas = mdo+  resultsRef <- newSTRef $ do+    as <- stas+    writeSTRef resultsRef $ return as+    return as+  return $ Results $ join $ readSTRef resultsRef+ instance Applicative (Results s) where   pure  = return   (<*>) = ap@@ -58,7 +66,7 @@         -> !(a -> Results s b)         -> !(Conts s r e t b c)         -> State s r e t c-  Final :: Results s a -> State s r e t a+  Final :: !(Results s a) -> State s r e t a  -- | A continuation accepting an @a@ and producing a @b@. data Cont s r e t a b where@@ -231,7 +239,8 @@           asref <- newSTRef $ args a           writeSTRef argsRef $ Just asref           ks  <- simplifyCont scont-          let kstates = map (contToState $ Results $ join $ unResults <$> readSTRef asref) ks+          res <- lazyResults $ join $ unResults <$> readSTRef asref+          let kstates = map (contToState res) ks           parse (kstates ++ ss)                 env {reset = writeSTRef argsRef Nothing >> reset env}     Alts as (Pure f) -> do

@@ -10,7 +10,7 @@   whitespace  <- rule $ () <$ many (satisfy isSpace)   whitespace1 <- rule $ () <$ satisfy isSpace <* whitespace <?> "whitespace" -  ident <- rule +  ident <- rule     $ (:) <$> satisfy isAlpha <*> many (satisfy isAlphaNum)    <?> "identifier"