无法理解相互递归 [英] Unable to understand a mutual recursion

问题描述

我正在阅读Programming In Haskell，在第8章中，作者给出了一个编写解析器的例子。
完整的源代码位于： http：//www.cs。 nott.ac.uk/~gmh/Parsing.lhs
我无法理解以下部分： many 允许零个或多个 p ，
而 many1 至少需要一个成功的应用程序：

  many :: Parser a→Parser [a] 
 many p = many1 p +++ return [] 
 many1 :: Parser a→Parser [a] 
 many1 p = do v←p 
 vs←many p 
 return（v：vs）
  

递归调用如何发生在

  vs < - 许多p 
  

vs 是许多p ，但许多p称为 many1 p ，所有 many1 都在其定义中是一个符号，并且结果值又是 v 和 vs ，何时再次出现呼叫回复？
为什么下面的代码段可以返回 [（123，abc）] ？

 > parse（many digit）123abc
 [（123，abc）] 
  

解决方案

对于最后一个问题：

 > parse（many digit）123abc
 [（123，abc）] 
  

表示解析已成功，因为答案列表中至少返回了一个结果。 Hutton解析器总是返回一个列表 - 空列表意味着解析失败。

结果（123，abc）表示解析已经找到三个数字123并停在'a'这不是一个数字 - 所以其余的输入是abc。

请注意 many 表示尽可能多而不是一个或多个。

  [（1，23abc）如果它是一个或多个，你会得到这个结果： ，（12，3abc），（123，abc）] 
  

这种行为对于确定性分析并不是很好，但有时可能需要进行自然语言分析。

I am reading Programming In Haskell, in the 8th chapter, the author gives an example of writing parsers. The full source is here: http://www.cs.nott.ac.uk/~gmh/Parsing.lhs I can't understand the following part: many permits zero or more applications of p, whereas many1 requires at least one successful application:

many        ::    Parser a → Parser [a ]
many p      =     many1 p +++ return [ ]
many1       ::    Parser a → Parser [a ]
many1 p     = do v ← p
                 vs ← many p
                 return (v : vs)

How the recursive call happens at

vs <- many p

vs is the result value of many p, but many p called many1 p, all many1 has in its definition is a do notation, and again has result value v, and vs, when does the recursive call return? Why does the following snippet can return [("123","abc")] ?

> parse (many digit) "123abc"
[("123", "abc")]

解决方案

For the last question:

> parse (many digit) "123abc"
[("123", "abc")]

Means that parsing has been successful as at least one result has been returned in the answer list. Hutton parsers always return a list - the empty list means parsing failure.

The result ("123", "abc") means that parsing has found three digits "123" and stopped at 'a' which is not a digit - so the "rest of the input" is "abc".

Note that many means "as many as possibly" not "one or more". If it were "one or more" you'd get this result instead:

[("1", "23abc"), ("12", "3abc"), ("123", "abc")]

This behaviour wouldn't be very good for deterministic parsing, though it might sometimes be needed for natural language parsing.

这篇关于无法理解相互递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！