情報処理学会論文誌. プログラミング 49(SIG 1(PRO 35)), 117-126, 2008-01-15

1

Packrat Parsing のメモリ効率の改善手法
○水島

宏 太†

前 田 敦 司†山 口 喜 教†Packrat parsing は，バックトラック付き再帰下降構文解析にメモ化を組合せた構文解析法であり，
parsing expression grammar(以下 PEG) で記述できる広範囲の文法を入力サイズの線形時間で解析することができるという特徴を持っている．しかし，packrat parsing には，メモ化を行うために入力サイズに比例する記憶領域を要するという欠点がある．本論文では，カット演算子を PEG に加えることにより，不要な記憶領域を削除する機能を持つ packrat パーザ生成系を提案する．カットはProlog から借用した概念であり，構文規則中でカットより後ろでバックトラックが不要な場合にそのことを処理系に指示し，不必要なバックトラックが起こらないようにするための機能である．カットの評価によって，ある入力位置より前にバックトラックしないということが判明した場合，その入力位置より前にバックトラックしたときのために使用されているメモ化領域を動的に削除し，再利用することができる．我々は，構文規則中にカットを適切に挿入することで，多くの実用的文法について
有界なメモリ量で解析できるパーザを生成可能と考えている．一方，カットによるメモリ効率の改善
は，パーザ生成系のユーザが手動でカットを挿入しなければいけないという問題点があるが，本論文ではこの問題点を解決するために，解析する言語の構文の意味を変えない範囲でカットを自動的に挿入する手法と，不要なメモ化が行われている箇所を検出して必要な記憶領域を静的に削減するための手法についても提案する．

Improvement technique of memory eﬃciency of Packrat Parsing○ Kota Mizushima,† Atusi Maeda† and Yoshinori Yamaguchi†
Packrat parsing is a parsing technique that combines memoization with backtracking recursive descent parser. It can handle any grammars that can be expressed in powerful grammar
notation called parsing expression grammar (PEG). Generated parsers can analyze its input
in linear time. However, to memoize intermediate result, packrat parsing requires storage area
proportional to the input size. In this paper, we propose the packrat parser generator systemthat disposes unnecessary storage area by adding the notion of a cut operator to PEG. Cutoperators is the notion we borrowed from Prolog that can be used by programmers to ‘cut
oﬀ’ an alternative execution branch of a choice point in a syntax rule when the alternative
should not be tried for suppressing unnecessary backtracking. When an alternative is removedby execution of a cut operator (and thus the parser can make sure that no backtracking canoccur before a particular input positon), the memoization storage kept against backtracking
can be deallocated and reclaimed dynamically. We believe that, for most pratical grammars,
parsers which only use bounded memory size can be generated by appropriate insertion of cut
operators in syntax rules. Although memory eﬃciency that can be achieved by hand-insertionof cut operators would be valuable, it is awesome and error-prone. In this paper, we also propose a technique to reduce required storage area by statically detecting syntax rules which
memoization is unnecessary and another technique for automatically inserting cut operators
without changing meanings of syntax rules.

1. は じ め にの場合文法が複雑であり，yacc1) (bison) などの一般的に使用されているパーザ生成系が生成する LALR(1)

近年，Web アプリケーションの開発をはじめとするなどの構文解析アルゴリズムを用いたパーザでは解分野で，Ruby などのスクリプト言語と呼ばれる種類

析するのが困難である．各スクリプト言語の処理系はのプログラミング言語が急速に普及してきている．ス

ad hoc な手法を取ることで対応しているが，そのた

クリプト言語は C や Java といった言語と比べて，多く

めに文法の記述が煩雑になり，メンテナンスが困難に† 筑波大学システム情報工学研究科
Graduate School of Systems and Information Engineering, University of Tsukuba

なるという問題がある．例えば，プログラミング言語

Ruby の処理系はパーザ生成系として yacc を使用しているが，その入力ファイルのサイズは 6000 行以上

2におよぶ (Ruby1.8.6)．また，スクリプト言語には式どに比べて一般的に実行性能が悪いという点である．

を埋め込める文字列など，字句要素に構文要素を埋めこの点も，同様に大規模なファイルの解析を行う場合

込む機能を持っているものが多いが，このような機能に問題になる．

は字句解析をベースとした構文解析アルゴリズムではad hoc な手法を使わなければ解析を行うことができ

Packrat parsing は parsing expresssion grammar

ない．

2. Packrat Parsing(Ford02)
Packrat parsing

3. Parsing Expression Grammar

2)は Ford が 2002 年に発表した構(PEG) と呼ばれる形式文法をベースにしているた
め，PEG について簡単な説明を行っておく．PEG は，

BNF に類似した記法を用いて文法を表現する．PEG

文解析アルゴリズムである．Parsing expression gram-は任意個の構文規則の集合 R および開始記号 S(厳密mar(PEG)3) という形式文法をベースにしており，決には開始式であり，任意の式をとることができるが，定的な任意の LR(k) 言語および，一部の文脈依存言

ここでは非終端記号のみをとることとする) からなっ語を入力の長さに対して線形時間で解析することがており，構文規則は N ← e という形をとる．N は非できる．Packrat parsing を使えば，yacc が生成する

