パーサーコンビネーターを使用したC＃でのDSLの構築

Autofac IoC / DIコンテナの著者である有名な.NET開発者であるNicholas Bloomhardtによる記事の翻訳。 この記事では、Nicholasが実際の例を使用して、パーサーコンビネーターのライブラリであるSpracheを使用して、最小限の労力でサブジェクト指向プログラミング言語のパーサーを作成する方法を示します。


現在のプロジェクトには、ユーザーアカウントを作成するためのアプリケーションを送信および承認するための小さなプロセスが含まれています。 これは、ドメイン固有の言語とSpracheを議論する良い例です。 次に、いくつかの要件について説明します。

ユーザーアカウントの種類のセットは無制限です。 現在は、「従業員」、「請負業者」、「派遣社員」などです。 アカウントを取得するには、ユーザーは適切なフォームに入力する必要があります。

アンケートのデータを収集して保存する場合、関連する情報が管理者に提示されるまで、その内容は重要ではありません。管理者は最終的にアプリケーションを承認または拒否します。


VS2010のソリューションの形式の例へのリンク。

難しさ

多くの点で、システムの設計は、可能なタイプのアカウントのセット（したがって、さまざまなプロファイル）が無制限であるという事実によるものです。 アプリケーションを再デプロイしなくても、新しいプロファイルを作成できるはずです。 さらに、アンケートの構成は、エンドユーザー自身が簡単に変更できる必要があります。

プロファイルを送信するには多くの方法があります。

• アンケートのドメインモデルをリレーショナルデータベーステーブルにマップする
• XMLベースのアンケート形式を作成する
• 一般的なXAMLファイルでWindows Workflow Foundationを使用する
• CSVファイルまたは他のテーブルからプロファイルを読み取る

これらの各メソッドには、実装の容易さ、保守性、利便性、および柔軟性に関連した長所と短所があります。

この記事では、別の魅力的なオプションを検討します。プロファイルを記述するための便利なミニ言語を作成します。

プロファイル記述言語

内部DSLと外部DSLの違いについての議論を読んだことがあるかもしれません。

内部 DSLは汎用言語（C＃など）の専用APIであり、使用すると、問題を解決するプログラムとしてではなく、問題の説明として読まれます。

外部 DSLは、プログラムが動作する前にソースコードから解析する必要がある別個の言語です。 また、これは私たちのタスクにとって特に重要であり、外部DSLは最小限の構文ノイズに寄与し、プログラムを再コンパイルせずに読み取ることができます。

DSLアンケートの例は次のようになります。

