On Tue, 2008-11-04 at 18:26 +0100, Achim Schneider wrote:

Martijn van Steenbergen wrote:

...

Does anyone have any experience with this? What's the best way to achieve this?

For anything remotely connected to parsing, always use parsec.

I'd not be surprised if the beast is touring complete in itself...

This is an interesting question: what would constitute Turing-completeness for an EDSL, independently of the host language? jcc

"Dan Piponi" wrote:

On Tue, Nov 4, 2008 at 9:26 AM, Achim Schneider wrote:

...

Martijn van Steenbergen wrote: For anything remotely connected to parsing, always use parsec.

I'd not be surprised if the beast is touring complete in itself...

Actually, this can count against you. It's very easy to use Parsec to build an innocent looking grammar that's too slow to use because it'll do all kinds of backtracking to find a way to make your input fit the grammar. I recommend Parsec for lots of tasks, but take care to design the grammar so it doesn't take exponential time to do anything.

Considering that he's talking about a mud, I figure the grammar is a quite straightforward command = l[eft] | r[ight] | ... | t[ake] <item> | c[ast] <spell> That is, I'd be very surprised if you even need more than two or three characters lookahead, much less backtracking. Parsec is a thousand times more efficient for such things than regular expressions, and you can just lazily parse all the input into a list of data constructors and happily fold it into your state... The only thing more straightforward than this is reading a xml with HaXML (if you have a DTD, that is) -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

G'day all. Quoting Achim Schneider :

Considering that he's talking about a mud, I figure the grammar is a quite straightforward

command = l[eft] | r[ight] | ... | t[ake] <item> | c[ast] <spell>

That is, I'd be very surprised if you even need more than two or three characters lookahead, much less backtracking.

In the case of a command followed by arguments, it would make more sense to use a keyword recogniser followed by a command-specific parser. One suggestion follows. Cheers, Andrew Bromage --------8<---CUT HERE---8<-------- module KeywordMatch (keywordMatch) where import Data.List import Data.Function import Control.Arrow -- Exercise: Why would it be wrong to curry this function? keywordMatch :: (Ord k) => [([k],v)] -> [k] -> Maybe v keywordMatch kvs = compileTrie . generateTrie . sortBy (compare `on` fst) $ kvs data Trie k v = Trie (Maybe v) (Trie' k v) data Trie' k v = Node0 | Node1 k (Trie k v) | Node2 k (Trie k v) k (Trie k v) | Branch k (Trie' k v) (Trie k v) (Trie' k v) generateTrie :: (Ord k) => [([k],v)] -> Trie k v generateTrie (([],v):rest) = Trie (Just v) (generateTrie' rest) generateTrie rest = Trie Nothing (generateTrie' rest) generateTrie' :: (Ord k) => [([k],v)] -> Trie' k v generateTrie' [] = Node0 generateTrie' [(k:ks,v)] = Node1 k $ foldr (\k -> Trie Nothing . Node1 k) (Trie (Just v) Node0) ks generateTrie' [(k1:ks1,v1),(k2:ks2,v2)] = Node2 k1 (generateTrie [(ks1,v1)]) k2 (generateTrie [(ks2,v2)]) generateTrie' kvs = gt . map (head.fst.head &&& map (first tail)) . groupBy ((==) `on` head.fst) $ kvs where gt [] = Node0 gt [(k,kvs)] = Node1 k (generateTrie kvs) gt [(k1,kvs1),(k2,kvs2)] = Node2 k1 (generateTrie kvs1) k2 (generateTrie kvs2) gt kvs = let (l,(k,m):r) = splitAt (length kvs `div` 2) kvs in Branch k (gt l) (generateTrie m) (gt r) compileTrie :: (Ord k) => Trie k v -> [k] -> Maybe v compileTrie (Trie emptyCase trie') = let ctrie' = compileTrie' trie' in \key -> case key of [] -> emptyCase (k:ks) -> ctrie' k ks compileTrie' :: (Ord k) => Trie' k v -> k -> [k] -> Maybe v compileTrie' Node0 = \k ks -> Nothing compileTrie' (Node1 k' t) = let t' = compileTrie t in \k ks -> if k == k' then t' ks else Nothing compileTrie' (Node2 k1 t1 k2 t2) = let t1' = compileTrie t1 t2' = compileTrie t2 in \k ks -> if k == k1 then t1' ks else if k == k2 then t2' ks else Nothing compileTrie' (Branch k' l m r) = let cl = compileTrie' l cm = compileTrie m cr = compileTrie' r in \k ks -> case compare k k' of LT -> cl k ks EQ -> cm ks GT -> cr k ks -- vim: ts=4:sts=4:expandtab

