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

差分的に記述された解析表現文法に対する構文解析器の合成
森 健輔

脇田 建

本稿では，解析表現文法が差分的に合成される場合に，対応する差分的な構文解析器を合成することが可能であるような構文解析器の生成方法を紹介する．構文解析器が差分的に合成可能であると，文法が拡張された際にその構文解析器を高速に生成することができる．本研究では構文解析器を解析表現に対応するモジュールで構成された再帰降下解析器として生成することで，差分的な文法の合成と構文解析器の合成を対応させた．また，PEG.js という
JavaScript の構文解析器生成系を用いて，差分的に合成可能な構文解析器を生成する構文解析器生成系のプロトタ
イプを実装し，既存の構文解析器生成系との比較実験を行った．

うな構文解析器を生成する解析器生成系の構築を目

1 はじめに標とした．

ある構文を解析する構文解析器があったとき，構文本研究では使用が想定される文法を一般に用いらの一部を変更して新たな構文にする場合，通常は新たれる文脈自由文法ではなく，解析表現文法 (Parsingに構文解析器を一から生成し直さなければならない．

Expression Grammar ) [5] とした．解析表現文法は文一般に，構文解析器は生成回数が少ないので，構文解

脈自由文法と違い曖昧性がないので，構文解析器は析器の生成時間は長くても問題にならないが，解析器

複数の構文解析木を作る必要がなく，構造が単純であが扱う構文が頻繁に変更される状況では，解析器の生る．また，解析表現文法は文法が生成する言語間の組

成時間は大きな問題になる．例えば，新たなプログラ

み合わせを柔軟に行えるため，拡張性が高い．

ミング言語処理系の試作として，既存の言語に新た本研究の解析器生成系が生成する構文解析器はパッに様々な構文を追加する場合がそのような状況に当クラット構文解析器 (Packrat Parser ) [4] である．パッたる．

クラット構文解析器は解析の中間結果をメモ化するこ

文法を差分的に変更する場合，構文解析器も差分的とで，解析時間が入力文字列の長さの線形時間であるに一部分だけ変更することで変更後の文法を解析すことを保証する．この解析器は実装が容易で，解析表ることができれば，解析器生成にかかる時間を短縮で現文法と相性が良い．また，パックラット構文解析器

きる [9]．本研究では文法が差分的に合成される状況

はその構造上，プログラミング言語の解析によく用いを想定し，それに対応して差分的に合成可能であるよられる LALR 構文解析器などに比べて解析器同士のComposition of parsers for incremental Parsing Expression Grammars.
Kensuke Mori, 東 京 工 業 大 学 大 学 院 情 報 理 工 学 研 究科, Dept. of Mathematical and Computing Sciences,
Tokyo Institute of Technology.
Ken Wakita, 東京工業大学大学院情報理工学研究科，JST
CREST, Dept. of Mathmatical and Computer Science, Tokyo Institute of Technology, Japan Scienceand Technology Agency.

組み合わせが容易い．
解析表現文法は解析表現によって構成されており，
解析表現文法の変更は文法規則に含まれる解析表現の変更と等価であるといえる．ある解析表現文法の構文解析器を生成する際，文法内に現れる解析表現とそれを解析する構文解析器の構成要素を一対一に対応させておくと，解析表現が変更されたときに対応する構文解析器の構成要素を適切に変更することで構文解
析器を差分的に変更することができる．本研究では，

表1

解析表現の定義．

ここで，e, e1 , e2 は解析表現である．

解析表現文法を解析するパックラット構文解析器を，
解析表現

意味

ε

空文字列

本稿では，解析表現文法の差分的な変更を，文法の

a

終端記号

変更部分に対応する関数を変更するだけで反映する

A

非終端記号

ことが出来る構文解析器の理論と，そのような構文解

e*

0 回以上の反復

析器を生成する解析器生成系の実装について述べる．

!e

NOT 述語また，解析器生成の速度についての既存の解析器生成

e1 e2

連続

系との比較実験の結果や，関連研究について述べる．

e1 /e2

優先的選択

解析表現と一対一に対応する関数の群として構成する事で，差分的に扱えるようにした．

本稿では，2 節で解析表現文法とパックラット構文解
析器の詳細を述べ，3 節で差分的に合成可能な構文解

析表現文法では優先的選択演算子 /析器のアルゴリズムを説明する．4 節で実装技法につつめの選択肢がマッチしたか否かにかかわらず二つめを用いる．一いて紹介し，5 節でその評価を行う．6 節で関連研究の選択肢を調べる | とは異なり， / は一つめの選について述べ，7 節でまとめを述べる．

択肢にマッチしたら二つめの選択肢については調べない．例えば，文脈自由文法において A|B と B|A は

