递归解析语法会消耗输入并无法解析序列。

Question

我正在尝试编写一个 增强型巴克斯-诺尔范式 解析器。然而，每当我尝试解析替代方案时，都会遇到堆栈溢出异常。下面是一个触发此问题的示例：

#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))

问题很容易解决，只需像这样重新排列choice即可：

do pRuleElementRef :=
    choice
        [
            pAlternates
            pString
        ]

然而，这会导致堆栈溢出，因为它不断尝试解析新的备选序列而没有消耗输入。此外，该方法还会破坏ABNF优先级顺序：

1. 字符串，名称形成
2. 注释
3. 值范围
4. 重复
5. 分组，可选
6. 连接
7. 备选项

我的问题基本上可以归结为：如何组合解析单个元素，该元素可以是元素序列或元素的单个实例？如果您需要任何澄清/附加示例，请告诉我。

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

编辑：

我应该提到还有各种其他类型的分组。序列组(element[s])和可选组[optional element[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))

如果我首先尝试解析替代/序列组，它会因为不断地尝试解析替代而导致堆栈溢出异常发生。

- Chris Altig

Answer 1

问题在于当你在输入上运行 pRuleElement 解析器时，它正确地解析了一个字符串，留下了一些未使用的输入，但随后在 choice 之外失败了，无法回溯。

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

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

我猜您可以直接这样做 - 即使只有一个字符串，pAlternates解析器仍然可以正确工作 - 它将会返回仅包含单一字符串的Alternates。"最初的回答"。

- Tomas Petricek

---

你好Tomas，谢谢你的回复！我已经相应地编辑了我的问题。 - Chris Altig

@ChrisAltig 我认为区分 pString 和 pSequenceGroup 将会很好，因为这两者在它们的第一个字符上不同 - 即如果不是这两者之一，则解析器将失败。然而，pAlternates 仍然需要在顶层运行，以便它可以消耗一个接一个的东西 - 所以我认为你需要两个解析器 - 一个用于任何可以通过第一个字符确定的内容，另一个用于通过交替迭代这些内容。 - Tomas Petricek

你真是读懂了我的心思。我刚刚完成了一个类似的解决方案，并准备回答时，你就发表了评论。我也得出了结论，顺序可能与维基百科链接中列出的优先级顺序不匹配（不能匹配？）。虽然，我认为这并不重要。 - Chris Altig

Answer 2

看起来解决方案就是在解析备选项时不尝试解析备选项，以避免无限循环导致堆栈溢出。 我问题中发布的代码的工作版本如下：

#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 (pNotAlternatives, pNotAlternativesRef) : (Parser<Element> * Parser<Element> ref) = createParserForwardedToRef()

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

let pAlternates : Parser<_> =
    pipe2
        (pNotAlternatives .>>? (many (pchar ' ') >>? (pchar '/') >>. many (pchar ' ')))
        (sepBy1 pNotAlternatives (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
        ]

do pNotAlternativesRef :=
    choice
        [
            pSequenceGroup
            pString
        ]

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

除了添加 pNotAlternatives 之外，我还对其进行了修改，使其在无法解析备选分隔符 / 时回溯，从而使其在“意识到”它实际上不是备选列表后能够继续进行。

- Chris Altig