日本ソフトウェア科学会第 41 回大会 (2024 年度) 講演論文集

LL(1) 文法から ﬂat-chaining および sub-chaining のﬂuent interface を自動生成する DSL の提案にむけて
山隈 由衣

山崎 徹郎

千葉 滋

本論文では，LL(1) 文法から ﬂat-chaining および sub-chaining の ﬂuent interface を生成するツールの提案をおこなう．ﬂuent interface は，method chain と呼ばれるメソッド呼び出しの連鎖からなるインターフェースである．
ﬂuent interface の表現方法には，ﬂat-chaining と sub-chaining の２種類がある．本論文は，Python 上の埋め込
み DSL を使って開発者が BNF 風の文法規則を記述すると Java で書かれた ﬂuent interface の雛形を生成する生成器の設計とその生成アルゴリズムについて述べる．提案する生成アルゴリズムは，Greibach 標準形の LL(1) 文法から ﬂat-chaining の ﬂuent interface を生成する手法を，sub-chaining に拡張したものである．εルールを除去できる LL(1) 文法からであれば，ﬂat-chaining および sub-chaining の ﬂuent interface の生成が可能になる．

ﬂat-chaining の静的型検査付き ﬂuent interface を生

1 はじめに成する手法があれば，εルールを除去できる LL(1)Fluent interface は，メソッド呼び出しの連鎖から文法から ﬂat-chaining および sub-chaining の ﬂuentなるインターフェースである．近年，高機能なライブinterface の生成が可能になる．

ラリの利用インタフェースとして採用されることが増えている [1] [2]．ホスト言語の型システムを利用することでメソッドの並び順の間違いを静的に検出す

2 Subchaining に対応した ﬂuent interface 生成器

ることも可能だが，インタフェースの実装が複雑にな

Fluent interface は，method chain と呼ばれるメる．このため，複雑な実装を支援するために，インタソッド呼び出しの連鎖からなるインターフェースでフェースの実装のひな形を出力するコード生成器の開ある．method chaining の各メソッドはオブジェクト発が重要である．

を返し，そのオブジェクトから次のメソッドが呼び

Fluent interface の表現方法には，ﬂat-chaining と出される．ﬂuent interface は埋め込み型領域特化言

sub-chaining の２種類がある．Flat-chaining の ﬂu-語 (embedded domain speciﬁc languages, EDSLs)

ent interface 生成器を，sub-chaining の生成器に応のようなライブラリの設計に有用である．例えば，用する手法が研究されている．本論文では，LL(1) のJOOQ は SQL 文を表現する Java のコードを生成すより大きい部分集合から sub-と ﬂat-の ﬂuent inter-る．以下のような SQL クエリに対して，face を生成するツールを提案する．このツールを用

SELECT TITLE
FROM BOOK
WHERE BOOK . PUBLISHED_IN = 2011
ORDER BY BOOK . TITLE

いると Graibach 標準形 (GNF) で書ける LL(1) から
Toward a proposal for a DSL that automatically generates ﬂuent interfaces for ﬂat-chaining and subchaining from LL(1) grammar.
Yui Yamaguma, Testuro Yamazaki, Shigeru Chiba, 東京大学大学院情報理工学系研究科, Graduate Schoolof Information Science and Technology, The University of Tokyo.

以下のクエリが Java で生成される．
create . select ( BOOK . TITLE ). from ( BOOK ). where ( BOOK . PUBLISHED_IN . eq (2011)). orderBy ( BOOK . TITLE );Fluent interface の利用者は誤ったメソッドの並びを書いてしまうことがあるが，そのような誤った並る．GNF は全ての生成規則の右辺が終端記号から始まる文法の形である．

びは文法エラーと見なすことができる．この ﬂuent

LL(1) 文法の中には等価な GNF が存在しないもの

