BNF fparsec语法分析器出错

Question

我制作了以下解析器来尝试解析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

为了测试，我按照维基百科在BNF的BNF上运行它：

<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> "'"

但它总是失败，并出现以下错误：

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

我做错了什么？

---

编辑

我用来测试的功能：

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

Answer 1

您的第一个问题是pList：sepBy1贪婪地占用尾部空格，但一旦这样做，它就会期望后面有一个额外的术语，而不是列表的末尾。解决此问题的最简单方法是使用sepEndBy1。

这将暴露出您的下一个问题：pEndLine没有得到忠实的实现，因为您总是只寻找一个后面跟一个换行符的空间，而应该寻找任意数量的空间（也就是说，您希望pWS >>. newline位于内部，而不是pchar ' ' >>. newline）。

最后，请注意，您的定义要求每个规则都以换行符结尾，因此您将无法按照给定的方式解析字符串（您需要在末尾附加一个空行）。相反，您可能希望从pRule的定义中提取newline，并将主解析器定义为sepBy1 pRule pLineEnd |>> BNF.Syntax。