Go to Qiita Advent Calendar 2024 Top
LoginSignup
6
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@matarillo

エスケープありテキストのパーサーを2通り書いてみた

Last updated at Posted at 2018-12-24

はじめに

これは「オフラインリアルタイムどう書く E29」で出題された「アンエスケープ」という問題のC#による実装例です。

問題 : http://nabetani.sakura.ne.jp/hena/orde29unes/
実装リンク集 : https://qiita.com/Nabetani/items/f2db9b916c0a301b744f

問題は、「ファイルパスの文字列表現が与えられる。区切り文字は / だが、ディレクトリエントリ名の中でも使うことができる。その際は、// と二重に書くことでエスケープするか、" " または ' ' のようにクォートする。与えられた文字列表現を解析して、生のディレクトリエントリ名のリストを出力せよ。」です。細かい制約などは上のリンク先を読んでください。

出題はファイルパスと言っているけど、ダブルクォートのあたりはなんだかCSVにも似ているな。ってことはこの問題を解いていれば、CSVパーサーを実装する練習にもなりそうだ。俺は詳しいんだ1。

さてこの記事では、わりとまじめにパーサーを実装して問題を解いてみます。「わりとまじめに」というのは、コードの短さよりも丁寧さを優先する、という意味です。パーサーの実装方法として、「有限ステートマシン」「パーサーコンビネーター」の２通りを試しました。

有限ステートマシンでパーサーを書く

パーサーが1文字読み取るごとに内部状態を遷移させ、それに応じて出力が変わる、というかっこうです。たとえば「"を読み取ったのでダブルクォート状態に遷移する」とか、「/を読み取ったのでエスケープ状態に遷移する」とか、そのようなルールをもれなく矛盾なく構成する感じです。

出力を伴う有限ステートマシンには、出力が内部状態だけに依存する関数となるもの（ムーア・マシン）と、出力が入力と内部状態の両方に依存する関数となるもの（ミーリ・マシン）の2通りがあります。今回は入出力の文字種がそこそこあるので、状態数を減らすためにミーリ・マシンを選びました。

コードの前に、状態遷移図を見てみましょう。

yhpg_E29_statemachine.png

  • Empty の状態からパースを開始します。すべての文字を読み取った後、状態が Entry に遷移していればパース成功、それ以外はパース失敗です。
  • 問題文に「空文字列のエントリーは無効」とあるので、それを状態遷移に反映させてあります。これを状態遷移に埋め込まなければ（たとえば、空文字列を許容したエントリーをパースし終わった後で、最後に空文字列チェックをするなどすれば）、状態数はもっと少なく済むでしょう。
  • クォートされていない状態で / をひとつ読み取った時、それが区切り文字なのかエスケープ文字（ダブルスラッシュのひとつ目）なのかを決められません。次の文字が / 以外だった時に、さっきの文字が区切り文字だったことがやっとわかります。なので、出力には「一つ前の文字が区切り文字だった」ことを示すフラグが必要になります。上の状態遷移図の中の 赤い下線文字 で書かれた出力はそれを表しています。

ではコードです。

YhpgE29Mealy.cs
using System;
using System.Collections.Generic;
using System.Text;

