NHKから国民を守る党文法のパーサーをRustで実装する

この記事は元々 Qiita に投稿されていたもの ですが、色々あってこちらに移植しました。 [:contents]

【数学】NHKから国民を守る党からNHKを守る党からNHKから国民を守る党を守る党 がかなりツボに入ってしまったので、もう少し考えてみることにした。何年ぶりに Qiita の記事書いてるだろう……

簡略化された「NHKから国民を守る党文法」を BNF で表現する

上記記事で提示されている「NHKから国民を守る党文法」を素朴に構文定義すると以下のようになる。

<camp> ::= 'N'
         | 'K'
         | <camp> '[' <camp> ']'

見てわかるとおり、この文法は左再帰を含む。そのため、 LL(1) パーサーをこのまま実装しようとすると無限再帰に陥ってしまう。そこで、この直接左再帰を除去することを考える。

左再帰 - Wikipedia を参考にしつつ変形してみると多分こう。

<camp>      ::= 'N' <camp_tail>
              | 'K' <camp_tail>

<camp_tail> ::= ε
              | '[' <camp> ']' <camp_tail>

左再帰がなくなった。

Rust で構文解析を実装する

BNF で定義ができたらやることは一つ、再帰下降構文解析に限る。(いいえ)

1. AST

ということで、とりあえず AST を作る。国民は Citizen でもよいが Kokumin のほうが面白いのでこちらを採用する。

enum CampTarget {
    Nhk,
    Kokumin,
}

enum CampAst {
    Epsilon,
    Camp {
        head: CampTarget,
        tail: Box<CampAst>,
    },
    CampTail {
        convoying: Box<CampAst>,
        tail: Box<CampAst>,
    },
}

ついでに使いそうなエラー用の enum も定義しておく。

enum CampError {
    InvalidCharacter(char),
    NoMoreCharacter,
    InvalidSyntax,
}

構文解析器はあんまり面白みの構成になってしまったが、 std::iter::Peekable がいい感じに使えた(用途これであってるのか？)。

/// 構文解析器
struct Parser;

impl Parser {
    pub fn parse(source: &str) -> Result<CampAst, CampError> {
        let mut peekable = source.chars().peekable();
        Parser::camp(&mut peekable)
    }

    /// <camp> の解析
    fn camp(source: &mut Peekable<impl Iterator<Item = char>>) -> Result<CampAst, CampError> {
        let head = match source.next() {
            Some('N') => CampTarget::Nhk,
            Some('K') => CampTarget::Kokumin,
            Some(otherwise) => return Err(CampError::InvalidCharacter(otherwise)),
            None => return Err(CampError::NoMoreCharacter),
        };
        let tail = Box::new(Parser::camp_tail(source)?);

        Ok(CampAst::Camp { head, tail })
    }

    /// <camp_tail> の解析
    fn camp_tail(source: &mut Peekable<impl Iterator<Item = char>>) -> Result<CampAst, CampError> {
        match source.peek() {
            Some('[') => {
                source.next();
                let convoying = Box::new(Parser::camp(source)?);

                match source.next() {
                    Some(']') => {
                        let tail = Box::new(Parser::camp_tail(source)?);
                        Ok(CampAst::CampTail { convoying, tail })
                    }
                    Some(otherwise) => Err(CampError::InvalidCharacter(otherwise)),
                    None => Err(CampError::NoMoreCharacter),
                }
            }
            Some(']') => Ok(CampAst::Epsilon),
            Some(otherwise) => Err(CampError::InvalidCharacter(*otherwise)),
            None => Ok(CampAst::Epsilon),
        }
    }
}

これで最低限のコードは完成したので、手始めに「NHKから国民を守る党」に対応する N[K] をテストしてみると……

Ok(Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Kokumin, tail: Epsilon }, tail: Epsilon } })

よさそう。

2. ACT (Abstract Camp Tree, 抽象陣営木)

さて、 AST が完成したのはいいがこれは本来の陣営の構造とは対応していないので、陣営の構造に変換する。

/// 抽象陣営木
enum Camp {
    /// NHK
    Nhk,

    /// 国民
    Kokumin,

    /// 党
    Party {
        /// ……から
        attacker: Box<Camp>,

        /// ……を守る
        convoying: Box<Camp>,
    },
}

impl From<&CampTarget> for Camp {
    fn from(c: &CampTarget) -> Camp {
        match c {
            CampTarget::Nhk => Camp::Nhk,
            CampTarget::Kokumin => Camp::Kokumin,
        }
    }
}