2 解析表現文法とパックラット構文解析器

意味として等価だが，解析表現文法において A/B と

本節では，本研究で構築した解析器生成系が扱う

B/A は等価ではない．また，解析表現文法では反復文法である解析表現文法の定義，性質と，パックラッ

を貪欲に行う．つまり，マッチが成功する限り入力をト構文解析器の性質について述べる．

消費する．以上の性質より，文脈自由文法と異なり，
解析表現文法には曖昧性がない．

2. 1 解析表現文法

解析表現文法は NOT 述語! をサポートしてい解析表現文法は，言語の構文を表す文法である．

る．e が解析表現のとき，!e は，e にマッチに成功しG = (VN , VT , R, eS ) の 4 つ組で表される．ここで，たらマッチ失敗を返し，マッチに失敗したらマッチ成VN は非終端記号の有限集合，VT は終端記号の有限集

功を返すという意味を表す述語で，マッチに成功した

合，R は規則の有限集合，eS は開始解析表現である．

場合でも，入力を消費しない．つまり，NOT 述語に

解析表現文法の規則は A ← e の形で記述される．

よって無限の先読みを実現できる．これは解析表現文

ここで A ∈ VN は非終端記号，e は解析表現である．

法の記述力に大きく貢献している [5]．

解析表現は表 1 の 7 種類から帰納的に定義される．上

文脈自由文法で扱える言語のクラスを文脈自由言にあるものほど優先度が高い．解析の際には，優先度語といい，解析表現文法で扱える言語のクラスを解析が高いものほど優先的に解析される．

表現言語という．文脈自由言語は和集合に関して閉じ文法が異なる構文木で同じ文字列を生成するとき，ているが，積集合，補集合に関して閉じていない [8]．

その文法において文字列が曖昧に導出されたという．

一方，解析表現言語は和集合，積集合，補集合に関し文法がある文字列を曖昧に生成するならば，その文法て閉じている [5]．なので，解析表現文法は文脈自由

は曖昧であるという．解析表現文法の一番の特徴とし文法に比べて構文の拡張に柔軟性がある文法であるて，文脈自由文法と異なり，曖昧性が無いことが挙げ

といえる．

られる．

文法 G において，G はマッチする文字列の集合

解析表現文法に曖昧性が無い理由を説明する．文脈を 持 つ ．こ れ を 文 法 が 表 す 言 語と 呼 び ，L(G) で

自由文法で用いられる OR 演算子 | の代わりに，解表 記 す る ．あ る 解 析 表 現 文 法 が 与 え ら れ た と き ，

それらの言語の和集合，積集合，補集合に対応すcompose(G, ∆G){

る文法を生成することができる [5]．解析表現文法

newR = ϕG1 = (VN1 , VT , R1 , e1S ), G2 = (VN2 , VT , R2 , e2S )（たfor r ∈ R

だ し ，VN1 ∩ VN2 = ϕ）が あ る と き ，G′ = (VN1 ∪′newR ← r′

VN2 , VT , R1 ∪ R2 , eS ) とすると，eS を適切に選ぶこfor dr ∈ ∆Rとで，L(G′ ) が L(G1 ), L(G2 ) の和集合，積集合，補newR ← dr集合を表すような文法を生成できる．
′⇒ L(G′ ) = L(G1 ) ∪ L(G2 )′⇒ L(G′ ) = L(G1 ) ∩ L(G2 )′⇒ L(G′ ) = VT∗ − L(G1 )eS = e1S /e2S
eS = &e1S e2SeS = !e1S

return (VN ∪∆VN , VT ∪∆VT , newR, eS )}図1compose 関数の疑似コード．ここで，G = (VN , VT , R, eS ), ∆G = (∆VN , ∆VT , ∆R)

2. 2 パックラット構文解析器
パックラット構文解析器は，解析時間が入力サイズ

3. 1 解析表現文法における差分的な文法の合成の線形時間であることを保証する下向き構文解析器

この節では，解析表現文法において，文法の合成をである．

どのように取り扱うのかを述べる．

一般に，下向き構文解析器の解析時間が入力サイ

解析表現文法において，文法を差分的に変更するこズの指数時間かかってしまうのは，一度解析を終え，とは，文法の規則の部分集合に対し，右辺の解析表現

既に結果が分かっているような部分的な解析に対しを変更することに当たる．文法 G = (VN , VT , R, eS )ても同じ解析を何度も繰り返してしまうためである．