interface の文法エラーはホスト言語の静的な型エラーがある [6] ので，GNF の LL(1) 文法から ﬂat-chainingとしてコンパイル時にエラーとすることができる．のインタフェースを生成できても，任意の LL(1) からしかし，このような ﬂuent inferaface の文法エラー

falt-chaining のインタフェースを生成できるとは限らを型検査で判別するようなインターフェースを手作ない．例えば，言語 an (bk d + b + cc)n |n >= 1(k >=業で開発するのは難しい．なぜなら，ホスト言語上で1) を認識する以下の文法は，εルールを除去できなたくさんの型を定義する必要があるからである．静い [6]．

的型検査を行う仕組みは，文法に対応するプッシュS→aDA

ダウンオートマトンのスタックを表現する型を定義

D → a D A | ε A → cc |b B

して構文検査を行う．文法の規則が多いと，使うス

B → bk−1 d | εタックの種類も多くなる．ﬂuent interface の表現方

GNF の文法はεルールを含まないことから，この文

法には，ﬂat-chaining と sub-chaining の２種類があ法は等価な GNF が存在しない．

る．ﬂat-chaining は，以下のように一つの method

chaining からなる．

3 GreenChain の提案

i (9). add (). i (2). multiple (). i (3)

本論文では，εルールを除去可能な LL(1) 文法か

ﬂat-chaining は，短いあるいは単純な連鎖の表現に有用である．sub-chaining は複数の method chaining
で表現し，ある連鎖を他の連鎖に引数として渡す．

sub-chaining では，以下のように，あるメソッド呼び出し連鎖を他の連鎖に引数として渡す．
add ( i (9) , i (2). multiple (). i (3))

ら ﬂat-chaining および sub-chaining の ﬂuent inter-face を文法エラーの静的検査付きで生成するツール
GreenChain を提案する．GreenChain は Python 上の EDSL(embedded domain speciﬁc language) である．本論文は GreenChain のために ﬂuent interfaceを自動生成するための新しいアルゴリズムを示す．
このアルゴリズムは，εルールを除去可能という制

sub-chaining は長いあるいは複雑な連鎖の表現に有限があるものの LL(1) 文法から ﬂat-chaining および用である．

sub-chaining の ﬂuent interface を文法エラーの検出

文法エラー検出機能つきの ﬂuent interface の開発

機能つきで生成する現実的なアルゴリズムである．

を支援するために自動生成器が開発されている．しかしながら，ﬂat-chainging と sub-chaining の両方に生

3. 1 利用方法

成する自動生成器で，対応可能な ﬂuent interface のGreenChain の EDSL は BNF 風の文法を記述する

文法クラスが明らかになっているものはない．

ための言語で，GreenChain はこの記述から Java でYamazaki らによって，LL(1) から ﬂat-chaining の書かれた ﬂuent interface の雛形を生成する．例えばインターフェースを生成するアルゴリズムがあれば，次のような加算と乗算の前置記法を表現する BNF のLL(1) から ﬂat-chaining と sub-chaining の両方を生文法成するアルゴリズムが提案されている [3]．しかし終端記号：i, add, multiple

LL(1) から ﬂat-chaining のインターフェースを生成

非終端記号：E, T, Fするアルゴリズムは知られていない．知られている

生成規則：のは GNF(グライバッハ標準形，Graibach Normal

E → add T E |TForm) [4] の LL(1) 文法に対応する ﬂat-chaining のイ

T → multiple F t |Fンターフェースを生成するアルゴリズム [5] だけであF→ifi . Lang
. rule (). nt ( ’E ’ ). arrow (). t ( ’ add ’ ). nt ( ’T ’ ). nt ( ’E ’). rule (). nt ( ’E ’ ). arrow (). nt ( ’T ’). rule (). nt ( ’T ’ ). arrow (). t ( ’ multiple ’ ). nt ( ’F ’ ). nt ( ’T ’). rule (). nt ( ’T ’ ). arrow (). nt ( ’F ’). rule (). nt ( ’F ’ ). arrow (). t ( ’i ’). terminal ( ’i ’ ). arg_type ( ’ Integer ’ ). action_type ( ’ boolean ’). start_from ( ’E ’ ). end ()図1

