この記事はIQ1の2枚目っ Advent Calendar 2019の19日目の記事です。

みなさんもきっと書いたことないプログラミング言語をちょっと試してみようというときにPEG Parser Combinatorを書こうかなという気持ちになると思います(?)

というわけで，今回は私のOCamlの練習も兼ねて，PEG Parser Combinatorの実装を紹介したいと思います．

そもそもPEGとは

PEGはParsing Expression Grammarの略でCFGのような形式文法です。
式（Parsing Expression）の組み合わせによって入力文字列を受理するかどうかを決定し，言語を定義します．
PEGの文法は以下のような見た目をしています．

四則演算の文法

Expression = Product (('+' / '-') Product)*
Product = Value (('*' / '/') Value)* 
Value = Num Num* 
Num = '0' / '1' / '2' / '3' / '4' / '5' / '6' / '7' / '8' / '9'

この例は、"1+2*3"のような四則演算の文字列を受理する文法です．¹
PEGの文法はいくつかの規則によって構成されています．
規則は以下のように左側に非終端記号（A），右側に式（e）を書きます．

A = e

四則演算の文法のValueの規則では，

Valueの規則

Value = Num*

Valueが非終端記号でNum*が式という感じです．
今回使うPEGの式を以下のように定義します．（他にもあるのですが，今回は四則演算に必要な定義のみを記述しています．）

 \begin{align}
e &=& a       & & (\mbox{character}) \\
  & & A       & & (\mbox{nonterminal}) \\
  & & e\;e    & & (\mbox{sequence}) \\
  & & e\;/\;e & & (\mbox{ordered choice}) \\
  & & e*      & & (\mbox{greedy repetition}) 
\end{align}

最初のcharacterは任意の一文字にマッチする式です．
四則演算の文法ではプログラマのみなさんに馴染みやすいように'a'とシングルクォーテーションで括っていました．
例えば，入力文字列"abc"に対して式'a'を適用すると先頭文字のaが消費されて残り文字列が"bc"となります．
このように見事文字列が一致した場合には「解析が成功した」ということになり，「入力文字列は定義した文法によって受理される言語である」といえます．（本当は残り文字列を全て消費しなければならないみたいな制約をつけるかつけないかみたいな話をしなきゃいけないですが）
反対に，入力文字列"bbc"が与えられた場合は式'a'にマッチしないので，「解析が失敗した」ことになるわけです．

nonterminalは先程登場した非終端記号を表す式です．
非終端記号が左辺に定義されている他の規則の右辺の式を試します．

sequenceは左の式eを試した後に右の式eを試す式です．両方とも解析が成功すれば全体として解析が成功したことになります．どちらかが解析に失敗をしたときは全体として解析が失敗したことになります．

ordered choiceは左の式eを試したときに失敗したときだけ右の式eを試します．CFGのchoiceに似ていますが，優先順位がついている点で異なるのでordered choiceと呼ばれていたりします．

最後のgreedy repetitionは式eが失敗するまで貪欲に繰り返すという式です．式eが一度も成功しなかったとしても全体として成功とします．なんかIQ1っぽくてかわいいですよね．

ここまでを読んでから四則演算の文法を読むと，たしかに四則演算の文字列を受理するような気になれます．
なれた時点でみなさんのIQは1を超えてしまった気がします．おめでとうございます．

OCamlでPEG Parser Combinatorを書いてみよう!

「IQ1なのでParserを実装して確かめないと納得がいかない」という方は，一緒にOCamlでPEG Parser Combinatorを実装していきましょう．

Parser CombinatorというのはCombinator²と呼ばれる小さな関数を組み合わせてParserを組み立てたものです．
先程の四則演算を解析できるところまで作っていきたいと思います．

準備

まずは，Parserの文脈を表すparser_contextをレコード型で表現してみましょう．

type parser_context = {
  input: string;
  pos: int;
}

inputは入力文字列でposは現在の文字列位置です．
PEGの説明で述べたように式が適用されて文字がマッチされると入力文字列を消費します．
なので，文字列位置を用意して残り文字列の先頭のインデックスを指すようにしています．
つまり，入力文字列inputが'abc'で先頭の'a'が消費されたとき，posを0から1に増加させることで'a'を消費したという状態を表現します．

どんどんいきましょう．次に，parser_contextの初期化用の関数とprintデバッグ用の関数を用意しておきます．

...

let init_pc str = { input = str; pos = 0 };;

let print_pc pc = Printf.printf "input: %s pos: %d\n" pc.input pc.pos;;

これでinit_pc "aaa"とすれば，入力文字列"aaa"のparser_contextが生成できるようになりました．
次に，あるparser_contexが与えられたときに一つだけposを増やすnext関数を定義しておきます．

...
let next pc = {input = pc.input; pos = pc.pos + 1 };;

これぐらいならIQ1でも楽勝です．

式（Parsing Expression）の定義

ここからが本題です．
今回の実装ではPEGの式のひとつひとつをCombinatorとして定義していきます．
OCamlは大変便利なことに高階関数と部分適用が簡単に使える（関数型なので当たり前ですが）のでPEGの式を生成する高階関数を作ることになります．

PEGの式の型expressionは以下のようにします．

ParsingExpression

type expression = parser_context -> bool * parser_context

このexpressionを生成するような高階関数を書けばよいので，characterの型は

type character = char -> expression

となり，実装すると

character

...
let ch c pc =
  if String.length pc.input > pc.pos && ( String.get pc.input pc.pos ) = c
  then (true, next pc)
  else (false, pc);;

このようになります．
ch 'a'のように文字だけ部分適用させることで'a'のPEGの式を表現するCombinatorを生成します．

