我正在尝试写一个 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 优先级:
- 字符串、名称构成
- 评论
- 值范围
- 重复
- 分组,可选
- 串联
- 替代方案
我的问题本质上可以归结为:如何组合对单个元素(可以是元素序列或元素的单个实例)的解析?如果您需要任何说明/其他示例,请告诉我。
非常感谢您的帮助,谢谢!
编辑:
我可能应该提到还有各种其他类型的分组。序列组(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))
如果我尝试首先解析替代项/序列组,它会因堆栈溢出
异常而终止,因为它随后会尝试重复解析替代项。
最佳答案
问题是,当您在输入上运行 pRuleElement
解析器时,它会正确解析一个字符串,留下一些未使用的输入,但随后它会在 choice
之外失败> 那会原路返回。
您可以在主输入上运行 pAlternates
解析器,它实际上有效:
"\"0\" / \"1\" / \"2\" / \"3\" / \"4\" / \"5\" / \"6\" / \"7\""
|> run (pAlternates .>> (skipNewline <|> eof))
我怀疑您可能可以这样做 - pAlternates
解析器可以正常工作,即使只处理单个字符串 - 它只会返回包含单例列表的 Alternates
。
关于parsing - 递归解析语法消耗输入并且无法解析序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56520740/