I'm pleased to announce the first release of the Parsed library (pronounced par-séd). Parsed is a reimplementation of Haskell's excellent Parsec library in the Unix shell. In particular, the Unix pipe operator | corresponds exactly to Haskell's Applicative bind *>. Here's a quick example to get a feel for the syntax. The following bash one liner creates a parser for matching balanced parenthesis: ``` parens() { choice "$1" "match '(' | parens \"$1\" | match ')'"; } ``` For more detailed examples and implementation notes, please see the Parsed paper accepted at SIGBOVIK2015: https://github.com/mikeizbicki/parsed/raw/master/sigbovik2015/paper.pdf You can download Parsed from its github page at: https://github.com/mikeizbicki/parsed
Hi, Mike Izbicki wrote:
I don't want to bash your library, but I fear you made a wrong choice. In parsec, (many1 (string "a") <|> many1 (string "b")) >> string "c" accepts "bc", but I don't see how the corresponding grammar can be par-séd. Maybe you should replace a failure by a list of successes? Tillmann
Hi again, I wrote:
In parsec,
(many1 (string "a") <|> many1 (string "b")) >> string "c"
accepts "bc", but I don't see how the corresponding grammar can be par-séd.
Sorry, I think I was confused because your implementation looked like an attempt at unlimited backtracking to me. To compare with Parsec, it is better to treat your implementation as an attempt to implement Parsec's semantics. In that case, we should note that in Parsec, (string "ab" <|> string "a") rejects "a", but maybe your implementation would accept it? Tillmann
For the Parsec parser
(many1 (string "a") <|> many1 (string "b")) >> string "c"
we have an equivalent Parsed parser given by:
(choice "many 'match a'" "many 'match b'" | match c)
Verifying it accepts your test case:
$ (choice "many 'match a'" "many 'match b'" | match c) <<< 'bc'
bc
$ echo $?
Indeed, you are correct about the slightly different semantics of
choice. It essentially automatically wraps its arguments in "try".
For those wanting the more traditional Alternative interface, I've
just uploaded a combinator called (<|>). We can use this combinator
exactly as you would in haskell (except that bash requires lots of
escaping):
$ (\(\<\|\>\) 'match ab' 'match a') <<< "a"
$ echo $?
2
$ (\(\<\|\>\) 'match ab' 'match a') <<< "ab"
ab
$ echo $?
0
Thanks for the bug report!
On Wed, Apr 1, 2015 at 4:48 AM, Tillmann Rendel
Hi again,
I wrote:
In parsec,
(many1 (string "a") <|> many1 (string "b")) >> string "c"
accepts "bc", but I don't see how the corresponding grammar can be par-séd.
Sorry, I think I was confused because your implementation looked like an attempt at unlimited backtracking to me. To compare with Parsec, it is better to treat your implementation as an attempt to implement Parsec's semantics. In that case, we should note that in Parsec,
(string "ab" <|> string "a")
rejects "a", but maybe your implementation would accept it?
Tillmann _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
On Wed, Apr 1, 2015 at 11:01 AM, Mike Izbicki
$ (\(\<\|\>\) 'match ab' 'match a') <<< "ab"
'(<|>)' should work as well and be a little more readable. -- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net
participants (3)
-
Brandon Allbery -
Mike Izbicki -
Tillmann Rendel