終端記号であり，e は parsing expression という式を

LALR(1) パーザよりも広範囲の言語を解析すること表す．以下は PEG の式の主要な構成要素である．

ができる．また，packrat parsing のアルゴリズムは字句解析を前提としないアルゴリズムであるため，前述の式を埋め込み可能な文字列といったものも簡単に解析できる．

Packrat parsing の概念はシンプルであり，backtrack recursive descent parsing(以下 backtrack parsing) に対してメモ化を追加したものである．Backtrackparsing では構文規則を，解析対象の部分文字列を引数に取る構文解析関数として実装する．関数は解析が

ε

:

空文字列

"s"

:

文字列リテラル

N

:

非終端記号

e1 e2

:

式の列

e1 / e2:

優先度付き選択e∗:

0 回以上の繰り返し&e:And-predicate!e:

Not-predicate

成功したか失敗したかを示す情報を返し，成功した場

ここで，BNF の | と違って / には順序に意味があ

合には非終端記号にマッチした部分を入力から除いたるという点に注意する必要がある．つまり，PEG に残りの部分文字列も返す．構文規則の右辺に複数の選おいて e1 / e2 と e2 / e1 は等価ではない．これは，択肢があった場合は，最初の選択肢をまず試し，成功

e1 / e2 が単に e1 と e2 のどちらかにマッチするといした場合はその結果を返し，失敗した場合はバックト

う定義では無く，最初に e1 にマッチするかどうか試

ラックして次の選択肢を試すという動作を行う．Pack-

して，失敗したらバックトラックして e2 にマッチする

rat parsing ではそれに加えて，各部分文字列に対す

か試すという動作を表しているためである．また，∗る解析結果をメモ化しておき，同じ部分文字列に対しは正規表現における繰り返しと異なり，一度繰り返して同じ解析関数が呼び出された場合はメモ化しておいにマッチしたら，後続の式が失敗してもバックトラッ

た結果を返すという動作を行う．Backtrack parsing

クを行わない点に注意する必要がある．これは，例えでは，入力の長さに対して最悪の場合解析に指数関数ば e1 ∗ e2 という式があったとき，e1 ∗ にマッチした時間かかるのに対して，packrat parsing ではメモ化

後に e2 で失敗しても，e1 にバックトラックして繰りによって線形時間で解析を行うことができる．

返しをやり直すことは無く，e1 ∗ e2 全体が失敗する

しかし，packrat parsing には二つの問題点が存在すということである．この動作は，最近の言語におけるる．一つ目の問題点は，メモ化を行うため，必要な記憶

正規表現ライブラリでサポートされている強欲な繰り領域が入力長に対して線形に増大するという点である．

返し演算子と呼ばれる演算子の動作に類似している．

この点は，プログラムが機械的に生成した巨大なソー& は先読みを行う演算子であり，式 e にマッチするかスコードなどを解析する場合に問題になる．Ford のを試して，マッチした場合に成功するが，入力を消費

packrat parsing の論文2) では，大規模な XML ファ

しない．! は否定先読みを行う演算子であり，e にマッ

イルの解析などには packrat parsing には向かないとチするかを試して，マッチしなかった場合に成功するされている．二つ目の問題点は，packrat parsing はが，入力を消費しない．

バックトラックやメモ化を行うために，LALR(1) な3て，メモ化のための記憶領域を除去できる．次に第二4. 提 案 手 法の問題点について考えると，カットを適切に挿入する

4.1 カット演算子

ことでバックトラックの回数を削減でき，また保持す本研究では，packrat parsing の問題点を改善する

るデータ量を削減できるために，ガベージコレクショための手法として，PEG へのカット演算子 (以下カッンによるオーバーヘッドを減らすことができると考えト) の導入を提案する．カットは Prolog

4)

から借用し

られる．

た概念であり，本研究では e1 ↑ e2 / e3 という形で，4.2 カットの定性的な性質/ の左辺に挿入できる演算子として定義する．カット

前節で，カットによってメモリ効率を改善できるとは次のように動作する．まず最初に，e1 のマッチを試いう事を述べたが，どの程度改善できるのかについて行する．マッチに成功した場合，次に e2 のマッチをは述べなかった．この節では，カットによるメモリ効

試行する．e1 のマッチに失敗した場合，e1 のマッチ率の改善がどのような性質を持つのかについて述べの開始位置にバックトラックして，e3 のマッチを試行る．まず，前節のカットを挿入した算術式の PEG にする．e1 e2 / e3 との違いは，e2 のマッチに失敗した

ついて，E に対して入力を構文解析することを考える．

場合に，バックトラックして e3 のマッチを試さずにカットが入っているため，P "+" または P "-" にマッ

式全体が失敗することである．つまり，カットによっチした後，現在の入力位置までのメモ化領域を除去すてバックトラックを抑制することができるといえる．

ることができる．P にマッチする文字列の長さは常に

ここで，カット (図の中では ↑ 記号で表記) を使っ1 であるため，2 文字読むたびに現在の入力位置までて定義した次の算術式の PEG に入力"a+"が与えられのメモ化領域を除去できる．つまり，メモ化に必要なた場合を例として，カットがどのように動作するかに領域の空間計算量は O(1) である．

ついて説明する．

E←

