makenowjust-labs/blog

自然数の分割とは、ある数と和が等しくなるような自然数の多重集合です。 例えば $\{\!| 3, 2, 2, 1 |\!\}$ は $3 + 2 + 2 + 1 = 8$ なので $8$ の分割となります。

この記事では、自然数の分割の積の最大値について考えます。

このブログは現在 (2023年12月11日付) Next.jsで実装されています (移行の際の記事)。

これまでは実装にPages Routerを使っていました。 最近「カテゴリ機能」(現在は「タグ機能」) を追加したのですが、その際にカテゴリの一覧の取得をすべてのページのgetStaticPropsで行わなければならず、不便に感じていました。 そうした問題の解消のために、App Routerへと移行しました。

他にもOGP画像の生成にsatoriを使うようにしたり、GitHub PagesへのデプロイをGitHub Actionsで成果物をアップロードする形にしたり、色々と修正をしました。 それらの実装を通じて学んだことを、この記事では整理します。

最近RPrecという演算子の優先順位に基づいて構文解析を行うRubyのライブラリを実装しました。 その中で、演算子の優先順位と結合順位についての理解が深まりました。

演算子の優先順位 (precedence) というのは、1 + 2 * 3が1 + (2 * 3)と解釈されて「*は+よりもつよく結合する」というように言われるものです。 この優先順位はJavaScriptであればこの辺りに、Rubyであればこの辺りにまとまっています。

そして、演算子の結合規則 (associativity) というのは、左結合とか右結合とか言われるものです。 1 + 2 + 3は(1 + 2) + 3と解釈されるので+は左結合であったり、a = b = 1がa = (b = 1)と解釈されるので=は右結合というようなものです。

今回は、この演算子の結合規則のバリエーションについて考察したことについて、まとめたいと思います。

想定読者: 構文解析やプログラミング言語の構文に興味があり、これらについて多少の知識があることを想定しています。

commlogはこれまでNuxt 2を利用してきました。 しかし、Nuxtは2022年11月にNuxt 3がリリースされており、Nuxt 2はVue 2と共に2023年12月末をもってサポートが終了されることが発表されていました。 commlogの大部分のコードを書いたのは5年以上前になっているということもあり、コードをメンテナンスすることが困難になっていました。

そこで今回、commlogを完全に書き直すことでNuxt 3に移行しました。 その記録を、この記事では報告します。 また、Nuxt 3の他にTailwind CSSやMock Service Worker (msw)、Bun、Netlify Buildなどの、様々なライブラリ・開発ツールを利用して開発を進めました。 これらにより、モダンな構成にできたのではないかと考えています。

正規表現マッチングの実装手法の1つとしてPike VMと呼ばれるものがあります。 これはGo言語の正規表現実装やRustのregex crateで使われている手法であり、正規表現$r$と入力文字列$w$に対して$O(|r| \times |w|)$の計算量でマッチングができるのが特徴です。

Earley法はJay Earleyの提案した文脈自由文法 (CFG) の構文解析手法の1つです。 すべてのCFGを構文解析できる手法で最悪計算量は$O({|w|}^3)$ですが、無曖昧であれば$O({|w|}^2)$で、決定的であれば$O({|w|})$で構文解析ができます。

実装してみると分かりますが、Pike VMとEarley法には類似している点があり、Earley法をPike VMの発展系のように考えることができます。 この記事ではPike VMとEarley法のRubyでの実装を通じて、それらの関係を解説します。

想定読者: 形式言語や構文解析についての基本的な知識がある (NFAやCFGなどを知っている) ことを想定しています。