error in BNF fparsec parser

Question

I have made the following parser to try to parse BNF:

type Literal = Literal of string
type RuleName = RuleName of string
type Term = Literal of Literal
          | RuleName of RuleName
type List = List of Term list
type Expression = Expression of List list
type Rule = Rule of RuleName * Expression
type BNF = Syntax of Rule list

let pBFN : Parser<BNF, unit> = 
   let pWS = skipMany (pchar ' ')
   let pLineEnd = skipMany1 (pchar ' ' >>. newline)

   let pLiteral = 
       let pL c = between (pchar c) (pchar c) (manySatisfy (isNoneOf ("\n" + string c)))
       (pL '"') <|> (pL '\'') |>> Literal.Literal

   let pRuleName = between (pchar '<') (pchar '>') (manySatisfy (isNoneOf "\n<>")) |>> RuleName.RuleName
   let pTerm = (pLiteral |>> Term.Literal) <|> (pRuleName |>> Term.RuleName)
   let pList = sepBy1 pTerm pWS |>> List.List
   let pExpression = sepBy1 pList (pWS >>. (pchar '|') .>> pWS) |>> Expression.Expression
   let pRule = pWS >>. pRuleName .>> pWS .>> pstring "::=" .>> pWS .>>. pExpression .>> pLineEnd |>> Rule.Rule
   many1 pRule |>> BNF.Syntax

For testing, I'm running it on BNF's BNF as per Wikipedia:

<syntax> ::= <rule> | <rule> <syntax>
<rule> ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | ""
<expression> ::= <list> | <list> <opt-whitespace> "|" <opt-whitespace> <expression>
<line-end> ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list> ::= <term> | <term> <opt-whitespace> <list>
<term> ::= <literal> | "<" <rule-name> ">"
<literal> ::= '"' <text> '"' | "'" <text> "'"

But it always fails with this error:

Error in Ln: 1 Col: 21
<syntax> ::= <rule> | <rule> <syntax>
                    ^
Expecting: ' ', '"', '\'' or '<'

What am I doing wrong?

Edit

The function I'm using to test:

let test =
   let text = "<syntax> ::= <rule> | <rule> <syntax>
<rule> ::= <opt-whitespace> \"<\" <rule-name> \">\" <opt-whitespace> \"::=\" <opt-whitespace> <expression> <line-end>
<opt-whitespace> ::= \" \" <opt-whitespace> | \"\"
<expression> ::= <list> | <list> <opt-whitespace> \"|\" <opt-whitespace> <expression>
<line-end> ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list> ::= <term> | <term> <opt-whitespace> <list>
<term> ::= <literal> | \"<\" <rule-name> \">\"
<literal> ::= '\"' <text> '\"' | \"'\" <text> \"'\""
   run pBNF text

You should do detailed test cases starting with the most fundamental parsers including the ones given to you with FParsec, e.g. pchar, skipMany, and work your way up and then if you did valid test cases, you will find your problem. I did get the exact same error as you but after looking at it for a minute I did not see the problem. As such my next course of action to solve this would be to do what I just suggested. — Guy Coder
A general note for others learning FParsec and looking at this solution. Since FParsec builds parsers using functional composistion if you try to use a debugger on this problem in the same way you debug imperative code it will not work as expected because the debugger will step over all of the parsing steps and you will only end up seeing the call then the error. Also if you try and instrument the code simply with printf statements it will also fail, again because the called parser is built up using functional composition. — Guy Coder
Another option I prefer with parser combinators is to actually do a lexing then a parsing step. Typically with FParsec there are no separate steps. There is nothing wrong with that, it is just a personal preference but I find it easer, being old school, to do it that way. In my opinion it also makes it easer to generate errors because the syntax and semantics are more clearly separated. — Guy Coder
I find that when doing test cases for parser combinators the first ones that test all of the char parsers, e.g. upper, lower, white space, numerical, special, misc. are the hardest because you have to test each character, but after you have those and then the basic sequential, or and option parsers done, it gets much easier and faster. Don't for get to test the parsers without the treatment, e.g. |>> and then with the treatment. — Guy Coder
Are you aware that you can use triple quoted string so you don't have to delimit the double quotes, e.g. instead of "x\"y" you can do """x"y""" — Guy Coder

kvb kvb · Accepted Answer · 2016-04-15T16:01:36

Your first problem is with pList: sepBy1 is greedily grabbing trailing spaces, but once it does that it then expects an additional term to follow rather than the end of the list. The simplest way to fix this is to use sepEndBy1 instead.

This will expose your next problem: pEndLine isn't faithfully implemented because you're always looking for exactly one space followed by a newline, when you should be looking for any number of spaces instead (that is, you want pWS >>. newline in the interior, rather than pchar ' ' >>. newline).

Finally, note that your definition requires each rule to end with a newline, so you won't be able to parse your string as given (you'll need to append an empty line to the end). Instead you might want to pull newline out of your definition of pRule and define the main parser as sepBy1 pRule pLineEnd |>> BNF.Syntax.

error in BNF fparsec parser

1 Answers