impl Camp {
    pub fn from_ast(ast: &CampAst) -> Result<Camp, CampError> {
        match ast {
            CampAst::Camp { head, tail } => match &**tail {
                CampAst::Epsilon => Ok(head.into()),
                CampAst::CampTail { convoying, tail } => {
                    // TODO: fold できそうな雰囲気がある
                    let mut result = Camp::Party {
                        attacker: Box::new(head.into()),
                        convoying: Box::new(Camp::from_ast(convoying)?),
                    };
                    let mut last_tail = tail;
                    while let CampAst::CampTail {
                        convoying: next_convoying,
                        tail: next_tail,
                    } = &**last_tail
                    {
                        result = Camp::Party {
                            attacker: Box::new(result),
                            convoying: Box::new(Camp::from_ast(next_convoying)?),
                        };
                        last_tail = next_tail;
                    }

                    Ok(result)
                }
                _ => Err(CampError::InvalidSyntax),
            },
            _ => Err(CampError::InvalidSyntax),
        }
    }
}

3. 陣営を表示する

あとはもう消化試合みたいなものね。

impl ToString for Camp {
    fn to_string(&self) -> String {
        match self {
            Camp::Nhk => "NHK".into(),
            Camp::Kokumin => "国民".into(),
            Camp::Party {
                attacker,
                convoying,
            } => format!(
                "{}から{}を守る党",
                attacker.to_string(),
                convoying.to_string()
            ),
        }
    }
}

4. 矛盾した世界かどうかを判定する

これで簡略されたNHKから国民を守る党文法をパースして元の陣営名を表示できるようになったので、未解決問題にあった「政党名を与えたとき、世界が矛盾しているか否かを判定するアルゴリズムは存在するか？」についても考えてみよう。 cisdur7さんのコメントに、このような解法の存在が示されているので引用する。

「政党名を与えたとき、世界が矛盾しているか否かを判定するアルゴリズム」については、「K[N]をNに、N[K]をKに置換する」ということを繰り返せばいいのではないでしょうか。 途中でK[K]またはN[N]が出現したら世界は矛盾していることになります。 矛盾がない場合には、最後にその政党の与する陣営が残ります。

POPPONさんのコメント も参考とした。これらを参考にもう少し噛み砕いて考えると……

• いま、α[β][γ] という党が存在したとする。 (α[β] ≠ γ)
  • 最終的に守られている陣営は γ である。
  • ということで、連鎖的な防衛についてはこの置換を実行しても問題なさそうである。
  • 他の誰かによって守られた瞬間に自分は誰かを攻撃していることになるというのは中々殺伐とした世界な気がしなくもないが……
• α[β[γ]] については、この党は α から β[γ] を防衛している。 (α ≠ β[γ])
  • 直観的には防衛対象の防衛対象もやはり防衛対象であるから、多重防衛についても問題なさそうである。
• ただし、これらの仮定のもとでは N[K][K] は矛盾している。

あとはまあ、数学的帰納法でなんとかなるでしょう…… (ここは適当に書いているので間違っていたら教えてください)(眠い)

impl Camp {
    pub fn simplify(&self) -> Camp {
        match self {
            Camp::Party {
                attacker,
                convoying,
            } => {
                let head = attacker.simplify();
                let tail = convoying.simplify();
                if head != tail {
                    tail
                } else {
                    // 陣営が競合/矛盾している
                    Camp::Party {
                        attacker: Box::new(head),
                        convoying: Box::new(tail),
                    }
                }
            }
            otherwise => otherwise.clone(),
        }
    }
}

完成

Rust Playground のリンク (2019/12/21 00:50 expr を文字列リテラルで取るようにしました)

遊ぶ

