程式設計師雜談

  • 發行項

剖析器組合器

Ted Neward

Multiparadigmatic 系列的結論，似乎時間去闖到新的地面。命運得很，不過，一些用戶端工作最近離開我的有趣的材料負有的討論，涉及到軟體的設計，作為另一個例子的通用性/變異性分析為核心的 multiparadigmatic 系列，和 … … 嗯，最終，它是真的很酷。

問題

我有用戶端是光神經科學世界的脖子深又問我和他一起工作的一個新的專案，旨在方便做實驗對光學組織。具體來說，我正在控制 rig 顯微鏡，它將推動各種刺激設備 （指示燈、 燈等等），將觸發回應從光學組織，然後捕獲結果測定看光學組織的硬體軟體系統。

如果這一切隱約聽矩陣-y 給你，你不是完全孤獨的。當我第一次聽說這個專案，我的反應是同時，"哦，哇，真酷 ！"，"哦，等等，我只是吐了我嘴裡有點。"

無論如何，對鑽井平臺的關鍵內容之一是，它將有相當複雜的配置與運行，每個實驗關聯和導致我們仔細考慮如何指定該配置。一方面，它似乎明顯的問題，為 XML 檔。但是，平臺運營的人們不會去是電腦程式員，而是科學家和實驗室助理，所以似乎有點嚴厲期望他們寫格式正確的 XML 檔 （和每次都得到正確）。思想的產生某種形式的基於 GUI 的配置系統達成我們作為高度 over-engineered，特別是因為它會很快變成討論如何最有效地捕獲的資料的類型不限成員名額。

最後，似乎更合適，給他們一種自訂配置格式，這意味著噸分析我的部分文本。（對某些人來說，這意味著我建築的 DSL ； 這是最好的一場辯論左哲學家和酒精消費嚴重任務中涉及的其他）。幸運的是，解決方案比比皆是，在這一領域。

思想

解析器是有趣且有用的兩個目的： 將文本轉換為一些其他的、 更有意義的形式，並驗證/驗證文本遵循一定的結構 （這通常是把它轉換成一種更有意義的形式説明的一部分）。例如，一個電話號碼，這只是一個數位序列的核心是，所以，仍有需要驗證，它的結構。這種格式差異從大陸到大陸，但這些數位仍然是數位。事實上，電話號碼是"更有意義的形式"並不是一個整數值的情況的一個偉大的例子 — — 數位並不是一個整數值，它們通常是更好地代表作為一種欄位型別的符號表示。（視其為"只是"數量很難提取的國家/地區代碼或地區代碼，例如。）

