LoginSignup
35
18

More than 5 years have passed since last update.

@pocariinしくみ製作所株式会社

[ruby] Parsletで構文解析する[その1]

Last updated at Posted at 2018-06-06

Parsletで構文解析する[その1]

その2
その3

概要

普通にwebな環境な開発の場合、あまり日常的に書くことはないけども、たまに書く必要があるときに困ることの一つに文字列のパースがあると思います。

  • フォームで入力される文字列に一定のルールがあって、そのルールに従って入力内容を解釈する
  • 他システムからのデータのフォーマットに一定のルールがあるが、結構そのルールが複雑

などなど

rubyで文字列をパースする場合

  • 正規表現で頑張る
  • racc で構文解析する

などあるとおもいますが、

  • 正規表現で頑張る
    自分でもよくやりますが、一番お手軽ですぐ実装できますが、ちょっとした例外や追加ルールがでてくるととたんに無理がでてくることが多いですよね。ただ、パースするルールを自分である程度決定でき、例外をなくすために制約をつけられるのであれば一番お手軽かなとも思います。

  • racc(などのパーサジェネレータ系)
    きちんとパースはできるが、別途rubyとは異なる言語での文法ファイルがあり、一旦そのファイルをrubyのファイルに変換するフェーズがあったりお手軽でない。

など一長一短です。

Parslet

最近たまたまそのような、ある程度複雑なルールで文字列パースしたい、ということがありいろいろ調べていると

parslet

というライブラリを見つけ実際に試してみたところ非常にお手軽、かつシンプルに処理できたので記事にしたいと思います。

Parsletとは

parslet

  • PEGという規則に基づいたパーサ
  • rubyの式としてパーサが書ける
  • replを使ってインクリメンタルにパーサを作りやすい

正直PEGがどうとかはあまり理解していないですが、

  • BNF的な　AAAとはBBBまたはCCCからできてる というような宣言的な感じをrubyのコードとして作れる
  • 作った規則を試しやすい

という部分でとても効率的に作れました。

日本語であまりまとまった資料がなかったので、簡単なパーサを実際に作成することで紹介してみようと思います。

Parslet概要

parsletの処理フェーズ

Parsletは大きく２つのフェーズから処理されます。

  • parse処理
    実際に生の文字列をパースし、parsletの内部的な表現(見た目は単純なhash的な）の木構造を作成するフェーズ

  • transform処理
    parse処理で作った木構造から実際に必要となるデータ構造に変換するフェーズ

transform処理がピンとこないかもしれませんが、あとで実際の処理を見るとわかりやすいと思います。
parse処理の構文規則の記述も結構シンプルでrubyでの言語内dslを使って書けるようになっています。
また先程 インクリメンタルにパーサを作りやすい に関して次以降で実際に小さいパーサを作りそれを組み合わせて最終的に四則演算の計算機程度の言語を書いてみようと思います。

Parsletサンプル

パースの基本

  • パーサのテンプレート
require 'parslet'

# パーサ用に Parslet::Parserクラスを継承したクラスを定義すると
# 下記のrootやruleなどのパーサ定義用のDSLメソッドが使えるようになります。
class NumericParser < Parslet::Parser
  # トップレベルのパースルール
  root(:number)

  # rule(:symbol) { rules }
  # の形式で rules にマッチする文字列を symbol というルールで定義できます
  rule(:number) {
    #具体的なパースルールを記述していく。後述
    any
  }
end

# parseに渡した文字列がrootで指定したルールをみたしているなら
# パース結果のparsleでの内部表現のHash的なオブジェクトが返されます。
p NumericParser.new.parse('1')
# => "1"@0

だいたいコメントの通りですが、 ruleで具体的な文法ルールを記述していき、 rootで指定したruleがそのパーサでパースしたい全体になるようにする、という感じです。
ruleは複数定義できて、ruleの定義に別のruleも使えます。

パースルール概要

number ルールで any というルールを使いましたが、ここに組み込みのルールや自分で定義したルールを組み合わせて大きなルールを作っていきます。

組み込みのルールとしては

ルール名 内容
any 任意の一文字にマッチ
str(x) 文字列xにマッチ
match(x) 正規表現xにマッチ
xxx >> yyy ルールxxxにマッチし、その後 ルールyyyにマッチ
xxx | yyy ルールxxxまたはルールyyyにマッチ
xxx.repeat ルールxxxにゼロ回以上マッチ
xxx.repeat(1) ルールxxxに1回以上マッチ
xxx.maybe ルールxxxにマッチするかまたはマッチしない
xxx.absent? この後にルールxxxにマッチする文字列がこない(が文字を消費はしない)
xxx.present? この後にルールxxxにマッチする文字列がくる(が文字を消費はしない)

だいたいこれぐらい知っておくと結構なパターンのパーサが書けると思います。

またこのレベルの小さなパーサの挙動を調べるときは、pry(やirb)で対話的に試すとやりやすいので、上記のサンプルをpry上で試しましょう。

pryの共通の準備

1] pry(main)> require 'parslet'
> true
2] pry(main)> include Parslet
> Object