P "+" ↑ E / P "-" ↑ E / P

P←"a" / "b" / "c";

ま ず，入 力"a+"が 与 え ら れ る と ，最 初 は 上 か らE("a+")，P ("a+") の順番で構文規則が呼び出され，P ("a+") の中で"a"にマッチするため，マッチに成功したという情報と残りの文字列"+"が E に返される．

E の中では，P が成功したため，それに続く"+"に対

次に，算術式に括弧を許すように拡張した以下のPEG について考える．この場合，P の最大長は入力中に現れる括弧で囲まれた算術式の最大長によって決まる．そのため，入力文字列中に現れる括弧で囲まれた算術式の最大の長さを s とすると，メモ化に必要な領域の空間計算量は O(s) になる．

E←

P "+" ↑ E / P "-" ↑ E / P

P←"(" E ")" / "a" / "b" / "c"して"+"のマッチを試みる．このマッチも成功し，成

ここで，E 中に現れる P をくくり出すとともに，功したという情報と残りの文字列""が得られる．マッ"("の直後にカットを入れて以下のようにすると，"("

チが成功したため，それに続いて E("") を呼び出さまで解析した時点で他の選択肢にバックトラックする

れるが，これは失敗する．ここで通常ならば，E 中の可能性が無くなるので，メモ化に必要な領域の空間計

次の選択肢 P "-" ↑ E を試すことになるが，マッチ算量は最初のものと同様に O(1) になる．

した"+"の直後に ↑ が挿入されているため，他の選択肢を試さずに失敗したという情報を返す．
カットを導入することで，2 節で挙げた二つの問題

E←

P ("+" ↑ E / "-" ↑ E / ε)P←"(" ↑ E ")" / "a" / "b" / "c"

点を改善できる可能性がある．まず第一の問題点につ

このように，カットを挿入することによってどの程いて考える．/ の左辺の選択肢を試す際には，バック度メモリ効率を改善できるかは，文法の性質とどの程トラックに備えて，文字列中の現在の位置をスタック

度カットを挿入するかによって変化する．一般的なプにプッシュするという動作を行うことになる．カット

ログラミング言語などの文法においては，式や文など，を通過した際にはここでのバックトラックは起きず，

通常はサイズが一定以上の大きさにならない要素の長プッシュした情報は不要となるのでスタックに保存しさによって必要なメモ化領域の大きさが決まるようにた情報をポップすることができる．カットを通過した

カットを挿入して，実用的な入力についてメモ化に必場合などで，スタックが空になった場合，パーザはそ

要な領域の空間計算量が実質的に O(1) になるようにの時点で解析中の位置 i より前には決してバックトすることが可能であると考えている．なお，この節でラックしないため，文字列中の 0 から i 番目についはメモ化に必要な記憶領域の除去について述べたが，

4
パーザが保持している入力文字列のために必要な記憶領域も同様に除去することができる．

5. 関連研究との比較
2 節で述べた packrat parsing の問題点を改善する研4.3 不要なメモ化の除去
本研究では，不要なメモ化を除去するための手法に究としては，Grimm によるものが存在する5) ．Grimm

ついても提案する．Packrat parsing では全ての非終の研究では，packrat parser 生成系 Rats!を提案して端記号に対してメモ化を行うが，文法によっては静的いる．Rats!は PEG 風の文法定義を入力として与えるにある非終端記号のメモ化が不要であると判定すること，Java 言語によるパーザを自動的に生成する．Rats!

とができる場合がある．例えば，以下の PEG(開始記では処理系によるいくつかの自動的な最適化と，ユー

号は N0 とする) について考えると，N0 の解析中にザによる明示的な最適化を行うことができるように

N2 および N3 の解析が失敗した場合はバックトラック

なっており，LALR(1) パーザ生成系などと比べても，が発生せず，N0 の解析そのものが失敗するため，N2

実行性能および記憶領域の両方の点でさほど劣らないおよび N3 の結果をメモ化する必要は無いといえる．

効率の良いパーザを生成することが可能になっている．

N0←

N1 ↑ N2 / N3

N1

←

"a"

N2

←

"b"

N3

←

"c"

この節では，Rats!が提案している最適化と，本研究による最適化がどのような関係を持つかについて考察を行う．なお，最適化の名称は文献 5) のものをそのまま使用している．

5.1 Transient

メモ化が不要な非終端記号を完全に検出することはTransient 最適化は，構文規則に対して人手で tran-

困難であると考えられるため，判定は保守的に行う．

sient という修飾子を付加することで，対象となる構

大まかな方針としては，ある非終端記号について，そ

文規則の解析結果をメモ化しないようにする最適化でれが開始記号から直接・間接的に参照されていないか，ある．この最適化によって，メモ化のためのテーブル

参照されている全ての文脈においてバックトラックせのカラムからフィールドを削除できるため，メモリ効ず，呼び出し元に失敗を返すような場合に，それをメ率を改善することができる．しかし，メモ化した結果モ化が不要であると判定する．具体的には，ある非終が再利用される構文規則に対して付加すると，実行効

端記号 N について，N の中で直接参照されている非率が悪化する危険性がある．場合によっては，解析に終端記号の集合 AN の中で，失敗時にバックトラック