Excerpts from ajb's message of Wed Nov 05 03:59:03 +0100 2008:

G'day all.

Hi,

Quoting Achim Schneider :

...

Considering that he's talking about a mud, I figure the grammar is a quite straightforward

command = l[eft] | r[ight] | ... | t[ake] <item> | c[ast] <spell>

That is, I'd be very surprised if you even need more than two or three characters lookahead, much less backtracking.

In the case of a command followed by arguments, it would make more sense to use a keyword recogniser followed by a command-specific parser.

One suggestion follows.

Oops there is a bug in there: GHCI> keywordMatch [("a", 1), ("aa", 2)] "aa" Nothing The third equation of generateTrie' is missing a guard, namely k1 /= k2. generateTrie' [(k1:ks1,v1),(k2:ks2,v2)] | k1 /= k2 = Node2 k1 (generateTrie [(ks1,v1)]) k2 (generateTrie [(ks2,v2)]) Best regards, -- Nicolas Pouillard aka Ertai

On Wed, Nov 5, 2008 at 1:56 PM, Martijn van Steenbergen wrote:

I think I'll try roger's (private)

eek, bitten by "reply to sender only" again! i had intended to send to the list too.

Mitchell, Neil wrote:

Hi Martijn,

It's not that tricky if you do a regular expression state machine yourself, but that's probably a bit too much work. One way to get a speed up might be to take the regular expressions a,b,c,d and generate a regex a+b+c+d, and one a+b. You can then check any string s against a+b+c+d, if that matches check a+b, if that matches check a. At each stage you eliminate half the regular expressions, which means a match will take log n, where n is the number of regular expressions.

This assumes the underlying regular expression engine constructs a finite state machine, making it O(m) where m is the length of the string to match.

If you're implementing the machine yourself, you can implement it as trie automaton which has some "value" associated with each final state. That is, rather than just accepting or rejecting, when the automaton accepts it returns the value associated with the particular final state that it accepted by. This is a trivial extension on DFA/NFA implementations and is perfectly suited to the problem of combining multiple linear tries (sic: regexes) into a single machine. The minimization algorithms are a bit more complex than for DFA/NFAs, but still fairly straightforward if you're only doing prefix merging. And this gets rid of the O(log n) factor. -- Live well, ~wren

ChrisK wrote:

If you need to be left-biased then you need a perl-style engine, and you can use the regex-pcre or pcre-light haskell package and the PCRE library. These are obtainable from Hackage. I doubt PCRE uses a simple DFA...

I don't know if regex-pcre or pcre-light supports the (?{...})-ism of Perl 5.6 and above, but if it does then it's fairly easy to implement the trie automaton I mentioned in my previous post: just add a (?{ $value = ... }) action to the end of each component regex and read out the value of $value after you match. You'll still want to run the automata through a minimizer/optimizer after gluing all the components together, otherwise you still get O(n) behavior since you don't share the work for common prefixes. -- Live well, ~wren

Bulat Ziganshin wrote:

Hello wren,

Thursday, November 6, 2008, 12:00:22 PM, you wrote:

...

the trie automaton I mentioned in my previous post: just add a (?{ $value = ... }) action to the end of each component regex and read out the value of $value after you match.

$value? in haskell? :)

Shh, they'll notice :) -- "callCC implementation left as an exercise for the reader" ~wren

Johannes Waldmann schrieb:

using strings (inside a program) to represent structured data is wrong (*).

of course you need strings for interfacing the "outside" world, but the microsecond they get on the inside, they should be tokenized and parsed away into something useful (= an abstract syntax tree).

(*) corollary: using strings to represent regular expressions is also wrong...

I consider these regular expression strings an embedded domain-specific language. It seems to me, that putting regexps into strings was a work-around, because you could not extend Haskell's syntax. But now things change with this new GHC feature - what was its name? Nevertheless, I never used regexps in Haskell programs, parsec is much nicer.