pry（やirb）で上記の用にParsletをincludeすると、any, strなどのメソッドがトップレベルで使えるようになります。

any

任意の一文字にマッチします。

[3] pry(main)> any.parse('1')
=> "1"@0
[4] pry(main)> any.parse('a')
=> "a"@0

以下

[pry上の行番号] その解説
という形式で書いていきます。

上記のanyであれば、

[3] 任意の一文字にマッチする any パーサは文字列'1'を正常にパースできます。

という感じです。

str(x)

文字列xにマッチします。

[3] pry(main)> str('1a').parse('1a')
=> "1a"@0
[4] pry(main)> str('1b').parse('1a')
Parslet::ParseFailed: Expected "1b", but got "1a" at line 1 char 1.
from /usr/local/bundle/gems/parslet-1.8.2/lib/parslet/cause.rb:70:in `raise'

[3] 1aをパースできる str('1a')パーサに 文字列'1a'をパースさせると正常にパースできます。
[4] 1bをパースできる str('1b')パーサに 文字列'1a'をパースさせるとパースできずにエラーになります。

match(x)

正規表現xにマッチします。

[5] pry(main)> match('\d').parse('1')
=> "1"@0
[6] pry(main)> match('\d').parse('a')
Parslet::ParseFailed: Failed to match \\d at line 1 char 1.
from /usr/local/bundle/gems/parslet-1.8.2/lib/parslet/cause.rb:70:in `raise'
[7] pry(main)> match('[a-z]').parse('a')
=> "a"@0
[8] pry(main)> match('[a-z]').parse('A')
Parslet::ParseFailed: Failed to match [a-z] at line 1 char 1.
from /usr/local/bundle/gems/parslet-1.8.2/lib/parslet/cause.rb:70:in `raise'
[9] pry(main)>

[5] 任意の数字一文字にマッチする match('\d')パーサは '1'を正常にパースできます。
[6] 任意の数字一文字にマッチする match('\d')パーサは 'a'をパースできずエラーになります。
[7] 任意のアルファベット小文字にマッチする match('[a-z]')パーサは 'a' を正常にパースできます。
[8] 任意のアルファベット小文字にマッチする match('[a-z]')パーサは 'A' をパースできずエラーになります。

xxx >> yyy

ルールxxxにマッチし、その後 ルールyyyにマッチします。

[12] pry(main)> (str('abc') >> match('\d') >> match('[A-Z]')).parse('abc1X')
=> "abc1X"@0

[12] 文字列abcに続けて、数字が一文字、アルファベット大文字一文字という文字列をパースできるパーサ

xxx | yyy

ルールxxxまたはルールyyyにマッチします。

[24] pry(main)> ((str('a') | str('b')) >> str('c')).parse('ac')
=> "ac"@0
[25] pry(main)> ((str('a') | str('b')) >> str('c')).parse('bc')
=> "bc"@0
[27] pry(main)> ((str('a') | str('b')) >> str('c')).parse('xc')
Parslet::ParseFailed: Failed to match sequence (('a' / 'b') 'c') at line 1 char 1.
from /usr/local/bundle/gems/parslet-1.8.2/lib/parslet/cause.rb:70:in `raise'

[24] 'a'または'b'が来た後に'c'が来るルールは文字列'ac'をパースできます。
[25] 'a'または'b'が来た後に'c'が来るルールは文字列'bc'をパースできます。
[27] 'a'または'b'が来た後に'c'が来るルールは文字列'xc'をパースできません。

xxx.repeat

ルールxxxにゼロ回以上マッチするパーサ

parsletでは基本的に複数回マッチするケースはこのルールを使います。
例えば、正規表現自体の繰り返しは使いません。(一文字以上の文字列をパースするために、 match('\d+') などとしたりは しない )

[15] pry(main)> match('[a-z]').repeat.parse('')
=> ""
[16] pry(main)> match('[a-z]').repeat.parse('a')
=> "a"@0
[17] pry(main)> match('[a-z]').repeat.parse('aa')
=> "aa"@0
[18] pry(main)> match('[a-z]').repeat(1).parse('')
Parslet::ParseFailed: Expected at least 1 of [a-z] at line 1 char 1.
from /usr/local/bundle/gems/parslet-1.8.2/lib/parslet/cause.rb:70:in `raise'
[19] pry(main)> match('[a-z]').repeat(1).parse('a')
=> "a"@0
[20] pry(main)> match('[a-z]').repeat(1, 2).parse('aa')
=> "aa"@0
[21] pry(main)> match('[a-z]').repeat(1, 2).parse('aaa')
Parslet::ParseFailed: Don't know what to do with "a" at line 1 char 3.
from /usr/local/bundle/gems/parslet-1.8.2/lib/parslet/cause.rb:70:in `raise'

