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

Question

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

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

表达式的正确语法示例如下：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]]"

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

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

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

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

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

Answer 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 Freedman 评论，使用createParserForwardedToRef().