identification "Personal Details" [ name "Full Name" department "Department" ] employment "Current Employer" [ name "Your Employer" contact "Contact Number" #months "Total Months Employed" ] 

これは、個人データと雇用の詳細を収集する2段階のアンケートです。

• 各セクションには、独自の識別子、タイトル、質問のリストがあります。
• 各質問には識別子と特定のクエリテキストがあります。
• 質問識別子の宣言（たとえば、＃months）には、収集されるデータのタイプを示す記号からの接頭辞が含まれる場合があります-この場合のポンド記号は自然数を示します。

アプリケーションは、対応する種類のアカウントに関連付けられたアンケートの説明を読み取り、ユーザーに段階的なインターフェイスを提示します。

プロファイルの記述の分析へのアプローチ

解析は、上記のアンケートなどのソース言語のテキストを受け入れ、特定の表現に変換するプロセスです。通常は、プログラムで使用できる何らかのオブジェクトモデルに変換します。 C＃プログラマーには、これを実現する方法がいくつかあります。

手書きパーサー

多くの場合、最も単純なパーサーと最も複雑なパーサーの両方が手動で作成されます。 単純なものは、解決策が明らかな場合に記述されます（たとえば、「ループ内でコンマを検索して行を分割する」）。 最も複雑なパーサーは、プログラマーが異常なレベルの制御（たとえば、C＃コンパイラー）を必要とする場合に作成されます。 もちろん、あなたがこの分野の専門家であり、彼が何をしているかを正確に知っていない限り、手動で何かを解析することは通常、努力する価値はありません（これは間違いなく私についてではありません！

正規表現

これは、テキストからパターンを照合および抽出する便利な方法です。 .NETには、正規表現を効率的に使用するための組み込みSystem.Text.Regexクラスが含まれているため、通常、解析タスクに直面したときに考慮する最初のオプションです。 かなり単純な文法にもかかわらず、正規表現はすぐに読みにくくなり、保守しにくくなります。 これはおそらく最大の欠点です。 さらに、正規表現が解析できない文法が多くあります（ネストを許可するものから開始）。

パーサージェネレーター

パーサージェネレーターである「言語ツールキット」を使用すると、宣言形式で文法を指定できます。 ツールキットには、プロジェクトのビルド中に機能するツールが含まれており、文法を解析できるターゲット言語（C＃など）のクラスを生成します。 このようなツールを使用すると、作業を調査してプロジェクトのアセンブリプロセスに統合するのに時間がかかります。 小さな解析タスクの場合、これは冗長な場合がありますが、非常に複雑な場合や高速の解析速度が必要な場合は、このようなツールを学習して使用することを強くお勧めします。

パーサーコンビネーター

この関数ベースの手法は、HaskellやF＃などの関数型言語でデフォルトで使用されることが多く、どちらも高品質のパーサーコンビネーターライブラリを備えています。 C＃には、謙虚な使用人によって開発され、この記事の後半で使用される若いSpracheコンビナトリアルライブラリもあります。 Spracheを使用すると、急な学習曲線やアセンブリプロセスへの統合なしに、単純なパーサーを非常に簡単に記述および保守できます。 テストを通じて開発プロセスに適しています。 現在の弱点には、パフォーマンスと、場合によってはエラーメッセージの品質が含まれます。小さなDSLを解析する上で大きな問題はありません。 [ 更新：この記事の執筆後、Spracheの解析速度とエラー処理が大幅に改善されました。 ]

はじめに

開始するには、 Sprache.dllをダウンロードしてください 。 この記事は、Visual StudioでNUnitを使用してパーサーを作成およびテストし、テキストを追跡できるように構成されています 。

文法は下から上に構築されます。 パーサーは、識別子、文字列、数値などの低レベルの構文要素用に最初に作成されます。 その後、これらの単純な部分をより複雑な部分に結合し、完全な言語が得られるまで、徐々に高くなります。

ID解析

プロファイルを記述するための言語では、最もネストされた重要な要素は質問です。

 name "Full Name" 

ここでの主要な部分は、識別子と引用符で囲まれたテキストです。 パーサーの最初のタスクは、識別子、この場合は「名前」の解析です。

 [Test] public void AnIdentifierIsASequenceOfCharacters() { var input = "name"; var id = QuestionnaireGrammar.Identifier.Parse(input); Assert.AreEqual("name", id); } 

Spracheパーサーは、文法を表す静的クラスメソッドです。 タイプParser <string>の QuestionnaireGrammar.Identifier 、つまり string型の値を返します。

パーサー定義：

 public static readonly Parser<string> Identifier = Parse.Letter.AtLeastOnce().Text().Token(); 

このコードはかなり読みやすいです。空でない文字列を分析し、テキスト表現を返します。 パーサーの要素は次のとおりです。

Parse.Letter -SparcheのParseクラスには、一般的な解析タスクを実行するためのヘルパーメソッドとプロパティが含まれています。 Letterは、入力から文字を読み取り、それをcharとして返す単純なパーサー<char>パーサーです。 入力シンボルが文字でない場合、このパーサーはそれに一致しません。

AtLeastOnce（） -Spracheを使用して作成されたすべてのパーサーは繰り返しをサポートします。 AtLeastOnce（）は、 T型の1つの要素のパーサーを受け取り、そのような要素のシーケンスを解析する新しいパーサーを返し、 IEnumerable <T>を返します。

Text（） -AtLeastOnce（）修飾子はParser <char>を取得し、 Parser <IEnumerable <char >>型のパーサーに変換します 。 補助関数Text（）は、 Parser <IEnumerable <char >>型のパーサーを受け取り、それをParser <string>に変換して、より便利な作業にします。

トークン（）は、先頭および末尾の空白を受け入れて破棄する修飾子です。

ただ？

識別子パーサーには、さらに興味深いテストがいくつかあります。

 [Test] public void AnIdentifierDoesNotIncludeSpace() { var input = "a b"; var parsed = QuestionnaireGrammar.Identifier.Parse(input); Assert.AreEqual(“a”, parsed); } 

Spracheの各パーサーは、可能な限り多くの入力を解析します。 このテストでは、解析は成功しますが、入力文字列全体を吸収しません。 （後で入力の終了を要求する方法を確認します。）

 [Test] public void AnIdentifierCannotStartWithQuote() { var input = "\"name"; Assert.Throws<ParseException>(() => QuestionnaireGrammar.Identifier.Parse(input)); } 

Parse（）拡張メソッドは、パーサーが適切でない場合、 ParseExceptionをスローします。 また、非スローのTryParse（）を使用することもできます。

正しく解析された識別子に満足したら、次に進みます。

引用テキストの解析

引用テキストの解析は、識別子の解析よりもはるかに難しくありません-単純なバージョンでは、エスケープ文字や複雑なものはサポートされていません。

入力行をもう一度見てみましょう。

 name "Full Name" 

引用符で囲まれたテキストを解析するには、一致する必要があります：

1. 引用符を開く
2. 他の引用符を除くすべて
3. 引用符を閉じる

引用自体は特に興味深いものではないため、引用の間でのみテキストを返します。

パーサーのテストは次のようになります。

 [Test] public void QuotedTextReturnsAValueBetweenQuotes() { var input = "\"this is text\""; var content = QuestionnaireGrammar.QuotedText.Parse(input); Assert.AreEqual("this is text", content); } 

アナライザーに直行しましょう。

 public static readonly Parser<string> QuotedText = (from open in Parse.Char('"') from content in Parse.CharExcept('"').Many().Text() from close in Parse.Char('"') select content).Token(); 

LINQクエリ構文のこの便利な再利用は、F＃チームのLuke Hobanによって（私の知る限り）最初に説明されました。 操作から個々の構文単位を分割し、selectを使用してパーサー全体の戻り値に変換します。

パーシム質問

パーサーが強く型付けされていることに気づいたかもしれません。 文字のパーサーはcharを返し、テキストのパーサーはstringを返します 。 質問のパーサーはQuestionを返します！

 public class Question { public Question(string id, string prompt) { Id = id; Prompt = prompt; } public string Id { get; private set; } public string Prompt { get; private set; } } 

これは、組み合わせ分析の大きな利点です。 問題のセマンティックモデルが構築されるとすぐに、パーサーは入力データを直接変換できます。

 public static readonly Parser<Question> Question = from id in Identifier from prompt in QuotedText select new Question(id, prompt); 

質問の単体テストに合格しました：

 [Test] public void AQuestionIsAnIdentifierFollowedByAPrompt() { var input = "name \"Full Name\""; var question = QuestionnaireGrammar.Parse(input); Assert.AreEqual("name", question.Id); Assert.AreEqual("Full Name", question.Prompt); } 

セクション解析

セクションの分析は、質問の分析と同じです。最初にセマンティックモデルを構築し、次に既存のパーサーを使用して、ソーステキストをそれに変換します。

このセクションは次のようになります。

 identification "Personal Details" [ name "Full Name" department "Department" ] 

次のようにオブジェクトモデルで表現できます。

 public class Section { public Section(string id, string title, IEnumerable<Question> questions) { Id = id; Title = title; Questions = questions; } public string Id { get; private set; } public string Prompt { get; private set; } public IEnumerable<Question> Questions { get; private set; } } 

パーサーの開発は、オブジェクトモデルの開発と同じくらい簡単です。

 public static readonly Parser<Section> Section = from id in Identifier from title in QuotedText from lbracket in Parse.Char('[').Token() from questions in Question.Many() from rbracket in Parse.Char(']').Token() select new Section(id, title, questions); 

この例を完了するために、別のモデルクラスがあります。

 public class Questionnaire { public Questionnaire(IEnumerable<Section> sections) { Sections = sections; } public IEnumerable<Section> Sections { get; private set; } } 

対応するパーサー（今回は構文を解析せずに）：

 public static Parser<Questionnaire> Questionnaire = Section.Many().Select(sections => new Questionnaire(sections)).End(); 

.End（）修飾子では、すべての入力データを解析する必要があります（つまり、最後にゴミが残っていません）。

これは、データ型修飾子なしの例に必要なすべてです。

応答データ型のサポート

文法の最後の仕上げは、回答タイプ修飾子のサポートです。

 #months "Total Months Employed" 

それらを表すために、可能なすべての型の列挙を使用できます。

 public enum AnswerType { Natural, Number, Date, YesNo } 

これはかなり限られたセットなので、列挙を使用して、可能なすべての修飾子をチェックします。

 public static Parser<AnswerType> AnswerTypeIndicator = Parse.Char('#').Return(AnswerType.Natural) .Or(Parse.Char('$').Return(AnswerType.Number)) .Or(Parse.Char('%').Return(AnswerType.Date)) .Or(Parse.Char('?').Return(AnswerType.YesNo)); 

Questionクラスは、 AnswerTypeをコンストラクターパラメーターとして受け入れるように変更されました。 質問パーサーの簡単な変更で作業が完了します。

 public static Parser<Question> Question = from at in AnswerTypeIndicator.Or(Parse.Return(AnswerType.Text)) from id in Identifier from prompt in QuotedText select new Question(id, prompt, at); 

まとめ

完全なアナライザーは、25の整形式のコード行にある6つのルールです。

信頼できる構文解析は現実の世界では些細な作業ではありませんが、この記事で正規表現と言語ツールのギャップを埋める簡単なバリエーションがあることを示したいと思います。