Search

LINE株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。 LINEヤフー Tech Blog

Blog


PEG Parser Generator + Packrat Parserを実装してみた

Masami Yonehara2018-12-20

フロントエンドエンジニアです。2年前に東京からIターンして福岡に来ました。

PEG Parser Generatorを作りたくなりました

この記事はLINE Advent Calendar 2018の21日目の記事です。

こんにちは。LINE Fukuokaのフロントエンドエンジニアの米原（@h_demon）です。 PEG parser generatorを、Packrat Parsingという手法を使うように実装してみたので、今日はその話をしようと思います。

私がPEGを知ったのは5、6年前で、CoffeeScriptとかelmとかTypeScriptとか、AltJSが実用的なものとして認知され始めた時期でした。

きっかけは確かこの記事で、当時エンジニアになりたてだった私は、コンパイラの深い知識がない今の自分でもこれなら自分で言語が作れるのではないかというのに興奮したのを覚えています。その後自分で実際にbasic.jsというBASICからJavaScriptへのトランスパイラも試しに書いてみました。…が、途中で飽きてしまってPRINTとかIFとかの基本機能しか実装できていませんでした。

そこで今回、basic.jsを完成させるのをAdvent Calendarの記事にするのもいいなと思ったんですが、basic.jsで使っているPEG Parser GeneratorであるPEG.jsを久しぶりに触っているうちに、PEG Parser Generatorそれ自体を実装してみたいという気になってきました。そこでPEGに関連する重要な概念であるPackrat Parsingを勉強しながら、自分でそれも含めて実装してみることにしました。

PEGとは何か

私はPEGとは、「ある文字列がある言語として成り立っているかを判定するルールを記述する形式的なメタ文法」であり、正規文法や文脈自由文法と同じレイヤーの概念だと理解しています。ただ、概念的な理解は今回の実装にさほど必要ではなかったので、正しく易しく表現できているか自信がありません。私と一緒にこの初出の論文を読みましょう。ただ少なくとも言えるのは、PEGがパーサーのアルゴリズムそのものを指すわけではないということです。

ではまずPEGの文法を簡単に確認しておきましょう。

  EBNF PEG
Sequence e1 e2 e1 e2
Choice e1 | e2  
Prioritized Choice   e1 / e2
Zero or more e* e*
One or more e+ e+
Optional e? e?
And predicate   &e
Not predicate   !e

詳しい解説はネット上に沢山存在するので割愛しますが、ご覧のようにEBNFの表現の一つに（EBNFはいくつかの表現方法があるようです。例えばこれはW3Cが定義しているものです）似ています。違いは先に述べたようにChoiceの働きが異なるのと、文法上に先読みが存在することです。

このPEGを使って四則演算を受理するシンプルなルールを書くとすると、例えばこのようになります。

# expressionからパースが始まるとする
expression <- additive
additive <- multitive ("+" multitive /  "-" multitive)*
multitive <- primary ("*" primary / "/" primary)*
primary <- "(" expression ")" / number
number <- digit+
digit <- ("0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9")

これに"1"という文字列が与えられたとすると、

  1. expression -> additive -> multitive -> primary と常に最も左の規則をたどっていく
  2. primaryの1つめのchoiceである"(" expression ")"の"("と一致しないので、2つめのnumberとして受理されるかが試みられる
  3. `number` -> 1つ以上の`digit` -> choice中の`"0"`は失敗するが`"1"`で成功するので、`digit`は成功する
  4. さかのぼって`primary`のchoiceが成功する
  5. 更にさかのぼってexpressionとしてのパースが成功する

というような過程を経てパースが成功するはずです。

さっきPEGはパーサーのアルゴリズムを指すわけではないと言いましたが、今の過程を見ると分かるように、「PEGはトップダウン構文解析を形式的に表したものと言える」とPEGの提唱者であるBryan Ford氏は述べています。彼によればBNFとの重要な違いの一つはPrioritized Choiceを導入したことで文法の曖昧さがなくなったことにあります。BNFの曖昧さというのは例えば

number ::= digit | number number
digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

というEBNFの文法があるとき、123が与えられると、仮にある特定のパーサーの実装を前提にしないならば、

                   ┌─ digit (1)
        ┌─ number ─┤
number ─┤          └─ digit (2)
        │
        └─ number ─── digit (3)

と解釈できるし、一方で

        ┌─ number ─── digit (1)