アルファベット小文字一文字にマッチするパーサ　match('[a-z]')　を以下ルールXとします。

[15] ルールXに0回以上マッチするパーサは空文字をパースできます(ルールXに０回マッチするから)
[16] ルールXに0回以上マッチするパーサは文字列 'a' をパースできます。
[17] ルールXに0回以上マッチするパーサは文字列 'aa' をパースできます。
[18] ルールXに1回以上マッチするパーサは空文字をパースできません。
[19] ルールXに1回以上マッチするパーサは文字列 'a' をパースできます。
[20] ルールXに1回以上2回以下マッチするパーサは文字列 'aa' をパースできます。
[21] ルールXに1回以上2回以下マッチするパーサは文字列 'aaa' をパースできません。

xxx.maybe

ルールxxxにマッチするかまたはマッチしない

[3] pry(main)> (str('-').maybe >> match('[0-9]')).parse('-1')
=> "-1"@0
[4] pry(main)> (str('-').maybe >> match('[0-9]')).parse('1')
=> "1"@0
[5] pry(main)> (str('-').maybe >> match('[0-9]')).parse('+')
Parslet::ParseFailed: Failed to match sequence ('-'? [0-9]) at line 1 char 1.
from /usr/local/bundle/gems/parslet-1.8.2/lib/parslet/cause.rb:70:in `raise'

[3] 先頭に-が来るかまたはこず、その後に数字が一つくるパーサは、 '-1'をパースできる。
[4] 先頭に-が来るかまたはこず、その後に数字が一つくるパーサは、 '1'をパースできる。
[5] 先頭に-が来るかまたはこず、その後に数字が一つくるパーサは、 '+'をパースできない。

xxx.absent?, xxx.present?

この後、ルールxxxに,

  • absent? ... マッチする文字列がこない
  • present? ... マッチする文字列がくる

が、入力文字を消費はしません。
文字を消費というのが分かりづらいですが、下記のようなイメージです。

str('abc') >> str('def') という文字列abcdefにマッチするケースを考えます。
各ルール適用時、パース対象文字列のマッチ開始位置を持っており、マッチするたびにそのマッチ位置を更新していきます。
　
例えば、 str('abc')にマッチした直後、次のマッチ用に文字dから始まる位置に開始位置が更新されます。

abcdef
   ^
   |
   str('abc')にマッチした直後の開始位置

開始位置が d に更新されたことで、その後のstr('def')ルールがマッチするようになります。

そうではなく次にくる(or こない)文字列を指定するが、実際にマッチさせる位置は変えたくない場合この absent?や present を使います。

[28] pry(main)> (match('irregular_word').absent? >> any.repeat(1)).parse('abcdef')
=> "abcdef"@0
[29] pry(main)> (match('irregular_word').absent? >> any.repeat(1)).parse('12345')
=> "12345"@0
[30] pry(main)> (match('irregular_word').absent? >> any.repeat(1)).parse('irregular_word1234')
Parslet::ParseFailed: Failed to match sequence (!irregular_word .{1, }) at line 1 char 1.
from /usr/local/bundle/gems/parslet-1.8.2/lib/parslet/cause.rb:70:in `raise'

[28] この後文字列irregular_wordが続かず、任意の文字列にマッチするルールは、文字列'abcdef'をパースできます。
[29] この後文字列irregular_wordが続かず、任意の文字列にマッチするルールは、文字列'12345'をパースできます。
[30] この後文字列irregular_wordが続かず、任意の文字列にマッチするルールは、文字列'irregular_word1234'をパースできません。

数値リテラルパーサ

とりあえず基本的なルールは見たので実際に意味のある文字列として数値リテラルのパーサを作りましょう。
正確な表現かどうかわかりませんが、だいたい小中学校で習った正負の整数、小数にみえるものをパースできるようにしようと思います。
(正確な浮動小数点や、指数形式とか１６進数とかは対応しない)

先頭の+-に関しては単項演算子扱ったりもしそうですが、ここでは数値の一部として一緒にパースします。

ですので、ルールとしては

  • 先頭に+-　のいずれかまたは何もなし
  • 次のいずれかが来て
    • 二文字以上のケース
      • [1-9]の文字が1つある
      • その次に[0-9]の文字が0個以上存在する
    • 一文字のケース
      • [0-9]の文字が一つある
  • その後にもし . があれば、[0-9]の文字が1個以上続く