かかる時間計算量のオーダが O(n) より悪化する可能せず，N 自体の解析が失敗するような非終端記号の集性もある (このことは文献 5) においても述べられてい合 BN を以下のようにして求めることができる (eNる)．一方，カットによるメモ化領域の除去は，メモ化

は非終端記号 N が持つ式を表す)．

した結果が決して再利用されないことが判明した領域

BN=

B(eN )

B(e1 ↑ e2 / e3 )=B(e2 ) ∪ B(e3 )B(e1 / e2 )=B(e2 )

B(e1 e2 )=B(e1 ) ∪ B(e2 )

B(e∗)

=

∅

B(N )

=

{N }

B("s")

=

∅

B(ε)

=

∅

に対してのみ行われるため，時間計算量のオーダは変化しない．また，その性質からわかるように transient
最適化によるメモリ効率の改善は係数レベルの改善であり，空間計算量のオーダは変化しない．それに対してカットは適切に挿入することによって空間計算量のオーダを改善することができる．Transient 最適化はカットと直交しており，併用することが可能である．

5.2 Nontransient
Nontransient は，transient が指定されていない構

ここから，AN の中で失敗時にバックトラックする

文規則に対して，ある条件を満たす場合に処理系が自非終端記号の集合 CN を AN − BN と定義すること

動的に transient を付加する最適化である．この最適∗と非終端記号の集合 V ，開ができる．CN の閉包 CN化の利点は，人手で transient 修飾子を付加する手間

始記号 S に対して，V − CS∗ を求めることで，明らかが必要無いことである．処理系が自動的にメモ化しなにメモ化が不要な非終端記号の集合を求めることがでい規則を決定するという点で本研究の不要なメモ化のきる．

除去と類似している．どのような構文規則を transientをみなすかについては，現時点では他の構文規則からの参照が 1 箇所しか存在しない場合にのみ transient5とみなすということが文献 5) において述べられている．そのため，どのような構文規則を transient とみ

まう☆ ．

5.5 考

察

なすかという点で本研究における不要なメモ化の除去

Packrat parsing では，メモ化のために構文規則の手法とは異なると言える．Nontransient 最適化もカッ

数 m(入力によって変化しないため，定数とみなすこ

トと直交しており，併用することが可能である．

とができる) と入力長 n に対して，一般にサイズ mn

5.3 Chunksのテーブルが必要である．この節で述べた Rats!のメChunks 最適化はメモ化に使用するテーブルのカラ

モリ効率に関する最適化は，いずれも空間計算量をムを複数のチャンクと呼ばれるオブジェクトに分割し，係数レベルで改善するものであり，そのため，通常の必要になった段階で各チャンクの中にメモ化領域を確

packrat parser と同様に空間計算量は O(n) のままで保することで，不要なオブジェクトのアロケーションある．このことは，Rats!においても大規模なファイルを削減するものである．文献 5) において，chunks はの構文解析は向いていないということを示している．

ヒープ利用率の改善のために最も重要な最適化である

4.2 節で述べたように，カットは空間計算量をオーダと述べられている．Transient と同様にこの最適化ものレベルで改善できるため，カットを適切に挿入する

係数レベルでメモリ効率を改善するものであり，空間

ことで，大規模なファイルの構文解析に適用できる可計算量のオーダは変化しない．Chunks 最適化もカッ能性があるという点が，Rats!の最適化手法と比較しトと直交するものであり，併用することが可能である．

た場合の提案手法の利点である．また，これらの最適

5.4 Repeated

化はいずれもカットと直交するものであるため，カッRepeated 最適化は transient な構文規則中に現れトと併用することでさらにメモリ効率を改善できる可る，繰り返し演算子を使った繰り返しに関して，それを右再帰に展開せず，単なるループとして処理する最適化である．この最適化によって，関数呼び出しの回能性がある．

6. 実

験

数を減らせるため，実行性能を向上させることがでカットがメモリ効率および実行効率にどのような影きる上に，繰り返しを右再帰に展開しないことによっ響を与えるのかを検証するための実験を行った．まてメモ化のための領域を減らすことができる．また，ず実験のために，カットの機能および不要なメモ化

右再帰に展開する場合と違って処理系のスタックを消の除去機能を持つ Java による packtrat parser 生成

費しないため，スタックオーバーフローが起こるのを系 Yapp を開発した (カットの自動挿入については未

抑制することができる．Repeated 最適化も係数レベ実装)．実験 1 と 2 では実装した Yapp に Java 言語

ルでメモリ効率を改善するものであり，空間計算量の(Java 1.4) および XML のサブセットの文法定義を与

オーダは変化しない．上で述べた他の最適化同様に，えて，カットを挿入しない場合と挿入した場合のパー

repeated 最適化もカットと直交するものであり，併用

ザを生成し (不要なメモ化の除去は未使用)，それらすることが可能である．なお，repeated 最適化には厳のパーザと Rats!(バージョン 1.11.0) から生成された

密な根拠があるわけではなく，文法定義によっては時パーザで，実行効率およびメモリ効率を測定した．実間計算量が悪化する危険性がある．例えば，以下のよ験 3 では Java 言語および XML のサブセットの文法

うな文法定義を考える．

