如何使用 FParsec 解析递归左语法规则？-解网

问：

我通常将 FParsec 用于 LL 语法，但有时在整个语法中只有一个元素需要左递归解析（因此语法不再是 LL）。目前我有这样的情况，我有一个用 FParsec 实现的大型 LL 语法，但是一个小的语法元素困扰着我，因为它显然无法正确解析。

有问题的语法元素是对 F# 数组索引的访问，例如 where 可以是任何表达式，也可以是任何表达式。事实证明，我的函数调用使用方括号，而不是括号，并且我的标识符可以用点来限定。myArray.[index]myArrayindex

表达式的正确语法示例为：。std.fold[fn, f[myArray.[0]], std.tail[myArray]]

语法元素显然是递归的，但也许有一个技巧可以让我解析它？我的最小代码如下：.[]

open FParsec

type Name = string list

type Expr =
    (* foo, Example.Bar.fizz *)
    | Variable of Name

    (* 9, 17, -1 *)
    | Integer of int

    (* foo[3, 2], Std.sqrt[2] *)
    | FunCall of Name * Expr list

    (* (a + b), (a + (1 - c)) *)
    | Parens of Expr

    (* myArray.[0], table.[index - 1] *)
    | ArrayAccess of Expr * Expr

    (* a + b *)
    | Addition of Expr * Expr

let opp =
    new OperatorPrecedenceParser<Expr, _, _>()

let pExpr = opp.ExpressionParser

let pName =
    let id =
        identifier (IdentifierOptions(isAsciiIdStart = isAsciiLetter, isAsciiIdContinue = isAsciiLetter))

    sepBy1 id (skipChar '.')

let pVariable = pName |>> Variable

let pInt = pint32 |>> Integer

let pFunCall =
    pipe4
        pName
        (spaces >>. skipChar '[')
        (sepBy (spaces >>. pExpr) (skipChar ','))
        (spaces >>. skipChar ']')
        (fun name _ args _ -> FunCall(name, args))

let pArrayAccess =
    pipe5
        pExpr
        (spaces >>. skipChar '.')
        (spaces >>. skipChar '[')
        (spaces >>. pExpr)
        (spaces >>. skipChar ']')
        (fun expr _ _ index _ -> ArrayAccess(expr, index))

let pParens =
    between (skipChar '(') (skipChar ')') (spaces >>. pExpr)

opp.TermParser <-
    choice [ attempt pFunCall
             pVariable
             pArrayAccess
             pInt
             pParens ]
    .>> spaces

let addInfixOperator str prec assoc mapping =
    opp.AddOperator
    <| InfixOperator(str, spaces, prec, assoc, (), (fun _ leftTerm rightTerm -> mapping leftTerm rightTerm))

addInfixOperator "+" 6 Associativity.Left (fun a b -> Addition(a, b))

let startParser = runParserOnString (pExpr .>> eof) () ""

printfn "%A" <| startParser "std.fold[fn, f[myArray.[0]], std.tail[myArray]]"

一种方法是如下：与其列出解析选项列表，也像上面一样列出，这在某些时候会导致无限循环，不如修改以将有问题的语法元素解析为表达式后面的可选元素：pArrayAccesspExpr

let pExpr =
    parse {
        let! exp = opp.ExpressionParser
        let pArrayAccess =
            between (skipString ".[") (skipString "]") opp.ExpressionParser

        match! opt pArrayAccess with
        | None -> return exp
        | Some index -> return ArrayAccess(exp, index)
    }

经过测试，事实证明，如果不满足以下两个条件，这将非常有效：

方括号的内容不得包含对另一个数组的访问;
不能连续第二次访问数组（）。my2DArray.[x].[y]

这在一定程度上限制了使用。我怎样才能逃脱这个？有没有办法做到这一点，或者我必须改变语法？

f# fparsec 左递归

您需要使用 .现在没有时间生成答案，但例如，请参阅我的锻炼练习解决方案 - exercism.org/tracks/fsharp/exercises/sgf-parsing/solutions/... （请注意，他们的在线测试运行器尚未包含 FParsec 库，因此它抱怨说，它确实在本地通过了所有测试）。createParserForwardedToRef()

1赞 Martin Freedman 8/1/2022

编辑我之前的评论为时已晚，但我的示例专门针对嵌套括号。

答：

0赞 Foxy 8/9/2022 #1

最后，这个问题的解决方案非常简单：只需期待数组访问列表即可。如果列表为空，则返回初始表达式，否则折叠所有数组访问并返回结果。这是实现：

let rec pExpr =
    parse {
        let! exp = opp.ExpressionParser

        let pArrayAccess =
            between (skipString ".[") (skipString "]") pExpr

        match! many pArrayAccess with
        | [] -> return exp
        | xs -> return List.fold
                    (fun acc curr -> ArrayAccess(acc, curr)) exp xs
    }

这种做事方式满足了我的需求，所以我会很高兴，如果有人路过并想要更通用的东西并且不适用于建议的解决方案，那么我参考@Martin弗里德曼评论，使用 .createParserForwardedToRef()

上一个：为什么我的 FParsec 解析器无法识别块注释？

下一个：使用 FParsec，是否可以在解析器失败时操纵错误位置？

如何使用 FParsec 解析递归左语法规则？

How to parse a recursive left syntax rule with FParsec?

评论