namespace Yhpg
{
    class Program
    {
        static void Main(string[] args)
        {
            Test("foo/bar/baz", "foo,bar,baz");
            Test("/foo/bar/baz'/", "-");
            Test("\"", "-");
            Test("'", "-");
            Test("/", "-");
            Test("\"\"", "-");
            Test("''", "-");
            Test("//", "/");
            Test("\"/'", "-");
            Test("'/\"", "-");
            Test("Qux", "Qux");
            Test("Foo/Bar", "Foo,Bar");
            Test("foo\"bar", "-");
            Test("foo'bar", "-");
            Test("/foo/bar", "-");
            Test("Foo//Bar", "Foo/Bar");
            Test("foo/bar/", "-");
            Test("'\"'a'\"'/b", "\"a\",b");
            Test("Foo\"/\"Bar", "Foo/Bar");
            Test("foo\"'\"bar", "foo'bar");
            Test("foo'\"'bar", "foo\"bar");
            Test("foo///bar", "foo/,bar");
            Test("\"Z\"\"tO\"uFM", "ZtOuFM");
            Test("''/foo/bar", "-");
            Test("////'/\"//'", "///\"//");
            Test("File/'I/O'", "File,I/O");
            Test("Foo'//'Bar", "Foo//Bar");
            Test("foo/''/bar", "-");
            Test("foo/bar/\"\"", "-");
            Test("'/////'////", "///////");
            Test("'foo\"\"\"bar'", "foo\"\"\"bar");
            Test("//'int'/V/c", "/int,V,c");
            Test("foo/bar/baz", "foo,bar,baz");
            Test("'H//Sg//zN'/", "-");
            Test("//'//\"/'/'\"'", "///\"/,\"");
            Test("foo//bar/baz", "foo/bar,baz");
            Test("\"\"\"///\"/'/'//", "///,//");
            Test("58\"\"N\"//nIk'd", "-");
            Test("foo\"/\"bar/baz", "foo/bar,baz");
            Test("/////'\"/'/'\"/'", "//,\"/,\"/");
            Test("f\"//J\"/O9o\"//'", "-");
            Test("foo\"//\"bar/baz", "foo//bar,baz");
            Test("foo/bar////baz", "foo,bar//baz");
            Test("\"\"\"'/'//'''/\"//", "'/'//'''//");
            Test("8//'/k///\"3da\"'", "8//k///\"3da\"");
            Test("foo/'/bar/'/baz", "foo,/bar/,baz");
            Test("///''\"//\"\"///\"\"\"", "/,/////");
            Test("//wUJ8KNAk'n0//\"", "-");
            Test("What/is/'\"real\"'", "What,is,\"real\"");
            Test("\"//'/////\"''/'//'", "//'/////,//");
            Test("\"8hKE\"3Fx/4//Hk/J", "8hKE3Fx,4/Hk,J");
            Test("'////''\"'//'/\"///'", "////\"//\"///");
            Test("Ro\"/j''/2u/f/r/\"3n", "Ro/j''/2u/f/r/3n");
            Test("hoge\"//\"fuga//piyo", "hoge//fuga/piyo");
            Test("'foo//bar'//baz/qux", "foo//bar/baz,qux");
            Test("//'//\"'/\"///'\"/''//", "///\",///',/");
            Test("2/L'3'A8p/7//wP49Jb", "2,L3A8p,7/wP49Jb");
            Test("\"foo'\"/\"bar'\"/\"baz'\"", "foo',bar',baz'");
            Test("'//'\"//'///'///''\"//", "////'///'///''/");
            Test("F6vX/q/Zu//5/'/H\"/'w", "F6vX,q,Zu/5,/H\"/w");
            Test("\"foo'bar\"/'hoge\"fuga'", "foo'bar,hoge\"fuga");
            Test("/\"/'//'/\"\"\"''//'/\"'''", "-");
            Test("0gK\"koYUb\"\"S/p''z/\"Et", "0gKkoYUbS/p''z/Et");
            Test("Foo/Bar/\"Hoge'/'Fuga\"", "Foo,Bar,Hoge'/'Fuga");
        }

        static void Test(string input, string expected)
        {
            var actual = Parser.Parse(input);
            if (expected != actual)
            {
                Console.WriteLine($"input:{input} expected:{expected} actual:{actual}");
            }
        }
    }

    class Parser
    {
        private readonly StringBuilder builder = new StringBuilder();
        private readonly List<string> entries = new List<string>();
        private readonly MealyMachine stateMachine = new MealyMachine();

        public static string Parse(string input)
        {
            var p = new Parser();
            p.ParseInternal(input);
            return p.GetResult();
        }

        private void ParseInternal(string input)
        {
            foreach (var c in input)
            {
                Next(c);
            }
            entries.Add(builder.ToString());
            builder.Clear();
        }

        private void Next(char c)
        {
            var output = stateMachine.Next(c);
            if (output.IsSeparated)
            {
                entries.Add(builder.ToString());
                builder.Clear();
            }
            if (output.HasRawCharacter)
            {
                builder.Append(output.RawCharacter);
            }
        }