の差分的な変更を考える．G に合成する文法差分をそこで，文法の非終端記号，入力位置のペアをキーと∆G とおく．∆G を，(∆VN , ∆VT , ∆R) の 3 つ組でして，キーに対する解析結果をメモ化して再利用でき定義する．∆VN は文法差分内に現れる非終端記号のるようにしておくことにより，O(| 文法の規則数 | × |有限集合，∆VT は文法差分内に現れる終端記号の有入力サイズ |) の解析時間で解析を行うことができる．

限集合，∆R は文法差分を表す規則の有限集合である．

また，パックラット構文解析器は無限の先読みが可ある文法 G に差分的に文法差分 ∆G を合成して G′

能で，LL(k) 文法や，LR(k) 文法 (k = 1, 2, . . . ) でという新たな文法を生成することを考える．式としては扱えない文法も解析することができる [4]．

表すと以下のようになる．

ただし，パックラット構文解析器には制限があり，G′ = compose(G, ∆G)

解析結果をメモ化して再利用する性質上，状態を持っcompose は，文法 G と文法差分 ∆G を受け取って，た解析は行うことができない．また，一般の下向き構

合成後の文法 G′ を返す関数である．関数内では G と文解析器と同じく，左再帰が含まれている文法を扱う∆G の終端記号，非終端記号，規則を合成して G′ を事ができないが，メモ化の情報を利用した左再帰をサ作っている．この際，G と ∆G の規則の左辺の非終ポートする拡張が提案されている [1]．

端記号が同じときは ∆G の規則を優先して G′ の規則に入れる．compose 関数の疑似コードは図 1 のよう

3 アルゴリズムになる．

この節では与えられた解析表現文法に対する，差分

文法合成の例を示す．例として，以下のような規的に合成可能な構文解析器構築のアルゴリズムを示

則 Ra を持つ解析表現文法 Ga = (VNa , VTa , Ra ) を考す．また，差分的な文法の合成と対応する構文解析器

える．

の合成のアルゴリズムを示す．

Start = Add
Add = Mul "+" Add / Mul
Mul = Num "*" Mul / NumNum = [1-9][0-9]* / [0]が与えられたとき，それを解析できるモジュールが生a

成できればよい．

G は加算と乗算が扱える簡単な算術式を表す．例
えば，12，2+3，8*3+2 などは L(Ga ) に含まれる．

一般に，下向き構文解析を行う再帰降下構文解析

ここで， " で囲まれた記号は終端記号を表し，[0-9]器は，文法の非終端記号に対応する関数をモジュールは 0/1/. . ./9 の構文糖衣を表す．また，この文法におとする．この関数は入力文字列の位置を引数に取り，いて VNa = {Start, Add, Mul, Num}，VTa ={0, 1, 2,

その位置から非終端記号に対応する解析を行い，結果

3, 4, 5, 6, 7, 8, 9, +, *}，eaS = Start である．

として解析後の入力文字列の位置を返す．文法の全て

Ga の算術式に文法差分 ∆Ga = (∆VNa , ∆VTa , ∆Ra )を合成することで，新たに減算の演算子 − を加えの非終端記号に対してこのような関数を作ることで，再帰降下構文解析器を生成することができる．

ることを考える．減算の演算子を加える際の制約とし本研究では，解析表現文法の各解析表現を解析すて通常の算術演算と同じく， − は乗算よりも結合度る関数によって再帰降下構文解析器を構成する．つまが低く，加算と同じ結合度にしたい．非終端記号 Add

り，非終端記号よりも細かい粒度で関数を生成する．

内の"+"に対応する解析表現に注目する．この解析表

この関数を解析関数と呼ぶことにする．これが上記で現を e+ とおく．e+ は入力が + だったらマッチし，述べた構文解析器のモジュールにあたる．解析関数はa

それ以外の終端記号にはマッチしない．G が減算を解析表現と入力文字列の位置を引数に取り，戻り値とサポートするには，Add が減算の形でもマッチできる

して，引数の入力文字列の位置に解析表現をマッチさようになればよいので，e+ を入力が + か − だっせた後の入力文字列の位置を返す．-1 はマッチ失敗

たらマッチし，それ以外の終端記号にはマッチしないを表す特殊な値とする．

解析表現に変えればよい．つまり，e+ ← "+" / "-"a

解析表現文法の解析表現は，表 1 の 7 種類で帰納とすればよい．これで G で減算を扱うことができ，的に定義される．各解析表現に対応した解析関数を表

減算は加算と同じ結合度になっている．

2 のように定義する．

aa以上より，文法差分 ∆G の規則 ∆R は以下のようになる．

度の高い順に解析表現を表 2 に従って解析関数に変Add = Mul ("+" / "-") Add / Mul
この文法において ∆VNa

ある解析表現文法が与えられたとき，表 1 の優先= {Add, Mul}，∆VTa ={+,-} である．

