Text.Derp

Data Types

data Parser a

Represents both a formal context-free language and the reduction of a member of that language to a value of type a.

Instances

Show (Parser a)

data Token

The input type for parsing. For example the parser:

 (ter "x") 

will parse:

 (Token "x" "foo") 

into:

 (eps "foo")

Constructors

Token

Fields

tokenClass :: String

tokenValue :: String

Instances

Eq Token

Ord Token

Show Token

Parser construction

(<|>) :: Ord a => Parser a -> Parser a -> Parser a

Alternation.

(<~>) :: (Ord a, Ord b) => Parser a -> Parser b -> Parser (a, b)

Concatenation.

(==>) :: (Ord a, Ord b) => Parser a -> (a -> b) -> Parser b

Reduction.

(==>|) :: (Ord a, Ord b) => Parser a -> (Set a -> Set b) -> Parser b

Set generalized version of ==>.

nul :: Ord a => Parser a -> Parser a

Null-parse extraction.

pzip :: (Ord a, Ord b) => Parser a -> Context a b -> Parser b

One-hole-context focus.

ter :: String -> Parser String

Terminal.

eps :: Ord a => a -> Parser a

Epsilon/empty-string.

epsM :: Ord a => Set a -> Parser a

Set generalized version of eps.

emp :: Ord a => Parser a

The empty language.

Parser computation steps

derive :: Parser a -> Token -> Parser a

The main derivative function.

compact :: Parser a -> Parser a

The optimization step of the algorithm.

parseNull :: Ord a => Parser a -> Set a

Extract the parse-null set of a parser.

Full parsing and result extraction

defaultCompactSteps :: Int

The number of compact steps that usually keeps a parser constant in size while parsing.

compactNum :: Int -> Parser a -> Parser a

A specified number of compactions.

deriveStepNum :: Int -> Parser a -> Token -> Parser a

Derivation followed by specified number of compactions.

runParseNum :: Ord a => Int -> Parser a -> [Token] -> Set a

Parse using a specified number of intermediate compactions.

deriveStep :: Parser a -> Token -> Parser a

Derivation followed by the default number of compactions.

runParse :: Ord a => Parser a -> [Token] -> Set a

Parse using the default number of intermediate compactions. This is the main parsing function. Examples:

 let e =     ter "num"
         <|> e <~> ter "+" <~> e ==> (\(x1,(o,x2)) -> "(" ++ x1 ++ o ++ x2 ++ ")")
 in runParse e [Token "num" "1", Token "+" "+", Token "num" 3", Token "+" "+", Token "num" "5"]

evaluates to:

 Set.fromList ["((1+3)+5)", "(1+(3+5))"]

 let e =     ter "num" ==> read 
         <|> e <~> ter "+" <~> e ==> (\(x1,(_,x2)) -> x1 + x2)
 in runParse e [Token "num" "1", Token "+" "+", Token "num" 3", Token "+" "+", Token "num" "5"]

evaluates to:

 Set.fromList [9]

Demos

xsR :: () -> Parser String

xsL :: () -> Parser String

xsIn :: [Token]

parens :: () -> Parser String

parensIn :: [Token]

amb :: () -> Parser String

ambIn :: [Token]

sexp :: () -> Parser String

sexpIn :: [Token]