Parsing Expression Grammar という文法がある。

どのようなものかというと、とりあえずは「正規表現や EBNF などに似た文法の一種で、正規表現よりも強力でプログラミング言語を作れるくらいの文法」、みたいなものをイメージしておけばよいと思う。

補足: ここで言っている文法というのは、正規文法とか文脈自由文法とかその辺のいわゆる形式文法と呼ばれるもののこと。

PEG の文法は、そのまま再帰下降構文解析な実装の構文解析器 ( parser ) に変換でき、また文脈自由文法で必要な字句解析器 (lexer | tokenizer) が不要で、構文規則のなかで字句解析にあたる規則も扱うことができるという特徴がある。

...とまあ、snobbyな 小難しそうな説明は置いといて、この PEG をベースにした PEG.js という parser generator があるのでそれで遊んでみよう！というのがこの記事の本題。

parser generator とは parser の実装を生成するというメタなプログラムのこと。yet another compiler compiler (yacc) などが有名で、言語処理系に興味なくても名前だけは知っているという人も多いと思う。

ちなみに、別に PEG に特別こだわりがあるわけではなく、yacc で遊んでみてもいいんだけど、PEG.js にはオンラインエディターがあって環境構築不要ですぐに試せるので今回は PEG を選んだ。

なお、PEG.js 以外にもいろんな PEG ベースの parser generator や parser combinator がある。

---

使い方

つ ドキュメントをどうぞ。

オンラインエディターで環境構築等は不要ですぐに試すことができるので、ドキュメントの Grammar Syntax and Semantics 以下だけを読めばおｋ。詳しい人が日本語で解説した記事もインターネット上にいろいろあるので、そういう記事を探して読んでも良いと思う。（雑）

遊ぶ

早速何かを書いて遊んでみる。

まずはどんな parser を作りたいかを考える。

parser と言えば、あるプログラムの抽象構文木を生成したりするみたいなイメージがあるかもしれないが、最初はもっと簡単そうなところから始める。

Hello, World

Name: foo; という構文を受けとったら Hello, foo に変換するというものを書いてみる。

以降、簡単のためなるべく雑に書いていく。

たとえば現実的には改行コードとして \n の他に \r や \r\n なども考慮するべきかもしれないが、この世界ではそんなものはないとする。

Input
  = NameKeyword name:$Name EndKeyword { return "Hello, " + name }

NameKeyword = 'Name: '

Name = [^;\n ]+

EndKeyword = ';' / EOL

EOL = '\n'

Input

Name: HOGE;

Output

"Hello, HOGE"

Hello, World 完。

Hello, World その2

複数の名前を受け取れるようにしてみる。

Input
  = Expr+

Expr
  = NameKeyword name:$Name EndKeyword+ { return "Hello, " + name }

NameKeyword = 'Name: '

Name = [^;\n ]+

EndKeyword = ';' / EOL

EOL = '\n'

Input

Name: HOGEMAN;
Name: FUGAMAN;
Name: たろう;

Output

[
   "Hello, HOGEMAN",
   "Hello, FUGAMAN",
   "Hello, たろう"
]

Hello, World その2 完。

AST

Nameに加えて年齢も受け取れるようにする。

そして、Hello, foo と変換するのはやめて、あとから好きなように使えるように一旦ASTに変換するようにしてみる。

Input
  = Expr+

Expr
  = NameKeyword name:$Name _ AgeKeyword age:$Age EndKeyword+ {
      return { type: 'person', name, age }
    }

_ = WhiteSpace+
WhiteSpace = ' '

NameKeyword = 'Name: '
AgeKeyword = 'Age: '

Name = &AgeKeyword / [^;\n ]+

Age
  = '0'
  / NonZeroNum Num

Num
  = [0-9]

NonZeroNum
  = [1-9]

EndKeyword = ';' / EOL

EOL = '\n'

Input

Name: foo Age: 0;
Name: hoge Age: 10;
Name: たろう Age: 98;

Output

[
   {
      "type": "person",
      "name": "foo",
      "age": "0"
   },
   {
      "type": "person",
      "name": "hoge",
      "age": "10"
   },
   {
      "type": "person",
      "name": "たろう",
      "age": "98"
   }
]

以上。オワリ。

Goodbye 👋