換することで，解析関数をモジュールとする構文解析器を生成できる．つまり，構文解析器は解析関数の集合として生成されるということである．各解析関数

VNa = VNa ∪ ∆VNa ，VTa = VTa ∪ ∆VTa と終端記号，aが，文法の解析表現に対応した解析器のモジュールで

非終端記号それぞれの和集合をとり，R の要素で左ある．以上のようにして，差分的な変更に対応可能な

辺が Add である規則を ∆Ra の規則で上書きすると，構文解析器を得ることができる．

a

G は減算も扱える文法となる．
3. 3 差分的な構文解析器の合成
3. 2 差分的な文法の合成に対応可能な構文解析器の生成

この節では，文法が差分的に合成されるとき，対応する構文解析器の合成のアルゴリズムを示す．

解析表現文法において，文法を書き換えるというこ

3. 1 節で述べたように，解析表現文法における差分とは規則の導出（右辺）の解析表現を書き換えるとい的な文法の合成は，文法差分を作り，終端記号，非終うことと等価である．そこで，構文解析器を文法内に

端記号，規則について，元の文法との和集合をとる操

現れる各解析表現を解析するモジュールの群として生作に対応する．3. 2 節で述べた解析表現に対応するモ成しておくことで，解析表現の書き換えによる文法のジュールで構成された構文解析器を用いることで，文変更を，モジュールの置き換えによる構文解析器の変法の差分的な合成を構文解析器に反映させることが更に対応させることができる．あとは，ある解析表現できる．

表 2 解析関数の定義．
ここで，e, e1 , e2 は解析表現，input は入力文字列である．
解析関数 fe は解析表現 e に対応しており，引数は入力文字列の位置である．

fε (pos)= pos

fa (pos)= pos + 1

(input[pos] == a)= −1(otherwise)fA (pos)fe∗ (pos)(ただし，A ← e)

= fe (pos)′(pos′ >= 0)= fe∗ (pos )(pos′ == −1)

= pos
′

where pos = fe (pos)f!e (pos)fe1 e2 (pos)= −1(fe (pos) >= 0)= pos(otherwise)= −1(pos′ == −1)= fe2 (pos′ )(otherwise)′

where pos = fe1 (pos)fe1 /e2 (pos)= pos′(pos′ >= 0)= fe2 (pos)(otherwise)′

where pos = fe1 (pos)P′ = ϕが非終端記号の場合は解析関数が異なる場合がある．

for f ∈ P

このときは ∆P の解析関数を優先して P ′ に入れる．

P′ ← f

このことからも，図 2 の疑似コードは図 1 のコード

for df ∈ ∆Pに対応していることが分かる．

′

P ← df4 実装

return P ′図2

構文解析器合成の疑似コード

本研究では，3. 2 節で述べた構文解析器を生成する
構文解析器生成系の実装を行った．実装において，構文解析器生成系の生成に PEG.js [7] を用いた．PEG.js

前述した図 1 の compose 関数を用いて，解析表現′

は JavaScript 用の構文解析器生成系で，解析表現文

文法 G に差分的な文法 ∆G を加えて G を生成する法に基づいた文法記述を与えると，対応するパックことを考える．式としては以下のようになる．

ラット構文解析器を生成する．

′

G = compose(G, ∆G)

解析表現文法自身の定義も解析表現文法で記述すG， ∆G に対応する構文解析器をそれぞれ P ，∆Pることができる [5] ので，解析表現文法そのものを解とする．P ，∆P はそれぞれ G，∆G に含まれる解析析するパックラット構文解析器を PEG.js を用いて作表現に対応する解析関数の集合である．これらを用いることができる．PEG.js を用いて，与えられた解析′′て G の構文解析器 P を生成するアルゴリズムを示

表現文法を解析関数の集合に変換する解析器生成系

す．疑似コードは図 2 のようになる． 図 2 の構文解を実装した．

析器合成の際に，P と ∆P 内に同じ解析表現に対す
る解析関数がある場合がある．解析表現が同じなら解析関数も同じになるので問題はないが，解析表現

4. 1 解析関数テンプレート

4. 3 メモ化

ある解析表現を解析関数に変換する事を考えたと

本システムはパックラット構文解析器生成系なのき，解析表現が表 1 のどの定義に当てはまるのかがで，生成される構文解析器に含まれる解析関数は，解分かれば，あとは表 2 の対応する定義に従って関数析時に戻り値のメモ化を行う．

を作ることができる．解析関数の形はそれぞれ決まっ

JavaScript には連想配列があるので，簡単にメモているので，表 2 の定義に対応した解析関数テンプ化を行うことができる．本システムでは，非終端記号