Python 上での入力文法の記述

sub-chaining と ﬂat-chaining の ﬂuent interface を生成する．以下では Python の EDSL で記述した文法を変換して得られた GNF の LL(1) 文法を G = (T,N, δ, S) とする．T は終端記号，N は非終端記号，δは生成規則，S は開始記号である．

3. 2. 1 εルールの除去
L(A)⊇ εとなる記号を nullable な記号と呼ぶ [6]．
ここで L(A) は，A を展開して生成される言語である．nullable な記号とその後ろの non-nullable な記号を組み合わせて，新しい記号を作る．例えば以下の規則に対して，S→aBC
図2

終端記号が受け取った引数を処理するメソッド

B→bD|εC → c D |e

開始記号：ED→dを，GreenChain では Python で図 1 のように記述

nullable な記号 B とその後ろに出てくる記号 C を組する．

み合わせた新しい記号 B’ を以下のように定義する．

各生成規則は rule から始まり，nt は非終端記号，

B’ → b D C |Ct は終端記号を表す．各終端記号に対応するメソッ

記号 B が含まれる規則 S → a B C を以下の規則に置

ドの引数の型は arg type で指定する．受け取ったき換える．

引数をどのように処理するかは，GreenChain が生

S → a B’成したクラスの中にある図 2 のようなメソッドの雛

これによりεルールが除去できる．ただし，規則の右形を修正して記述する．このメソッドの戻り値の型

辺が nullable な記号で終わる場合には適用できない．

は action type で指定した型になる．arg type を指3. 2. 2 εルールなしの LL(1) 文法から GNF の定しない場合は引数はなし，action type を指定しない場合は戻り値の型は void になる．開始記号はstart from で与える．

LL(1) への変換
この変換では規則の右辺の始めの記号を，終端記号になるまで展開する．∀A ∈ N, ∀X ∈ δ (A) について，X を aY1 ...Yn (n ≥ 1, Yi ∈ N ∪ T (1 ≤ i ≤ n))

3. 2 生成アルゴリズムとする．a ∈ N の場合，δ（A）から X を削除して，GreenChain は与えられた LL(1) 文法からまずε以下の規則をδ (A) に追加する．

ルールを除去し，これを GNF の LL(1) に変換し，∀Z ∈ δ (a).

A→a

ZY1 ...Yn
さらに X を Z に置き換えて，a ∈/ N となるまで繰りA → aY1 ...Yn (n >= 1, a ∈ T, Yi ∈ N (1 <=返す．左再帰があるとこの繰り返しは停止しないが，i <= n))

LL(1) は左再帰を許さないので，繰り返しは停止す
る．このようにしてεルールを含まない全ての LL(1)
文法を GNF に変換できる．

3. 2. の規則の右辺に開始記号が出現しない．
Yi ̸= Sf irstG (A) は文法 G における A を展開して得られる

3. 2. 3 GNF の LL(1) か ら ﬂat-chaining とsub-chaining の 両 方 の ﬂuent interface の生成終端記号列の最初になり得る記号の集合である．

(i) G が 1. を満たすとき，G が空列を生成する非終端記号を含む場合を除いて G’ も 1. を満たす

ここでは Yamazaki アルゴリズム [3] を応用したアことが示されている [3]．

ルゴリズムで生成をおこなう．アルゴリズムは，GNF(ii) G が 2. を満たすとき，の LL(1) から ﬂat-chaining の ﬂuent interface を生

Asubchain が終端記号であることから規則 A →成するツールが存在することを仮定する．まず 3.2.2

Asubchain は 2. を満たす．前提からδ (A) の規の変換で得られた文法 G から sub-chaining の表現を則も 2. を満たすから，δ’(A) = {Asubchain } ∪埋め込んだ次のような文法 G