number ─┤
        │          ┌─ digit (2)
        └─ number ─┤
                   └─ digit (4)

とも解釈できるということです。一方でPEGはPrioritized Choiceがあると常に左からパースを試みるため、解釈に曖昧さがなく、unambiguous grammarであるとされます。

バックトラックはいつ起こる

PEGを理解するにはバックトラックの理解が必要です。バックトラックとは、ある複数の選択肢の積み重ねの中から一つの解を探す時に、前提となる選択肢を試して次の選択肢に進み、それがダメだった場合に直前の選択肢に戻って別の候補を試していくような探索手法のことを言います。したがってPEGにおいてはPrioritized Choiceが定義したルールに含まれるとき、その先で起こり得ることになります。

バックトラックはその仕組み上、例えば選択肢がk個の分岐がn層あるとすれば最悪のケースでk^nの組み合わせを試すことになるので、つまり最悪の時間計算量はO(2^n)になります。ということはそれを使うPEGパーサーの最悪計算量もそうなるということです。つらいですね。

バックトラックは一般的なアルゴリズムの概念ですが、PEGのパーサーを再帰下降構文解析器として実装する場合バックトラックを使うことになるはずで（PEGの文法を遵守しながらバックトラックを伴わない実装が可能なのかは知識不足で自信がないが、できないのでは？）、PEGを実装する上では避けて通れません。

Packrat Parsingとは

さて、本題です。 PEGはバックトラック付きの再帰下降構文解析器としてシンプルに実装できるが、入力文字列の長さに応じて指数関数的に処理時間が増えてしまうのでした。これを解決するための手法がPackrat Parsingで、解析結果をメモ化して線形時間で解析することを指します。したがってPEGに限定された最適化手法ではなく、バックトラック付きのトップダウン構文解析に対する最適化手法であるとされます。

どのように解析結果をメモ化するのかですが、1. 現在の解析しようとする位置 2. 定義の種類をキーとして、「（入力する文字列数 + 1) * 定義の種類」の大きさのテーブルに解析結果を保存します。そしてバックトラックが起こったあと、仮に同じ位置、同じ定義で解析しようとした場合、テーブルに結果があるならそれを使うこととし、解析処理をスキップします。これがPackrat Parsingの基本的なコンセプトです。

直感的にはこの論文の2枚目右上の画像や、この論文のOverviewがわかりやすいです。また、次に紹介する私の実装ではこんな感じやこんな感じに実装しています。

実際に何が起こるのかを、メモ化が有効になる例で説明します。

# 同様にexpressionからパースが始まるとする
expression <- number "+" number / number "-" number
number <- digit+
digit <- ("0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9")

に対して入力 123-4 が与えられたとしましょう。このとき以下のように解析結果が再利用されるはずです。

  1. expressionの最も左のnumberとして123のパースが成功する
  2. この時、開始位置0に対してnumberのパースを行い成功したので、解析結果の保存テーブル(0, 'number')に消費した文字数3を記録する
  3. 次に"+"のパースを試みるが、位置4の文字は"-"なので失敗する。
  4. number "+" numberは失敗し、バックトラックが発生して位置が0に戻る。
  5. number "-" numberのパースが試みられる。このとき、開始位置0に対して試行するルールはnumberであるから、テーブル(0, 'number')にすでに記録されている解析結果が呼ばれる。そして実際のパースをすることなく、文字数3が消費される。
  6. 位置4に"-"、位置5にnumberが存在するのでnumber "-" numberは成功する。かくしてexpressionは成功して文字列は受理される。

というように、バックトラック後に同じ位置の文字を同じ定義で解析しようとした場合、すでにそこが以前に解析されていたのであれば結果が再利用されます。

ほんとにそうなるの？ PEG Parser Generator "sally"で試す

…ほんとにそうなるの？ 

本当にそうなんでしょうけど、せっかくだから体感したいですよね。ウフフお任せください、こちらに実装を用意してございます。JavaScriptで書かれたのPEG Parser Generator、sallyです。もうこのAdvent Calendarのために費やした8割ぐらいの時間はこの実装でした。大変だった。

また、Packrat Parsingを試すための効果的なルールとinputも探してきました。こちらの素敵で恐ろしいルールとinputは、こちらに掲載されていたものをそのままお借りしています。

ルール

S <- A
A <- P "+" A / P "-" A / P
P <- "(" A ")" / "1"