レートを作成した．図 3 は優先的選択と，非終端記号と入力位置の対を（非終端記号名）+ ”@” + (入力位に対応する解析関数テンプレートの JavaScript コー

置を表す数値) の文字列に変換し，この文字列をキードである．

として，解析関数の戻り値を連想配列に入れている．
メモ化の実装を説明する．図 3 の nonTerminal 関

4. 2 解析表現から解析関数への変換

数が非終端記号に対応する解析関数テンプレートであPEG.js によって表 1 の優先度が高い順に解析表現る．この解析関数が構文解析時に呼ばれる際，引数のを解析する構文解析器が生成できる．よって，あとはdname には非終端記号名，pos には解析を行う入力文

その解析器に解析表現を解析するたびに，それをテン

字列の位置が渡される．memory がメモ化を記録する

プレートに当てはめて対応する解析関数を作るといテーブルである．まず解析関数が呼ばれたら，先ほどう意味動作を加えてやれば良い．この構文解析器が目説明したように，関数に対応するキーとなる文字列的の構文解析器生成系となる．

(図 3 内の cacheKey 変数) を作る．その文字列を使っ解析表現は帰納的に解析されるので，ある解析表てメモ化テーブルを検索し，見つかれば入っている値

現から対応する解析関数を作り出す時に，必要な解をそのまま返す．見つからなければ，定義通りに計算

析関数がないということは起こり得ない．例えば，表を行う．以上のようにしてメモ化を実現している．

2 の fe1 /e2 を作る際には fe1 と fe2 が必要であるが，直感的には，メモ化は全ての解析関数で行った方が両方とも必ず既に作られていることが保証される．

高速な解析が行えるように思える．しかし，メモ化に

図 3 を使って，PEG.js に生成された解析器生成系

よるトレードオフが発生してしまうため，メモ化が多が，解析表現を解析関数に変換する例を紹介する．解く行われすぎるとかえって性能が落ちてしまう場合が析表現が優先的選択の形である場合を説明する．解析ある．そこで，本システムでは非終端記号に対応する器生成系が，文法の解析中に ea /eb のような形の解析

解析関数のみメモ化機能を付加した．

表現を発見したとする．このとき，構文解析器生成系
はこの解析表現に対応する解析関数 fea /eb の生成を

4. 4 エラー処理行う．なお，前述したように，fea と feb が既に生成

構文解析において，入力された文字列が文法が表すされている．優先的選択の形のテンプレートは図 3 の言語に含まれない場合，構文エラーが起こる．一般にprioritizedChoice 関数で定義されている．これを構文エラーは構文解析器が発見するエラーの大半をベースとして fea /eb を作成する．表 2 を見ると，優占めており不可避であるので，構文解析器の構文エ

先的選択に対応する解析関数 fe1 /e2 を作る際には fe1

ラー時の対応は重要である．

と fe2 が必要である．これらが prioritizedChoice

構文エラーが発生した時，入力に誤りが存在すると関数の引数の f1,f2 にあたる．prioritizedChoice

いうメッセージよりも，入力に ; が足りないといっ関数の引数の f1,f2 にそれぞれ fea , feb を束縛した

た具体的なメッセージが望ましい [10]．そこで，本シ

関数が fea /eb となる．

ステムでは構文エラー発生時に，エラーが検知された解析関数名，期待されていた文字列，実際にエラーが発生した入力の部分文字列をメッセージに含んだ

JavaScript のエラーを投げることにした．