δ (A) の規則も 2. を満たす．

= (T’, N, δ’, S) を得る．

T’ = T ∪ {Asubchain |A ∈ N}
δ’(A) = {Asubchain } ∪ δ (A)すなわち G’ も 2 を満たす．

(iii) G が 3. を満たすとき，Asubchain は開始記号ではない．前提からδ (A)Asubchain は，A に対応する sub-chaining を表現するの規則も右辺に開始記号を含まないから，δ’(A)記号である．次に GNF の LL(1) から ﬂat-chaining= {Asubchain } ∪ δ (A) の右辺に開始記号が出の ﬂuent interface 生成器で，G’ から ﬂat-chaining現しない．の ﬂuent interface を生成する．これは G に対応すすなわち G’ も 3. を満たす．

る ﬂat-chaining と sub-chaining の両方を表現する

以上のことから入力文法 G が空列を生成する非終端

ﬂuent interface である．

記号を含まない GNF の LL(1) なら，変換後の文法上のアルゴリズムは Yamazaki のアルゴリズムと同

G’ も GNF の LL(1) になる．

じであるが，Yamazaki アルゴリズムは任意の LL(1)から ﬂat-chaining の ﬂuent interface を生成するツー4 利用例

ルの存在を仮定している．本論文のアルゴリズムは，3.1 節で示した加算と乗算の前置記法を表現する

GNF の LL(1) から ﬂat-chaining の ﬂuent interface

文法から生成される ﬂuent interface のプログラムをを生成するツールが存在することを仮定するので，そ図 3, 4 に示す．Fluent interface のクラスは，各スの正しさを示すためには別途証明が必要である．

タックを表すクラス，初期状態を表すインスタンス，G が空列を生成する非終端記号を含まない GNF の各メソッドが呼ばれた時の動作を利用者が書き込む

LL(1) なら，G’ も GNF の LL(1) になる．G = (T,ためのメソッドを持つ．各スタックを表すクラス (SEN, δ, S) が GNF の LL(1) 文法の時，以下の条件が等) には，スタックの状態を表す変数 rest と，そのス満たされる．

タックがトップにある時に呼び出し可能なメソッド

1. ∀A ∈ N, ∀X, Y ∈ δ (A).
X ̸= Y → f irstG (X) ∩ f irstG (Y ) = φ
2. ∀ A ∈ N, δ (A) の規則が以下のいずれかになる．

A → ε (A = S のときのみ)が含まれている．これにより図 5 のように，methodchaining の入力途中では，次に選択できるメソッドが表示される．
また図 6 のような SQL を表す入力文法から，図 7の よ う な sub-chaining の 表 現 を 含 む ﬂuent inter-図3

生成された ﬂuent interface

図4

生成された ﬂuent interface(続)face が生成される．最後の Main クラスは生成さンスタンスをフィールドの値に持つ．Subchain をれた ﬂuent interface の利用例である．whereClause

受け取るメソッドの引数の型は，引数となる sub-

メソッドの引数が subchain になっている．この ﬂu-chain におけるスタックの底に対応する型である．

ent interface のクラス FI のインスタンスは外側の非終端記号 SelectQuery，WhereClause に対応する

chain と subchain の初期状態に対応する 2 つのイ

sub-chaining 表現のための終端記号に対応するメ図5

補完候補のメソッドの表示

fi . Lang. rule (). nt ( ’ SelectQuery ’ ). arrow (). t ( ’ selectFrom ’ ). nt ( ’ WhereClause ’). rule (). nt ( ’ WhereClause ’ ). arrow (). t ( ’ where ’). terminal ( ’ selectFrom ’ ). arg_type ( ’ String ’ ). arg_type ( ’ String ’ ). action_type ( ’ void ’). terminal ( ’ where ’ ). arg_type ( ’ String ’ ). action_type ( ’ void ’). start_from ( ’ SelectQuery ’ ). end ()図6

