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

#  Parsletで構文解析する[その1]
[その2](https://qiita.com/pocari/private/76f97631838b3d8ceafa)
[その3](https://qiita.com/pocari/private/95845782bbc43b1c73be)

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

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

などなど

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

- 正規表現で頑張る
- [racc](https://github.com/tenderlove/racc) で構文解析する

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

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

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

など一長一短です。

### Parslet

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

[parslet](http://kschiess.github.io/parslet/)

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

## Parsletとは

[parslet](http://kschiess.github.io/parslet/)

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

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

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

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

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

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

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

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

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

## Parsletサンプル
### パースの基本
- パーサのテンプレート

```rb
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 <code>&#124;</code>  yyy | ルールxxxまたはルールyyyにマッチ
| xxx.repeat | ルールxxxにゼロ回以上マッチ |
| xxx.repeat(1) | ルールxxxに1回以上マッチ |
| xxx.maybe | ルールxxxにマッチするかまたはマッチしない |
| xxx.absent? | この後にルールxxxにマッチする文字列がこない(が文字を消費はしない) |
| xxx.present? | この後にルールxxxにマッチする文字列がくる(が文字を消費はしない) |

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

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

#### pryの共通の準備

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

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

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

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

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

上記のanyであれば、

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

という感じです。

#### str(x)
文字列xにマッチします。

```irb
[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にマッチします。

```irb
[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にマッチします。

```irb
[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+')` などとしたりは *しない* )

```irb
[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にマッチするかまたはマッチしない

```irb
[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` を使います。

```irb
[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すれば良さそうですね。

```rb
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`というルールにします。

```rb
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にするとして、ここでは一旦"."がありきのルールにしておきます。

```rb
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` が来るかまたは来ない

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

```rb
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`にして一旦数値リテラルパーサを完成させます。

```rb
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](https://qiita.com/pocari/private/76f97631838b3d8ceafa)に続く