工作的程序员

项目
07/13/2015

构建组合子

Ted Neward
我 12 月列中 (msdn.microsoft.com/magazine/hh580742），我看了看解析器 combinators，文本解析器创建的结合小、原子解析成更大的功能，和那些转到更大的功能，适用于解析非普通文字文件和流的功能。这是有趣的技术，其中的一些核心的功能概念的基础上，它值得深入探讨。

较早前专栏的读者会记得我们建造解析器处理工作，美式电话号码，但执行是有点 … … 我们应当说 … … 古怪的地方。特别是语法解析三和四位数字的组合 — 它 clunked，老实说，嗯。它的工作，但它是几乎不漂亮，优雅，或以任何方式可扩展性。

作为复修，电话号码解析代码如下：

public static Parser<PhoneNumber> phoneParser =
  (from areaCode in areaCodeParser
   from _1 in Parse.WhiteSpace.Many().Text()
   from prefix in threeNumberParser
   from _2 in (Parse.WhiteSpace.Many().Text()).
Or(Parse.Char('-').Many())
   from line in fourNumberParser
   select new PhoneNumber() { AreaCode=areaCode, Prefix=prefix, Line=line });

电话号码类型是相当猜出。 图 1 显示的 threeNumberParser 和 fourNumberParser，是，尤其是什么"哐"所有的慈悲与临足球防守的投手尝试第一次在舞台上芭蕾鸭油油脂润滑。

图 1 笨重的解析器

public static Parser<string> threeNumParser =
  Parse.Numeric.Then(first =>
    Parse.Numeric.Then(second =>
      Parse.Numeric.Then(third =>
        Parse.Return("" + first.ToString() +
          second.ToString() + third.ToString()))));
public static Parser<string> fourNumParser =
  Parse.Numeric.Then(first =>
    Parse.Numeric.Then(second =>
      Parse.Numeric.Then(third =>
        Parse.Numeric.Then(fourth =>
          Parse.Return("" + first.ToString() +
            second.ToString() + third.ToString() +
            fourth.ToString())))));

这是很难种灵感，希望在这些网页中传达的编码实践。有一种更优雅的方法来构造这些，但要把它描述，我们需要深入有点 combinators 解析器是如何工作的。而这正是本月专栏的主题。不只是因为我们需要一种更优雅的方式来构造解析器，你要注意，而是因为一般技术可帮助说明它们是如何工作的也是更重要的您如何可能构建这样的事，将来。

从函数的函数

解析器 combinators 关于实现重要的一点是解析器是真的"只"功能：函数分析文本，然后可能转变成别的东西的字符。这东西所证明的是，当然，达人实施解析器。可能是抽象语法树 (AST) 进行验证和验证文本的传递中（和以后转换成可执行代码或者直接，解释为在某些语言中），也有可能是一个简单的域对象或甚至只是插入到现有的类，像一个字典的名称-值对的值。

在代码中的发言，然后，解析器如下所示：

T Parse<T>(string input);

换句话说，解析器是泛型函数，以字符串，并返回一个实例的东西。

简单，那就是，不过，它并不完全准确。是的我们就会的总和，回到写一个完整的解析器，每个函数，并不真正可供重复使用的方式有很多。但如果我们看看解析为一系列的功能 — 换句话说，解析器组成的一群小小的解析器，每个知道如何解析只是一块的输入和返回生成的对象只是一块 — 很明显我们需要返回不仅将生成的对象，还需要分析的其余文本。与"T"从以前的声明已作出稍微复杂的包中包含"T"和一个字符串，其余都"解析器结果"类型的手段分析文本，就像这样：

public class ParseResult<T>
{
  public readonly T Result;
  public readonly string Rest;
  public ParseResult(T r, string i) { this.Result = r; this.Rest = i; }
}

鉴于 C# 自然管理职能委托类型和实例，现在宣布分析器变成一个委托声明：

public delegate ParseResult<T> ParseFn<T>(string input);

现在，我们可以想象编写一系列的小的解析器，知道如何分析文本到一些有用其它类型例如，ParseFn <int> 它采用一个字符串并返回 int （请参见图 2），或 ParseFn <string> 解析到第一个空格字符，等等。

图 2 分析的字符串并返回 Int

ParseFn<int> parseInt = delegate(string str)
{
  // Peel off just numbers
  int numCount = 0;
  foreach (char ch in str)
  {
    if (Char.IsDigit(ch))
      numCount++;
    else
      break;
  }
  // If the string contains no numbers, bail
  if (numCount == 0)
    return null;
  else
  {
    string toBeParsed = str.Substring(0, numCount);
    return new ParseResult<int>(
      Int32.Parse(toBeParsed), str.Substring(numCount));
   }
};
Assert.AreEqual(12, parseInt("12").Result);

请注意这里分析器执行实际上是一个相当可重复：要编写一个解析器解析到一个空白字符的文本，所有你想要做是更改 IsDigit IsLetter 调用调用。这用于使用 <T> 的谓语的重构中尖叫键入要创建一个更基本的解析器，但这就是我们在这里不会尝试优化。

此实现是伟大解析如整数和单个的词，小事，但到目前为止它不像太多的改进在较早版本。这是功能更强大，不过，因为您可以通过创建函数并返回函数函数，组合功能。这些称为高阶函数；虽然理论是超出了本文的范围，显示它们如何应用在此个案中加入。起点是当您创建函数，知道如何采取两个解析器函数，并将它们组合在布尔"与"和"或"时尚：

public static class ParseFnExtensions
{
  public static ParseFn<T> OR<T>(this ParseFn<T> parser1, ParseFn<T> parser2)
  {
    return input => parser1(input) ??
parser2(input);
  }
  public static ParseFn<T2> AND<T1, T2>(this ParseFn<T1> p1, ParseFn<T2> p2)
  {
    return input => p2(p1(input).Rest);
  }
}

这两个前提，对 ParseFn 的扩展方法委托类型，以便"缀"或"流利界面"样式的编码，以使其更具可读性结束，理论上，"parserA.OR(parserB)"读取比"OR(parserA, parserB)。"

从 LINQ 的职能

我们离开这套小例子之前，让我们采取一步，创建三种方法，如图所示，在图 3，这本质上是将给分析器挂接到 LINQ，提供独特的经验，编写的代码（这是语言的特征以及之一）时的能力。 LINQ 库和语法是中，彼此紧密同步的 LINQ 语法（"从美孚在栏选择 quux q … …"）紧密相连的几种方法签名是出席并可供使用的期望。具体来说，如果某个类提供选择中，SelectMany 和凡与他们可以使用的方法，然后 LINQ 语法。

图 3 的位置，请选择和 SelectMany 方法

ParseFn<int> parseInt = delegate(string str)
  {
    // Peel off just numbers
    int numCount = 0;
    foreach (char ch in str)
    {
      if (Char.IsDigit(ch))
        numCount++;
      else
        break;
    }
    // If the string contains no numbers, bail
    if (numCount == 0)
        return null;
    else
    {
      string toBeParsed = str.Substring(0, numCount);
      return new ParseResult<int>(
        Int32.Parse(toBeParsed), str.Substring(numCount));
    }
  };
Assert.AreEqual(12, parseInt("12").Result);
public static class ParseFnExtensions {
  public static ParseFn<T> Where<T>(
    this ParseFn<T> parser,
    Func<T, bool> pred)
  {
    return input => {
      var res = parser(input);
      if (res == null || !pred(res.Result)) return null;
      return res;
     };
  }
  public static ParseFn<T2> Select<T, T2>(
    this ParseFn<T> parser,
    Func<T, T2> selector)
  {
    return input => {
      var res = parser(input);
      if (res == null) return null;
      return new ParseResult<T2>(selector(res.Result),res.Rest);
     };
  }
  public static ParseFn<T2> SelectMany<T, TIntermediate, T2>(
    this ParseFn<T> parser,
    Func<T, ParseFn<TIntermediate>> selector,
    Func<T, TIntermediate, T2> projector)
  {
    return input => {
      var res = parser(input);
      if (res == null) return null;
      var val = res.Result;
      var res2 = selector(val)(res.Rest);
      if (res2 == null) return null;
      return new ParseResult<T2>(projector(val, res2.Result),res2.Rest);
     };
  }
}

这让 LINQ 解析 LINQ 表达式，如你所看到的在上一篇文章中需要的方法。

我不想去通过行使（重新）在这里；解析器组合库设计卢克胡和布莱恩 · 麦克纳马拉都有优秀的博客文章谈一谈有关 (bit.ly/ctWfU0 和 bit.ly/f2geNy，分别），我必须指出，作为对其编写本专栏的标准。我只想证明的机制的构造解析器的这种语言，像解析器组合库中，因为，提供较早前的三、四位数字电话号码解析器在解析器问题解决方案的核心。简而言之，我们需要一个解析器组合，读取正好为三位，及另一人，读取包含四个位数。

比重、比

既然问题是用于读取正是三位数，正是四位数字，显而易见的原因我们希望从输入流中读取究竟该数目的字符的函数。语言库并没有给我们这样的组合 — 有出这种-的-字符，直到将读什么种-的-字符重复序列的组合，但这就是"零到多"（因此它的名字，许多）生产规则，不是一个特定数目的字符的规则，因此无益。看着它的定义可以是有趣和有见地的但是，作为图 4 显示。

图 4 定义的很多的组合

public static Parser<IEnumerable<T>> Many<T>(this Parser<T> parser)
{
  if (parser == null) throw new ArgumentNullException("parser");
  return i =>
  {
    var remainder = i;
    var result = new List<T>();
    var r = parser(i);
    while (r is ISuccess<T>)
    {
      var s = r as ISuccess<T>;
      if (remainder == s.Remainder)
          break;
      result.Add(s.Result);
      remainder = s.Remainder;
      r = parser(remainder);
    }
    return new Success<IEnumerable<T>>(result, remainder);
  };
}

对于大多数开发人员，此方法（、乃至整个语言库）的最困难部分是来自此函数的返回值是一个函数 — 具体地说，lambda 方法 < （总是解析器 > 某种形式，记住），采用字符串，并返回一个 <T> 其结果的结构；实际解析器的肉埋内返回函数，这意味着它将执行后，不是现在。这是很长的路，只返回 T ！

一旦这怪胎处理，其余是作用的很明显：势在必行，我们单步执行，并要求通过在分析器 <T> 要分析每个"不管"；和只要解析器保持成功返回，我们不断循环，并将解析的结果添加到列表 <T> 当一切都完成时，，获取返回。这我到库中，而你愿意现在，基本上，就会调用两次的分机的模板执行一个给定的解析器 <T> 两次（和产生错误，如果任一解析失败），如图所示，在图 5。

图 5 两次函数

public static Parser<IEnumerable<T>> Twice<T>(this Parser<T> parser)
{
  if (parser == null) throw new ArgumentNullException("parser");
  return i =>
  {
    var remainder = i;
    var result = new List<T>();
    var r = parser(i);
    var c = 0;
    while (c < 2 && r is ISuccess<T>)
    {
      var s = r as ISuccess<T>;
      if (remainder == s.Remainder)
          break;
      result.Add(s.Result);
      remainder = s.Remainder;
      r = parser(remainder);
      c++;
    }
    return new Success<IEnumerable<T>>(result, remainder);
  };
}

事实上，它本来有点容易循环回路的两成命令式语句只是两套编写此代码，请记住，虽然两次加入特别我们要找的。我们需要三次和 Quadrice，和那些与"3"和"4"的"2"在代码中，这听起来好像我们可以将它们提取到一个单独的方法来分析的次数，而不是两次，只是特别种版本。我选择调用此方法的"比重、比，"因为我们解析特定次数（请参见图 6)。

图 6 比重、比方法

public static Parser<IEnumerable<T>> Twice<T>(this Parser<T> parser) {
  return Specifice(parser, 2); }
public static Parser<IEnumerable<T>> Thrice<T>(this Parser<T> parser) {
  return Specifice(parser, 3); }
public static Parser<IEnumerable<T>> Quadrice<T>(this Parser<T> parser) {
  return Specifice(parser, 4);
}
public static Parser<IEnumerable<T>> Quince<T>(this Parser<T> parser) {
  return Specifice(parser, 5);
}
public static Parser<IEnumerable<T>> Specifice<T>(this Parser<T> parser, int ct)
{
  if (parser == null) throw new ArgumentNullException("parser");
  return i =>
  {
    var remainder = i;
    var result = new List<T>();
    var r = parser(i);
    var c = 0;
    while (c < ct && r is ISuccess<T>)
    {
      var s = r as ISuccess<T>;
      if (remainder == s.Remainder)
          break;
      result.Add(s.Result);
      remainder = s.Remainder;
      r = parser(remainder);
      c++;
    }
    return new Success<IEnumerable<T>>(result, remainder);
  };
}

因此，我们现在已扩展到解析完全解析（字符、数字、任何种类的解析器 <T> 的"ct"数字语言我们通过在），其中固定长度的解析方案例如，无处不在的固定长度记录文本的文件，aka 的平面文件中的使用开辟了语言。

一种功能的方法

语言是中型解析的正则表达式是过于复杂的项目，用于解析器库和全面解析器发电机组（例如，ANTLR 或 lex/yacc) 是大材小用。在解析器故障生成错误消息，可能很难理解，是不是完美的但一旦你已经通过最初的复杂，语言可以是您的开发人员工具箱中的一个有用的工具。

更重要的是，虽然，语言演示一些电源和提供不同的方法，比我们所使用的编程能力 — 在这种情况下，从功能世界。因此下, 一次有人问你，"有什么好处来自了解其他语言，如果你不打算使用他们的工作？"有一个简单的响应："即使你并不直接使用一种语言，它可以教你可以使用的技术思想。"

但这就是现在。下个月，我们将一刀在完全不同的东西。因为只有这么多的概念和理论语言专栏作家的观众可以一次。

编码愉快！

Ted Neward 是一名建筑顾问与 Neudesic LLC。他写了一百多篇，是 C# MVP 和 INETA 的扬声器和编写及合著十几本书，包括最近公布"专业 F # 2.0"（Wrox）。他咨询、定期指导。他在到达 ted@tedneward.com 如果你有兴趣，让他来和你的团队，工作或阅读他的博客，在 blogs.tedneward.com。

多亏了以下技术专家审查这篇文章： Nicholas Blumhardt