$ cargo run -- 'N[K][N][N[N[K]]]'
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/nhk-citizen 'N[K][N][N[N[K]]]'`
抽象構文木: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Kokumin, tail: Epsilon }, tail: CampTail { convoying: Camp { head: Nhk, tail: Epsilon }, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Kokumin, tail: Epsilon }, tail: Epsilon } }, tail: Epsilon } }, tail: Epsilon } } } }
抽象陣営木: Party { attacker: Party { attacker: Party { attacker: Nhk, convoying: Kokumin }, convoying: Nhk }, convoying: Party { attacker: Nhk, convoying: Party { attacker: Nhk, convoying: Kokumin } } }
党(陣営)名: NHKから国民を守る党からNHKを守る党からNHKからNHKから国民を守る党を守る党を守る党
陣営根: 国民

本当か？

追記: 矛盾しない党(陣営)名とは?

では、 逆に矛盾しない党(陣営)名とはどのようなものか考えてみよう。説明のために、最初の党は N[K] とする。

• 最後の防衛対象と対立する陣営を防衛する党は妥当である。
  • N[K][N] は妥当である。
  • N[K][N][K] も妥当である。
  • 一般に、 N[K][N][K][N]... は妥当である。
• ある防衛対象を攻撃している陣営から防衛する党を攻撃している陣営から防衛する党も妥当である。
  • N[N[K]] は妥当である。
  • N[N[N[K]]] も妥当である。
  • 一般に、 N[N[N[...N[K]]...] は妥当である。
• **ある防衛対象を攻撃している陣営から同じ防衛対象を防衛する党は矛盾をおこす。
  • N[K][K] は矛盾を含む。

というようなところだろうか。つまり、最初に N もしくは K を用意して、以下を好きなように実行すればよさそうである。

1. 末尾の N(K) と対立する K(N) を守る党 として、 [K] or [N] を好きなだけ交互に追加する。
2. 手前の陣営から守る党を好きな場所で好きなだけ入れ子にする。

すると……

K[K[K[N]]][N[N[K]]][N][N[N[N[K]]]][K[N]][N[N[K]]][K[K[K[K[N]]]]][N[K]][N][N[N[K]]]

というおぞましい党が生成される。

抽象構文木: Camp { head: Kokumin, tail: CampTail { convoying: Camp { head: Kokumin, tail: CampTail { convoying: Camp { head: Kokumin, tail: CampTail { convoying: Camp { head: Nhk, tail: Epsilon }, tail: Epsilon } }, tail: Epsilon } }, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Kokumin, tail: Epsilon }, tail: Epsilon } }, tail: Epsilon } }, tail: CampTail { convoying: Camp { head: Nhk, tail: Epsilon }, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Kokumin, tail: Epsilon }, tail: Epsilon } }, tail: Epsilon } }, tail: Epsilon } }, tail: CampTail { convoying: Camp { head: Kokumin, tail: CampTail { convoying: Camp { head: Nhk, tail: Epsilon }, tail: Epsilon } }, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Kokumin, tail: Epsilon }, tail: Epsilon } }, tail: Epsilon } }, tail: CampTail { convoying: Camp { head: Kokumin, tail: CampTail { convoying: Camp { head: Kokumin, tail: CampTail { convoying: Camp { head: Kokumin, tail: CampTail { convoying: Camp { head: Kokumin, tail: CampTail { convoying: Camp { head: Nhk, tail: Epsilon }, tail: Epsilon } }, tail: Epsilon } }, tail: Epsilon } }, tail: Epsilon } }, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Kokumin, tail: Epsilon }, tail: Epsilon } }, tail: CampTail { convoying: Camp { head: Nhk, tail: Epsilon }, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Nhk, tail: CampTail { convoying: Camp { head: Kokumin, tail: Epsilon }, tail: Epsilon } }, tail: Epsilon } }, tail: Epsilon } } } } } } } } } } }
抽象陣営木: Party { attacker: Party { attacker: Party { attacker: Party { attacker: Party { attacker: Party { attacker: Party { attacker: Party { attacker: Party { attacker: Party { attacker: Kokumin, convoying: Party { attacker: Kokumin, convoying: Party { attacker: Kokumin, convoying: Nhk } } }, convoying: Party { attacker: Nhk, convoying: Party { attacker: Nhk, convoying: Kokumin } } }, convoying: Nhk }, convoying: Party { attacker: Nhk, convoying: Party { attacker: Nhk, convoying: Party { attacker: Nhk, convoying: Kokumin } } } }, convoying: Party { attacker: Kokumin, convoying: Nhk } }, convoying: Party { attacker: Nhk, convoying: Party { attacker: Nhk, convoying: Kokumin } } }, convoying: Party { attacker: Kokumin, convoying: Party { attacker: Kokumin, convoying: Party { attacker: Kokumin, convoying: Party { attacker: Kokumin, convoying: Nhk } } } } }, convoying: Party { attacker: Nhk, convoying: Kokumin } }, convoying: Nhk }, convoying: Party { attacker: Nhk, convoying: Party { attacker: Nhk, convoying: Kokumin } } }
党(陣営)名: 国民から国民から国民からNHKを守る党を守る党を守る党からNHKからNHKから国民を守る党を守る党を守る党からNHKを守る党からNHKからNHKからNHKから国民を守る党を守る党を守る党を守る党から国民からNHKを守る党を守る党からNHKからNHKから国民を守る党を守る党を守る党から国民から国民から国民から国民からNHKを守る党を守る党を守る党を守る党を守る党からNHKから国民を守る党を守る党からNHKを守る党からNHKからNHKから国民を守る党を守る党を守る党
陣営根: 国民

国民から国民から国民からNHKを守る党を守る党を守る党からNHKからNHKから国民を守る党を守る党を守る党からNHKを守る党からNHKからNHKからNHKから国民を守る党を守る党を守る党を守る党から国民からNHKを守る党を守る党からNHKからNHKから国民を守る党を守る党を守る党から国民から国民から国民から国民からNHKを守る党を守る党を守る党を守る党を守る党からNHKから国民を守る党を守る党からNHKを守る党からNHKからNHKから国民を守る党を守る党を守る党 は国民の味方である。

追記2: ヒエラルキーの無矛盾性を検証する

元記事の追記にて、ヒエラルキーについて言及されていた。 γ := α[β] が世界として矛盾を含まないときに β <= α <= γ なる力関係が存在するとした場合、党名によっては力関係に矛盾が生じる場合があるというものである。

これを見てすぐに思い浮かぶのは半順序だ。もしヒエラルキーに矛盾がない世界であれば、党名から導かれるすべての部分党は半順序をなすものと考えられそうである。簡単のため、「γ は α[β] と同等以上に強い」 というやや弱めた定義を用いることにすると、

• 対称律: 全ての陣営は自明に自分自身と同じ強さをもつので正しい。
• 推移律: 矛盾がなければ、党の定義よりおそらく自明である。
• 反対称律: 矛盾がなければ、自分と同等以上かつ自分と同等以下の強さをもつとみなされる陣営は自分自身のみである。

【ASMR】失恋duino.php SUMMER

この記事は mstdn.maud.io Advent Calendar 2019 の 2 日目の記事です。

昨日は VanBackfat(背脂) さんの 末代珍走団2019年活動報告 - ゲロ日記 でした。 FH4 買う買うつって半年たってしまいました。 FH4 の代わりに買った 様 々 な 物 が……

Sipeed Maixduino と OLED モジュール (SSD1331) を使って漢字を表示する

mstdn.maud.io 性懲りもなく今度は Sipeed Maixduino を買ってしまいました。

Sipeed Longan Nano を入手しました

先日秋葉原で Sipeed Longan Nano を購入しました*1。最近流行りの RISC-V アーキテクチャの MCU を搭載したものですね。アツい。僕が入手したのはラジオデパートの Shigezone なんですが、店頭在庫は秋月も Shigezone も微妙っぽいので通販のほうが入手性は安定しているかもしれません。

所感

キットに 160x80 の RGB LCD (OLED という噂もあるが真偽は定かではない) とケースが付いてます。よくインタネッツで見かける Longan Nano の写真には透明なアクリルケースが写っていることが多いですが、最近のは半透明のケースになっているようです。尤も、あの透明なケースは閉めたら開けるのが意外と大変という声もあるようなので、これでいいのかもしれません。これで 750 円だっていうんだから大したものです。僕は思い切って 2 つ買ってしまいました。

ドキュメントを探していくとまあ中国語の多いこと多いこと。大陸パワーを感じます。公式ドキュメントは英語のものが同量ぐらいにはあるので活用しましょう。みんな Bad Apple! を再生してるけどまさかこれが公式のサンプルだとは思いませんでした。

:+1: ポイント

• USB Type-C 接続。僕が持っているものだとこれ以外に Type-C で接続できるものは M5Stack ぐらいしかない。
• Platform IO サポートがある。まああるのは当たり前として、比較的まともなのがいい。
• 公式の Firmware Library が充実している。リファレンスマニュアルもあるし、サンプルが大量に用意されている。
• ChaN 氏の FatFs のデバイス側実装が( Apache License 2.0 で)用意されているので、microSD を使うのに困らない(でしょう)。

:thinking_face: ポイント

• LCD の制御方法が不明というかサンプルからしかわからない。多分何か有名な RGB LCD コントローラー IC と互換性のあるものなんだろうけど……
  • 追記 (Wed Nov 13 00:22:10 2019) 160x80 LCD でググったらそれっぽいのが千石に売ってた。もしこれと同じパーツならST7735Sとして扱ってよいのかな？
  • そういえば GREEN TAB でしたね。
• というかそもそもサンプルを見ないとわからないことが多い気がする。さすがに多くを求めすぎだと思うのでこれは割り切って使うけどね。
• プラケースの加工精度が怪しい。フタが完全に閉まらないのさすがに仕様ということはないでしょうし、本来切らない場所も多少切ってしまいました。

感想

今まで買った中で一番使い勝手がいいのでは感がある。性能が低すぎるということはないし(RISC-V 108MHz動作なら中々では?)、全体のサイズもデカすぎない。 Sipeed は他にも RISC-V で色々面白そうなボードを出しているので他に何か入手したいですね。

*1:厳密には ROM 64KB, RAM 20KB のモデルだったので Longan Nano Lite です