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

パーサの段階的開発のための対話による文法編集に向
けて
奥田 勝己

千葉 滋

本論文では，パーサを生成することを目的とする文法を，lake 記号を用いて段階的に記述する手法を提案する．プ
ログラムの構文解析を行うパーサはさまざまなソフトウェアツールに応用されるが，パーサを生成することを目的とした文法の記述は容易ではない．この一因は文法が完全に記述し終わるまで動作確認可能なパーサを得ることが困難なことである．そこで，提案手法では lake 記号をソフトウェアにおけるテストスタブのように用いることで，編集中の文法から常に実行可能なパーサを得られるようにする．この結果，動作確認のためのテキストハイライトや文法
規則追加のための操作を例示により実現することができる．プロトタイプを用いたケーススタディでは，構文拡張のためのプログラム変換器の開発に提案手法を応用できることを確認した．

我々の lake 記号 [5] はこの労力を軽減することを目

1 はじめに的とした PEG の新しい文法記号である. Lake 記号

パーサは，コンパイラやインタプリタだけでなくは island 文法に適した最短一致を実現するためのワ

ソフトウェア開発の様々な用途に用いられる．例え

イルドカードとしての機能をユーザに提供する．ユー

ば，構文拡張のためのプログラム変換器やソフトウェ

ザは文法中で省略したい位置に lake 記号を記述する

アメトリクスの計測ツール，リファクタリングツー

ことで，比較的容易に island 文法を記述することがルなどもパーサをその一部とする．これらの用途でできる．

は，必ずしも対象言語の完全な文法を必要としない．

しかし，lake 記号を導入しても island 文法のデバッ

例えば，Java の if 文を抽出するだけであれば，Java

グは難しいという問題が残る．Island 文法が扱う言の完全な構文解析を必要とはせず，if 文のみを抽出で語は，元の完全な言語とは一致しない．このため，開きるような構文解析ができればよい．このように興発者は元の言語の仕様書と比べながら island 文法中味があるプログラム構文のみを抽出するパーサを生の誤りを見つけることはできない．したがって，開発

成可能な文法は island 文法 [4] と呼ばれる．開発者は

者は試行錯誤しながら island 文法をデバッグする必island 文法を記述することで，対象言語の完全な文法要があった．

と比べて少ない文法規則で必要なパーサを得ることが本論文では，正しい island 文法の記述を容易化すできる．Island 文法は，PEG（Parsing Expression

ることを目的とし，island 文法を対話的に編集する

Grammar）などの文法記述言語で記述することがで手法を提案する．本手法では，lake 記号をソフトウェ

きるが，興味があるプログラム構文以外に対応する規

アテストにおけるスタブのように使用することで，対則を適切に作成するためには労力が必要である．

話的かつ段階的に文法を更新するための操作を提供する．これによって小さな動作確認済みの文法規則

This is an unrefereed paper. Copyrights belong to the
Author.
Katsumi Okuda, 東京大学 / 三菱電機株式会社, The University of Tokyo / Mitsubishi Electric Corporation.
Shigeru Chiba, 東京大学, The University of Tokyo.

を組み合わせて上位の文法規則を作ることができる．
また，常に動作するパーサが得られることを利用し，例題プログラムを用いたテキストハイライトによる動作確認手段や操作適用時における候補の提示機能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

