壁ツェーン

オンギャーの思考回路

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: ヒエラルキーの無矛盾性を検証する

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

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

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

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

電子工作 プログラミング

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

続きを読む