        private string GetResult() =>
            (stateMachine.state == State.Entry)
                ? string.Join(",", entries)
                : "-";
    }

    enum State
    {
        EmptyEntry,
        EmptyDoubleQuoting,
        EmptySingleQuoting,
        EmptySlashing,
        Entry,
        DoubleQuoting,
        SingleQuoting,
        Slashing,
        Invalid
    }

    class MealyMachine
    {
        internal State state = State.EmptyEntry;

        public Output Next(char c)
        {
            (State next, Output output) = Next(state, c);
            state = next;
            return output;
        }

        private static (State, Output) Next(State state, char c)
        {
            switch (state)
            {
                case State.EmptyEntry:
                    return FromEmptyEntry(c);
                case State.Entry:
                    return FromEntry(c);
                case State.EmptyDoubleQuoting:
                    return FromEmptyDoubleQuoting(c);
                case State.DoubleQuoting:
                    return FromDoubleQuoting(c);
                case State.EmptySingleQuoting:
                    return FromEmptySingleQuoting(c);
                case State.SingleQuoting:
                    return FromSingleQuoting(c);
                case State.EmptySlashing:
                    return FromEmptySlashing(c);
                case State.Slashing:
                    return FromSlashing(c);
                default:
                    return (State.Invalid, default(Output));
            }
        }

        private static (State, Output) FromEmptyEntry(char c)
        {
            switch (c)
            {
                case '\'':
                    return (State.EmptySingleQuoting, default(Output));
                case '"':
                    return (State.EmptyDoubleQuoting, default(Output));
                case '/':
                    return (State.EmptySlashing, default(Output));
                default:
                    return (State.Entry, new Output(c));
            }
        }

        private static (State, Output) FromEntry(char c)
        {
            switch (c)
            {
                case '\'':
                    return (State.SingleQuoting, default(Output));
                case '"':
                    return (State.DoubleQuoting, default(Output));
                case '/':
                    return (State.Slashing, default(Output));
                default:
                    return (State.Entry, new Output(c));
            }
        }

        private static (State, Output) FromEmptyDoubleQuoting(char c)
        {
            switch (c)
            {
                case '"':
                    return (State.EmptyEntry, default(Output));
                default:
                    return (State.DoubleQuoting, new Output(c));
            }
        }

        private static (State, Output) FromDoubleQuoting(char c)
        {
            switch (c)
            {
                case '"':
                    return (State.Entry, default(Output));
                default:
                    return (State.DoubleQuoting, new Output(c));
            }
        }

        private static (State, Output) FromEmptySingleQuoting(char c)
        {
            switch (c)
            {
                case '\'':
                    return (State.EmptyEntry, default(Output));
                default:
                    return (State.SingleQuoting, new Output(c));
            }
        }

        private static (State, Output) FromSingleQuoting(char c)
        {
            switch (c)
            {
                case '\'':
                    return (State.Entry, default(Output));
                default:
                    return (State.SingleQuoting, new Output(c));
            }
        }

        private static (State, Output) FromEmptySlashing(char c)
        {
            switch (c)
            {
                case '/':
                    return (State.Entry, new Output(c));
                default:
                    return (State.Invalid, default(Output));
            }
        }

        private static (State, Output) FromSlashing(char c)
        {
            switch (c)
            {
                case '"':
                    return (State.EmptyDoubleQuoting, new Output(true));
                case '\'':
                    return (State.EmptySingleQuoting, new Output(true));
                case '/':
                    return (State.Entry, new Output(c));
                default:
                    return (State.Entry, new Output(true, c));
            }
        }
    }

    struct Output
    {
        public bool IsSeparated;
        public char RawCharacter;

        public Output(bool isSeparated)
        {
            IsSeparated = isSeparated;
            RawCharacter = default(char);
        }

        public Output(char rawCharacter)
        {
            IsSeparated = false;
            RawCharacter = rawCharacter;
        }

        public Output(bool isSeparated, char rawCharacter)
        {
            IsSeparated = isSeparated;
            RawCharacter = rawCharacter;
        }

