 | regex-dfa-0.91: Replaces/Enhances Text.Regex | Contents | Index |
| Text.Regex.DFA.Engine |
By Chris Kuklewicz (haskell (at) list (dot) mightyreason (dot) com), 2006.
This file is licensed under the LGPL (version 2, see the LICENSE file), because it is a derivative work. This DFAEngine takes the lazy transition table from Manuel Chakravarty's lexer in CTK Light, but uses it for simpler purposes. The original CTK code can be found here http://www.cse.unsw.edu.au/~chak/haskell/ctk/
Don Stewart (http://www.cse.unsw.edu.au/~dons/contact.html) also contributed to this code.
I want the freedom to alter the types a bit, so this is a separate module.
The CTK and DFA code can be thought of as three parts:
1. The ability to compose Regexp combinators which will lazily assemble a DFA. This is mainly bound up in the Cont type and the internal functions that merge it (exported as >||<).
2. The interface of how to specify Failure and Success. This was bound up in LexAction holding an function and is now lexAcceptlesFailurelexContinue.
3. The traversal engine. At each longer and longer match the last seen match is updated. Different traversals keep track of different levels of detail.
As a descendent of the regex-dna entry at http://shootout.alioth.debian.org/gp4/benchmark.php?test=regexdna&lang=all, this module has contributions from Don Stewart, Alson Kemp, and Chris Kuklewicz.
tree structure used to represent the lexer table each node in the tree corresponds to a of the lexer; the associated actions are those that apply when the corresponding is reached | ||||||||||||||
| Constructors | ||||||||||||||
| ||||||||||||||
 Instances | ||||||||||||||
| This is interface between the DFA table and the traversal engine, and is simpler than the original CTK version. | ||
| Constructors | ||
| ||
| Instances | ||
| Done or a table-like-thing to associate the next character with a Lexer | ||
| Constructors | ||
| ||
| Instances | ||
| Need to encode, as data, the between character decision am I at this boundary?. The different types of boundary checks and their outcomes are all value of Boundary. Currently only the ^ and $ anchors are encoded. | ||||||||
| Constructors | ||||||||
| ||||||||
| Instances | ||||||||
These create Regexp
Empty lexeme (noop)
disjunctive combination of two regexps, corresponding to x|y.
This will find the longest match
These combine two Regexp's
Concatenation of regexps is just concatenation of functions x +> y corresponds to xy
| :: Lexer | The regular expression to match |
| -> String | The input string to scan along, looking for a match |
| -> (String, Int, Maybe (String, Int, String)) | The input string before the match, length of the string before the match, Nothing if there was no match or Just input string at the start of the match, length of the match, input string starting just past the match |
This is the ultra-lazy matching engine. It returns the longest match. This will not examine any more of the input than needed, checking and returning a character at a time. Once a character is read that leads to no possibility of future match it does not evaluate any deeper. When a match is found, the input past match is not examined at all. In the extreme case of the input string being (error _) this will still succeed if the Regexp matches only an empty string since the input will not be demanded at all. The input before matching in this case will be [] and its length is 0, and the length of the match is 0, which the input at start of match and the input past the match will both be (error _). This loops over matchHere to find the first match | |
| :: Lexer | current lexeme |
| -> Int | Origin offset |
| -> Char | previous input character |
| -> [Char] | current input |
| -> Bool | |
| This checks for a match to the regex starting at the beginning of the input There is no need to wait for the longest match, so stop at first lexAccept | |