inputの例

(((((((((((((1)))))))))))))

これをPackrat Parsingを使ってパースする場合とそうでない場合とで速度を比べてみようというものです。

さっきの例にちょっと似ていますね、でもこのルールと文字列の組み合わせの肝は、必ずすべてのAとPの組み合わせを経てから最終的にパースされることです。つまりバックトラックによる最悪のケースをほぼ再現できます。したがって愚直にバックトラックさせるならば、括弧の対応の数に応じて処理時間は指数関数的な増加をみせるはずです。

これを、以下のテスト用のスクリプトを使って試してみたいと思います。APIの解説は省略しますが、なんとなく雰囲気から分かってもらえるのではないかと思います。興味があったら公式ドキュメントもぜひ読んでみて下さい。また、実行するには事前準備として以下のコマンドを実行して下さい。

事前準備

git clone git@github.com:hdemon/sally.git
cd sally
npm i
npm run build

examples/too_many_backtracks.js

const { Parser, choice, sequence, terminal } = require('../dist/sally')
const p = new Parser()

// The definition below was borrowed from http://kmizu.hatenablog.com/entry/20090226/1235649181

p.startFrom('S') // ここから開始

p.define('S', () => p.refer('A')) // `p.refer`は他の定義への参照
p.define('A', () =>
  choice([
    sequence([p.refer('P'), terminal('+'), p.refer('A')]), // terminalは終端文字
    sequence([p.refer('P'), terminal('-'), p.refer('A')]),
    p.refer('P'),
  ])
)

p.define('P', () =>
  choice([
    sequence([terminal('('), p.refer('A'), terminal(')')]),
    terminal('1'),
  ])
)

...

console.time(label)
// この処理に掛かった時間のみがコンソールに表示される。
const result = p.parse(input, { enablePackratParsing })
console.timeEnd(label)

...

使い方は、

# Packrat Parsingを使う場合
node examples/too_many_backtracks.js -- {対応する括弧の個数}
# Packrat Parsingを使わない場合
node examples/too_many_backtracks.js --disable-packrat {対応する括弧の個数}

です。実行すると解析に掛かった時間と成否が表示されるはずです。では実際にやってみましょう。

結果とまとめ

私の環境（MacBook Pro 15inch 2017)ではこんな感じでした。たかだか1回ずつしかやっていないちょっと雑な検証ですが、Packrat Parsingがある方はだいたいリニアな感じで伸びているのが分かります。

括弧の対応個数 Packrat Parsingなし あり
1 6.185 3.226
2 6.523 3.015
3 6.384 3.714
4 11.945 4.440
5 29.945 6.761
6 49.139 6.408
7 96.700 9.415
8 214.584 9.931
9 552.517 11.807
10 1553.101 19.908

よかったよかった。余談ですが、実装初期は全然期待はずれの解析結果になったり、Packrat Parsingをしたら結果が変わったりしていました。普段Webサービスばかり書いているので、脳みそがコンピューターサイエンス方面のコードを書くのに慣れてないんだな〜と書きながらずっと感じていました。これからはもっとそういうのやっていくぞ。

さて、ではまとめです。

  • PEGはある文を受理するかどうかのルールを記述するメタ文法の一つであり、その表記法である。
  • PEGで表現できる文に対してバックトラックありの再帰下降構文解析器を実装できるが、素朴な実装だと最悪のケースでは解析に指数関数時間を要する。
  • Packrat Parsingは解析の結果をメモ化することで、線形時間で解析できるようにする最適化手法である。

です。理解してしまえばそれほど複雑なことはやっていませんね。

おわりに

この文章は多大なる仕事の時間とプライベートの時間を使って書かれました。それを認めてくれたトーク占い/CAREチームのみんな、そして妻の杏奈、どうもありがとう。明日はayasudaさんの「Ruby on Rails で作る！ Clova スキル 〜LINE 連携もあるよ〜」です。 Ruby on Rails僕も昔仕事で書いてました。楽しみですね！

参考にした記事・論文

Parsing Expression Grammars: A Recognition­Based Syntactic Foundation

Parsing Expression Grammars: A Recognition-Based Syntactic Foundation

Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking

Packrat Parsers Can Support Left Recursion

PEG基礎文法最速マスター - kmizuの日記

Recursive Descent ParserとPackrat Parser

Scalaで作るPackrat Parserコンビネータ

Incremental Packrat Parsing