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

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

作業プログラマ

結合子を作成する (機械翻訳)

Ted Neward 12 月のコラム (msdn.microsoft.com/magazine/hh580742)、パーサーについて、小さいより大きい関数と順番にさらに大きな機能、以外の些細なテキストファイルやストリームの解析に適した関数を解析を組み合わせることによって作成されるテキストパーサーを見て。これは、興味深い技術と、1 つは、いくつかのコア機能概念の構築し、それについてより深く探求に値する。

以前のコラムの読者はリコールが、パーサーは、米国スタイルの電話番号を処理するために構築、実装ビット… と言って… 風変わりな場所。特に、3 と 4 桁の組み合わせを解析するための構文-まあ、正直に言うと、それに 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 });

PhoneNumber 型はかなり推測です。 図 1 threeNumberParser とは、具体的には、どのような」のすべての恵みと、プロのサッカーの守備 clunk」ラインマンのバレエはステージの最初の時間をしようとして油アヒル脂肪を 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())))));

これは、ほとんどはこれらのページ内を伝えることを期待インスピレーションのコーディングします。これらを構築するには、それを説明するよりエレガントな方法は、我々パーサーについてのしくみには少し深くダイブする必要があります。そして、今月のコラムのテーマです。重要なだけでなく、我々よりエレガントな方法をあなたの心に、パーサーを構築する必要がありますが彼らのしくみを説明する一般的なテクニックを助けるので、このような何かが将来作成方法可能性があります。

関数から関数に

パーサーについてについてを実現するために、重要なポイントは、パーサーは本当に「ちょうど」、関数です。関数テキストを解析し、文字し、何か他に変換可能性があります。何が何か判明もちろん、人まで、パーサを実装するは。それ、抽象構文ツリー (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);

今、私たちにいくつかのテキストを解析する方法を知っている小さなパーサーのシリーズを書いて想像することができます便利な <int>、ParseFn などの他のタイプは、文字列を受け取り、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> を使用してリファクタリングの悲鳴します。さらにもっと根本的なパーサーを作成するには入力が、私達ここに試みることはありませんを最適化。

この実装整数と 1 つの単語などのささいなことを解析するために素晴らしいですが、これまでのところはあまり改善のように、以前のバージョンでいないようです。これは機能し関数を返す関数を作成することによって機能を組み合わせることができるためにただしより強力です。これらは高階関数と呼ばれます。理論は、この資料の範囲外ですが、この特定のケースでを適用する方法を表示されていません。 2 つのパーサー機能を取るし、それらをブール「と」で結合する方法を知っている機能を作成するときの出発点であると」または「方法。

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

読みやすく最終的には、理論上は「parserA.OR(parserB)」は、ParseFn の拡張メソッドデリゲートを「挿入辞」または「流暢なインターフェイス"スタイルコーディングのを許可する型には、を読み取り提供これらの両方はより「OR(parserA, parserB)。」

Linq から関数

我々がこの一連の小さな例を残す前に、1 つのステップといきましょうで示すように 3 つのメソッドを作成図 3、本質的には与えるだろうパーサー LINQ には、(これは言語の機能と同様の) コードを記述する場合、ユニークな体験を提供するためにフックする機能。構文と LINQ のライブラリで、近くの同期では、LINQ の構文 (」からのバー foo 選択 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 式を解析するに必要な方法を提供します。

（再）ここでパーサー $o ライブラリ設計の行使を通過しない; ルークホーバンとブライアン・マクナマラの両方ある優れたブログの記事は、件名に (bit.ly/ctWfU0 と bit.ly/f2geNy、それぞれ）は、私を指摘する必要があります、に対しては、このコラムの書か標準として提供します。問題を解決する、以前の 3 と 4 桁のパーサーの電話番号解析のコアを提供するためのみこれらのパーサーのパーサー $o ライブラリ言語のような構築は、メカニズムを説明したいと思います。一言で言えば、我々は正確に 3 つの数字を読み取るパーサーは 1 つ $o と別の 4 桁を読み取る必要があります。

Specifice

問題が正確に 3 桁と正確に 4 桁の数字を読むことを考えると、それはまさにその数文字の入力ストリームからの読み取りは機能することを理由に立っています。言語ライブラリは私たち $o の種を与えない — あること-種-の-文字のうち、実行まで、どんな種類-の-文字の繰り返しシーケンスを読む $o が、「0-多」(したがってその名多く) プロダクションルールいない特定の文字数のルール、としたがって役に立たない。定義を検索することができます面白いと洞察力に富んだ、しかし、 図 4 を示しています。

図 4 の定義の多く $o

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

ほとんどの開発者にとっては、このメソッド（と、確かに、全体の言語ライブラリ) の最大の難所この関数からの戻り値は関数です — ラムダメソッド (常に、パーサー <> 具体的には、いくつかのフォームを覚えている) は、文字列を受け取り、IEnumerable <T> を返すその結果構造; 実際のパーサーの肉は内部関数は、今後、実行されることを意味返さ埋葬されています。これは単に T を返すことから、長い道のりです！

関数の残りの部分、風変わりで配られた後は、かなりはっきりしている：強制的、我々を介してステップし、渡されたパーサー <T> を呼び出す各「何」; を解析するにはパーサーが正常に戻ります限り、我々維持ループ解析の結果の一覧に <T> 追加すべてが完了すると、返されるを取得します。特定のパーサー <T> my 拡張を今のところ、本質的に 2 回を呼び出すよ、ライブラリ用のテンプレートとしてこの機能を実行 2 回 (、いずれかの失敗を解析する場合は、エラーを降伏）で示すように図 5。

図 5、2 回の機能

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

命令文のちょうど 2 つのセットに、ループの 2 解きの間隔でこのコードを書き込み、覚えやすいが、実際には、2 回特に私たちが探しているものないです。私たち 3 倍と Quadrice、必要があり、それらは特別な場合のバージョン 2 回、「3」と私たちを解析する回数を受け取り、1 つのメソッドに抽出することができます音コードは、「2」の代わりに「4」です。我々が特定の回数を解析しているため「Specifice、」このメソッドを呼び出して選択 (を参照してください図 6).

図 6 Specifice メソッド

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

したがって、我々今まさに「ct」数解析 (文字数字、どんな種類のパーサー <T> を解析する言語を拡張している私たちに渡す)、ユビキタスの固定長レコードのテキストを別名、フラットファイルなどの固定長解析のシナリオで使用する言語を開きます。

ファンクショナル・アプローチ

言語パーサーライブラリ解析プロジェクトの正規表現には複雑すぎるが、中堅のあり、本格的なパーサージェネレーター (など ANTLR yacc ・ lex) やり過ぎ。パーサーエラーを理解するは難しいことができますエラーメッセージを生成、完璧ではないですが、初期の複雑さを得たら、言語、開発者用ツールボックスに便利なツールをすることができます。

それ以上に、しかし、言語、電源とは別のアプローチよりも私たちを使用しているプログラミングによって提供される機能のいくつか示します-この場合は、機能の世界から。誰かがあなたを求める次の時間、「どのような良い来るそれらジョブを使用するつもりはない場合、他の言語について学習から？」が、簡単な応答。「言語を直接使用していない場合でもそれは技術やアイデアを使用することができます教えることができます。」

しかし、今のところは。来月、私たち何か全く別の刺し傷を取るでしょう。あるだけので、多くの概念と理論言語コラムニストの観客が一度に取ることができます。

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

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

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