[Haskell-cafe] Parsec question
Dear Cafe, I am trying to implement[1] parsec in go using the Monadic Parser Combinators paper [2] . I've been able to implement plus bind and many While doing the implementation - I looked at bind closely bind :: Parser a - (a - Parser b) - Parser b p `bind` f = \inp - concat [f v inp' | (v,inp') - p inp] I wondered if the result needs the complete list - wouldn't just the first successful value suffice? Perhaps - p `bind` f = \inp - take 1 $ concat [f v inp' | (v,inp') - p inp] Will this miss out matches? Regards, Kashyap [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Think about this: if you always take only the first element, why do you need lists at all? Roman * C K Kashyap ckkash...@gmail.com [2013-07-24 19:56:29+0530] Dear Cafe, I am trying to implement[1] parsec in go using the Monadic Parser Combinators paper [2] . I've been able to implement plus bind and many While doing the implementation - I looked at bind closely bind :: Parser a - (a - Parser b) - Parser b p `bind` f = \inp - concat [f v inp' | (v,inp') - p inp] I wondered if the result needs the complete list - wouldn't just the first successful value suffice? Perhaps - p `bind` f = \inp - take 1 $ concat [f v inp' | (v,inp') - p inp] Will this miss out matches? Regards, Kashyap [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
There is reference in the paper that empty list indicates failure...so could we just use it like Maybe? I'd like it very much if I could get an example of a missed match by not using the complete match. regards, Kashyap Sent from my Windows Phone From: Roman Cheplyaka Sent: 24/07/2013 8:19 PM To: C K Kashyap Cc: Haskell Cafe Subject: Re: [Haskell-cafe] Parsec question Think about this: if you always take only the first element, why do you need lists at all? Roman * C K Kashyap ckkash...@gmail.com [2013-07-24 19:56:29+0530] Dear Cafe, I am trying to implement[1] parsec in go using the Monadic Parser Combinators paper [2] . I've been able to implement plus bind and many While doing the implementation - I looked at bind closely bind :: Parser a - (a - Parser b) - Parser b p `bind` f = \inp - concat [f v inp' | (v,inp') - p inp] I wondered if the result needs the complete list - wouldn't just the first successful value suffice? Perhaps - p `bind` f = \inp - take 1 $ concat [f v inp' | (v,inp') - p inp] Will this miss out matches? Regards, Kashyap [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Because of laziness, you do in a sense only take the first successful value. When I've made parser combinators for Python before, I've used either generators or exceptions to get lazy evaluation, since computing the whole list of possibilities for each bind would ruin the running time of the algorithm (or make it never terminate). From your go code, it looks like you're evaluating the entire list. The bind you give looks like it's for a backtracking parser. For non-backtracking, though, I believe it would be possible to use Maybe. Parsec has a different bind operator which only lets backtracking happen when you explicitly allow it with 'try'. Assuming you're wanting a full backtracking parser, here's a counterexample for the take 1: needsList = do v - many (char 'a') a - return v -- just to make sure the take 1 bind happens at least once before the next step guard $ length a == 3 return a If my input string is , then many (char 'a') will produce matches of '', 'a', 'aa', 'aaa', and '', but the bind will probably force the incorrect one of these before it reaches the guard. I can't guarantee this is any good, and I haven't looked at it in a while, but at [1] I have an example of using exceptions to get a parsec-like backtracking-when-explicitly-allowed parser. I was planning on writing an article about how to do this technique, but I never got around to it. Kyle [1] https://github.com/kmill/metaview/blob/master/src/mparserlib/parser.py On Wed, Jul 24, 2013 at 10:26 AM, C K Kashyap ckkash...@gmail.com wrote: Dear Cafe, I am trying to implement[1] parsec in go using the Monadic Parser Combinators paper [2] . I've been able to implement plus bind and many While doing the implementation - I looked at bind closely bind :: Parser a - (a - Parser b) - Parser b p `bind` f = \inp - concat [f v inp' | (v,inp') - p inp] I wondered if the result needs the complete list - wouldn't just the first successful value suffice? Perhaps - p `bind` f = \inp - take 1 $ concat [f v inp' | (v,inp') - p inp] Will this miss out matches? Regards, Kashyap [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
To construct such an example, you have to ask yourself: when can we get a
list of more than one element?
Consider this:
a = char 'a'
((a a) | a) a
Suppose that our input is aa. The result of ((a a) | a) would be
the list
[('a', ), ('a', a)]
If you proceed with the first element of the list, the overall parse
will fail. It can only succeed if you then try the second element.
By the way, you shouldn't confuse Parsec (the library) with the general
concept of parser combinators or the implementation from the paper you
reference. The above parse would fail in Parsec as well, despite the
fact that Parsec allows backtracking.
Roman
* Kashyap CK ckkash...@gmail.com [2013-07-24 08:38:53-0700]
There is reference in the paper that empty list indicates failure...so
could we just use it like Maybe? I'd like it very much if I could get
an example of a missed match by not using the complete match.
regards,
Kashyap
Sent from my Windows Phone
From: Roman Cheplyaka
Sent: 24/07/2013 8:19 PM
To: C K Kashyap
Cc: Haskell Cafe
Subject: Re: [Haskell-cafe] Parsec question
Think about this: if you always take only the first element, why do you
need lists at all?
Roman
* C K Kashyap ckkash...@gmail.com [2013-07-24 19:56:29+0530]
Dear Cafe,
I am trying to implement[1] parsec in go using the Monadic Parser
Combinators paper [2] . I've been able to implement plus bind and
many
While doing the implementation - I looked at bind closely
bind :: Parser a - (a - Parser b) - Parser b
p `bind` f = \inp - concat [f v inp' | (v,inp') - p inp]
I wondered if the result needs the complete list - wouldn't just the first
successful value suffice?
Perhaps -
p `bind` f = \inp - take 1 $ concat [f v inp' | (v,inp') - p inp]
Will this miss out matches?
Regards,
Kashyap
[1] https://github.com/ckkashyap/parsec/blob/master/parsec.go
[2] Monadic Parser Combinators: Graham Hutton, Erik Meijer
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Thanks Kyle, My initial implementation was evaluating the whole list - the current one though just returns the first successful result. Anyway, I think I need the backtracking - I would want the aaa as the result :) I will now explore using go-routines to implement laziness. Thank you so much for your input. Regards, Kashyap On Thu, Jul 25, 2013 at 1:44 AM, Kyle Miller kmill31...@gmail.com wrote: Because of laziness, you do in a sense only take the first successful value. When I've made parser combinators for Python before, I've used either generators or exceptions to get lazy evaluation, since computing the whole list of possibilities for each bind would ruin the running time of the algorithm (or make it never terminate). From your go code, it looks like you're evaluating the entire list. The bind you give looks like it's for a backtracking parser. For non-backtracking, though, I believe it would be possible to use Maybe. Parsec has a different bind operator which only lets backtracking happen when you explicitly allow it with 'try'. Assuming you're wanting a full backtracking parser, here's a counterexample for the take 1: needsList = do v - many (char 'a') a - return v -- just to make sure the take 1 bind happens at least once before the next step guard $ length a == 3 return a If my input string is , then many (char 'a') will produce matches of '', 'a', 'aa', 'aaa', and '', but the bind will probably force the incorrect one of these before it reaches the guard. I can't guarantee this is any good, and I haven't looked at it in a while, but at [1] I have an example of using exceptions to get a parsec-like backtracking-when-explicitly-allowed parser. I was planning on writing an article about how to do this technique, but I never got around to it. Kyle [1] https://github.com/kmill/metaview/blob/master/src/mparserlib/parser.py On Wed, Jul 24, 2013 at 10:26 AM, C K Kashyap ckkash...@gmail.com wrote: Dear Cafe, I am trying to implement[1] parsec in go using the Monadic Parser Combinators paper [2] . I've been able to implement plus bind and many While doing the implementation - I looked at bind closely bind :: Parser a - (a - Parser b) - Parser b p `bind` f = \inp - concat [f v inp' | (v,inp') - p inp] I wondered if the result needs the complete list - wouldn't just the first successful value suffice? Perhaps - p `bind` f = \inp - take 1 $ concat [f v inp' | (v,inp') - p inp] Will this miss out matches? Regards, Kashyap [1] https://github.com/ckkashyap/parsec/blob/master/parsec.go [2] Monadic Parser Combinators: Graham Hutton, Erik Meijer ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Thanks Roman .. I'll try and implement laziness to retain the whole list.
Regards,
Kashyap
On Thu, Jul 25, 2013 at 3:41 AM, Roman Cheplyaka r...@ro-che.info wrote:
To construct such an example, you have to ask yourself: when can we get a
list of more than one element?
Consider this:
a = char 'a'
((a a) | a) a
Suppose that our input is aa. The result of ((a a) | a) would be
the list
[('a', ), ('a', a)]
If you proceed with the first element of the list, the overall parse
will fail. It can only succeed if you then try the second element.
By the way, you shouldn't confuse Parsec (the library) with the general
concept of parser combinators or the implementation from the paper you
reference. The above parse would fail in Parsec as well, despite the
fact that Parsec allows backtracking.
Roman
* Kashyap CK ckkash...@gmail.com [2013-07-24 08:38:53-0700]
There is reference in the paper that empty list indicates failure...so
could we just use it like Maybe? I'd like it very much if I could get
an example of a missed match by not using the complete match.
regards,
Kashyap
Sent from my Windows Phone
From: Roman Cheplyaka
Sent: 24/07/2013 8:19 PM
To: C K Kashyap
Cc: Haskell Cafe
Subject: Re: [Haskell-cafe] Parsec question
Think about this: if you always take only the first element, why do you
need lists at all?
Roman
* C K Kashyap ckkash...@gmail.com [2013-07-24 19:56:29+0530]
Dear Cafe,
I am trying to implement[1] parsec in go using the Monadic Parser
Combinators paper [2] . I've been able to implement plus bind and
many
While doing the implementation - I looked at bind closely
bind :: Parser a - (a - Parser b) - Parser b
p `bind` f = \inp - concat [f v inp' | (v,inp') - p inp]
I wondered if the result needs the complete list - wouldn't just the
first
successful value suffice?
Perhaps -
p `bind` f = \inp - take 1 $ concat [f v inp' | (v,inp') - p inp]
Will this miss out matches?
Regards,
Kashyap
[1] https://github.com/ckkashyap/parsec/blob/master/parsec.go
[2] Monadic Parser Combinators: Graham Hutton, Erik Meijer
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsec question (new user): unexpected end of input
I am a new Parsec user, and having some trouble with a relatively simple parser. The grammar I want to parse contains tags (not html) marked by angle brackets (e.g., some tag), with arbitrary text (no angle brackets allowed) optionally in between tags. Tags may not nest, but the input must begin and end with a tag. Whitespace may occur anywhere (beginning/end of input, inside/between tags, etc.), and is optional. I think my problem may be a lack of using try, but I'm not sure where. At runtime I get: Error parsing file: ...\sampleTaggedContent.txt (line 4, column 1): unexpected end of input expecting The input was: tag1stufftag 2 more stuff tag 3 even more lastTag The code is below. (I'm using Parsec-2.1.0.1.) I don't really want to return anything meaningful yet; just parse okay. Any advice about the error (or how to simplify or improve the code) would be appreciated. Thanks much, -- Peter -- Parsers: taggedContent = do optionalWhiteSpace aTag many tagOrContent aTag eof return Parse complete. tagOrContent = aTag | someContent ? tagOrContent aTag = do tagBegin xs - many (noneOf [tagEndChar]) tagEnd optionalWhiteSpace return () someContent = do manyTill anyChar tagBegin return () optionalWhiteSpace = spaces -- i.e., any of \v\f\t\r\n tagBegin = char tagBeginChar tagEnd = char tagEndChar -- Etc: tagBeginChar = '' tagEndChar = '' ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question (new user): unexpected end of input
On Tue, Sep 28, 2010 at 10:35 PM, Peter Schmitz ps.hask...@gmail.com wrote: I am a new Parsec user, and having some trouble with a relatively simple parser. The grammar I want to parse contains tags (not html) marked by angle brackets (e.g., some tag), with arbitrary text (no angle brackets allowed) optionally in between tags. Tags may not nest, but the input must begin and end with a tag. Whitespace may occur anywhere (beginning/end of input, inside/between tags, etc.), and is optional. I think my problem may be a lack of using try, but I'm not sure where. At runtime I get: Error parsing file: ...\sampleTaggedContent.txt (line 4, column 1): unexpected end of input expecting The input was: tag1stufftag 2 more stuff tag 3 even more lastTag The code is below. (I'm using Parsec-2.1.0.1.) I don't really want to return anything meaningful yet; just parse okay. Any advice about the error (or how to simplify or improve the code) would be appreciated. Thanks much, -- Peter -- Parsers: taggedContent = do optionalWhiteSpace aTag many tagOrContent aTag eof return Parse complete. tagOrContent = aTag | someContent ? tagOrContent aTag = do tagBegin xs - many (noneOf [tagEndChar]) tagEnd optionalWhiteSpace return () someContent = do manyTill anyChar tagBegin return () optionalWhiteSpace = spaces -- i.e., any of \v\f\t\r\n tagBegin = char tagBeginChar tagEnd = char tagEndChar -- Etc: tagBeginChar = '' tagEndChar = '' ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Here's something I put together: http://hpaste.org/40201/parsec_question_new_user_un?pid=40201lang_40201=Haskell It doesn't have the whitespace handling you want. The big difference in what I did was that when parsing content, it needs to stop on EOF as well as the signal char. Otherwise it won't allow the document to end :-) Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
2009/4/17 Michael P Mossey m...@alumni.caltech.edu:
I want to write a parser that can read a file with this format: the file has
sections which are demarcated by keywords. Keywords always begin with two
forward slashes and consist of letters, digits, and underscore. The text can
be anything, including special characters. For instance:
//keyword some text
and more text //another_keyword and) some { more text
//ya_keyword $$
-- text
I'm not sure how to write a parser that considers anything but a double
slash to be a valid part of the text.
Maybe you can use a combination of 'many', 'noneOf' or 'manyTill' ?
Cheers,
Thu
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Here's what I've got so far.
-- Text is considered everything up to //. However, the problem
-- is that this consumes the //.
parseText = manyTill anyChar (try (string //))
-- Because the // is already consumed, parseKeyword just grabs
-- the available letters.
parseKeyword :: Parser String
parseKeyword = many1 letter
-- Test function.
parseSome = do t1 - parseText
k1 - parseKeyword
t2 - parseText
return (t1,k1,t2)
On some text//keyword more text// this gives
(some text,keyword, more text)
On some text//keyword more text
this gives the error expecting //
I wonder how I can get the manyTill to be happy with eof before finding the //?
I tried
parseText = manyTill anyChar (try (string //) | eof)
but got a type error.
minh thu wrote:
2009/4/17 Michael P Mossey m...@alumni.caltech.edu:
I want to write a parser that can read a file with this format: the file has
sections which are demarcated by keywords. Keywords always begin with two
forward slashes and consist of letters, digits, and underscore. The text can
be anything, including special characters. For instance:
//keyword some text
and more text //another_keyword and) some { more text
//ya_keyword $$
-- text
I'm not sure how to write a parser that considers anything but a double
slash to be a valid part of the text.
Maybe you can use a combination of 'many', 'noneOf' or 'manyTill' ?
Cheers,
Thu
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
You can use 'notFollowedBy' (probably with 'many1' and 'try').
Something like (untested):
notFollowedBy (try $ string //)
Thu
2009/4/17 Michael Mossey m...@alumni.caltech.edu:
Here's what I've got so far.
-- Text is considered everything up to //. However, the problem
-- is that this consumes the //.
parseText = manyTill anyChar (try (string //))
-- Because the // is already consumed, parseKeyword just grabs
-- the available letters.
parseKeyword :: Parser String
parseKeyword = many1 letter
-- Test function.
parseSome = do t1 - parseText
k1 - parseKeyword
t2 - parseText
return (t1,k1,t2)
On some text//keyword more text// this gives
(some text,keyword, more text)
On some text//keyword more text
this gives the error expecting //
I wonder how I can get the manyTill to be happy with eof before finding the
//? I tried
parseText = manyTill anyChar (try (string //) | eof)
but got a type error.
minh thu wrote:
2009/4/17 Michael P Mossey m...@alumni.caltech.edu:
I want to write a parser that can read a file with this format: the file
has
sections which are demarcated by keywords. Keywords always begin with two
forward slashes and consist of letters, digits, and underscore. The text
can
be anything, including special characters. For instance:
//keyword some text
and more text //another_keyword and) some { more text
//ya_keyword $$
-- text
I'm not sure how to write a parser that considers anything but a double
slash to be a valid part of the text.
Maybe you can use a combination of 'many', 'noneOf' or 'manyTill' ?
Cheers,
Thu
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
My confusion is that text is by definition followed by // or eof.
minh thu wrote:
You can use 'notFollowedBy' (probably with 'many1' and 'try').
Something like (untested):
notFollowedBy (try $ string //)
Thu
2009/4/17 Michael Mossey m...@alumni.caltech.edu:
Here's what I've got so far.
-- Text is considered everything up to //. However, the problem
-- is that this consumes the //.
parseText = manyTill anyChar (try (string //))
-- Because the // is already consumed, parseKeyword just grabs
-- the available letters.
parseKeyword :: Parser String
parseKeyword = many1 letter
-- Test function.
parseSome = do t1 - parseText
k1 - parseKeyword
t2 - parseText
return (t1,k1,t2)
On some text//keyword more text// this gives
(some text,keyword, more text)
On some text//keyword more text
this gives the error expecting //
I wonder how I can get the manyTill to be happy with eof before finding the
//? I tried
parseText = manyTill anyChar (try (string //) | eof)
but got a type error.
minh thu wrote:
2009/4/17 Michael P Mossey m...@alumni.caltech.edu:
I want to write a parser that can read a file with this format: the file
has
sections which are demarcated by keywords. Keywords always begin with two
forward slashes and consist of letters, digits, and underscore. The text
can
be anything, including special characters. For instance:
//keyword some text
and more text //another_keyword and) some { more text
//ya_keyword $$
-- text
I'm not sure how to write a parser that considers anything but a double
slash to be a valid part of the text.
Maybe you can use a combination of 'many', 'noneOf' or 'manyTill' ?
Cheers,
Thu
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
2009/04/17 minh thu not...@gmail.com: 2009/04/17 Michael Mossey m...@alumni.caltech.edu: I wonder how I can get the manyTill to be happy with eof before finding the //? I tried parseText = manyTill anyChar (try (string //) | eof) but got a type error. You can use 'notFollowedBy' [...] You get a type error because `string //` parses to a `String` while `eof` parses to a `()`. Instead you might use: parseText = manyTill anyChar (try (string // return ()) | eof) -- Jason Dusek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Jason Dusek wrote: 2009/04/17 minh thu not...@gmail.com: 2009/04/17 Michael Mossey m...@alumni.caltech.edu: I wonder how I can get the manyTill to be happy with eof before finding the //? I tried parseText = manyTill anyChar (try (string //) | eof) but got a type error. You can use 'notFollowedBy' [...] You get a type error because `string //` parses to a `String` while `eof` parses to a `()`. Instead you might use: parseText = manyTill anyChar (try (string // return ()) | eof) -- Jason Dusek Ah.. I think I get it... in the function manyTill, the second argument type doesn't matter.. doesn't have to match the first argument type. Here's what I have so far. It works, but it's a bit weird to consume the // as part of the text rather than the keyword. That happens because the try( string // ), which is part of the end arg to manyTill, consumes the // when it succeeds. But maybe it is the most natural way to express the problem. parseKeyword :: Parser String parseKeyword = many1 (alphaNum | char '_') parseText :: Parser String parseText = manyTill anyChar ((try (string //) return ()) | eof) parsePair :: Parser (String,String) parsePair = do k - parseKeyword t - parseText return (k,t) parseFile :: Parser [(String,String)] parseFile = do _ - parseText -- to skip any text at beginning and 'sync up' p - many parsePair return p ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
I've just about got this parser working, but wondering about something. Turns out I need try inside the lookahead here. parseText :: Parser String parseText = manyTill anyChar $ lookAhead (try (string //)) Without try, if I give it an input with a single slash, like some/text It stops with the error unexpected t; expecting // I'm curious why that happens when lookAhead is used with manyTill like this. I was under the impression that if the end parser given to manyTill failed, then manyTill would just continue with the main parser. Apparently there are two ways to fail: in some contexts, failing means that manyTill will just continue. In other contexts, such as the one above, there is some sense in which 'string' demands the entire string to be present. Can anyone explain? Thanks, Mike ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Am Samstag 18 April 2009 01:33:44 schrieb Michael P Mossey:
I've just about got this parser working, but wondering about something.
Turns out I need try inside the lookahead here.
parseText :: Parser String
parseText = manyTill anyChar $ lookAhead (try (string //))
Without try, if I give it an input with a single slash, like
some/text
It stops with the error unexpected t; expecting //
I'm curious why that happens when lookAhead is used with manyTill like
this. I was under the impression that if the end parser given to manyTill
failed, then manyTill would just continue with the main parser. Apparently
there are two ways to fail: in some contexts, failing means that manyTill
will just continue. In other contexts, such as the one above, there is some
sense in which 'string' demands the entire string to be present. Can anyone
explain?
Looking at the source:
manyTill :: GenParser tok st a - GenParser tok st end - GenParser tok st [a]
manyTill p end = scan
where
scan = do{ end; return [] }
|
do{ x - p; xs - scan; return (x:xs) }
if end fails after consuming some input, manyTill p end fails.
lookAhead :: GenParser tok st a - GenParser tok st a
lookAhead p = do{ state - getParserState
; x - p
; setParserState state
; return x
}
lookAhead fails if p fails, but if p fails, the state is not reset, so if p
fails after
consuming some input, like in your example some/text, where lookAhead (string
//)
consumes the slash and fails because the second expected slash is missing, that
is not put
back and since something is consumed, the second branch of scan in manyTill
isn't tried.
You could also have
keyword = try $ do
string //
kw - many1 keywordChar
return (Keyword kw)
parseText = manyTill anyChar (lookAhead keyword)
Seems cleaner to have the slashes in keyword.
Thanks,
Mike
Cheers,
Daniel
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsec question
I want to write a parser that can read a file with this format: the file has
sections which are demarcated by keywords. Keywords always begin with two
forward slashes and consist of letters, digits, and underscore. The text can be
anything, including special characters. For instance:
//keyword some text
and more text //another_keyword and) some { more text
//ya_keyword $$
-- text
I'm not sure how to write a parser that considers anything but a double slash to
be a valid part of the text.
Thanks,
Mike
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsec question
Hi all,
I'm rather new to Haskell and I'm diving right into the deep end
writing a parser using Parsec.
In particular I'm using Text.ParserCombinators.Parsec.Language to do
some of the heavy lifting and have this:
import qualified Text.ParserCombinators.Parsec.Language as L
import qualified Text.ParserCombinators.Parsec.Token as T
lexer = T.makeTokenParser L.emptyDef
{ L.identStart = letter | char '_',
L.identLetter = alphaNum | char '_',
identifier :: CharParser st String
identifier = T.identifier lexer
and now I need to parse things this.that.the.other. I'd like to have
a function with the following signature:
qualifiedIdentifier :: CharParser st [ String ]
which should return [ this, that, the, other ] and write it in
terms of identifier and thats where I'm stuck.
Anyone care to whack me with the cluestick?
Cheers,
Erik
--
-
Erik de Castro Lopo
-
If you don't have freedom as a principle, you can never see a reason not
to make an exception. -- Richard Stallman.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Erik de Castro Lopo wrote: qualifiedIdentifier :: CharParser st [ String ] Ahh, figured it out myself: qualifiedIdentifier :: CharParser st [ String ] qualifiedIdentifier = do i - identifier r - dotIdentifier return (i : r) where dotIdentifier = do char '.' i - identifier r - dotIdentifier return (i : r) | return [] Does that look sane to people who know Haskell and Parsec better than me? Erik -- - Erik de Castro Lopo - The Earth is around 70% water. Fish rule the seas. Humans are over 90% water. It's only a matter of time. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsec question
Hi,
Fairly new to Haskell and trying some parsec. (Also, new to
parsers/interpreters)
I had come up with this, which works, but I can't help thinking there's
a better way :)
| newtype Identifier = Identifier String
newtype Literal = StringLiteral String -- to be extended later
data Primary = PrimaryLiteral Literal | PrimaryIdentifier Identifier
|| primary = do {
i - identifier;
return $ PrimaryIdentifier i; }
| do {
l - stringLiteral;
return $ PrimaryLiteral l; }
|| identifier = do
i - many1 letter
return $ Identifier i
stringLiteral = do
(char '\'')
s - manyTill anyChar (char '\'')
return $ StringLiteral s
Is there a way through combining types/parsers that the double do block in
primary could
be avoided?
I understand it's necessary right now because the parsers identifier and
stringLiteral
return different types, so I can't just write:
i - identifier | stringLiteral
So, I'm not sure whether my types need work, the parsers, or if this is the
simplest way.
Thanks,
Levi
lstephen.wordpress.com
PS, have lurked on the list for a while, enjoy the discussions and content.
|
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
On Thu, Jun 21, 2007 at 03:34:54PM +0930, Levi Stephen wrote: Is there a way through combining types/parsers that the double do block in primary could be avoided? I understand it's necessary right now because the parsers identifier and stringLiteral return different types, so I can't just write: i - identifier | stringLiteral You can use the fact that (GenParser tok st) is a monad and use liftM: i - liftM PrimaryIdentifier identifier | liftM PrimaryLiteral stringLiteral I often find it convenient to use choice instead of | for long more complicated alternatives, for example like this: primary = choice [ do i - identifier return $ PrimaryIdentifier i , do l - stringLiteral return $ PrimaryLiteral l ] So, I'm not sure whether my types need work, I have a feeling that Identifier and Literal could just be type synonyms, because newtype's don't seem to be neccesary or beneficial here. I could be wrong though - after all, I don't know your intentions and the rest of the program. Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
I find it's good for the soul to remember what the do notation is doing for us. Also I'm with Einstein on You do not really understand something unless you can explain it to your grandmother :) Personally I think (in this instance) your three 'Parser a' functions read nicer as: primary = (identifier = (return . PrimaryIdentifier)) | (stringLiteral = (return . PrimaryLiteral)) identifier = (many1 letter) = (return . Identifier) stringLiteral = (char '\'') (manyTill anyChar (char '\'')) = (return . StringLiteral) Looking at them in this form Tomek's point should seem clear now, especially when we look at the type signature for liftM: liftM :: Monad m = (a1 - r) - m a1 - m r So we can (marginally) shorten down to: primary = (liftM PrimaryIdentifier identifier) | (liftM PrimaryLiteral stringLiteral) identifier = liftM Identifier (many1 letter) stringLiteral = liftM StringLiteral ((char '\'') (manyTill anyChar (char '\''))) You might like: http://syntaxfree.wordpress.com/2006/12/12/do-notation-considered-harmful/ Dave, On 21/06/07, Tomasz Zielonka [EMAIL PROTECTED] wrote: On Thu, Jun 21, 2007 at 03:34:54PM +0930, Levi Stephen wrote: Is there a way through combining types/parsers that the double do block in primary could be avoided? I understand it's necessary right now because the parsers identifier and stringLiteral return different types, so I can't just write: i - identifier | stringLiteral You can use the fact that (GenParser tok st) is a monad and use liftM: i - liftM PrimaryIdentifier identifier | liftM PrimaryLiteral stringLiteral I often find it convenient to use choice instead of | for long more complicated alternatives, for example like this: primary = choice [ do i - identifier return $ PrimaryIdentifier i , do l - stringLiteral return $ PrimaryLiteral l ] So, I'm not sure whether my types need work, I have a feeling that Identifier and Literal could just be type synonyms, because newtype's don't seem to be neccesary or beneficial here. I could be wrong though - after all, I don't know your intentions and the rest of the program. Best regards Tomek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
On 6/21/07, Dave Tapley [EMAIL PROTECTED] wrote: primary = (identifier = (return . PrimaryIdentifier)) | (stringLiteral = (return . PrimaryLiteral)) identifier = (many1 letter) = (return . Identifier) stringLiteral = (char '\'') (manyTill anyChar (char '\'')) = (return . StringLiteral) I have found this a sufficiently common pattern that I have a little combinator to tidy it up: p `with` f = p = (return . f) so I can write primary = (identifier `with` PrimaryIdentifier) | (stringLiteral `with` PrimaryLiteral) Obviously you could write it in terms of liftM, choose a different name, c, c. FWIW, the other little combinator I invariably use is p `returning` x = p = (\_ - return x) which I end up calling with () as the second argument so often (especially during development), I usually have another combinator void p = p return () YMMV, T. -- Dr Thomas Conway [EMAIL PROTECTED] Silence is the perfectest herald of joy: I were but little happy, if I could say how much. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Thomas Conway wrote:
p `with` f = p = (return . f)
so I can write
primary = (identifier `with` PrimaryIdentifier) | (stringLiteral
`with` PrimaryLiteral)
I would write
primary = PrimaryIdentifier `fmap` identifer
| PrimaryLiteral`fmap` stringLiteral
(I prefer fmap to liftM but they are the same for monads). To my mind
this fits the general pattern of 'constructor comes before contents'.
with is, of course, just fmap with the parameters reversed.
It's a question of taste if it's better to define a new name or use an
existing one.
p `returning` x = p = (\_ - return x)
I see no convincing reason to prefer that to
p return x
(which is fewer characters and, to me, just as clear).
In fact I'll also use
do { p ; return x }
and which of the two I choose will depend on context. If this is part of
a large 'choice' construct I prefer to have each branch using the same
notation (all do, or all not do).
Jules
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Levi Stephen wrote:
newtype Identifier = Identifier String
newtype Literal = StringLiteral String -- to be extended later
data Primary = PrimaryLiteral Literal | PrimaryIdentifier Identifier
primary = do {
i - identifier;
return $ PrimaryIdentifier i; }
| do {
l - stringLiteral;
return $ PrimaryLiteral l; }
|| identifier = do
i - many1 letter
return $ Identifier i
stringLiteral = do
(char '\'')
s - manyTill anyChar (char '\'')
return $ StringLiteral s
Is there a way through combining types/parsers that the double do block
in primary could be avoided?
I prefer using Control.Monad.ap:
primary = (return PrimaryIdentifier `ap` identifier)
| (return PrimaryLiteral `ap` stringLiteral)
identifier = return Identifier `ap` many1 letter
stringLiteral = return StringLiteral
`ap` (quote manyTill anyChar quote)
quote = char '\''
This scales easily to the case of multiple fields per constructor,
provided that the order of the subterms in the abstract syntax is the
same as in the concrete syntax:
data FunctionCall = FunctionCall Identifier [Primary]
functionCall = return FunctionCall
`ap` identifier
`ap` parens (primary `sepBy` comma)
parens = between lparen rparen
lparen = char '('
rparen = char ')'
comma = char ','
My self-defined monadic combinator of choice to use with parsec is
a ~ b = a = \x - b return x
It works like (), but returns the result of the first instead of the
result of the second computation. It is kind of an alternative for between:
between lparen rparen p == lparen p ~ rparen
It can be usefull like this:
data Term = TVar Identifier | TTerm Identifier [Term]
term = (return TTerm
`ap` try (identififer ~ lparen)
`ap` (term `sepBy` comma ~ rparen))
| (return TVar
`ap` identifier)
After accepting lparen, the second branch is discarded.
Tillmann
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Tillmann Rendel wrote: My self-defined monadic combinator of choice to use with parsec is a ~ b = a = \x - b return x It works like (), but returns the result of the first instead of the result of the second computation. It is kind of an alternative for between: between lparen rparen p == lparen p ~ rparen Cool. I've always liked how Parsec made parsers so readable, and this makes it even more so. It can be usefull like this: data Term = TVar Identifier | TTerm Identifier [Term] term = (return TTerm `ap` try (identififer ~ lparen) `ap` (term `sepBy` comma ~ rparen)) | (return TVar `ap` identifier) After accepting lparen, the second branch is discarded. Interesting. I think I'll have to keep this one around. Not sure if I'll need it, but its the kind of thing that would have taken me a while to solve ;) Levi lstephen.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsec question
Greetings. I'd like to write a parser that takes some Haskell source code and seperates it into two piles - comments, and everything else. I have a parser that recognises single-line comments, and another that recognises multi-line comments. What I'd like to do is make a big parser that returns [Either String String], which all the comments in one side and all the rest in the other side. But I can't figure out how to construct such a parser... Any hints? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Andrew Coppin [EMAIL PROTECTED] writes: I have a parser that recognises single-line comments, and another that recognises multi-line comments. What I'd like to do is make a big parser that returns [Either String String], which all the comments in one side and all the rest in the other side. But I can't figure out how to construct such a parser... Any hints? wholething = many comment comment = do fmap Left $ (linecomment `onFail` nestedcomment) `onFail` fmap Right $ noncomment ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
Malcolm Wallace wrote: Andrew Coppin [EMAIL PROTECTED] writes: Any hints? wholething = many comment comment = do fmap Left $ (linecomment `onFail` nestedcomment) `onFail` fmap Right $ noncomment Haskell: The language of truely scary people(tm) :-} Thanks, I'll give that a go... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsec Question
I'm trying to use parsec for parsing a custom input stream. As far as I understood the manual correctly I need to define the primitive parser: type MyParser a = GenParser (SourcePos,Tok) () a mytoken :: (Tok - Maybe a) - MyParser a mytoken test = token showToken posToken testToken where showToken (pos,tok) = show tok posToken (pos,tok) = pos testToken (pos,tok) = test tok The problem is, since SourcePos is an abstract datatype, how can I actually run this parser without explicitly using values of type SourcePos in the input stream? Many thanks in advance! _ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec Question
Am Montag, 9. Januar 2006 12:52 schrieb Gerd M: I'm trying to use parsec for parsing a custom input stream. As far as I understood the manual correctly I need to define the primitive parser: type MyParser a = GenParser (SourcePos,Tok) () a mytoken :: (Tok - Maybe a) - MyParser a mytoken test = token showToken posToken testToken where showToken (pos,tok) = show tok posToken (pos,tok) = pos testToken (pos,tok) = test tok The problem is, since SourcePos is an abstract datatype, how can I actually run this parser without explicitly using values of type SourcePos in the input stream? Many thanks in advance! I'm almost convinced, you don't really want to parse a list of (SourcePos,Tok) pairs. The SourcePos is taken care of in the internal state of the parsers. And maybe, you should use tokenPrim instead of token. Then you'd probably get something like type MyParser a = GenParser Tok () a mytoken :: (Tok - Maybe a) - MyParser a mytoken test = tokenPrim show update test where update pos tok toks = case tok of NewL - setSourceColumn (incSourceLine pos 1) 1 _- incSourceColumn pos 1 or whatever is an appropriate update function for the SourcePos. If Tok is Char, of course a wealth of parsers are already supplied. HTH Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsec question: how to access parser state
Hi, I am trying to develop a parser with the Parsec library. At some point I need to do something with parser state, say, convert it to a string. I declared the type for the parser: type TParser a = GenParser Token (FiniteMap String Declaration) a The FiniteMap (which is the user state) is expected to be updated during parsing whus building some internal lookup table. and in one of the parsing functions I want to call show getState assuming it will apply show to the FiniteMap and return some string of characters. During compliation, I get: No instance for (Show (GenParser tok st st)) arising from use of `show' at (file location) In the first argument of `', namely `(show getState)' But GenParser is a newtype, not a data constructor, so attempt to write instance Show (GenParser tok st t) results in error message about missing constructor GenParser. How could I extract actual user state from the result of getState? The parser itself works as needed, but dealing with user state gets me in trouble. Dimitry Golubovsky Middletown, CT ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question: how to access parser state
On Sun, Mar 20, 2005 at 03:32:38PM -0500, Dimitry Golubovsky wrote: type TParser a = GenParser Token (FiniteMap String Declaration) a The FiniteMap (which is the user state) is expected to be updated during parsing whus building some internal lookup table. and in one of the parsing functions I want to call show getState assuming it will apply show to the FiniteMap and return some string of characters. During compliation, I get: No instance for (Show (GenParser tok st st)) arising from use of `show' at (file location) In the first argument of `', namely `(show getState)' This is a good clue--you don't want to show a parser, you want to show the state. Look at the type of getState and think monadic thoughts. There is in fact an example of its use in the Parsec documentation. Andrew ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsec question
On Fri, 19 Nov 2004 14:28:07 + (UTC), John Goerzen [EMAIL PROTECTED] wrote: Hi, I'm porting a parser over from an OCamllex/Ocamlyacc version and I'm using Parsec for both the tokenizer and the resulting token stream parser. I have both of them working fine, but now my question is: how do I combine them? I can't quite figure out how to say take the output from this GenParser Char () Tok and use it as the input for this GenParser Tok () ParserOutput. Well, I have figured out an ugly way involving manually starting up both parsers, but it makes position calculations very complex. Did you try to pair tokens with their SourcePos'es? What I did in my program was this: tokenize :: CharParser st tok - CharParser st [(SourcePos, tok)] tokenize tp = do l - many t eof return l where t = do pos - getPosition tok - tp return (pos, tok) token :: (Show tok) = (tok - Maybe a) - GenParser (SourcePos, tok) st a token f = Parsec.token (show . snd) fst (f . snd) This has a space leak, but I didn't care, because my inputs are at most 10kb long. You can do a lazy version with getInput. BTW, it would be useful if Parsec allowed to throw a ParseError from one type of parser in another parser. It would help me in a situation, where I parse the whole file with one parser, but I retokenize some parts of it and parse them with another parser type. Right now I am using this workaround, but it doesn't work well: cs - chars pos - getPosition x - case p pos cs of Left err - do setPosition (errorPos err) fail (messageString (head (errorMessages err))) Right x - return x How about making an instance for instance Control.Monad.Error.MonadError ParseError (GenParser tok st) PS. I guess I could do this myself. Best regards, Tomasz ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Parsec question
I've also used Parsec for separated lexer + parser and currently have something like this to invoke them: testParse inputString = do case (parse myLexer inputString) of Left err - fail (lexical error: ++ err) Right tokens - case (parse myParser tokens) of Left err - fail (parse error: ++ err) Right result - return result ... or was this the manual startup that you were referring to? The above seems clunky to me, so I'd also welcome suggestions for piping the lexer output into the parser. What do you mean by makes position calculations very complex? Are you talking about reporting the position of lexical or parse errors? (If so, Parsec supports this quite well.) Alistair. -Original Message- From: John Goerzen [mailto:[EMAIL PROTECTED] Sent: 19 November 2004 14:28 To: [EMAIL PROTECTED] Subject: [Haskell-cafe] Parsec question Hi, I'm porting a parser over from an OCamllex/Ocamlyacc version and I'm using Parsec for both the tokenizer and the resulting token stream parser. I have both of them working fine, but now my question is: how do I combine them? I can't quite figure out how to say take the output from this GenParser Char () Tok and use it as the input for this GenParser Tok () ParserOutput. Well, I have figured out an ugly way involving manually starting up both parsers, but it makes position calculations very complex. I suspect I'm missing something. Ideas? - * Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. * ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsec question
On Fri, Nov 19, 2004 at 02:56:38PM -, Bayley, Alistair wrote: I've also used Parsec for separated lexer + parser and currently have something like this to invoke them: testParse inputString = do case (parse myLexer inputString) of Left err - fail (lexical error: ++ err) Right tokens - case (parse myParser tokens) of Left err - fail (parse error: ++ err) Right result - return result ... or was this the manual startup that you were referring to? The above seems clunky to me, so I'd also welcome suggestions for piping the lexer output into the parser. Yep, that is exactly the idea I took. Works, but just doesn't seem right. What do you mean by makes position calculations very complex? Are you talking about reporting the position of lexical or parse errors? (If so, Parsec supports this quite well.) The parse errors. I did take to passing around pairs of SourcePos, Tok around. It works, but I had to then write custom token functions to handle them. I'd rather be able to just access the other parser like normal (refer to it in a do block or whatever), so I don't have to manually handle it. I suppose very complex was an exaggeration, looking back. -- John ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