SQL を表現する入力文法の記述

ソッド selectQuery と whereClause が追加される．

selectQuery が SelectQuerysubchain ，whereClause

6 まとめが W hereClausesubchain に対応する．

本論文は，Python 上の EDSL で BNF 風の文法を記述すると，ﬂat-chaining と sub-chaining の両方を5 関連研究

表現する Java の ﬂuent interface を生成するツールをSub-chaining を表現できる ﬂuent interface 生成提案した．sub-chaining と ﬂat-chaining を表現する

器 Silverchain [7] が提案されている．Silverchain は元の入力文法が空列を生成する非終端記号を含まない

LL(1) の部分集合から sub-chaining と ﬂat-chaining

GNF の LL(1) なら，GNF の LL(1) に sub-chainingを生成できるが，GreenChain とは異なり，部分集合の表現を埋め込めることを示した.

が不明である．また LR(1) など大きい文法クラスに対応する ﬂuent interface 生成器が提案されている [8]参 考 文 献が，sub-chaining には対応していない．

[1] Tomoki Nakamaru, Tomomasa Matsunaga, Tetsuro Yamazaki, Soramichi Akiyama, and Shigeru
Chiba. An empirical study of method chaining injava. In Proceedings of the 17th International Conference on Mining Software Repositories, MSR ’20,
p. 93–102, New York, NY, USA, 2020. Association
for Computing Machinery.
[2] A. M. Keshk and R. Dyer. Method chaining redux: An empirical study of method chaining in java,
kotlin, and python. In 2023 IEEE/ACM 20th International Conference on Mining Software Repositories (MSR), pp. 546–557, Los Alamitos, CA, USA,may 2023. IEEE Computer Society.
[3] Tetsuro Yamazaki, Tomoki Nakamaru, andLL(1) 文法の ﬂat-chaining の ﬂuent interface 生成器が存在すると仮定して，それを利用して sub-chaining の表現も可能にする手法が提案されている[3]．しかし該当する ﬂat-chaining の ﬂuent interface

は我々の知るかぎり存在しない．本論文は GNF で書ける LL(1) の ﬂat-chaining の ﬂuent interface 生成器が存在する，というより現実的な仮定を置いて提案をおこなっている．

Shigeru Chiba. Yet another generating method ofﬂuent interfaces supporting ﬂat- and sub-chainingstyles. In Proceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2022, pp. 249–259, NewYork, NY, USA, 2022. Association for Computing
Machinery.
[4] Sheila A. Greibach. A new normal-form theorem for context-free phrase structure grammars. J.
ACM, Vol. 12, No. 1, pp. 42–52, jan 1965.
[5] Hao Xu. Erilex: An embedded domain speciﬁc language generator. In Jan Vitek, editor, Objects, Models, Components, Patterns, pp. 192–212,Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.

[6] D.J. Rosenkrantz and R.E. Stearns. Properties ofdeterministic top-down grammars. Information andControl, Vol. 17, No. 3, pp. 226–256, 1970.
[7] Tomoki Nakamaru, Kazuhiro Ichikawa, Tetsuro
Yamazaki, and Shigeru Chiba. Silverchain: a ﬂuent
api generator. SIGPLAN Not., Vol. 52, No. 12, pp.
199–211, oct 2017.
[8] Yossi Gil and Tomer Levy. Formal Language
Recognition with the Java Type Checker. In Shriram Krishnamurthi and Benjamin S. Lerner, editors, 30th European Conference on Object-OrientedProgramming (ECOOP 2016), Vol. 56 of Leibniz
International Proceedings in Informatics (LIPIcs),
pp. 10:1–10:27, Dagstuhl, Germany, 2016. Schloss
Dagstuhl – Leibniz-Zentrum für Informatik.

図7

Sub-chaining の表現を含む文法の ﬂuent interface