工作的程式師

2015-07-24

建置組合器

我 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

共用方式為