如果一個電話號碼組成的數位，所以，數位 (薪俸，雇員 Id 等等），然後那裡將會在代碼中，我們分析和驗證數位，一些重複，除非我們某種程度上擴展瞭解析器。然後，這意味著，我們希望無論我們建立不限成員名額，要讓一個人來擴展它以不同的方式 （加拿大郵遞區號，例如） 而無需修改源本身中使用解析器/庫的解析器。這被稱為"打開關閉原則"： 軟體實體應該對擴展開放，但對修改關閉。

解決方案： 生成元程式設計

一種解決方案是傳統"lex/yacc"的做法，已知更正式的"解析器發電機"。這種抽象的格式指定設定檔的語法 — — 通常一些變化對巴科斯范式形成 (BNF) 語法/語法用於描述形式的語法，如什麼大多數程式設計語言的使用 — — 然後運行生成代碼以拆分字串輸入並因此產生某種結構或物件樹的一個工具。一般情況下，此所涉及的過程分為兩個步驟，"詞法分析"和"解析，"在其中詞法分析器首先轉換輸入的字串標記，驗證字元做事實上形成合法的權杖，一路走來。然後解析器標記並驗證權杖適當的順序出現，並且包含相應的值，，等等，通常將標記類轉換為一些抽象的樹狀結構進行進一步的分析。

解析器發電機的問題是相同的任何生成的元程式設計方法： 生成的代碼將需要重新生成事件中語法更改。但更重要的是這種情況下，生成的代碼將生成電腦，所有精彩變數命名隨電腦生成的代碼 （有人準備站起來的變數如"integer431"和"string$ $x$ y$ z"？），因此很難調試。

解決方案： 功能

在某一種光，解析是從根本上功能： 它需要輸入、 執行某種操作上和生成輸出結果。關鍵的洞察力，事實證明，是一個解析器可以創建出的很多小的解析器，每個解析一點點的字串輸入，然後返回一個標記和另一個函數解析字串輸入下的一點。這些技術，我相信這在 Haskell 引入的稱為 combinators 解析器，正式和他們變成"中型"解析問題優雅的解決方案 — — 解析器不一定一樣複雜，需要一種程式設計語言，但一些超出 String.Split （或駭客攻擊了一連串的 regex 掃描） 能做些什麼。

在解析器 combinators 的情況下打開的擴展要求被通過創建小的函數，然後使用功能的方法"組合"成為更大的功能 （這是我們在那裡名稱"combinators"）。大解析器可以由任何人都有足夠的技能，瞭解函陣列合組成。這項技術是一般一個需要探索，但我會保存，為未來的列。

事實證明，有幾個解析器組合庫供 Microsoft。NET 框架，很多基於寫在 Haskell 這種設置解析器的標準組合庫模組秒差距。這兩個庫是 FParsec，為 F # 和語言，寫 C# 編寫的。每一個是開源和相對較詳細的記錄，這樣，他們有兩個目的的都有用出框中，作為一個模式，從中學習設計思想。我還將去 FParsec 以後的專欄。

"解析"的語言詩嗎？

語言，可在 code.google.com/p/sprache，自稱為"簡單、 輕型庫構建直接在 C# 代碼中，解析器"的"不和工業實力' 語言工作臺上競爭。它適合某個規則運算式和一個全功能的工具集如 ANTLR 之間。"（ANTLR 是一個解析器發電機，擬合到生成元程式設計的類別，如 lex/yacc）。

入門語言很簡單： 下載的代碼、 生成專案，然後將 Sprache.dll 程式集複製到您的專案依賴專案錄添加到專案的引用。從這裡，解析器定義工作聲明 Sprache.Parser 實例，然後將它們合併以特定的方式創建 Sprache.Parser 實例，所做的一切，反過來可能，如果需要 （和通常是），返回包含部分或所有的已解析的值的域物件。

簡單的語言

若要首先，讓我們從解析器，它知道如何解析為一個電話號碼欄位型別的使用者輸入電話號碼。為簡單起見，我永遠堅持 format—(nnn) nnn nnnn 美式 — — 但我們想專門識別故障區號、 首碼和行，並允許字母數位的位置 （因此有人可以輸入自己的電話號碼作為"(800) 吃堅果"，如果他們不希望)。理想情況下，電話號碼欄位型別將 alpha 和需求，全數位形式之間轉換但這功能將作為練習留給讀者 （意味著，基本上，我不想打擾它）。

(指出只需將所有字母轉換為數字方式不完全相容的解決方案，要求我墨守成規的人。在大學，正是共同在嘗試來闡明"酷"的電話號碼的朋友圈 — — 一個前室友仍在等待 1-800-CTHULHU 成為免費的事實上，所以他可以贏得這場比賽，永遠在一起。)

最簡單的開始位置是與電話號碼欄位型別：

class PhoneNumber
{
  public string AreaCode { get; set; }
  public string Prefix { get; set; }
  public string Line { get; set; }
}

這是"真正的"欄位型別，區號、 首碼和線將驗證代碼在其屬性設置的方法，但這會造成重複的代碼分析器和域類 （其中，順便說一句，我們會解決之前，這都是） 之間。

接下來，我們需要知道如何創建一個簡單的解析器知道如何解析 n 數位的位數：

public static Parser<string> numberParser =
  Parse.Digit.AtLeastOnce().Text();

定義的 numberParser，這是簡單的。 開始與原始分析器數位 （<T> 解析器實例 類上定義 Sprache.Parse），並介紹我們想要的輸入流中的至少一個數位、 隱式要麼直到輸入流消耗所有數位乾涸或解析器遇到一個非數位字元。 該文本的方法轉換為單個字串為我們消費流的分析結果。

測試這是很容易 — — 它餵食的字串並開始執行：

[TestMethod]
public void ParseANumber()
{
  string result = numberParser.Parse("101");
  Assert.AreEqual("101", result);
}
[TestMethod]
public void FailToParseANumberBecauseItHasTextInIt()
{
  string result = numberParser.TryParse("abc").ToString();
  Assert.IsTrue(result.StartsWith("Parsing failure"));
}