定義に対して，提案した不要なメモ化の除去手法がどA ← (&((a / b)∗) (a / b))∗の程度効果があるのかを調べた．なお，Java の文法
定義については，Rats!版は処理系に付属の Java 1.4

ここで，構文規則 A はメモ化する必要が無いため，のパーザをそのまま使用し，Yapp 版については文献

transient とみなすことができる ( Rats!でも nontran-

6) の著者の PEG for Java 1.5 を元に，Java 1.5 で追sient 最適化によって transient とみなされる)．その加された文法を取り除いたものになっている．XMLため，repeated 最適化の対象となる．しかし，A のの文法定義については，Rats!による XML の文法定中に現れる二つの繰り返しの両方を単なるループに展開してしまうと，一文字読むごとに残りの文字列についてマッチし続ける限り先読みを行うため，入力文字
列の長さ n に対して時間計算量が O(n2 ) になってし☆

現在の Yapp の実装でも，長い繰り返しでスタックオーバーフ
ローが発生するのを防ぐために繰り返しをループに展開しているため，同様の危険性がある．ただし，今回の実験においては文法定義が上のような形にはなっていないため，問題にはならない．この問題を解決するには，ループに展開しつつ，繰り返
しの解析結果を適切にメモ化するように実装する必要がある．

6
義が存在しなかったため，Rats!版と Yapp 版の両方とElement ←も，Extensible Markup Language (XML) 1.07) を参"<" NAME (S Attribute) ∗ S? (">" ↑ Content "</" NAME S? ">"考に，実験用の入力データを解析できる最小限の機能のみを実装したサブセットになっている．なお，Rats!

/ "/>"

版の XML パーザについては，transient にしても性)能が低下しないと考えられる規則については手動で

図2

XML の PEG の一部

transient を付加してある (構文規則 24 個中 6 個に付加)．また，Rats!版の Java パーザおよび XML パーザ

実験のためにパーザに与える入力としては，Javaは，Rats!の最適化オプションは特に指定していない．

パーザについては Rats!の処理系に付属のベンチマー

最適化オプションを指定しない場合，実験に使用した

ク用 Java プログラム (41 ファイル) を使用した．ベン

バージョンの Rats!では文献 5) の Table 3. に書かれチマーク用の Java プログラムは，Java のソースコーている最適化の全てが有効な状態になる ため，5 節

ドジェネレータや暗号化アルゴリズム (Blowﬁsh など)で論じた 4 個の最適化についても有効になっている．

の実装などで構成されている．一方，XML パーザに☆

実験のために使用した XML および Java パーザは，

ついては，スロベニア語と英語の並列コーパスである，

Rats!版と Yapp 版のどちらも，入力文字列が文法に

IJS-ELAN corpus Version 2.08) のデータ 48 ファイ合致するかどうかを検査するだけのもの (recognizer)

ルからサイズが 2MB 未満である 38 ファイルを抽出であり，抽象構文木の構築は行っていない．

して使用した．使用した IJS-ELAN corpus のデータ

これらの文法定義の性質について，次のような事がはファイルサイズが大きい (1MB 以上のものが存在す

挙げられる．まず，Java の文法定義は構文規則の数る) 現実に有り得る入力であるため，巨大な XML にが多く (183 個) 複雑な文法である．また，カット有り

対するパーザの性能を評価するために適切なデータでの Java の文法では，一つの文あるいは式の最大の長あると言うことができる．

さに比例したヒープサイズが必要になるようにカット• 実験環境を挿入した．一方，XML のサブセットの文法定義は– CPU: Intel Core2 Duo 2.4GHz

構文規則の数が少なく (24 個)，比較的単純な文法で– RAM: 2.0GBある．また，カット有りの XML の文法では，コメン– OS: Windows XP Professional

トまたは要素中のテキストの最大長に比例したヒープ
サイズが必要になるようにカットを挿入した．参考の– Java 実行環境: JDK1.6.0
6.1 実

験

1

ために，以下にカットを挿入した Java の PEG の一

カットによってメモリ効率がどれだけ改善されるか部 (図 1) と XML のサブセットの PEG の一部 (図 2)を確かめるために，生成されたパーザがあるサイズを例示する．構文規則 MemberDecl は Java 言語のクのファイルを解析するのにどれだけのヒープを使用す

ラスのメンバ宣言を表現しており，構文規則 Element

るのかを計測した．パーザが必要とする最小のヒーは XML の要素を表現している．

プサイズを求めるために，JVM の起動オプションである，-Xms と-Xmx を使用した．これらのオプション

MemberDecl ←はそれぞれ，JVM が使用する最小ヒープサイズと最Type Identiﬁer FormalParameters ↑ ...

大ヒープサイズを指定するものである．このオプショ/ VOID Identiﬁer FormalParameters ↑ ...

ンを使用して JVM が使用するヒープサイズを指定で/ Identiﬁer FormalParameters ↑ ...

きる．例えば，java -Xms64m -Xmx64m Main とする/ &INTERFACE ↑ InterfaceDeclarationと，Main の実行時に JVM が使用するヒープサイズ/ &CLASS ↑ ClassDeclaration

を 64MB に指定してプログラムを実行することにな/ Type VariableDeclarator

