Back to Questions
1.9k
views5
comments
FParsec parsing multiple characters - what am I doing wrong?
f#parsing

I'm just experimenting with FParsec, trying to figure out how I'd translate some regular expressions into their FParsec equivalents.

What's the right way to get something like regex asterisks:

1

/[ax]*/

The basic bit of this (just match the two characters) works like I would expect, but the 'many' version clearly isn't what's expected (error message shown below).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

open FParsec.Primitives
open FParsec.CharParsers

type sparser = Parser<string, unit>

module tst1 =
  let a = pchar 'a'
  let x = pchar 'x'
  let letter = a <|> x
  let letters = many letter
  let result = run letters "aaxxax"

//module tst1 = begin
//  val a : Parser<char,unit>
//  val x : Parser<char,unit>
//  val letter : Parser<char,unit>
//  val letters : Parser<char list,unit>
//  val result : ParserResult<char list,unit> =
//    Success: ['a'; 'a'; 'x'; 'x'; 'a'; 'x']
//end

module tst2 =
  let a: sparser = manyChars (pchar 'a')
  let x: sparser = manyChars (pchar 'x')
  let letter = a <|> x
  let letters = many letter
  let result = run letters "aaxxax"
  
//Microsoft.FSharp.Core.FailureException: (Ln: 1, Col: 3): The combinator 'many' was applied to a parser that succeeds without changing the parser state. (If no exception had been raised, the combinator likely would have entered an infinite loop.)
//   at Microsoft.FSharp.Core.Operators.failwith[T](String message)

I'd like to get ["aa"; "xx"; "a"; "x"]

.

The direct FParsec equivalent to the regex "[ax]*" would be 

1

manyChars (anyOf "ax")

There are other ways to achieve the same thing, the fastest being

1

manySatisfy (fun c -> c = 'a' || c = 'x').

As Brian correctly pointed out, the problem with your original code is that you apply "many" to a parser that can succeed without consuming input: your letter parser. Normally you shouldn't have a "many" parser directly nested within another "many" parser, like "many (manyChars ... <|> manyChars ...)" in this case. Instead you should require the inner parser to consume input, for example by using "many1Chars" instead of "manyChars".

By on 6/23/2009 11:25 AM ()

'manyChars' includes the case of no chars. Therefore, your 'letter' parser would successfully match an empty sequence.

'many' applies the parser that is given to it as an argument until it fails. If it succeeds on empty input, then on next iteration it will again be applied on the same input (and obviously again succeed), thus entering infinite loop. For this reason, 'many' specifically checks for the case of EmptyOk, and throws the exception that you see.

For starters, I'm not sure what's wrong with your first version. It is precisely equivalent to your original regexp, and will match subsequences of identical characters in the input just fine as well. If you're doing the second version just for performance reasons, then you should use 'many1Chars' (which needs at least 1 char to match to succeed).

By on 6/23/2009 11:21 AM ()

What I'd like to build eventually is a parser that understands enough Ruby to translate Ruby to HTML, suitable for posting nicely formatted snippets to blogs.

Ruby is interesting, since it's got a couple constructs most tools for translating code to HTML don't handle well:

User-selectable characters for string delimiters:

1
2

%q(these " literal strings are identical)
%q,these " literal strings are identical,

Similar for regular expressions:

1
2

%r(There's nothing special about / here)
%r[There's nothing special about / here]

And, what I assume is going to be the most nasty bit, interpolation like this:

1

"This is a string #{ lots_of_ruby_code "with string arguments" } to be printed"

(where everything in the #{} section is Ruby that gets evaluated and inserted into the string)

By on 6/23/2009 11:13 AM ()

I don't know the FParsec APIs well enough, but I think the problem is that 'manyChars' can succeed on the empty string, you want e.g. the moral equivalent of 'atLeastOneChars'.

By on 6/23/2009 11:05 AM ()

Thanks brian - that was the problem. many1Chars, not manyChars.

1
2
3
4
5
6

module tst2 =
  let a: sparser = many1Chars (pchar 'a')
  let x: sparser = many1Chars (pchar 'x')
  let letter = a <|> x
  let letters = many letter
  let result = run letters "aaxxax"
By on 6/23/2009 11:14 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper