在应用解析中苦苦挣扎

Question

所以我正在编写一个复杂的解析器,只使用Applicative(有问题的解析器甚至根本没有实现Monad).

对于普通的解析器,这很容易.对于非平凡的......不是那么多.应用界面似乎猛烈地迫使你以无点样式编写所有内容.这是非常难以处理的.

例如,考虑一下:

call = do
  n <- name
  char '('
  trim
  as <- sepBy argument (char ',' >> trim)
  char ')'
  trim
  char '='
  r <- result
  return $ Call {name = n, args = as, result = r}

现在让我们尝试使用applicative来编写:

call =
  (\ n _ _ as _ _ _ _ r -> Call {name = n, args = as, result = r}) <$>
  name <*>
  char '(' <*>
  trim <*>
  sepBy argument (const const () <$> char ',' <*> trim) <*>
  char ')' <*>
  trim <*>
  char '=' <*>
  trim <*>
  result

Applicative 迫使我把变量绑定放在离实际解析器很远的地方.(例如,尝试确认这as实际上是绑定的sepBy argument ...;验证我没有错误的_模式数量并不容易!)

另外一个很直观的是,<*>应用一个函数的值,但*>与<*只是纯粹的测序.这花了年龄到绕到我的脑海里.不同的方法名称可以做得更远,更清晰.(但单子似乎已经抓住>>和<<可悲的.)看来,这些可堆叠,就像屈服的东西

exit =
  "EXIT:" *>
  trim *>
  name <*
  char '(' <*
  trim <*
  char ')' <*
  trim

你可以做到这一点是非常明显的.而且,对我来说,这段代码真的不是非常易读.更重要的是,我仍然没有弄清楚如何在删除多个其他值时处理多个值.

总之,我发现自己希望我可以使用do-notation!我实际上不需要根据先前的结果改变效果; 我并不需要单子的力量.但这种符号更具可读性.(我一直想知道实现它是否真的可行;你能在语法上告诉我什么时候可以将特定的do-block机械转换为applicative？)

有没有人知道解决这些问题的方法？最特别的是,如何将变量绑定移动到更接近它们绑定的解析器？

Answer 1

好吧,你的示例解析器是人为复杂的.

有很多trim可以从中抽象出来:

token p = p <* trim

您还可以从一对匹配括号之间的某些内容中抽象出来:

parens p = token (char '(') *> p <* token (char ')')

现在剩下的是:

call =
  (\ n as _ r -> Call {name = n, args = as, result = r}) <$>
  name <*>
  parens (sepBy argument (() <$ token (char ','))) <*>
  token (char '=') <*>
  result

最后,你不应该计算出现_,而是学会使用<$和<*.以下是有用的经验法则:

• 仅使用*>在组合foo *> p <* bar如parens上述,别的地方.

• 让你的解析器有形式f <$> p1 <*> ... <*> pn,而现在之间进行选择<$>,并<$在第一位置之间或<*>与<*所有其它位置为纯粹的你是否有兴趣在随后的解析器的结果的问题.如果是,请使用变体>,否则,使用不带变体.然后你永远不需要忽略任何参数f,因为你甚至无法访问它们.在上面的简化示例中,只=留下我们不感兴趣的令牌,所以我们可以说

  call = Call <$> name
              <*> parens (sepBy argument (() <$ token (char ',')))
              <*  token (char '=')
              <*> result
  

(这假设Call实际上只需要这三个参数.)我认为这个版本比你原来do的版本更容易阅读.

回答你更普遍的问题:是的,可以识别do不需要monad功能的语句.简单地说,它们只是最后一个带有a的绑定序列return,并且所有绑定变量仅用于最终return和其他地方.有人建议将此添加到GHC.(就个人而言,我并不是它的忠实粉丝.我认为应用符号比功能符号更有用.)

Answer 2

我确实没有解决该问题的方法，但也许一些直觉可以帮助您更轻松地构建应用解析器。当谈到应用时，有两种“排序”需要考虑：

\n\n

\n
• 解析操作的顺序：这决定了编写解析器的顺序。
\n
• 基础值的排序：这个更加灵活，因为您可以按照您喜欢的任何顺序组合它们。
\n

\n\n

当两个序列彼此匹配良好时，结果是解析器在应用符号中的非常漂亮和紧凑的表示。例如：

\n\n

data Infix = Infix     Double     Operator     Double\ninfix      = Infix <$> number <*> operator <*> number\n

\n\n

问题是，当序列不完全匹配时，您必须调整基础值才能使事情正常工作（您无法更改解析器的顺序）：

\n\n

number = f <$> sign <*> decimal <*> exponent\n  where f sign decimal exponent = sign * decimal * 10 ^^ exponent\n

\n\n

在这里，为了计算数字，您必须执行一些不平凡的操作组合，这是由局部函数 完成的f。

\n\n

另一种典型情况是您需要丢弃一些值：

\n\n

exponent = oneOf "eE" *> integer\n

\n\n

这里，*>丢弃左侧的值，保留右侧的值。操作<*员做相反的事情，丢弃右侧并保留左侧。当你有一系列这样的操作时，你必须使用左关联性来解码它们：

\n\n

p1 *> p2 <* p3 *> p4 <* p5  \xe2\x89\xa1  (((p1 *> p2) <* p3) *> p4) <* p5\n

\n\n

这是人为设计的：您通常不想这样做。最好将表达式分解为有意义的部分（最好给出有意义的名称）。您将看到的一种常见模式是：

\n\n

-- discard the result of everything except `p3`\np1 *> p2 *> p3 <* p4 <* p5\n

\n\n

但有一个小警告，如果您想应用其他内容p3或p3由多个部分组成，则必须使用括号：

\n\n

-- applying a pure function\nf <$> (p1 *> p2 *> p3 <* p4 <* p5)  \xe2\x89\xa1  p1 *> p2 *> (f <$> p3) <* p4 <* p5\n\n-- p3 consists of multiple parts\np1 *> p2 *> (p3\' <*> p3\'\') <* p4 <* p5)\n

\n\n

同样，在这些情况下，通常最好将表达式分解为带有名称的有意义的片段。

\n\n

从某种意义上说，应用表示法迫使您将解析器划分为逻辑块，以便更容易阅读，而不是一元表示法，您可以想象在一个整体块中完成所有操作。

\n