る．これを利用して，二分探索法によって各ファイル(COMMA ↑ VariableDeclarator)∗
図 1 Java の PEG の一部に対して正常に構文解析を終了することができる最小のヒープサイズを求めた．実験の結果は図 3 と図 4 のようになった．ここで，グラフの横軸は構文解析の対象である各ファイルのサイズ (KB) を，縦軸はファイ☆

文献 5) の Table 3. に未出の最適化である-Oerrors2 および-Oleft1 は無効になっている．

ルを解析するのに必要な最小のヒープサイズ (MB) を表しており，個々の点が各ファイルに対応している．

7
なお，実験 1 と 2 ともに，1KB=210 B，1MB=220 B

ころ，共通する特徴として，一つの式や文が非常に巨の意味である．なお，-Xms オプションで指定できる大であることがわかった．今回実験に使用した PEG

最小のヒープサイズが 2MB であるため，この実験でではカットを十分に挿入し切れていないため，一つのは，パーザが必要とする最小のヒープサイズが 2MB

文や式の長さが巨大である場合，その式や文の解析を未満の場合の違いは検出できない．

終えるまでメモ化領域を削除することができないことが影響したものと考えられる．
一方，XML ファイルの構文解析については，カッ
ト無しと Rats!のどちらと比べても，カット有りの方が大幅にメモリ効率が改善されており，入力長が増えても必要なヒープサイズはほぼ変わっていない．これは，カット有りの場合では空間計算量は XML 中のテ
キストやコメントの最大長によって決まる一方で，入力に使用したファイルの性質として XML の要素の数は多いものの，テキストやコメント一つ辺りの長さは短いために入力のサイズが増大しても必要なヒープ使用量が増大せず，カット有りのパーザの空間計算量が

図 3 Java プログラムの構文解析に必要な最小ヒープサイズ

実質的に O(1) であったことと，入力のサイズが大き
い (1MB 以上) ために，空間計算量の差が明確にあらわれたためであると言える．
これらの結果から，カットを適切に挿入することによって，実用的な入力に対して空間計算量がほぼ O(1)であるようなパーザを生成することが可能であり，生成したパーザを大規模な入力に適用することが可能である事がわかる．

6.2 実

験

2

カットによって実行効率がどのように改善されるかを調べるために，生成されたパーザの構文解析速度が，設定したヒープサイズによってどのように変化するかを計測した．ヒープサイズの指定には，実験 1 と同
図 4 XML ファイルの構文解析に必要な最小ヒープサイズ

じように JVM の起動オプション-Xms と-Xmx を使用

まず，Java プログラムの構文解析については，カッとによって，ヒープサイズを 5MB に指定して構文解

ト無しに比べてカット有りの場合の方がメモリ効率が析を行った．構文解析の速度は，上記で述べたベンチ

改善しているものの，Rats!と比べた場合は，カット有

マーク用のデータの全ファイルを解析するのにかかっりでも有意な差が見られず，両方とも入力のサイズにた時間とファイルの合計サイズから求めた (10 回計測

した．例えば，java -Xms5m -Xmx5m ... とするこ

対してほぼ O(1) の空間計算量であるかのように見えした平均値を使用)．実験の結果は図 5 と図 6 のようる．これは，Java パーザの実験に使用したファイルのになった．なお，グラフの横軸は構文解析時に指定しサイズが大きいものでも 200KB に満たないものであたヒープサイズ (-Xms と-Xmx により指定) を，縦軸ることと，5 節で述べたように Rats!が空間計算量を係はそのときの構文解析の速度を表している．また，縦数レベルで改善するための様々な最適化を行っている軸の値が 0 であるデータは，対応するヒープサイズにために，JVM の-Xms オプションで指定できる最小のおいて構文解析を完了することができなかったことをヒープサイズである 2MB でも構文解析を行うことが表している．

できたことが原因であると考えられる．また，サイズ

実験の結果からはまず，カットを挿入することによっが 20KB から 40KB の間に，Rats!に比べてカット有て構文解析の速度が大幅に改善していることがわかる．

りの方が明らかにヒープ使用量が多いファイルが 2 つ

これは，必要とするヒープサイズが小さくなったこと存在するが，これらのファイルについて調べてみたとによって，ガベージコレクションのオーバヘッドが削8および表 2(XML) のようになった．
表1

Java の PEG においてメモ化される非終端記号の数
適用前
カット無し
カット有り

表2

183
183

XML の PEG においてメモ化される非終端記号の数
適用前

図5

適用後
176
176

カット無し
カット有り

Java プログラムの構文解析の速度

24
24

適用後
21
18

この結果から，カットを挿入することによって，不要なメモ化の除去手法の効果を改善できる可能性があること，どちらの PEG においても 10 個未満の少数の非終端記号のメモ化が除去可能になっていることがわかる．他の言語の文法定義についても同じ程度の数の非終端記号しか除去できないとすると，この手法の効果は，文法の規模が大きくなり複雑になるほど相対的に小さくなると言える．そのため，ある程度以上の規模の文法定義にこの手法だけを適用してもあまり効
図 6 XML ファイルの構文解析の速度減されたことやデータがキャッシュにヒットしやすく果は見込めないと考えられる．

7. 提案手法の改良案なったことなどによると考えられる．また，Java プ