characterの実装はというと，( String.get pc.input pc.pos ) = cでマッチしているかどうかを判定するだけですね．
あとは，String.length pc.input > pc.posで入力文字列を消費しきってる場合は解析失敗になるようにしています．
解析結果は成功したらtrueと一文字消費させたnext pc,失敗した場合はfalseと入力で与えられたpcを返しています．

とりあえずこれをテストしてみましょう．

...
let () = print_pc ( snd (ch 'a' (init_pc "a") ));;

実行結果

input: a pos: 1

ちゃんと一文字消費できていると思います．

次は，sequenceの定義です．

sequence

...
let seq e1 e2 pc = 
  let (res1, pc1) = e1 pc in
  if res1 then e2 pc1 else (false, pc);;

順番に試していくだけですね．
こんな感じで使います．

...
let aaa = seq (ch 'a') @@ seq (ch 'a') (ch 'a');;
let () = print_pc ( snd (aaa (init_pc "aaa")) );;

実行結果

input: aaa pos: 3

@@を使うことで括弧地獄から開放されて幸せな気持ちになりました．
OCaml良いですね．

次はordered choiceの定義です．

ordered_choice

let ord e1 e2 pc = 
  let (res1, pc1) = e1 pc in
  if res1 then (res1, pc1) else e2 pc;;

sequenceを少し改造するだけです．
sequenceと同じように使います．

let a_or_b =  ord (ch 'a') (ch 'b');;
let () = print_pc ( snd (a_or_b (init_pc "b") ));;

実行結果

input: b pos: 1

最後はgreedy repetition!

greedy_repetition

let rec many e pc =
  let (res, pc') = e pc in
  if res then many e pc' else (true, pc);;

再帰を使って綺麗に書けますね．
今回は式eが成功すると必ず文字を消費するのでよいのですが，厳密には成功しても文字を消費しないPEGの式もあるので無限再帰しないように書いてあげなきゃいけません．
以下のように使います．

let () = print_pc ( snd (many (ch 'a') (init_pc "aaaaa")));;

実行結果

input: aaaaa pos: 5

イイっすね〜

四則演算のPEGを定義する

全部の式がそろったので早速四則演算のPEGを書きましょう!

let num = ord (ch '0') @@ ord (ch '1') @@ ord (ch '2') @@ ord (ch '3') @@ ord (ch '4')
  @@ ord (ch '5') @@ ord (ch '6') @@ ord (ch '7') @@ ord (ch '8') (ch '9');;
let value = seq num (many num);;
let product = seq value @@ many (seq (ord (ch '*') (ch '/')) value);;
let expression = seq product @@ many (seq (ord (ch '+') (ch '-')) product);;

早速テスト!

let () = print_pc ( snd (num (init_pc "1") ));;

let () = print_pc ( snd (product (init_pc "1*3")));;

let () = print_pc ( snd (expression (init_pc "1+2*3")));;

let () = print_pc ( snd (expression (init_pc "12+3*4")));;

実行結果

input: 1 pos: 1
input: 1*3 pos: 3
input: 1+2*3 pos: 5
input: 12+3*4 pos: 6

おぉ〜ちゃんと文字を消費していますね!

まとめ

私のOCamlを試すのに付き合ってもらいました(?)
なかなか良い言語ですね!!（満足）

今回の実装では，大変なので構文木を作りませんでしたがプログラミング言語を作るとかになると構文木が欲しいのでもっと書かなきゃいけないし工夫が必要になってきます．

以下は実装の全体です．

math.ml

type parser_context = {
  input: string;
  pos: int;
}

let init_pc str = { input = str; pos = 0 };;

let print_pc pc = Printf.printf "input: %s pos: %d\n" pc.input pc.pos;;

let next pc = {input = pc.input; pos = pc.pos + 1 };;

type expression = parser_context -> bool * parser_context 

let ch c pc =
  if String.length pc.input > pc.pos && ( String.get pc.input pc.pos ) = c
  then (true, next pc)
  else (false, pc);;

let seq e1 e2 pc = 
  let (res1, pc1) = e1 pc in
  if res1 then e2 pc1 else (false, pc);;

let ord e1 e2 pc = 
  let (res1, pc1) = e1 pc in
  if res1 then (res1, pc1) else e2 pc;;

let rec many e pc =
  let (res, pc') = e pc in
  if res then many e pc' else (true, pc);;

let () = print_pc ( snd (ch 'a' (init_pc "a") ));;

let aaa = seq (ch 'a') @@ seq (ch 'a') (ch 'a');;

let () = print_pc ( snd (aaa (init_pc "aaa")) );;

let a_or_b =  ord (ch 'a') (ch 'b');;

let () = print_pc ( snd (a_or_b (init_pc "b") ));;

let () = print_pc ( snd (many (ch 'a') (init_pc "aaaaa")));;

let num = ord (ch '0') @@ ord (ch '1') @@ ord (ch '2') @@ ord (ch '3') @@ ord (ch '4')
  @@ ord (ch '5') @@ ord (ch '6') @@ ord (ch '7') @@ ord (ch '8') (ch '9');;
let value = seq num (many num);;
let product = seq value @@ many (seq (ord (ch '*') (ch '/')) value);;
let expression = seq product @@ many (seq (ord (ch '+') (ch '-')) product);;

let () = print_pc ( snd (num (init_pc "1") ));;

let () = print_pc ( snd (product (init_pc "1*3")));;

let () = print_pc ( snd (expression (init_pc "1+2*3")));;

let () = print_pc ( snd (expression (init_pc "12+3*4")));;

この文法で構文木を生成すると右側に成長してく木になってしまいますが，今回は構文木を作らないので採用しています． ↩
TaPL的にいうとラムダ計算における自由変数の出てこない項ですかね? ↩