parsing - 递归解析语法消耗输入并且无法解析序列

Question

我正在尝试写一个 Augmented Backus-Naur form解析器。然而，每当我尝试解析替代方案时，我都会遇到堆栈溢出异常。以下是触发该问题的示例:

#r @"..\packages\FParsec\lib\net40-client\FParsecCS.dll"
#r @"..\packages\FParsec\lib\net40-client\FParsec.dll"
open FParsec

type Parser<'t> = Parser<'t, unit>

type Element =
    | Alternates of Element list
    | ParsedString of string

let (pRuleElement, pRuleElementRef) : (Parser<Element> * Parser<Element> ref) = createParserForwardedToRef()

let pString =
    pchar '"' >>. manyCharsTill (noneOf ['"']) (pchar '"')
    |>> ParsedString

let pAlternates : Parser<_> =
    sepBy1 pRuleElement (many (pchar ' ') >>. (pchar '/') >>. many (pchar ' ') )
    |>> Alternates

do pRuleElementRef :=
    choice
        [
            pString
            pAlternates
        ]

"\"0\" / \"1\" / \"2\" / \"3\" / \"4\" / \"5\" / \"6\" / \"7\""
|> run (pRuleElement .>> (skipNewline <|> eof))

只需重新排序选择即可轻松解决该问题，如下所示:

do pRuleElementRef :=
    choice
        [
            pAlternates
            pString
        ]

但是，这会导致堆栈溢出，因为它不断尝试解析新的替代序列而不消耗输入。此外，该方法会破坏 ABNF 优先级:

1. 字符串、名称构成
2. 评论
3. 值范围
4. 重复
5. 分组，可选
6. 串联
7. 替代方案

我的问题本质上可以归结为:如何组合对单个元素(可以是元素序列或元素的单个实例)的解析？如果您需要任何说明/其他示例，请告诉我。

非常感谢您的帮助，谢谢!

编辑:

我可能应该提到还有各种其他类型的分组。序列组(element[s])和可选组[可选元素[s]。其中 element 可以是嵌套组/可选组/字符串/其他元素类型。下面是一个序列组解析的示例(为简单起见，不包括可选的组解析):

#r @"..\packages\FParsec\lib\net40-client\FParsecCS.dll"
#r @"..\packages\FParsec\lib\net40-client\FParsec.dll"
open FParsec

type Parser<'t> = Parser<'t, unit>

type Element =
    | Alternates of Element list
    | SequenceGroup of Element list
    | ParsedString of string

let (pRuleElement, pRuleElementRef) : (Parser<Element> * Parser<Element> ref) = createParserForwardedToRef()

let pString =
    pchar '"' >>. manyCharsTill (noneOf ['"']) (pchar '"')
    |>> ParsedString

let pAlternates : Parser<_> =
    pipe2
        (pRuleElement .>> (many (pchar ' ') >>. (pchar '/') >>. many (pchar ' ')))
        (sepBy1 pRuleElement (many (pchar ' ') >>. (pchar '/') >>. many (pchar ' ') ))
        (fun first rest -> first :: rest)
    |>> Alternates

let pSequenceGroup : Parser<_> =
    between (pchar '(') (pchar ')') (sepBy1 pRuleElement (pchar ' '))
    |>> SequenceGroup

do pRuleElementRef :=
    choice
        [
            pAlternates
            pSequenceGroup
            pString
        ]

"\"0\" / ((\"1\" \"2\") / \"2\") / \"3\" / (\"4\" / \"5\") / \"6\" / \"7\""
|> run (pRuleElement .>> (skipNewline <|> eof))

如果我尝试首先解析替代项/序列组，它会因堆栈溢出异常而终止，因为它随后会尝试重复解析替代项。

Answer 1

问题是，当您在输入上运行 pRuleElement 解析器时，它会正确解析一个字符串，留下一些未使用的输入，但随后它会在 choice 之外失败> 那会原路返回。

您可以在主输入上运行 pAlternates 解析器，它实际上有效:

"\"0\" / \"1\" / \"2\" / \"3\" / \"4\" / \"5\" / \"6\" / \"7\""
|> run (pAlternates .>> (skipNewline <|> eof))

我怀疑您可能可以这样做 - pAlternates 解析器可以正常工作，即使只处理单个字符串 - 它只会返回包含单例列表的 Alternates 。