{
doit();
if (fooIsNeeded()) {foo();
if (barIsNeeded()) {for (i = 0; i < 3; i++) {bar();
if (bazIsNeeded()) {for (j = 0; j < 3; j++) {baz();
}
}
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

{
doit();
onlyWhen(fooIsNeeded());foo();
onlyWhen(barIsNeeded());
for (i = 0; i < 3; i++) {bar();
onlyWhen(bazIsNeeded());
for (j = 0; j < 3; j++) {baz();
}
}
}
図2

}
図1

入れ子になった if 文

onlyWhen 構文の例

1 のプログラムに変換する．この変換は sed による置
換のようにパターンの書き換えで実現することがでを提供する．

きる．プログラム変換器はプログラム中に下記のようなパターンを検出した時，

2 Island 文法記述時の課題{<<A>>
onlyWhen(<<B>>);<<C>>

本節では，本研究で扱う lake 記号を用いた island
文法をその応用とともに説明し，記述時における課題}を説明する．
以下のように書き換える．

2. 1 Island 文法の応用{<<A>>
if (<<B>>) {<<C>>}

本論文で対象とする lake 記号を用いた island 文法
は，一部のプログラム構文のみに興味があるような応用に適している．例えば，lake 記号を用いた island}

文法は構文拡張のためのプログラム変換器のパーサ開

ここで<<A>>, <<B>>, <<C>>はプログラムの省略を表発に便利である．以下では，特定のドメインにけるプ

す．プログラム変換器はこのパターンが見つからなく

ログラムの記述容易性や可読性を向上するための構なるまで書き換えを繰り返すことで，プログラム中の文拡張を想定し，プログラム変換器向けの island 文

すべての onlyWhen 構文を変換する．なお，onlyWhen

法の応用を説明する．

構文は図 2 の 3 行目の onlyWhen キーワードで始まっ例として，図 1 のような入れ子になった if 文が多ているのではなく，１行目の{が開始である点に注意

用される場合を考えよう．このような場合，拡張構文が必要である．プログラム変換器は onlyWhen 文自である onlyWhen 構文を導入し，図 2 のように書き

身が属するブロックの末尾を検出する必要があるた

直して入れ子の数を減らしたいとする．一見するとめ，onlyWhen 構文の開始位置は onlyWhen 文を含む

onlyWhen は，普通の関数呼び出しに見える．しかし，ブロックの開始位置の{と一致する．onlyWhen 構文

実際には与えられた式が真の場合のみ自身を囲うブの書き換えでは，onlyWhen 構文のみを抽出できればロックの末尾までの後続文を実行することを意味してよく，その前後や<<A>>，<<B>>，<<C>>の部分の詳細いる．

な構文木は不要である．Lake 記号を用いた island 文

この onlyWhen 構文は，onlyWhen を if 文に変換するプログラム変換器で実現することができる．例えば， このプログラム変換器は図 2 のプログラムを図法はこのようなパーサの生成に用いることができる．

2. 2 Lake 記号を用いた island 文法

lake 記号は<>で囲まれる．例えば，<lake>は lake 記

Island 構文解析はプログラム中で興味のある構文だ号である．また，lake 記号は非終端記号と同じようけを詳細に解析し，それ以外の部分を読み飛ばす構文に自身を左辺とする規則を付加的に持つこともでき

解析の技法である．興味がある構文を island，それ以る．付加的な規則を持たない lake 記号は，lake の内外の部分を water と呼ぶ．先述の onlyWhen の変換

側や周りの island の一部を除く任意の文字にマッチ

において，{ <<A>> onlywhen(<<B>>); <<C>> } とする特別なワイルドカード記号として機能する．ユー

いう onlyWhen 構文のパターンを見つけて，その構文

ザは lake 記号を PEG の繰り返し演算子である* や+木を得ることは island 構文解析である．{, onlyWhen,

演算子と組み合わせて使用することで，island 間の(, ), }から構成される onlyWhen 構文は island であ任意の文字列を最短一致でマッチさせることができり，その前後や内側の<<A>>，<<B>>，<<C>>は waterる．Lake 記号は，Perl や Ruby の正規表現実装におとして読み飛ばして構わない．Island パーサはしばしける 1 つ以上の任意の文字列の繰り返しの最短一致ば生成器を用いて開発され，生成器の入力となる文法である .+? と似た働きをし，island の一部または全は island 文法 [4] と呼ばれる．Island 文法は，island

体に到達するまでマッチし続ける．例として，セミコ部分に対応する文法規則と，それ以外の部分を water

ロン（;）で終了する文を island とする場合を考えよとして読み飛ばすための文法規則から構成される．

う．この文に対応する PEG の文法規則は下記のとお

water に対応する文法規則は，ワイルドカードのようりである．

に入力文字を読み飛ばすことのみできれば良い．こstatement <- <e>+ ’;’のため water 用の文法規則群は，island のための文

上記の規則において<>で囲まれた文法記号<e> が lake

法規則群より少なくて済む．したがって，island 文法記号である．この規則は，<e>+ ’;’ が入力文字列にの規則数は，対象とする言語の完全な文法と比べてマッチした時に非終端記号 statement が認識される少ない傾向にある．例えば，Python の if 文のみを抽ことを意味する．ここで<e>+ ’;’ は，’;’ で終わる出するための island 文法の規則数は，Python の完全

lake 記号 <e>の 1 つ以上の繰り返しの最短一致であな文法の規則数に比べて 82% [5] 少ない．プログラム

り，例えば x = 1; のような文にマッチする．<e>はの一部の構文にのみ興味があるソフトウェアツール

正規表現の単純なワイルドカード記号であるドットの開発では，記述量が少ない island 文法は有用であ（.）とは異なる．上記の規則において，<e>+を単純なる．しかし，water に対応する規則を書くことは容易

ワイルドカード記号を用いて.+と置き換えることはででないという問題があった．

きない．この場合. が ’;’ にもマッチしてしまうため

Lake 記号 [5] は，water のための規則の記述を簡易である．例えば，入力文字列が x = 1; y = 1; の場化することを目的とした PEG（Parsing Expression

合，正規表現の.+; は最長一致のため入力全体，すな

Grammar） [1] の構文拡張である．文法の作成者は

わち 2 つの文とマッチしてしまう．この時. は x = 1

lake 記号を用いることで island の一部を water とし直後の’;’ にマッチしている．一方，<e>+ ’;’ は 1て扱う文法を容易に記述することができる．興味がつの文にのみマッチする．このため，<e>+は.+とはあってきちんと解析したい構文であっても，その途中異なる．また， <e>+は正規表現における最短一致で部分は読み飛ばしたいときがある．例えば onlyWhen

ある .+? とも異なる．これを示すため，前述の文法

構文では，途中に現れる<<A>>，<<B>>，<<C>>の詳規則を以下のように変更しよう．

細は興味が無いため water として読み飛ばしたい. そstatement <- <e>+ ’;’ / blockのような island の内側の water を lake と呼び，lake

ここで/ は PEG の優先度付き選択演算子である．ま記号は主に lake の記述を行うための文法記号である．

た，非終端記号 block は，例えば{ k = 1; }のよう

Lake 記号は非終端記号のように文法の記述に使用すに波括弧 {} で囲まれた文字列を認識するものとすることができる．非終端記号との区別がつくようにる．修正後の statement はセミコロンで終わる最短の文字列に加えて block も認識する．上記の文法

12
3
は block が認識する文字列にはマッチしない．一方， 4<e>+ を .+?に置き換えた場合，.+?は block が認識 5
6する文字列にもマッチする．例えば，.+?は{ k = 1; 7
8において block は，island である．このため，<e>+を認識するが，本来これは block の一部として認識されるべきである．このため，block が意図通りに認program <- <sea>*<sea> <- island / water
island <’{’ <sea>* ’onlyWhen’ group ’;’ <other>* ’}’<other> <- island / water
water <- group / blockgroup <- ’(’ <sea>* ’)’block <- ’{’ <sea>* ’}’
図3

Lake 記号を用いた island 文法

識されなくなる．
パーサは，lake 記号が island やその一部とマッチ

す．<sea>は，入力文字列が island と water の両方することを防ぐため，マッチすべきでないテキストにマッチしなかった場合，最短一致のワイルドカー

パターンを知る必要がある．これらのパターンは，ドとして island またはその一部以外の任意の文字とalternative 記号と呼ばれる終端記号または非終端記マッチする．4 行目で<sea>は{の後で使用され，先述号の集合で与えられる．例えば，上述の例では ’;’の<<A>>に対応する．ここで，<sea>は island またはや block が alternative 記号である．lake 記号は，こwater に入力がマッチしなかった場合，’onlyWhen’の alternative 記号群を自動的に計算することができが現れるまで最短一致で任意の文字にマッチする．まるため，island 文法向けの最短一致用ワイルドカード

た，<sea>は，’onlyWhen’ 以外に island の一部であ記号として使用することができる．

る} や ) にもマッチしない．同様に 4 行目の<other>lake 記号は，暗黙的に alternative 記号群とマッチも<sea>と概ね同じであるが，’onlyWhen’ を除外ししないが，ユーザが lake 記号として認識したいパターない点が<sea>とは異なる．<other>の規則は，5 行

ンを明示的に指定するための手段も提供する．ユーザ

目で<sea>と同様にして与えられる．このように lake

は，lake 記号を左辺とする規則を作り，右辺にその記号を用いることで少ない規則数で構文拡張のため

lake 記号がマッチすべきパターンを記述できる．付の文法を得ることができる．

加的な規則を持つ lake 記号は，その右辺のパターン

しかし，正しい文法を記述することはそれほど容易のマッチに失敗した場合に最短一致のワイルドカー

ではない．もし 6 行目の water の規則の右辺に block

ド記号として機能する．ユーザはこの仕組みを用いを記載し忘れた場合，この island 文法から得られるて lake に入れ子になった island も記述することがでパーサは期待通りに動作しない．block を明示的にきる．

water に指定しない場合，ブロックの一部である閉じ
波括弧を island の一部として解釈してしまう．例え2. 3 記述時の課題
onlyWhen 構文の変換には onlyWhen 構文を抽出するための構文解析が必要であるが，lake 記号を用いた island 文法を使うことで少ない文法規則でそのためのパーサを得ることができる．図 3 は onlyWhen

ば，下記の onlyWhen 構文を解析するとき{ onlyWhen(x); { doit(); } }パ ー サ は ，意 図 と は 異 な り 1 文 字 手 前 で 以 下 を

onlyWhen 構文として抽出してしまう．
{ onlyWhen(x); { doit(); }構文を island として抽出するための island 文法である．図 3 では，<sea>と<other>は lake 記号である．

このプログラムを正しく解析するためには， {先述の<<A>>と<<B>>による省略箇所は<sea>*が対応

doit(); } が water として認識されるようになっし，<<C>>による省略箇所は<other>*が対応する．

ている必要がある．このためには block が water の

1 行目ではプログラム全体を lake 記号<sea>の繰

規則の右辺に記述されている必要がある．

り返しとして定義している．2 行目の規則は，lake

デバッグの対象が island 文法ではなく，完全な文

記号<sea>が island と water を認識することを示法である場合，ユーザは言語の仕様書と見比べながら

個々の規則を確認することができる．しかし，island
文法の場合，一部を省略しているのでその方法は有効でない．正しい文法を得るには，実行してみて結果を

1
2
3

program <- <lake><lake> <- string
string <- r’"([^"]|\")*?"\s*’

確認する作業を繰り返すしかない．したがって，これ

図4を効率化するツール支援が必要である．

3 対話による文法の作成
3. 1 段階的な文法の詳細化

12

本節では，小さな island 文法から開始し段階的

34に詳細化しながら目的とする island 文法を得るこ

5とができる文法編集ツール PEGSEED を提案する．

PEGSEED は文法の詳細化後も常に動作するパーサ

初期文法

grammar = rul
rule = token_rule | choice_rule |sequence_rule
token_rule = nonterminal ’<-’ regex
sequence_rule = nonterminal ’<-’ (nonterminal’*’?| lake ’*’)+
choice_rule = (nonterminal / lake) ’<-’
nonterminal (’/’ nonterminal)*
図5

生成される文法の EBNF によるメタ文法が得られるようにすることで，ユーザが詳細化するたびに文法の正しさを確認・デバッグすることができる

文法を初期文法とし，これに対する規則の追加と動作ようにする．

確認を繰り返すことで，目的の文法を作成する．図 4

常に実行可能パーサが得られるように文法を更新

が初期文法である．開始記号は program であり，プ

しながら，任意の island 文法を得られるようにする

ログラム全体を文字列リテラルまたはワイルドカー

ことは容易ではない．そこで，PEGSEED では，編

ド記号でマッチさせる．文字列リテラルを初期文法で集可能な PEG のメタ文法を定め，そのメタ文法に基認識させるのは，文字列中には任意に文字列が含まづく文法規則を生成可能な UI 操作を提供する．ユーれる可能性があるため，その一部を誤って別の規則で

ザは，PEGSEED の提供する UI 操作で island 文法

認識することを防ぐためである．ユーザは，初期文法に規則を追加していくことで，メタ文法から生成可能から開始し，PEGSEED が提供する操作を適用するな任意の island 文法を作成することができる．

ことで段階的に新しい規則を追加し，文法を更新す

UI 操作で追加する規則には lake 記号を使うこともる．文法の更新は，主に（1）新しい字句を認識するできる．PEGSEED における lake 記号の利用は，ソための規則の追加，（2）既存規則の左辺の非終端記号

フトウェア開発におけるテストスタブの利用に似ていや lake 記号を組み合わせた新しい規則の追加によっる．ソフトウェアの開発ではテスト済みのモジュールて行われる．新しい規則を追加するとき，その一部をを結合することで，より大きなモジュールの試験を進省略することができる．省略したい部分に lake 記号

める．一部のモジュールが未実装の場合，代わりに簡をワイルドカードとして使うことで，一部を詳細化せ単な実装のプログラムをスタブとして用いることで，ずに済む．

上位モジュールの試験を進めることができる．文法のPEGSEED が提供する操作は，図 5 の EBNF に作成にも同じアプローチを適用することが提案手法

よるメタ文法で表現される PEG を生成することがのアイデアである．テスト済みの文法規則を組み合わできる．1 行目のメタ文法規則が示すように生成せてより大きな文法規則を作成する．一部の文法規される PEG は 1 つ以上の文法規則（rule）から構則が未作成の場合，その規則に対応する入力文字列成される．また，PEGSEED が生成する各文法規

を lake 記号で読み飛ばす．すなわち，lake 記号をテ

則 (rule) は，token_rule，sequence_rule または

ストスタブのように使用する．

choice_rule のいずれかである．PEGSEED では，
この３種類の規則それぞれを生成するための操作を

3. 2 編集対象文法のメタ文法

提供している．token_rule が対応する規則は，字句提案手法では，すべてを water として扱う islandを認識するための規則である．また・sequence_rule

が対応する規則は，定義済みの非終端記号や lake 記
号を組み合わせて作られる規則である．新しく作成した規則の左辺の非終端記号は，必ず choice_rule と対応する規則の右辺に追加される．

3. 3 ツールによる文法の編集支援
PEGSEED では，編集中常に動作するパーサが得られることを利用し，文法の動作確認や規則追加のためのツール支援が可能である．編集中の文法から

図6

字句規則を追加するためのダイアログ

パーサが得られるため，PEGSEED は対象言語の例
題プログラムをリアルタイムで構文解析した結果かる onlyWhen は，2 行目の規則の右辺にも加えられる．

ら，各規則が例題プログラムのどこにマッチしたかをユーザは PEGSEED が提供する字句追加操作を用い常に取得できる．PEGSEED は，例題プログラム中て，この文法の更新を行うことができる．ユーザは，においてユーザが選択した規則とマッチする部分を

PEGSEED 上のテキストエディタで図 2 のプログラ

ハイライト表示する．また，例題プログラムのテキムを開き onlyWhen キーワードの 1 つを選択してかスト領域をユーザが選択すると，PEGSEED は，そら字句追加の操作を選択する．すると，PEGSEEDの領域と対応する文法記号の一覧を構文木から得る．

は図 6 に示すダイアログを表示する．ユーザは，ダイ

PEGSEED では，これを用いて例題ベースの GUI 操

アログ上で新しく追加する規則の左辺の非終端記号と作によって新しい規則を追加することができる．

右辺の正規表現を入力することができる．PEGSEED
はユーザが選択したテキストからこれらの初期値を作

1
2
3
4

4 ケーススタディ

成することができる．また，図 6 のダイアログでは新文法編集システム PEGSEED のプロトタイプを用しく作成した非終端記号をどの規則に加えるかを選択

いて構文拡張のための文法を作成し，提案手法の有できる．PEGSEED はユーザが選択したテキストの用性を確認した．以下では 2 節で紹介した onlyWhen

位置から追加の対象となる規則の候補を自動的に選択

構文の変換に用いる island 文法を作成したケースをする．onlyWhen の字句を追加する場合，ユーザはダ紹介する．この onlyWhen 構文の変換器は C/C++やイアログの OK をクリックするのみで期待通りの規Java など C ライクな文法を持つ言語に適用すること則を追加することができる．ユーザは，この規則を追ができる．

加した直後に，この規則が正しいことを PEGSEED

図 2 の onlyWhen 構文を構成する字句は，onlyWhen，のテキストエディタ上で確認することができる．ユー{，}，(，) である．まずは，これらを正しく認識でザが非終端記号の一覧から onlyWhen を選択すると，きるようにした後，これらを段階的に組み合わせる

テキストエディタ上で対応するテキスト領域がハイラことで最終的に onlyWhen 構文を認識できるようにすイトされる．この様子を図 7 に示す．図 7 では期待る．まず，初期文法に字句である onlyWhen を認識で通りに 3 箇所がハイライト表示されている．もし期きるように規則を追加すると下記の文法となる．

待通りにハイライトされていない場合，ユーザは前回

program <- <lake>*<lake> <- onlyWhen / string
string <- r’"([^"]|\")*?"\s*’onlyWhen <- r’(?<!\w)onlyWhen(?!\w)\s*’の操作を取り消し，再度規則を追加しなおすこともできる．

onlyWhen と同様にしてその他の字句も GUI 操作のみで追加することができる．すべての字句の規則を

4 行目が初期文法に対して新たに追加された規則で追加した後の文法は下記の通りである．

ある．4 行目の右辺は字句である onlyWhen にのみマッチする正規表現である．左辺の非終端記号であ1program <- <lake>*

図7

2
3
4
5
6
7
8
9

ハイライトによる確認<lake> <- semi / rpar / lpar / rcub / lcub /onlyWhen / string
string <- r’"([^"]|\")*?"\s*’onlyWhen <- r’(?<!\w)onlyWhen(?!\w)\s*’
lcub <- r’\{\s*’rcub <- r’\}\s*’lpar <- r’\(\s*’rpar <- r’\)\s*’
semi <- r’;\s*’

認することができる．
同様にして動作確認済みの非終端記号 onlyWhen，

group，semi を連結して onlyWhen 文を island として追加する．ユーザが onlyWhen 文を例題テキスト
で選択し，連結操作を選択すると，PEGSEED は図

8 のダイアログを表示する．図 8 のダイアログでは，新しく追加する規則の左辺の非終端記号と右辺のパある．

ターンを記述できる．右辺のパターンは複数のリスト

次にこれらの字句を組み合わせて，より大きな is-

ボックスから適切な文法記号を選択することで作成すland の規則を追加する．追加する規則は図 5 におけることができる．PEGSEED は既に onlyWhen 文のる sequence_rule に対応する規則である．まず，こ構成要素に対応する非終端記号を認識できるため，ここでは onlyWhen 構文の一部である条件部を新しいの情報を用いて適切な候補をユーザに提示する．図 8

island として追加する．条件部は () で囲まれた部分

で新たに追加した規則は下記の通りである．

である．onlyWhen 構文の変換では条件部の式の構

onlyWhenStmt <- onlyWhen group semi

water として扱うことにする．この条件部のための規則は既存の非終端記号と lake 記号を連結することで作ることができる．GUI による連結操作で条件部に対応する規則を加えた文法は下記の通りである．

3
4
5
6
7
8
9
10

連結操作のためのダイアログ

5 行目から 9 行目の規則が新たに追加された規則で文木は不要である．このため，() で囲まれた内側は

1
2

図8

program <- <lake>*<lake> <- group/ semi / rcub / lcub / onlyWhen/ string
string <- r’"([^"]|\")*?"\s*’onlyWhen <- r’(?<!\w)onlyWhen(?!\w)\s*’
lcub <- r’\{\s*’rcub <- r’\}\s*’lpar <- r’\(\s*’rpar <- r’\)\s*’
semi <- r’;\s*’group <- lpar <lake>* rpar

同様にして連結操作を繰り返して適用することで最終的に図 9 の文法を得ることができる．なお，13 行目と 14 行目は連結操作で onlyWhen 構文に対応する規則を作成した時に追加されたものである．ひとつ前の操作では 12 行目の block の規則を連結操作で追加している．仮にこの 12 行目の追加操作が漏れていた場
合，onlyWhen 構文に対応する onlyWhenConstructの規則を追加した直後に例題プログラムをハイライ
トすると図 10 のようになり，ユーザは直ちに誤りに気付くことができる．図 10 では，本来 13 行目までがハイライトされるべきところが 12 行目までしかされていない．ハイライト表示から 6 行目から始まる

ここで 10 行目が新たに加えた規則である．ユーザはgroup の規則を追加した後，期待通りの箇所にマッチすることを例題プログラムのハイライトで直ちに確

onlyWhen 構文が 11 行目の{で終了していることが分かる．11 行目の}は実際には for 分のブロックの一の更新を繰り返すことで目的とする文法を記述する．
1
2
3
4
5
6
7
8
9
10
11
12
13
14

program <- <lake>*<lake> <- onlyWhenConstruct / block / group /waterstring <- r’"([^"]|\")*?"\s*’onlyWhen <- r’(?<!\w)onlyWhen(?!\w)\s*’
lcub <- r’\{\s*’rcub <- r’\}\s*’lpar <- r’\(\s*’rpar <- r’\)\s*’
semi <- r’;\s*’group <- lpar <lake>* rpar
onlyWhenStmt <- onlyWhen group semi
block <- lcub <lake>* rcub
<other> <- onlyWhenConstruct / block / group /water
onlyWhenConstruct <- lcub <lake>* onlyWhenStmt<other>* rcub

このため，特定の構文のみを抽出することを目的とするような場合には，完全な文法を記述することなく必要なパーサを得ることができる．

6 まとめ
本論文では，段階的に動作確認をしながらパーサを開発するための対話による文法編集手法とその実装である PEGSEED を提案した．本手法では，対話的に文法に規則を追加するための操作を提供する．操作で追加する規則の一部は lake 記号で省略することができる．これは lake 記号をテストスタブのように用

図9

対話操作で作成した onlyWhen 構文のためのisland 文法

いることに相当し，編集中の文法からも常に動作するパーサを得ることができる．PEGSEED は常に動作するパーサを用いることで，例題プログラムを用いたハイライト機能や操作適用時における候補の提示機能を提供する．PEGSEED を用いて onlyWhen 構文の抽出を行い，その有用性を確認した．今後，その他の構文拡張についても有用性を確認する予定である．

参 考 文 献図 10

block の規則が漏れている時の onlyWhen 構文のハイライト部である．このことからユーザは，block を認識する
規則が抜けていることに気付くことができる．

5 関連研究対話的な文法編集ツールとして Parsify [3] や Par-simony [2] が存在するが，island 文法向きではない．
Parsify や Parsimony では，GUI 操作で文法を教える．たとえば，エディタ上で式を選択し，式であることをラベル付けといったことを繰り返すことで，文法を作成していく．しかし，途中の文法は曖昧であり，曖昧性を取り除くには完全な文法を教える必要があった．それに対し，本論文で提案した PEGSEED
では，常に動作するパーサを得ることができる文法[1] Ford, B.: Parsing Expression Grammars: A
Recognition-based Syntactic Foundation, Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,
POPL ’04, New York, NY, USA, ACM, 2004,
pp. 111–122.
[2] Leung, A. and Lerner, S.: Parsimony: An IDE
for Example-guided Synthesis of Lexers and Parsers,
Proceedings of the 32Nd IEEE/ACM International
Conference on Automated Software Engineering,ASE 2017, Piscataway, NJ, USA, IEEE Press, 2017,
pp. 815–825.
[3] Leung, A., Sarracino, J., and Lerner, S.: Interactive Parser Synthesis by Example, Proceedings ofthe 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI
’15, New York, NY, USA, ACM, 2015, pp. 565–574.
[4] Moonen, L.: Generating Robust Parsers Using Island Grammars, Proceedings of the Eighth Working
Conference on Reverse Engineering (WCRE’01),
WCRE ’01, Washington, DC, USA, IEEE Computer Society, 2001, pp. 13–22.
[5] Okuda, K. and Chiba, S.: Lake symbols forisland parsing, Art Sci. Eng. Program., Vol. 5,
No. 2(2021), pp. 11.