[アーティクル]
08/19/2015

この記事は機械翻訳されたものです。

作業プログラマ

パーサー結合子 (機械翻訳)

Ted Neward Multiparadigmatic シリーズの結論では、それは新しい地面にベンチャー企業を時間だった。運命それがあるように、ただし、いくつかのクライアントの仕事最近左私、議論のクマ、ソフトウェアの設計に関連して、共通・心拍変動解析、multiparadigmatic シリーズの中核の別の例として興味深いが…、最後に、それは本当にクールなも。

問題

私がクライアントの首の深い神経光科学の世界で寄せられるある私彼と導電性実験光の組織を容易に新しいプロジェクトの作業に。具体的には、私は、光の組織からの応答をトリガーし、光の組織を見てハードウェアによる測定の結果をキャプチャさまざまな刺激デバイス (Led ライトなど) をドライブする顕微鏡装置を制御するソフトウェアシステムに取り組んでいます。

すべて漠然とマトリックス-y をね、完全にだけではないです。ときに私は最初にこのプロジェクトについては、私の反応を聞いて同時に、ああ、うわー、クールだ！」と、「ああ、待って、私はちょうど私口の中で少し投げた。」

任意のレートでは、重要なものについては、装置の 1 つは、各実験の実行と関連付けられている、かなり複雑な構成を導いてその構成を指定する方法を熟考します。 1 つの手で、それを XML ファイルに明らかな問題点に見えた。ただし、リグを実行している人整形式の XML ファイルの書き込み (および毎ターンでは権利を取得するには）それらを期待しては少し重いようコンピュータープログラマー、しかしむしろ科学者や研究室助手、するつもりではないです。特に、すぐにオープンの種類のデータをキャプチャする最善の方法の議論になるといくつかの種類の GUI ベースの構成システムの生産を考えて私たちとして非常に over-engineered、三振。

最後に、それらを私の一部のテキストを解析のトンを意味するカスタム構成フォーマットをより適切なように見えた。 (いくつか、この私は DSL の建物ですがほのめかすだろう; この最高の議論左哲学者にあり、他アルコール消費の深刻なタスクに関与。幸いにも、ソリューションはこのスペースで富みます。

思考

パーサー 2 つ興味深く、有用な目的が: テキストをいくつか他より意味のある形式に変換して、テキストを確認・検証に依存 (は通常それより意味のある形式に変換する手助けの一部) は、特定の構造。したがって、たとえば、その中心に一連番号は、電話番号、検証を必要とする構造体が。大陸から大陸へ、その形式は異なりますが、番号は番号。実際には、電話番号より意味のあるフォームを」の整数値ではない場合の素晴らしい例です-整数値は数字ではない、彼らは通常より、ドメインの種類として表される象徴的な表現をしています。（彼ら」「数として扱うはたとえば国コードまたは地域コードを抽出するに困難です。)

電話番号の構成番号 (給与、従業員 Id など)、桁、そうだ場合が起こっている私たちが何とかパーサーを拡張しない限りここで解析し、数字を確認コード内のいくつかの重複します。これは、その後、我々は無制限であると誰かそれを拡張するさまざまな方法 (カナダ郵便、たとえば) でソース自体を修正せずに、パーサー・ライブラリを使用できるように構築どんなパーサーを希望を意味します。これは、「開閉原理として」知られている: ソフトウェアエンティティ拡張をオープンする必要ありますが変更に対して閉じています。

解決方法: 生殖メタプログラミング

伝統的な「レックス・ yacc」アプローチは、より正式には「パーサージェネレーター」として知られている 1 つのソリューションであるこれは、構成ファイルの構文は、抽象の形式で指定する必要があります — 通常いくつかのバリエーションのバッカスナウア (記法 BNF) 構文・文法何ほとんどのプログラミング言語を使用してなどの正式な文法を記述するために使用をフォーム — 文字列入力をバラバラにし結果としていくつかの種類の構造体またはオブジェクトのツリーを生成するコードを生成するためのツールを実行し、。一般的に、この複雑な処理されたと、「字句解析」、「解析」の 2 つの手順は、する字句解析器最初入力文字列トークンには、文字、途中の合法的なトークン実際はことを検証する変換しますに分割されます。パーサーのトークンを取得し、トークンを適切な順序で表示されているし、適切な値が含まれているし、通常、トークンにいくつかの種類の変換抽象さらなる分析のためのツリー構造を検証します。

パーサーの発電機の問題は、生殖のメタプログラミングのアプローチは: 生成されたコードをイベントの構文の変更を再生成する必要があります。しかし、もっと重要なことのこのようなシナリオ、生成されたコードすべてが素晴らしい変数はコンピューターによって生成されたコードを (誰「integer431」と「文字列$ $$ y$ z x」など変数ために立ち上がること準備ができて？）命名とコンピューターが生成されるためデバッグが困難。

解決方法: 機能

ある種の光で、解析が根本的に機能している：いくつかの種類の操作を実行する入力を受け取り、出力結果として。重要な洞察力で、それが判明、少しパーサー、それぞれの小さなビットの文字列入力を解析し、トークンと、次の少しの入力文字列を解析する別の関数を返しますのたくさんのパーサーを作成できることです。私は Haskell で導入されたと信じて、これらのテクニックは、正式にパーサーについてとして知られている、彼らはエレガントなソリューション「中堅」問題を解析することが判明-プログラミング言語が必要となるように、必ずしも複雑ではないパーサーが、何かを超えて何 String.Split (ハッキングを一連の正規表現のスキャン) を行うことができます。

パーサーについての場合は、小さな機能を作成し、機能の技術」（これは我々名」について「どこで）大きい関数にまとめて」を開く拡張要件によって実現されます。大きいパーサー機能構成を理解するための十分なスキルとのだれでもによって構成できます。この手法は、探査、クマは一般的なものが、私は、今後のコラムに保存されます。

それには、いくつかパーサー $o ライブラリが、Microsoft の利用可能です。ネットフレームワークは、多くのそれらの組合せライブラリパーサーの標準を設定 Haskell で書かれたパーセクモジュールに基づいてです。などの 2 つのライブラリ FParsec の F c# 言語、c# で書かれて書かれています。オープンソースですと比較的よくとり上げられる、彼らの両方はデュアル役に立つ、モデルデザインのアイデアを検討して、ボックスの目的は。私はまた、今後のコラムの FParsec を残しておきます。

「言語解析 Sie ですか？」

言語で利用可能な code.google.com/p/sprache、」」「産業強さ」言語ワークベンチと競合しません直接 c# コードでは、パーサーを構築する単純で軽量なライブラリ」としての地位を説明。それどこかの間に正規表現と完全に呼び物のツールセット ANTLR などに。（ANTLR パーサージェネレーター、yacc ・ lex のような生殖メタプログラミングのカテゴリーに継手です。

言語をはじめに簡単です：コードをダウンロード、プロジェクトをビルドし、Sprache.dll アセンブリをプロジェクトの依存関係のディレクトリにコピーし、プロジェクトへの参照を追加します。ここから、すべてのパーサー定義です仕事で Sprache.Parser のインスタンスを宣言し、Sprache.Parser のインスタンスを作成する特定の方法で結合は順番に、必要な場合があります (、通常は)、パースされた値の一部またはすべてが含まれているドメインオブジェクトを返します。

言語の単純な

開始するには、ユーザーが入力した電話番号を PhoneNumber ドメイン型に解析する方法を知っているパーサーを始めましょう。わかりやすくするため、私は、米国スタイル format—(nnn) の nnn nnnn で付く — が私達が特にエリアコード、プレフィックスと線の故障を認識し、(彼らが望めば誰か自分の電話番号」(800) 食べるナッツとして「入力できます) 数字代わり文字を許可します。理想的には、機能、練習としてリーダー（それを気にしたいのですが。つまり、本質的に、) に残りますが、PhoneNumber ドメイン型アルファとオンデマンドでは、すべての数値形式に変換されます。

(単にすべてのアルファ値に変換、完全準拠のソリューションは、方法でないことを指摘する私の利かない人を要求します。大学では、それは「冷却する」ことを綴り電話番号を思い付くしようとする友人の私のサークルで共通だった — 1 つの元ルームメイトはまだ待って 1-800-実際自由 CTHULHU のため彼はすべての永遠のためのゲームを勝つことができるようにします)。

開始する最も簡単な場所と PhoneNumber ドメインの種類です。

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 クラスに定義されている)、私たち少なくとも 1 桁、入力ストリームで、暗黙的にすべての桁まで入力ストリームか消費する乾燥を実行または、パーサー、数字以外の文字を検出するを説明します。テキスト法解析結果のストリーム私たちの消費の 1 つの文字列に変換します。