        public bool HasRawCharacter => RawCharacter != default(char);
    }
}

テストコード部分は飛ばして構いません。コアは MealyMachineクラスのNext静的メソッドです。現在状態と読み取った文字の2つを引数として、次の状態と出力のタプルが戻り値になっています。中身は巨大な switch 文を複数メソッドに分割した形になっています。状態遷移図を愚直にコードに落としているのがわかるでしょうか。

パーサーコンビネーターでパーサーを書く

パーサーコンビネーターというのは簡単に言えば、ごく小さなパーサー部品（たとえば、「二重引用符を一文字読み取る」など）を関数として作り、関数合成によって部品を組み合わせていき、最終的に目的のパーサーを作り上げる、というものです。

このスタイルでパーサーを作る場合は、状態遷移図をステートマシンで表現した例とは違い、パーサーが正しく読み取れる文字列の集合を形式言語として文法定義して、それをコードに落とすことができます。

形式文法といえばBNFやEBNFが有名ですが、ここではPEGという文法でファイルパスのパーサーを定義してみます。PEGは、PEGで書かれた規則を左から順に試していくことが決められているもので、曖昧さが存在しないかわりに左再帰ができない（無限ループに陥る）という特徴があります。詳細はWikipediaのページを読んでください。

コードの前に、今回の問題をPEGで表現してみたものを見てみましょう。

Entries             ← Entry (Separator Entry)*

Entry               ← EmptySegment* NonEmptySegment Segment*
Separator           ← Slash

EmptySegment        ← DQ_EmptySegment / SQ_EmptySegment
NonEmptySegment     ← AlphaNumericSegment / DQ_NonEmptySegment / SQ_NonEmptySegment / DoubleSlashSegment
Segment             ← AlphaNumericSegment / DQ_Segment / SQ_Segment / DoubleSlashSegment

AlphaNumericSegment ← AlphaNumeric+
DQ_EmptySegment     ← DoubleQuote DoubleQuote
DQ_NonEmptySegment  ← DoubleQuote InsideDQ+ DoubleQuote
DQ_Segment          ← DoubleQuote InsideDQ* DoubleQuote
SQ_EmptySegment     ← SingleQuote SingleQuote
SQ_NonEmptySegment  ← SingleQuote InsideSQ+ SingleQuote
SQ_Segment          ← SingleQuote InsideSQ* SingleQuote
DoubleSlashSegment  ← Slash Slash

