Representing epsilon productions with FParsec parser combinators

Question

It is often convenient to express grammar productions in BNF like

A ::= "car"
   |  "bike"
   |  ε

where ε represents an empty production rule; i.e., the nonterminal "A" could expand to the terminals "car", "bike", or nothing. However, unless I refactor my grammar, it is unclear to me how I would represent such a grammar in FParsec. I am aware of the 'choice' combinator, <|>, but as far as I know there is no 'empty' combinator. I.e., a combinator that returns true and consumes no input.

I've searched the FParsec documentation high and low, but I have not found anything that does this, which surprises me, because this seems like a common scenario. I'm fairly new to FParsec (and combinators in general), so maybe I am just not using the right words. Any hints?

Answer 1

I think Jack's solution should do the trick for you. However, if you're looking for a primitive that represents a parser which succeeds, without consuming any input, then you probably want preturn from FParsec.Primitives (see preturn in the documentation).

It could be useful if you were combining parsers that build values of some AST instead of strings. For example if you had a discriminated union:

type Vehicle = Car | Bike | Other

You could use pstring "car" >>% Car and pstring "bike" >>% Bike to build parsers that return Vehicle values. Then you could combine them using <|> and add a special (empty) case using preturn:

let parseA = 
  pstring "car" >>% Car <|> 
  pstring "bike" >>% Bike <|>
  preturn Other

The preturn operation is probably not used directly very often, but it is one of the basic primitives (because it defines the monadic unit or return operation of parsers).

Answer 2

I'm not too familiar with FParsec -- I usually use fsyacc -- but what happens if you use an empty string with the choice combinator? E.g., something like:

let parseA = pstring "car" <|> pstring "bike" <|> pstring ""