このテストはかなり簡単です — 文字列フィードし、てください。

[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」の給紙する場合は、それは例外が発生します。 (仮動作を優先する場合は、言語も、成功または失敗に関する尋問することができます、結果のオブジェクトを返します、TryParse メソッドがあります。)

電話番号解析状況も、もう少し複雑です。それは 3 つまたは 4 つの数字を解析する必要がある-ないよりは少ない。このようなパーサーは 1 つ (3 桁パーサー) を定義する少しトリッキーだが、それでもなんとか。

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()))));

数値のパーサーは文字を取るしが数字の場合、次の文字に進みます。メソッドでは、関数 (ラムダ式の形式) で実行するのにかかるし、。戻りのメソッドそれぞれの 1 つの文字列に収集、その名のとおり、戻り値としてを使用 (を参照してください図 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 の定義がぎこちないです — 確かにこれを定義するのには良い方法する必要があります！恐れることはない：がパーサーを拡張する方法を理解するには、我々言語の構築に、深いダイビングをしてあり、このシリーズの次の部分の対象となります)。

今、ただし、我々を処理する必要があります、左括弧、右 -括弧、ダッシュとすべてを PhoneNumber オブジェクトに変換します。私たちはこれまでを参照してくださいが次に示すように何が起こるかを見るには少し厄介なようであるかもしれない図 2。

