parsing - 解析项的 FParsec 和后缀修饰符

Question

作为我自己的练习，我正在使用 FParsec 编写一个函数，该函数可以从(有限的)正则表达式形式的规范中生成随机字符串。
例如。

Input: ([Hh]ello ){1,3} world!?
Output: Hello hello world!

Input: (\d{1,2}\.){3}(\d{1,2})
Output: 38.12.29.05

我有很多工作，但我在后缀术语的想法上遇到了麻烦(即解析器可能需要返回并修改输出，而不仅仅是 Char 流中的位置)。例如。 “a”与“a+”
这是我的域类型的简化版本:

type Count =
    | ExactCount of int
    | MinCount of int
    | MaxCount of int
    | RangeCount of int * int

type Term =
    | CharLiteral of char
    | Count of Term * Count

type RandExpSpec = Term list

所以输入 ab应该生成 [CharLiteral 'a'; CharLiteral 'b']但是 ab+应该生成 [CharLiteral 'a'; Count (CharLiteral 'b', MinCount 1)] .所以这意味着，在遇到 Count 时流中的术语，解析器需要回溯输出，以便将最后一个术语包装在另一个对象中。
现在，我不知道该怎么做。这是我当前的解析定义，它(大部分)工作但效率很低:

let parseCharLiteral = choice [ letter; digit ] |>> CharLiteral

let rec parseTerm =
    parse.Delay(fun () -> choice [ parseCharLiteral ])

and parseCount =
    parseTerm
    .>>. choice [ skipChar '*' >>% (MinCount 0)
                  skipChar '+' >>% (MinCount 1)
                  skipChar '?' >>% (RangeCount(0, 1)) ]
    |>> Count

let parseTerms =
    many ((attempt parseCount) <|> parseTerm) .>> eof

您可以在 parseCount 中看到我打电话 parseTerm首先，然后解析实际计数信息。然后，在 parseTerms我尝试了 parseCount每次解析器，如果它不起作用，则回溯输入。这是非常低效的，因为我基本上对输入流中的几乎每个字符都进行了两次传递，以防万一它后面跟着一个计数修饰符。
有没有更有效的方法来做到这一点？我觉得我应该写一些更像的东西:

let parseCharLiteral = choice [ letter; digit ] |>> CharLiteral

let rec parseTerm =
    parse.Delay(fun () -> choice [ parseCharLiteral ] .>>. (attempt parseCount))

and parseCount =
    choice [ skipChar '*' >>% (MinCount 0)
             skipChar '+' >>% (MinCount 1)
             skipChar '?' >>% (RangeCount(0, 1)) ]
    |>> Count

let parseTerms =
    many parseTerm .>> eof

但自从 parseCount 起我就无法完成这项工作qould 需要包装 parseTerm 返回的前一项.

Answer 1

我想你可以用 opt允许 parseCount如果没有，则找不到计数:

let parseCount =
    parseTerm
    .>>. opt (choice [ skipChar '*' >>% (MinCount 0)
                       skipChar '+' >>% (MinCount 1)
                       skipChar '?' >>% (RangeCount(0, 1)) ])
    |>> function
    | term, None -> term
    | term, Some count -> Count (term, count)

let parseTerms =
    many parseCount .>> eof