Slash               ← '/'
DoubleQuote         ← '"'
SingleQuote         ← '\''
AlphaNumeric        ← [A-Za-z0-9]
InsideDQ            ← [A-Za-z0-9/']
InsideSQ            ← [A-Za-z0-9/"]

一番上で定義されたファイルパスは、「空でないファイルエントリーが1つか、または複数の空でないファイルエントリーがセパレーターで区切られたもの」となっています。こちらも、ファイルエントリーが空ではないことを表現するのがちょっと面倒でした。そして途中は飛ばしますが、一番下にあるのが終端記号で、「スラッシュ」「二重引用符」「引用符」「英数字」「二重引用符の内側で使える文字」「引用符の内側で使える文字」が定義されています。

ではコードです。

YhpgE29PEG.cs
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using Input = System.ArraySegment<char>;
using CharList = System.Collections.Immutable.ImmutableStack<char>;

namespace Yhpg
{
    class Program
    {
        static void Main()
        {
            Test("foo/bar/baz", "foo,bar,baz");
            Test("/foo/bar/baz'/", "-");
            Test("\"", "-");
            Test("'", "-");
            Test("/", "-");
            Test("\"\"", "-");
            Test("''", "-");
            Test("//", "/");
            Test("\"/'", "-");
            Test("'/\"", "-");
            Test("Qux", "Qux");
            Test("Foo/Bar", "Foo,Bar");
            Test("foo\"bar", "-");
            Test("foo'bar", "-");
            Test("/foo/bar", "-");
            Test("Foo//Bar", "Foo/Bar");
            Test("foo/bar/", "-");
            Test("'\"'a'\"'/b", "\"a\",b");
            Test("Foo\"/\"Bar", "Foo/Bar");
            Test("foo\"'\"bar", "foo'bar");
            Test("foo'\"'bar", "foo\"bar");
            Test("foo///bar", "foo/,bar");
            Test("\"Z\"\"tO\"uFM", "ZtOuFM");
            Test("''/foo/bar", "-");
            Test("////'/\"//'", "///\"//");
            Test("File/'I/O'", "File,I/O");
            Test("Foo'//'Bar", "Foo//Bar");
            Test("foo/''/bar", "-");
            Test("foo/bar/\"\"", "-");
            Test("'/////'////", "///////");
            Test("'foo\"\"\"bar'", "foo\"\"\"bar");
            Test("//'int'/V/c", "/int,V,c");
            Test("foo/bar/baz", "foo,bar,baz");
            Test("'H//Sg//zN'/", "-");
            Test("//'//\"/'/'\"'", "///\"/,\"");
            Test("foo//bar/baz", "foo/bar,baz");
            Test("\"\"\"///\"/'/'//", "///,//");
            Test("58\"\"N\"//nIk'd", "-");
            Test("foo\"/\"bar/baz", "foo/bar,baz");
            Test("/////'\"/'/'\"/'", "//,\"/,\"/");
            Test("f\"//J\"/O9o\"//'", "-");
            Test("foo\"//\"bar/baz", "foo//bar,baz");
            Test("foo/bar////baz", "foo,bar//baz");
            Test("\"\"\"'/'//'''/\"//", "'/'//'''//");
            Test("8//'/k///\"3da\"'", "8//k///\"3da\"");
            Test("foo/'/bar/'/baz", "foo,/bar/,baz");
            Test("///''\"//\"\"///\"\"\"", "/,/////");
            Test("//wUJ8KNAk'n0//\"", "-");
            Test("What/is/'\"real\"'", "What,is,\"real\"");
            Test("\"//'/////\"''/'//'", "//'/////,//");
            Test("\"8hKE\"3Fx/4//Hk/J", "8hKE3Fx,4/Hk,J");
            Test("'////''\"'//'/\"///'", "////\"//\"///");
            Test("Ro\"/j''/2u/f/r/\"3n", "Ro/j''/2u/f/r/3n");
            Test("hoge\"//\"fuga//piyo", "hoge//fuga/piyo");
            Test("'foo//bar'//baz/qux", "foo//bar/baz,qux");
            Test("//'//\"'/\"///'\"/''//", "///\",///',/");
            Test("2/L'3'A8p/7//wP49Jb", "2,L3A8p,7/wP49Jb");
            Test("\"foo'\"/\"bar'\"/\"baz'\"", "foo',bar',baz'");
            Test("'//'\"//'///'///''\"//", "////'///'///''/");
            Test("F6vX/q/Zu//5/'/H\"/'w", "F6vX,q,Zu/5,/H\"/w");
            Test("\"foo'bar\"/'hoge\"fuga'", "foo'bar,hoge\"fuga");
            Test("/\"/'//'/\"\"\"''//'/\"'''", "-");
            Test("0gK\"koYUb\"\"S/p''z/\"Et", "0gKkoYUbS/p''z/Et");
            Test("Foo/Bar/\"Hoge'/'Fuga\"", "Foo,Bar,Hoge'/'Fuga");
        }

        static void Test(string input, string expected)
        {
            var actual = Parse(input);
            if (expected != actual)
            {
                Console.WriteLine($"input:{input} expected:{expected} actual:{actual}");
            }
        }

        static string Parse(string input)
        {
            var t = Entries.Parse(new Input(input.ToCharArray()));
            if (t == null || t.Item2.Count > 0)
            {
                return "-";
            }
            var entries = t.Item1.Select(x => new string(x.ToArray()));
            return string.Join(",", entries);
        }

        static readonly Parser<char> Item =
            new Parser<char>(input => input.Count > 0 ? Tuple.Create(input[0], input.Slice(1)) : null);

        static Parser<char> Char(char c) =>
            Item.Filter(x => x == c);

        static readonly Parser<CharList> Empty =
            new Parser<CharList>(CharList.Empty);

        static readonly Parser<char> Slash = Char('/');
        static readonly Parser<char> DoubleQuote = Char('"');
        static readonly Parser<char> SingleQuote = Char('\'');
        static Func<char, bool> isAlphaNumeric = c =>
            ('A' <= c && c <= 'Z') ||
            ('a' <= c && c <= 'z') ||
            ('0' <= c && c <= '9');
        static readonly Parser<char> AlphaNumeric =
            Item.Filter(isAlphaNumeric);
        static readonly Parser<char> InsideDoubleQuote =
            Item.Filter(c => isAlphaNumeric(c) || (c == '/') || (c == '\''));
        static readonly Parser<char> InsideSingleQuote =
            Item.Filter(c => isAlphaNumeric(c) || (c == '/') || (c == '"'));

        static readonly Parser<CharList> AlphaNumericSegment =
            AlphaNumeric.OneOrMore();
        static readonly Parser<CharList> DoubleSlashSegment =
            Slash
                .AndThen(_ => Slash, (_, __) => CharList.Empty.Push('/'));

        static Parser<CharList> DQ(Parser<CharList> parser) =>
            DoubleQuote
                .AndThen(_ => parser, (_, x) => x)
                .AndThen(_ => DoubleQuote, (x, _) => x);

        static readonly Parser<CharList> DoubleQuotedEmptySegment =
            DQ(Empty);
        static readonly Parser<CharList> DoubleQuotedNonEmptySegment =
            DQ(InsideDoubleQuote.OneOrMore());
        static readonly Parser<CharList> DoubleQuotedSegment =
            DQ(InsideDoubleQuote.ZeroOrMore());

        static Parser<CharList> SQ(Parser<CharList> parser) =>
            SingleQuote
                .AndThen(_ => parser, (_, x) => x)
                .AndThen(_ => SingleQuote, (x, _) => x);
        static readonly Parser<CharList> SingleQuotedEmptySegment =
            SQ(Empty);
        static readonly Parser<CharList> SingleQuotedNonEmptySegment =
            SQ(InsideSingleQuote.OneOrMore());
        static readonly Parser<CharList> SingleQuotedSegment =
            SQ(InsideSingleQuote.ZeroOrMore());

        static readonly Parser<CharList> EmptySegment =
            DoubleQuotedEmptySegment
                .OrElse(SingleQuotedEmptySegment);
        static readonly Parser<CharList> NonEmptySegment =
            AlphaNumericSegment
                .OrElse(DoubleQuotedNonEmptySegment)
                .OrElse(SingleQuotedNonEmptySegment)
                .OrElse(DoubleSlashSegment);
        static readonly Parser<CharList> Segment =
            AlphaNumericSegment
                .OrElse(DoubleQuotedSegment)
                .OrElse(SingleQuotedSegment)
                .OrElse(DoubleSlashSegment);

        static readonly Parser<CharList> Entry =
            EmptySegment.ZeroOrMore()
                .AndThen(_ => NonEmptySegment, (_, x) => x)
                .AndThen(_ => Segment.ZeroOrMore(), (x, xs) => xs.Push(x).Flatten());

        static readonly Parser<Char> Separator = Slash;
        static readonly Parser<CharList> SeparatorEntry =
            Separator
                .AndThen(_ => Entry, (_, x) => x);
        static readonly Parser<ImmutableStack<CharList>> Entries =
            Entry
                .AndThen(_ => SeparatorEntry.ZeroOrMore(), (x, xs) => xs.Push(x));
    }

    class Parser<T>
    {
        public Parser(T unit)
        {
            this.func = input => Tuple.Create(unit, input);
        }

        public Parser(Func<Input, Tuple<T, Input>> func)
        {
            this.func = func;
        }

        private readonly Func<Input, Tuple<T, Input>> func;

        public Tuple<T, Input> Parse(Input input) => func(input);
    }

    static class Extensions
    {
        public static Parser<T> Filter<T>(this Parser<T> self, Func<T, bool> predicate) =>
            new Parser<T>(input =>
            {
                var t = self.Parse(input);
                return (t != null && predicate(t.Item1)) ? t : null;
            });

        public static Parser<TResult> Map<T, TResult>(this Parser<T> self, Func<T, TResult> f) =>
            new Parser<TResult>(input =>
            {	
                var t = self.Parse(input);
                return (t != null) ? Tuple.Create(f(t.Item1), t.Item2) : null;
            });

        public static Parser<TResult> AndThen<T1, T2, TResult>(this Parser<T1> self,
            Func<T1, Parser<T2>> f, Func<T1, T2, TResult> selector) =>
            new Parser<TResult>(input =>
            {
                var t1 = self.Parse(input);
                if (t1 == null) return null;
                var t2 = f(t1.Item1).Parse(t1.Item2);
                if (t2 == null) return null;
                return Tuple.Create(selector(t1.Item1, t2.Item1), t2.Item2);
            });

        public static Parser<T> OrElse<T>(this Parser<T> left, Parser<T> right) =>
            new Parser<T>(input => left.Parse(input) ?? right.Parse(input));

        public static Parser<ImmutableStack<T>> ZeroOrMore<T>(this Parser<T> self) =>
            self.OneOrMore()
                .OrElse(new Parser<ImmutableStack<T>>(ImmutableStack<T>.Empty));

        public static Parser<ImmutableStack<T>> OneOrMore<T>(this Parser<T> self) =>
            self
                .AndThen(_ => self.ZeroOrMore(), (x, xs) => xs.Push(x));

        public static ImmutableStack<T> Concat<T>(this ImmutableStack<T> left, ImmutableStack<T> right)
        {
            var rev = new Stack<T>(left);
            foreach (var e in rev)
            {
                right = right.Push(e);
            }
            return right;
        }

        public static ImmutableStack<T> Flatten<T>(this ImmutableStack<ImmutableStack<T>> self)
        {
            var rev = new Stack<ImmutableStack<T>>(self);
            var flat = ImmutableStack<T>.Empty;
            foreach (var e in rev)
            {
                flat = e.Concat(flat);
            }
            return flat;
        }
    }
}
  • パーサー部品そのものは Parser<T>クラスとして定義しています。パーサーの入力はstringではなく、char配列のビューとなるSystem.ArraySegment<char>構造体2にしました。
  • パーサーを合成するメソッドは拡張メソッドにしてあります。中でも、PEGの文法に沿っているのは、__並び__を表す AndThen3メソッド、__選択__を表すOrElseメソッド、__ゼロ個以上の繰り返し__を表すZeroOrMoreメソッド、__１個以上の繰り返し__を表すOneOrMoreメソッドの４つです。
  • ZeroOrMoreとOneOrMoreはSystem.Collections.Immutable.ImmutableStack<T>を返します。関数型言語に馴染みがある人向けに言うと、ImmutableStack<T>はイミュータブルなコンスセルリストです。再帰する関数やメソッドではとても便利に使えるのですが、C#では言語組み込みではないので、ちょっと仰々しくなってしまいますね。
  • 今回のコードではやっていませんが、拡張メソッド名を次のように変更すればLINQのクエリ構文が使えるようになり、AndThen3の合成がすこし見やすくなります。ちなみにMapメソッドはコードの中では使っていないのですが、この説明のためだけにあえて入れてあります。
    • Map → Select
    • AndThen → SelectMany
    • Filter → Where
  • 同じく、今回のコードではやっていませんが、OrElseメソッドは演算子 | か / のオーバーロードとして定義してもいいかもしれませんね。

  1. ネタです。 ↩

  2. 今回のコードではSpan<T>は使えませんでした。Span<T>はスタック上に置かれることを保証するため、ジェネリック型引数にできないという制約があります。 ↩

  3. 関数型言語に馴染みのある人向けに言うと、このメソッドのシグネチャはflatMapとmapを合成したものになっています。それは、本文で書いたようにLINQのクエリ構文を使うために満たさないといけないルールなのですが、なぜflatMapそのものではないかというと、ネストが深くなるとコンパイルに時間がかかってしまうから、とのことです。これとかこれにそのことが取り上げられています。 ↩ ↩2

6
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?