図 2 の入力を PhoneNumber オブジェクトに変換します。

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 オブジェクトまたは何か他の想像に変換、拡大パーサーに構成できるため、パーサーは完全に拡張可能です。

組み合わせ論の概念

歴史的に、解析本文「言語研究者」と学界主に複雑で困難な編集を生成-コンパイル-テスト-デバッグサイクル生成のメタプログラミングソリューションに固有のされています。コンピューター - を散歩しようコード生成 — 多くのパーサージェネレーター撹特に有限状態マシンベースバージョン — デバッガーでも、最も百戦錬磨の開発者への挑戦です。そのため、ほとんどの開発者はに沿ってテキスト・ベースの問題を提示するときの線の解析ソリューションについてとは思わない。そして、真実では、ほとんどの場合、パーサージェネレーター-ベースのソリューション抜本的なやり過ぎでしょう。

パーサーについてはいい中間のソリューションとして提供：柔軟性と強力な十分ないくつか重要な博士号を取得せず解析処理コンピュータサイエンスがそれらを使用する方法を理解するのには。さらに興味深いことには、組み合わせ論の概念を魅力的なものし、いくつかの後で私達を探検するいくつか他の興味深いアイデアに。

この列で誕生した、精神で、作る私の次のコラムの「目」を維持することを確認 (申し訳ありません、には言語だけでタッチをここで定義された 3 と 4 桁のパーサーの醜さを減らすために、拡張抵抗できませんでした).

コーディングを楽しんで！

Ted Neward Neudesic LLC、建築コンサルタントです。彼が 100 以上の記事を書いて作成や「プロ F c# 2.0」など、十数本を共著 (Wrox、2010）。彼は c# MVP であり、世界中のカンファレンスで話します。彼は相談し、定期的にメンター — 彼に到達 ted@tedneward.com または Ted.Neward@neudesic.com 、彼の仕事をチームには、または彼のブログで読むに興味を持っている場合 blogs.tedneward.com。

この記事のレビュー、技術スタッフのおかげでに： Luke Hoban