ということにしましょう。

またはここからは、最初のテンプレートで紹介したパーサクラスを作成し、ruleを定義する方式で定義していきます。

  • 先頭に+-のいずれかまたは何もなし

+-のいずれかにマッチするルールを定義すればよさそうです。これを sign というルールで定義しましょう。
または何もなしの部分はあとでルールを結合するときに signに対してmaybeすれば良さそうですね。

require 'parslet'

class NumParser < Parslet::Parser
  rule(:sign) { match('[-+]') }
end

p NumParser.new.sign.parse('-')
# => "-"@0
p NumParser.new.sign.parse('+')
# => "+"@0
  • 次のいずれかが来て
    • 二文字以上のケース
      • [1-9]の文字が1つある
      • その次に[0-9]の文字が0個以上存在する
    • 一文字のケース
      • [0-9]の文字が一つある

ちょっとややこしいですが、要は 一文字の 0 はありだけど、 二文字以上で先頭0の'01' とかは整数とはみなさないよ、ということです

これはその通り定義してintegerというルールにします。

require 'parslet'

class NumParser < Parslet::Parser
  rule(:sign) { match('[-+]') }
  rule(:integer) {
    (match('[1-9]') >> match('[0-9]').repeat) |
    match('[0-9]')
  }
end

p NumParser.new.sign.parse('-')
p NumParser.new.sign.parse('+')
p NumParser.new.sign.parse('')

p NumParser.new.integer.parse('0')
# => "0"@@
p NumParser.new.integer.parse('10')
# => "10"@@
p NumParser.new.integer.parse('01')
# => Parslet::ParseFailed パース失敗
  • その後にもし . があれば、[0-9]の文字が1個以上続く

これもその通り定義して decimal というルールにします。signと同様に、decimal部分自体の任意性はあとでくっつけるときにmaybeにするとして、ここでは一旦"."がありきのルールにしておきます。

require 'parslet'

class NumParser < Parslet::Parser
  rule(:sign) { match('[-+]') }
  rule(:integer) {
    (match('[1-9]') >> match('[0-9]').repeat) |
    match('[0-9]')
  }
  rule(:decimal) {
    str('.') >> match('[0-9]').repeat(1)
  }
end

p NumParser.new.decimal.parse('.0')
# => ".0"@0
p NumParser.new.decimal.parse('.12')
# => ".12"@0
p NumParser.new.decimal.parse('.001')
# => ".001"@0

さてこれで細かいルールは定義したのでくっつけましょう。
数値リテラルを number というルールで定義し、その定義は上で見たように

  • sign があるかまたはなく
  • その後に integer が来て
  • その後に decimal が来るかまたは来ない

となり下記のようになります。

require 'parslet'

class NumParser < Parslet::Parser
  rule(:sign) { match('[-+]') }
  rule(:integer) {
    (match('[1-9]') >> match('[0-9]').repeat) |
    match('[0-9]')
  }
  rule(:decimal) {
    str('.') >> match('[0-9]').repeat(1)
  }
  rule(:number) {
    sign.maybe >> integer >> decimal.maybe
  }
end

p NumParser.new.number.parse('1234')
# => "1234"@0
p NumParser.new.number.parse('12.34')
# => "12.34"@0
p NumParser.new.number.parse('0.01')
# => "0.01"@0
p NumParser.new.number.parse('-0.01')
# => "-0.01"@0
p NumParser.new.number.parse('+1.2')
# => "+1.2"@0
p NumParser.new.number.parse('1')
# => "1"@0
p NumParser.new.number.parse('-2')
# => "-2"@0
p NumParser.new.number.parse('+01.1')
# => Parslet::ParseFailed 数値部分の先頭の文字が0のため
p NumParser.new.number.parse('+2.')
# => Parslet::ParseFailed 小数点があるのにそれ以降の数値がないため

rootルールの設定

上記で数値のリテラルをパースできるようになりました。rootの設定をnumberにして一旦数値リテラルパーサを完成させます。

require 'parslet'

class NumParser < Parslet::Parser
  rule(:sign) { match('[-+]') }
  rule(:integer) {
    (match('[1-9]') >> match('[0-9]').repeat) |
    match('[0-9]')
  }
  rule(:decimal) {
    str('.') >> match('[0-9]').repeat(1)
  }
  rule(:number) {
    sign.maybe >> integer >> decimal.maybe
  }

  root(:number)
end

p NumParser.new.parse('-1.23')
# => "-1.23"@0

生の文字列、-1.23を正しくパースできていますね!

その2に続く

35
18
5

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
35
18