//優先的選択テンプレート
prioritizedChoice : function(f1, f2, dname, pos, input, memory, bThrowError){var ret = f1(pos, input, memory, false); //解析関数 f1 を呼ぶ
if(ret.pos == -1) ret = f2(pos, input, memory, bThrowError); //f1 が失敗したら f2
if(ret.pos == -1 && bThrowError == true) func.err(...); //エラーを投げる
return ret;}//非終端記号テンプレート
nonTerminal : function(dname, pos, input, memory, bThrowError){var cacheKey = dname + "@" + pos, ret; //メモ化に使うキー
if(memory[cacheKey]) ret = memory[cacheKey]; //メモ化テーブルを検索
else{
ret = ns[dname](pos, input, memory, bThrowError); //非終端記号名に対応する解析関数を呼ぶ

memory[cacheKey] = ret; //解析結果をメモ化テーブルに入れる}
return ret;}
図 3 優先的選択，非終端記号の解析関数テンプレート
prioritizedChoice, nonTerminal はそれぞれ表 2 の fe1 /e2 , fA に対応した解析関数テンプレートである．

本システムでは入力が文法が表す言語に含まれて開始解析関数以外の解析関数がマッチ失敗の値を返いないと分かったらできる限り早くエラーを投げる．

したら，入力が言語に含まれていないと判断してよ

これは，構文解析が失敗したと判断するタイミングがいか考える．これは反例がすぐに見つかる．例えば，

遅くなれば遅くなるほど，文法の意味動作がユーザー

開始解析関数が f!e である場合を考える．図 2 より，の意図しない動作を起こす可能性が高くなるからである †1 ．

f!e は帰納的に fe を呼び出し，fe のマッチ成功，失与えられた入力が文法が表す言語に含まれているか
は，入力全体が文法の開始解析表現にマッチするかどり，fe はマッチ失敗の値を返すが，その場で入力が言語に含まれていないと判断することはできない †2 ．

うかに対応するので，開始解析表現に対応する解析関

つまり，解析関数 f!e は関数内で帰納的に呼び出す解数の戻り値によって判断される．この解析関数を開始

析関数 fe とマッチ成功，失敗の判断が一致しないと解析関数と呼ぶことにする．開始解析関数がマッチ成いう事が分かる．

敗に関する戻り値を逆転させることが分かる．つま功の値を返せば入力は文法が表す言語に含まれ，マッ

入力全体が言語に含まれるかどうかの判断は開始

チ失敗の値を返せば入力は言語に含まれていない．

解析関数の戻り値によって判断される．よって，開始†1 現時点では意味動作を実装できていないのでこのような心配は無いが，将来的に意味動作の実装を行う予定
である．

解析関数とマッチ成功，失敗の判断が一致する解析関†2 fe がマッチ失敗の戻り値を返したら f!e はマッチ成功の戻り値を返す

数においては，マッチ失敗が判明したら構文エラー//JSを投げることができる．逆に，開始解析関数とマッチ

MultiplicativeExpression

成功，失敗の判断が一致しない解析関数においては，
マッチ失敗が判明しても構文エラーを投げることはで= UnaryExpression(__ MultiplicativeOperator __ UnaryExpression)*

きない．
表 2 の解析関数の中で，関数内で帰納的に呼び出す
解析関数とマッチが一致しないことがあるのは，fe∗ ，

f!e ，fe1 /e2 である．これらに帰納的に呼び出される解析関数はマッチが失敗したとしても，マッチ失敗を表す構文エラーを投げてはいけない．開始解析関数とマッチ成功，失敗の判断が一致しているかどうかが分//JS**
PowerExpression= UnaryExpression (__ "**" __ UnaryExpression)*
MultiplicativeExpression= PowerExpression(__ MultiplicativeOperator __ PowerExpression)*からないためである．もちろん，マッチ失敗を表す構

図4

JS と JS**の差分

文エラーを投げてはいけない解析関数が帰納的に呼び出す解析関数も同様に，構文エラーを投げてはいけ
ない．

5 評価

そ こ で ，解 析 関 数 の 引 数 に ブ ー ル 型 の 引 数本研究で実装した構文解析器生成系と PEG.js で，

bThrowError を追加した．この引数は，解析関数

構文解析器の生成速度の比較を行った．また，生成しがマッチ失敗の値を返す際に，構文エラーを投げてた構文解析器の解析速度の性能比較を行った．

良ければ true，投げてはいけないならば false の値を持つ †3 ．開始解析関数は bThrowError を true の実行環境は以下の通りである．

CPU: 1.8GHz Intel Core i5値で呼ぶ．fe∗ ，f!e ，fe1 /e2 においては，関数内部でMemory: 8GB 1600MHz DDR3

帰納的に呼び出す関数を呼ぶ際に，bThrowError の

OS: Mac OS X 10.8.4

値を false にして呼び，それ以外の関数ではそのまま

Node.js: v0.8.17

bThrowError を渡す．

PEG.js: v0.7.0

例を示す．図 3 の prioritizedChoice 関数は，帰PEG.js ではサンプルとして，ECMA-262 の構文

納的に呼び出す解析関数 f1 を呼ぶ際，bThrowError

を表す解析表現文法で記述されたファイル (約 1530

を false で呼んでいる．これは，f1 がマッチ失敗を行) が提供されている．この解析表現文法を JS と呼示す値を返しても，prioritizedChoice 関数自身がぶことにする．

マッチ失敗になるとは限らないためである．しかし，この解析表現文法を拡張し，ECMA-262 でもとf2 を呼ぶ際は false でなく，bThrowError をそのまもと扱えない累乗演算子** を扱えるように拡ま渡している．これはなぜかというと，f1 が失敗し張する．この解析表現文法を JS**と呼ぶことにすて f2 が呼ばれる場合，f2 のマッチ成功，失敗の判断る ．拡 張 の 際 の JS と JS**の 差 分 は 図 4 で あ る ．

は呼び出し元である prioritizedChoice 関数のマッ

MultiplicativeExpression は ECMA-262 におけ

チ成功，失敗の判断と一致するからである．また，いる乗算と同じ結合度を持つ演算子を含む算術式に対ずれの解析関数においても，戻り値が −1 で，かつ，応する非終端記号である．JS**では，乗算よりも結bThrowError の値が true であればエラーを投げる

合度の高い累乗演算子"**"を含む算術式に対応することができる．

非終端記号 PowerExpression を加えている．
本システムと PEG.js で，JS，JS**それぞれに対†3 つまり，true ならば開始解析関数とマッチ成功，失敗の判断が一致し，false ならばそうでないともいえる．

し，構文解析器生成の解析時間を測定した．PEG.js
においては構文解析器の差分的な合成はサポート

されていないので，構文が差分的に合成された際もるが，差分的な構文解析器の構築と合成のみでよい

構文解析器を一から生成しなければならない．対し

JS**の構築時間は非常に短時間で実現している事がて，本システムでは，JS**の構文解析器は JS との分かる．また，本システムの生成した構文解析器の解

文法差分のみ構文解析器を構築し，JS の構文解析

析速度は PEG.js の生成した構文解析器に比べてかな

器を再利用して生成出来る．つまり，JS**の構文解

り遅い．本システムは解析速度に関する最適化を全く

析器生成時においては，図 4 の PowerExpression，

行っていないので，それが原因と思われる．

MultiplicativeExpression に対応する解析関数を

本当は OMeta や Rats!などのパックラット構文解

生成し，JS の構文解析器に差分的に合成する．解析

析器生成系とも比較を行うべきなのだが，それぞれ解器の生成時間は，100 回の平均を計算したところ表 3

析器を生成する際に与える文法の記述形式がバラバのようになった．単位は秒である．

ラであり，実験で扱う文法が巨大であるため，文法の表3

構文解析器生成の速度比較（秒）変換を行うことが出来なかった．

本システム

PEG.js6 関連研究JS

2.11 ± 0.04

1.51 ± 0.04

構文の拡張に関連する研究は数多くなされている．

JS**

0.022 ± 0.0031

1.53 ± 0.04

Alessandro Warth らは，パターンマッチングに適したオブジェクト指向プログラミング言語 OMeta を続いて，生成した解析器の解析速度の比較を行っ開発した [1]．OMeta は解析表現文法やオブジェクト

た．PEG.js ではサンプルとして JS の他に簡単な算指向のアイデアが取り入れられており，オブジェクト術演算を表す構文，JSON の構文，CSS の構文を記指向言語の継承，オーバーライドを使うことで構文の述する 3 種類の解析表現文法が提供されている．こ

拡張を実現することができる．また，OMeta は構文

れらをそれぞれ AR，JSON，CSS とする．PEG.js

だけでなく，任意のデータ構造を解析することもでき

では生成した構文解析器を JavaScript のプログラム

る．OMeta は本研究のように差分的な文法の合成をとして出力することができる．そこで AR，JSON，クラスの継承を用いて実現可能であるが，OMeta に

CSS，JS の構文解析器を生成し，JavaScript のプロ

おける解析の詳しい実装については論文内で述べらグラムとして保存した．ファイルサイズはそれぞれれておらず，現在調査中である．

12KB，55KB，394KB，583KB である．

Robert Grimm は，構文拡張に適した拡張を施しそれぞれの JavaScript コードを先ほど生成したた解析表現文法とパックラット構文解析器について述

JS**の構文解析器で解析し，その解析時間を比較しべている [6]．具体的には，構文をオブジェクト指向

た．結果を表 4 に示す．なお，解析時間は 10 回の平におけるオブジェクトの様にモジュール化し，他のオ均をとった．単位は秒である．

ブジェクトと相互に構文の情報をやり取りすること

表4

生成した構文解析器の解析速度の比較（秒）で文法の拡張を実現している．パックラット構文解析
器は遅延評価を行う関数型言語で実装されることが本システム

PEG.js

多いが，この論文では正格評価を行う命令型言語にAR

7.24 ± 0.096

0.23 ± 0.031

おける実装方法が述べられている．また，一般にメモ

JSON

36.9 ± 0.53

1.1 ± 0.10化を行うパックラット構文解析器では状態を扱う解析

CSS

260 ± 117.7 ± 0.23はできないが，この論文では状態を扱うパックラット

JS

360 ± 7.0

12 ± 1.1

構文解析器についても考察されている．筆者は論文の理論に基づいて Java で書かれたパックラット構文以上の実験より，一から構築する JS 文法の構文解解析器のプロトタイプ Rats!を実装している．Rats!

析器生成には 1.4 倍ほどの時間がかかってしまっていは論文内で述べられているさまざまな高速化テクニッ

クが施されている．構文のモジュール化によって柔軟高速化 本研究で実装したシステムは，PEG.js とな拡張を実現しているが，モジュール化することで構比較して，解析時間が遅い．Bryan Ford の Pappy [3]文の記述量が増えてしまうのが難点である．

や，Robert Grimm の Rats! [6] では解析時間を短縮

パックラット構文解析器の性能を向上させる研究もするための様々な高速化が行われている．

行われている．パックラット構文解析器は下向き構文

上記で述べたように様々な課題が残されているが，解析器の一種なので，左再帰を含む文法を扱うことが

特に解析時間の高速化は実現が難しい大きな課題であ出来ない．メモ化しておく情報を拡張することで，左る．一般に使われているパックラット構文解析は様々再帰を含む文法を扱えるパックラット構文解析器が提な高速化が試みられているので，それらを取捨選択し案されている [2]．左再帰を含む文法を扱う場合は解て取り入れる事でかなりの高速化が出来るのではな

析時間が線形であるという保証は失われてしまうが，いかと考えている．

将来本システムに導入することを考えている．
参 考 文 献7 おわりに本稿では，解析表現文法が差分的に合成される場合に，対応する構文解析器を差分的に合成することが可能な構文解析器の理論を述べ，プロトタイプの実装を行った．また，差分的な文法を付け加えていく場合，
既存の構文解析器よりも高速に構文解析器を生成出来ることを示した．しかし，まだプロトタイプの域を出ていなく，課題が残されている．
アクション 現状ではアクションや意味値が扱えていないので，解析する文字列が与えられた解析表現文
法が表す言語に含まれているかどうかの判定しか行えない．アクションや意味値をサポートすることは今後の課題である．
エラー処理 誤りが発見された場合，その瞬間に構文解析器が止まってしまうのではなく，誤りから復帰
して，解析を続行することが望ましい [10]．そうすれば，一回の解析でその先にあるかもしれない誤りも全て検出することが出来るかもしれないからである．
しかし，一般にあらゆる誤りから復帰することはかなり難しく，今回は実装を見送った．また，簡単なエラーメッセージは出せるようにしたが，まだ PEG.jsのような詳細なエラーメッセージを出すことが出来な
い．ここも今後の課題である．
左再帰の対応 パックラット構文解析器は下向き構
文解析器なので，一般に左再帰を扱うことが出来な
い．しかし，拡張を行う事で，線形時間の解析という保証は失われるが，左再帰を扱う事が可能になる [2]．

[ 1 ] Alessandro Warth, I. P.: OMeta: an ObjectOriented Language for Pattern Matching, Proceedings of the 2007 symposium on Dynamic Languages, Montrèal, Quèbec, Canada., October 2007,
pp. 11–19.
[ 2 ] Alessandro Warth, J. R. D. and Millstein, T.:
Packrat Parsers Can Support Left Recursion, ACM
SIGPLAN 2008 Workshop on Partial Evaluation
and Program Manipulation, San Francisco, California, USA., January 2008, pp. 103–110.
[ 3 ] Ford, B.:
Pappy:a Parser Generator
for Haskell http://pdos.csail.mit.edu/~baford/
packrat/thesis/, 2013/07/17 アクセス.
[ 4 ] Ford, B.: Packrat Parsing: Simple, Powerful,
Lazy, Linear Time, Proceedings of the 7th ACM
SIGPLAN International Conference on Functional
Programming, Pittsburgh, Pennsylvania, USA.,2002, pp. 36–47.
[ 5 ] Ford, B.: Parsing Expression Grammars: A
Recognition-Based Syntactic Foundation, Proceedings of the 31st annual ACM SIGPLAN - SIGACT
symposium on Principles Of Programming Languages, Venice, Italy., 2004, pp. 111–122.
[ 6 ] Grimm, R.: Better Extensibility through Modular Syntax, ACM SIGPLAN 2006 conference on
Programming Language Design and Implementation, Ottawa, Ontario, Canada, June 2006, pp. 38–
51.
[ 7 ] Majda, D.: PEG.js, Parser Generator for
JavaScript, http://pegjs.majda.cz/, 2013/07/17
アクセス.
[ 8 ] Sipser, M.: 計算理論の基礎, Vol. 1, 共立出版, 原著第 2 版 edition, 2008.
[ 9 ] 甫水佳奈子, 脇田建, 佐々木晃: 解析表現文法とScheme マクロ展開器を用いた JavaScript 向け Hygienic 構文マクロシステムの実装, 情報処理学会論文誌
プログラミング Vol.6 No.1, Jan 2013, pp. 1–17.
[10] 佐々政孝: プログラミング言語処理系, 岩波書店,
1989.