5

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

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

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

4

2 回答 2

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

于 2013-07-28T18:24:41.790 回答
1

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

方面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
于 2020-06-25T18:14:37.040 回答