カットには，使い方によっては，文法の意味を変えてログラムの解析では Rats!の方が 2〜3 倍程度高速でしまうことがある．これは，カットの挿入によって，本あるのに対し，XML ファイルの解析では Yapp の方来は起こるバックトラックが起きなくなってしまうこが 3 倍程度高速であることがわかる．原因についてとがあるためである．例えば，4.1 節の算術式の PEG

はいくつか考えられるが，まず，Java プログラムののカットを挿入する位置だけを変えた以下の文法定義

文法定義において Rats!版は処理系に付属のものをそについて考える．

のまま使用したために，Rats!において性能が出るよ
うな文法定義であったのが，XML の文法定義では同
じ PEG を元にして実装したため，Rats!で性能が出るような文法定義になっていなかったという事が考えE←

P "+" ↑ E / P "-" ↑ E / PP←↑ "a" / "b" / "c"

ここで，P の最初の選択肢で"a"の前にカットが挿られる．別の原因としては，メモ化領域のデータ構造

入されているため，"a","a+a","a-a",... という形

が Rats!と Yapp とで異なるため，それによって性能以外の式以外を解析できなくなってしまう．本研究にが変化したということも考えられる．また，これらのおけるカットは，純粋に最適化のために導入したもの結果から，カット有りのパーザが様々な最適化を行っであり，このような文法の意味を変えるようなカットている Rats!に比べても極端に遅いわけではなく，十は意図していないし，望ましく無いと考える．

分実用に耐え得ることがわかる．

6.3 実

験

3

この節では，上記のカットの問題点を改善するために，カットを自動挿入するための手法について考察を

4.3 節で提案した不要なメモ化の除去手法を Java の行う．文法の意味が変わらない範囲でカットを処理系

PEG( カット無し, あり) および XML のサブセットのが自動挿入できれば，カットを手動で挿入する危険無PEG に適用し，どれだけの非終端記号のメモ化が不しに，同等の効率を達成できる可能性がある．これは，要になったかを調査した．実験の結果は，表 1(Java)Γa ,Γb ,∆ を任意の PEG の式として，カットを Γa Γb /∆9という形の PEG の式に対して挿入して，Γa ↑ Γb /∆この式が満たされているということは，式 Γa Γb /∆aとしても意味が変わらないかどうかを判定する問題とにカットを挿入して Γa ↑ Γb /∆a としても意味が変わ考えることができる．カットを挿入しても意味が変わらないということであるため，式 Γa Γb /∆ にカットをらないことを判定するには，Γa と ∆ の受理する言語

挿入して，Γa ↑ Γb /∆ としても意味が変わらないとが disjoint であるかどうか，つまり以下の式が満たさ言うことができる．

れているかを判定する必要がある．なお，PEG が受理

ただし，この自動挿入手法には，ある式の 0 回以上のする言語 (PEL) の定義は，与えられた入力文字列に繰り返しに適切にカットを挿入できないという問題点

対して式が成功することであり，全ての入力を消費すが存在する．PEG においては，ある式 e の 0 回以上のる必要は無い ( 例えば ε という PEG の式が受理する繰り返しを，E = e E / ε という形で表現するが (e∗言語は任意の文字列を含む集合になる) ことが文献 3)はこれと意味的に同じである)，このとき，ε という必で述べられているため，判定すべき条件はこの式で良ずマッチする式が / の右辺にあるため，E も必ずマッいと言える．しかし，この問題 (PEL の disjointness

チする式になる．そのため，人手でカットを挿入するの判定) は決定不能問題であることが示されている3) ．

場合は E の直前にカットを挿入して E ← e ↑ E / ε

なお，L(Γa ) は Γa を受理する言語 (文字列の集合) をとしても意味が変わらないことがわかる．一方，自動表している．

挿入手法を適用することを考えた場合，/ の右辺の式

L(Γa ) ∩ L(∆) = ∅ε が受理する言語は，任意の文字列を含む集合であり，LR (R(ε)) も同様に任意の文字列を含む集合になるた

そのため，プログラムによってカットを自動挿入可

め，カットを挿入することができない (厳密に言えば，能かを判定するには，より保守的な判定を用いる必要

e または e を分割したプレフィクスの受理する言語ががある．具体的には，∆ を分割した ∆a と ∆b があっ

空集合である場合にはカットを挿入できる可能性があたとして (∆ = ∆a ∆b )，式 Γa Γb /∆a にカットを挿入るが，通常は，受理する言語が空集合になる式を記述

して Γa ↑ Γb /∆a としても意味が変わらないならば，する意味は無い)．プログラミング言語などの文法に同様に式 Γa Γb /∆ にカットを挿入して Γa ↑ Γb /∆ とおいて，ある要素の 0 回以上の繰り返しは頻出するた

しても明らかに意味が変わらないことと，Γa と Γb がめ，カットを自動挿入する別のアルゴリズムを組み合正規言語であるとき，問題を正規言語の disjointness