在運行時，該檔存儲"101"成結果。 如果 Parse 方法美聯儲的"abc"的輸入的字串，它將產生異常。 （如果 nonthrowing 的行為是首選，語言也有 TryParse 方法返回一個物件，可以詢問有關成功或失敗的結果物件。）

電話號碼分析情況是有點複雜，雖然 ； 它需要解析只是三或四位數位 — — 不多也不少。 定義一個這種分析器 (三位解析程式) 是有點棘手，但是仍然可行：

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

數位解析器需要的字元，而且，如果它是一個數位，前進到下一個字元。 然後方法所需的功能 （在 lambda 運算式的形式） 執行。 返回的方法收集每個單個字串，正如其名稱所示，將其作為返回值 （請參見圖 1)。

圖 1 解析電話號碼

[TestMethod]
public void ParseJustThreeNumbers()
{
  string result = threeNumberParser.Parse("123");
  Assert.AreEqual("123", result);
}
[TestMethod]
public void ParseJustThreeNumbersOutOfMore()
{
  string result = threeNumberParser.Parse("12345678");
  Assert.AreEqual("123", result);
}
[TestMethod]
public void FailToParseAThreeDigitNumberBecauseItIsTooShort()
{
  var result = threeNumberParser.TryParse("10");
  Assert.IsTrue(result.ToString().StartsWith("Parsing failure"));
}

成功。 到目前為止。 （是的 threeNumberParser 的定義是尷尬 — — 肯定有更好的方式來定義此 ！ 不要害怕： 有，但若要瞭解如何擴展解析器，我們要深入探討語言如何構造的和這就是在這一系列的下一部分的主題。）

但是，現在，我們需要做的是處理左-parens，右-­parens 智勇雙全，和一切轉換為電話號碼物件。 它看起來有點尷尬，與我們的看得很遠，但下一步，如圖所示，在發生了什麼圖 2。

將輸入轉換成一個電話號碼物件圖 2

public static Parser<string> fourNumberParser =
  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())))));
public static Parser<string> areaCodeParser =
  (from number in threeNumberParser
  select number).
XOr(
  from lparens in Parse.Char('(')
  from number in threeNumberParser
  from rparens in Parse.Char(')')
  select number);
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});
Using the parser becomes pretty straightforward at this point:
[TestMethod]
public void ParseAFullPhoneNumberWithSomeWhitespace()
{
  var result = phoneParser.Parse("(425) 647-4526");
  Assert.AreEqual("425", result.AreaCode);
  Assert.AreEqual("647", result.Prefix);
  Assert.AreEqual("4526", result.Line);
}

最重要的是，解析器是完全可擴展的因為它，也可以組合成更大的解析器將文本輸入轉換為位址的物件或 ContactInfo 物件或任何其他可以想像。

組合數學概念

從歷史上看，解析文本已"語言研究人員"和學術界，生成的元程式設計解決方案所固有的複雜和困難編輯生成的編譯-測試-調試週期要歸功於省。 試圖通過電腦-行走­生成的代碼 — — 特別是基於有限狀態機版本的許多解析器發電機推出 — — 在調試器中是一項挑戰，即使是最頑強的開發人員。 為此原因，大多數開發人員認為有關沿解析行時提出了一個基於文本的問題的解決方案。 而且，事實上，大部分時間，分析器基於發電機的解決方案是激烈大材小用。

解析器 combinators 作為一個很好的中間解決方案： 具有足夠的靈活性和強大到足以處理一些非平凡解析，而無需博士 瞭解如何使用它們的電腦科學。 更有趣的是，組合數學的概念是一個有趣的問題，並導致一些其他有趣想法，稍後我們將探討其中的一些。

在此列出生的精神，使確保將"眼"我的下一篇專欄 （對不起，忍不住），其中我會擴展語言是觸摸，以減少在這裡定義的三、 四位數位解析器的醜惡。

編碼愉快 ！

Ted Neward Neudesic LLC 建築顧問。 他已寫了一百多篇和編著或合著了十幾本書，包括"專業 F # 2.0"（Wrox，2010年）。 他是 C# MVP，在世界各地的會議上發言。 他諮詢、 定期指導 — — 達到他在 ted@tedneward.com 或 Ted.Neward@neudesic.com 如果你有興趣，讓他來和你的團隊，工作或閱讀他的博客，在 blogs.tedneward.com。

多虧了以下技術專家審查這篇文章： 盧克胡