如何在Parsec中实现下标运算符

Question

我正在Parsec中编写一个解析器。像E->E+E这样的左递归生成无法在LL解析器中轻松编写，因此Parsec提供了buildExpressionParser，它支持中缀、后缀和前缀运算符。但是下标运算符呢？

E->E[E]将如何实施？如果我可以使用右括号而不使用第二个表达式，那么我可以用buildExpressionParser的Infix表条目来模拟它。想法？

编辑：我知道有一种左递归消除算法，它很可能适用于我的语法。我正在寻找一些简单或抽象的东西（例如buildExpressionParser）。否则我就用Happy。

Answer 1

在我们的项目中，我们手动从表达式中消除了左递归。其工作方式如下：

我们创建了一种通用的表达式形式，它由术语解析器参数化：

expressionGen :: MParser (Expr LocInfo) -> MParser (Expr LocInfo)
expressionGen term = buildExpressionParser precedenceTable term <?> "expression"
  where precedenceTable = -- unary, binary expressions

我们有一个普通的术语解析器和一个没有递归规则的术语解析器。这样，我们就可以解析（多个）下标运算符：

term :: MParser (Expr LocInfo)
term = do indBase <- termNoArray
          indexes <- many $ (brackets expression >>= return)
          return -- semantics
        <?> "term"
termNoArray :: MParser (Expr LocInfo)
termNoArray = -- normal terms

最后，我们有一个最顶层的表达式解析器：expression = expressionGen term

Answer 2

诀窍是将后缀下标运算符视为一个整体，包括索引表达式。

在megaparsec/parsec-combinators术语中：

pExpr = makeExprParser pTerm operatorTable
...
parseSubscr :: Operator Parser Expr
parseSubscr =
  Postfix $ do
    symbol space "["
    index <- pExpr
    symbol space "]"
    pure $ parent ->
      Subscript parent index