わせるなどして，この問題点を解決すれば，自動挿入を判定する問題に変換できることを利用する (正規言手法の実用性は高まると考えられる．例えば，5.4 節

語の disjointness については，それを判定する手法がでは repeated 最適化には時間計算量が悪化する場合存在する)9) ．まず，式が次の形をしているとする．こがある事を示したが，繰り返しにカットを自動的に挿こで，∆a の受理する言語が正規言語になるように ∆入することができれば，そのカットによってメモ化領を分割する．また，ある P EG の受理する言語が正規域を削除できる場合に，repeated 最適化と同様の効言語であるかどうかの判定が一般に決定可能であるか

果を時間計算量が悪化する危険性無しに達成できる可どうかは不明であるため，明らかに Γa と ∆a の受理能性がある．

する言語が正規言語になるように分割する (例えば，
式"if"の受理する言語は明らかに正規言語である)．

Γa Γb /∆a ∆b (Γa ∆a は正規言語を受理する式)
Γa と ∆a はともに正規言語を受理する式であるため，次の式が満たされるかどうかを判定できる．

LR (R(Γa )) ∩ LR (R(∆a )) = ∅R(e) : L(e) を包含する言語を表す正規表現
LR (r) : 正規表現 r が受理する言語

8. ま と め
本研究では，packrat parsing の改善手法として，
カットの導入を提案した．カットをユーザが適切に用いることによって，packrat parsing による構文解析の実行性能の向上や必要な記憶領域の削減の効果が得られることを，実験によって示すことができた．特に，提案手法によって，今まで packrat parsing が苦手であるとされていた大規模な XML ファイルの構文解析を効率良く行える事を示せたのは大きいと考えている．

LR (R(e)) は L(e) を包含しているため，上の式を今後の課題としては，まず，提案したカット自動挿

満たしているならば次の式も満たしていると言える．

入手法の改良が挙げられる．7 節で言及したように，

L(Γa ) ∩ L(∆a ) = ∅

現状の手法だけでは一般的なプログラミング言語の文法に対して十分ではないと考えられるためである．次10に，カット自動挿入手法を実装し，Rats!などとの性(平成 ? 年 ? 月 ? 日受付)

能比較を行い，カットの自動挿入がどの程度有効であ(平成 ? 年 ? 月 ? 日採録)

るかを確かめる必要がある．また，今回提案した不要なメモ化の除去手法は，あまり効果が見られなかった

水島 宏太ため，より多くの不要なメモ化を除去できる手法を考昭和 58 年生．平成 18 年筑波大学

えたい．

第三学群情報学類卒業．同年筑波大

参 考

文 献

1) Johnson, S.: Yacc: Yet Another Compiler
Compiler, UNIX Programmer’s Manual, Holt,
Rinehart, and Winston, New York, NY, USA,pp.353–387 (1979).
2) Ford, B.: Packrat Parsing: Simple, Powerful,
Lazy, Linear Time, Proceedings of the 2002 International Conference on Functional Programming (2002).
3) Ford, B.: Parsing Expression Grammars: A
Recognition-Based Syntactic Foundation, Symposium on Principles of Programming Languages (2004).
4) Colmerauer, A. and Roussel, P.: The birth of
Prolog, The second ACM SIGPLAN conference
on History of programming languages, ACM
Press, pp.37–52 (1993).
5) Grimm, R.: Better Extensibility throughModular Syntax, Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation, pp. 19–28(2006).
6) Redziejowski, R.: Parsing Expression Grammar as a primitive recursive-descent parser
with backtracking, Concurrency Speciﬁcation
and Programming Workshop (2006).
7) Bray, T., Paoli, J. and Sperberg-McQueen,
C.: Extensible Markup Language (XML) 1.0(Fourth Edition),
W3C Recommendation (2006).
8) Erjavec, T.: The IJS-ELAN Slovene-English
Parallel Corpus, International Journal of Corpus Linguistics, Vol.7, No.1, pp.1–20 (2002).
9) Hopcroft, J. and Ullman, J.: Introduction to
Automata Theory, Languages and Computation, Addison-Wesley (1979). (訳：オートマト
ン言語理論計算論 I，サイエンス社 (1984)).

学大学院システム情報工学研究科コンピュータサイエンス専攻博士前期課程入学．プログラミング言語の構文解析に関する研究に従事．

前田 敦司（正会員）

1994 年慶應義塾大学大学院理工学
研究科単位取得退学．博士（工学）（慶應義塾大学 1997 年）．1997 年
電気通信大学大学院情報システム学研究科助手．2000 年筑波大学電子・情報工学系講師．2004 年筑波大学大学院システム情報工学研究科助教授 (2007 年准教授)．プログラミン
グ言語の実装，ガーベッジコレクション，スクリプト
言語，パターンマッチングなどに興味を持つ．日本ソフトウエア科学会，ACM 各会員

山口 喜教（正会員）

1972 年東京大学工学部電子工学科卒業．同年通商産業省工業技術院
電子技術総合研究所入所．計算機方式研究室長などを経て，1999 年筑波大学電子・情報工学系教授．博士(工学）（東京大学 1993 年）．現在，筑波大学システ
ム情報工学科教授．高級言語計算機，並列計算機アー
キテクチャ，並列実時間システム，ネットワーク侵入検知システムなどの研究に従事．1991 年情報処理学会論文賞，1995 年市村学術賞受賞．著書「データ駆動型並列計算機（共著）」．IEEEComputer Society，ACM，電子情報通信学会各会員．