⚡

[入門] 全自作言語erに告ぐ、PEG パーサはいいぞ

2021/12/22に公開

Rust

自作言語

PEG

tech

はじめに

N高等学校生徒のがーねっとです。

今回は自作言語の開発において便利な PEG について紹介。
オリジナル PEG パーサ FCPEG の紹介とともに解説していきます。
記事に不自然な点などあればやさしくご報告ください・・・

この記事は N・S高等学校 Advent Calendar 2021 22 日目です。

主な対象

プログラミング言語をある程度理解している方
自作コンパイラに興味がある方

PEG って何？

PEG は Parsing Expression Grammar の略で、Bryan Ford 氏によって提唱されました。
正規表現に似たような形式でプログラミング言語の構文を記述できます。
PEG ではさまざまな構文を複数の「規則」に小分けして定義します。

例として整数の足し算を行う構文を簡単に定義してみましょう。

Number <- [0-9]+,
Add <- Number " "# "+" " "# Number,

たったこれだけで構文が定義できました。

これは私が共同で開発した PEG 方言 FCPEG の構文で、基本的に 規則名 <- 構文, という形になっています。

規則 Number の文法 [0-9]+ は 0 ~ 9 の文字のいずれかがが 1 回以上続くことを表しています。
要するに 1 桁以上の整数ですね。

規則 Add では Number の後ろにスペース, 演算子 +, スペース, Number が 1 つずつ続いています。

構文定義ができたらどうするかというと、PEG パーサを用いて構文解析を受けるテキスト (=入力) と定義した規則が合っているかチェック (=検査) してあげます。

この構文で成功する例: 1 + 2 26 + 538 3724 + 5

例えば入力が hoge + 1 であれば先ほど定義した文法と合わないため構文解析に失敗し、処理は終了します。
逆に入力が 1 + 2 であれば構文解析が成功し、入力が「抽象構文木」に変換されます。

抽象構文木はソースコードの意味に関係する要素のみを構文木としてまとめたものです。
例えば関数定義時の括弧 ( および ) はプログラムの解釈において特別意味を持っているわけではないので抽象構文木からは除外されます。
ちなみに先ほどの PEG コード中にあった記号 # は要素を構文木から除外するための記号でした。

( この先 FCPEG パーサを実際に動かしてみますのでお楽しみに )

余談ですがこのように直接パースを行わず、PEG を解釈してパーサプログラムを生成するツールがあり、これはパーサジェネレータと呼ばれています。
JavaScript 製のパーサジェネレータ PEG.js はブラウザ上でも動かせるようなのでドキュメントとともにぜひ遊んでみてください。

仕組み

ソースコードは基本的に左から右に解析が進んでいきます。

仮に入力 ab と構文定義 "a" "b" "c" : "a" "b" があるとしましょう。

まずは一番最初の "a" から検査が始まりますが、この場合は入力 1 文字目の a とマッチするため、入力位置 (=入力の何文字目を解析しているか) を 1 文字分進めて次は "b" の検査に移ります。

"b" も同様にマッチするため入力位置を進めて "c" の検査に移るのですが、おっと、ここでは入力の文字数を超えてしまうためマッチしません。
このようにマッチしなかった場合は一度検査をやり直すため、入力位置を 1 文字目に戻します。(=バックトラック)

記号 : については "a" "b" "c" or "a" "b" に置き換えてみるとわかりやすいと思いますが、"a" "b" "c" で検査が失敗したので次の "a" "b" に検査が移ります。

そうしたら先ほどの "a" ~ "b" と同じように検査を行って最終的にマッチするのでここで全体の検査が成功します。

利点 / 欠点

PEG の利点といえば、楽に構文解析ができるという点があります。
通常、コンパイラを作る際はソースコードをトークン単位に分解する字句解析器を作りますが、PEG ではその必要がなく構文を定義するだけで解析の準備ができます。

それに PEG で定義した構文には曖昧性がありません。
~~文脈自由文法を触った経験がないんですけど曖昧な構文定義ってなんでしょうね (理解していない顔)~~

もちろん欠点もあります。
一つは「左再帰」ができないことです。
例として、以下の構文定義を用いてパースすると無限再帰 (無限ループ) に陥ってしまいます。

A <- A,

% 以下の場合も間接的に再帰しているのでアウト
A <- B,
B <- A,

これは A のパースを試みた時にさらに A をパースしようとしてしまうためです。
ちなみにこの場合は A の前に "a" のパースが入るため無限再帰は起こりません。

A <- "a" A,

また、パースにおいては速度上の問題があり、計算量は最悪の場合で O(2^n) となります。
しかし Packrat Parsing という手法 (メモ化) を用いれば計算量を O(n) に抑えることができるため特に問題はありません。

基本文法

規則名 <- 構文定義 で規則を定義します。
構文定義に用いる基本的な構文は以下のとおりです。
( e1 e2 というのは PEG 構文の最小単位を expression と呼ぶため )

名前	構文	機能	構文例	入力例
文字列	`"string"`	特定の文字列にマッチするエスケープシーケンス可能	`"abc"`	`abc`
文字クラス	`[chars]`	特定の文字にマッチする `[a-f]` `[0-9]` のように範囲指定可能	`[abc]`	`a` `b` `c`
ID	`ID`	指定した規則を検査する	`Number`	※ `Number` の定義による
ワイルドカード	`.`	すべての一文字にマッチする	`.`	`d` `@` `5`
グループ	`(e1 e2)`	複数の要素をグループ化する	`("a" : "b") "c"`	`ac` `bc`
連接	`e1 e2`	左から順に検査いずれかがマッチしなければ失敗	`"a" "b"`	`ab`
選択	`e1 : e2`	左から順に検査いずれかがマッチすれば成功	`"a" : "b"`	`a` `b`
繰り返し	`e?` `e*` `e+` `e{n}` `e{n,m}`	一定回数繰り返す (後述)	`"a"{2,3}`	`aa` `aaa`
肯定先読み	`&e1 e2`	`e1` と `e2` の両方にマッチすれば成功	`&[a-z] "a"`	`a`
否定先読み	`!e1 e2`	`e1` にマッチせず `e2` にマッチすれば成功	`![a-z] .`	`1` `A`

繰り返し回数の指定にはいくつかバリエーションがあります。
e{n} で n 回、e{n,m} で n ~ m 回と指定できます (FCPEG の場合) が、省略記号 ? * + を使うとそれぞれ 0 ~ 1 回、0 回以上、1 回以上と簡略化できます。

～以下は FCPEG 特有の機能～

空文字列 "" はすべての場合で成功し、入力の位置を進めません。
一つ注意として、FCPEG では "\z" によって EOF を記述をする必要があります。

この他にもさまざまな機能があるので紹介。
詳細は後述します。

名前	構文	機能	構文例
除外	`e#`	構文木から除外	`"a"#`
命名	`e#Name`	命名して構文木に追加	`"a"#LetterA`
展開	`e##`	ノード `n` の子ノードを `n` の親ノードに移動する	`("a" "b")##`
ジェネリクス	`g<arg1, arg2>`	規則引数を渡して処理をパターン化する	`rule<"a", "b">##`
関数	`f(arg1, arg2)`	主にプリミティブ関数に引数を渡す	`rule(1)##`

実際にパースしてみる

FCPEG パーサを用いて構文解析をしてみましょう。(開発中のため実際に試す場合は自己責任)
現時点では Rust 実装しか用意がありませんが、使いやすいよう fcpeg コマンドに機能をまとめておきました。

ダウンロード: FunCobal-family/FCPEG
( Windows 以外の方々、準備不足で申し訳ないです )

まずはパース対象のソースファイルを作成しましょう。
ファイル名はなんでも構いませんがここでは source.txt としておきます。

[1, [2, 3], 4]

次に構文定義用の syntax.fcpeg ファイルを作成。
これは私が即興で書いた、数値型配列の構文を定義したものです。

[Main]{
    + start Syntax.Main,
}

[Syntax]{
    Main <- Array? "\z"#,
    Array <- "["# Space*# ArrayElem (Space*# ","# Space*# ArrayElem)+## Space*# "]"#,
    ArrayElem <- Number : Array,
    Number <- [0-9]+,
    Space <- " ",
}

それともう一つ、FCPEG ファイルと同じ名前の設定ファイル syntax.cfg を作成。

ASTReflect: reversed,

最後にコンソールで fcpeg parse コマンドを叩けばすぐにパースをすることができます。

./fcpeg parse -f syntax.fcpeg -i syntax.txt -o

このように抽象構文木が出力されると思います。

--- Syntax Tree ---

syntax.txt
| .Syntax.Test
|   |- "test" 0/0/0 ()
|   |- "" 4/0/4 [hidden]

--- End ---

ここでの構文木の見方はこんな感じ
| ノード名
|   |- リーフ値
|   | ノード名
|   |   |- リーフ値
|   |   |- リーフ値

絶賛開発途中のため多少の問題は目をつむってもらって・・・ (多言語対応メッセージが生で表示されていたり)

Rust 言語でソースコードを書けば構文木を中間言語に変換したりとさまざまなことができますが、現時点だと少々手間がかかるためまた今度紹介することにします。
もし今すぐにでも書きたい方がいればコメントなどでお知らせを。

fcpeg parse コマンドのオプション一覧も置いておきます。( fcpeg man で簡易表示 )
ぜひ遊んでみてください。

オプション	短縮名	機能
`--fcpeg <パス>`	`-f`	FCPEG ファイルを指定する
`--input <パス>`	`-i`	ソースファイルを指定する
`--output`	`-o`	抽象構文木をコンソールに出力する
`--time`	`-t`	パース処理時間をコンソールに出力する
`--mon`	なし	ソースファイルと FCPEG ファイルの変更を検知して自動でパースする

～～～～～

おっと、FCPEG 特有の機能の詳細を説明していませんでしたね。
一部検討中の機能もありますが基本的に実装が完了しているものなので利用が可能です。

ブロック

FCPEG ではブロックごとに規則を分類します。
また、外部ブロックにある規則の利用を宣言するには use プラグマを使います。

[ブロック名]{
    % これがブロックの中のコメント,
    + use 外部ブロック名,
    規則名 <- 構文定義,
    ...
}

Main ブロック内の規則 Main が最初に検査されます。
( まだ実装側の対応が追いついていないため現在は Main ブロックを作ってそこで start プラグマを宣言し、パースの最初に検査する規則を指定しています )

[Main]{
    + start ブロック名.規則名,
}

ジェネリクス

ジェネリクスではこのようなコードを省略して書く方法があります。

ParenA <- "(" [a-z] ")",
ParenB <- "(" ID ")",

< > で引数を設定することにより丸括弧で囲まれた構文を規則 Paren にまとめることができます。

% ジェネリクスの定義,
Paren<$Item> <- "(" $Item ")",

% ジェネリクスの利用,
ParenA <- Paren<[a-z]>,
ParenB <- Paren<ID>,

これは簡素な例ですが、同じような構文パターンが何度も出てきた時にかなり役立ちます。

プリミティブ関数

プリミティブ関数という名前は私が独断で決めたものなので仮の名前として・・・
PEG コードを書く上で便利な機能が用意されています。

関数名	引数	機能	備考
`JOIN($Item)`	`$Item` ... 対象の要素	すべての値を結合してリーフを生成する	-
`LOOP($Item, $Div)`	`$Item` ... 各要素 `$Div` ... 区切り要素	区切り要素で繋がった各要素の構文を定義する	未実装

JOIN(...) は特に文字クラスを利用する際に重宝します。
通常、文字クラスでは一文字ごとリーフ (構文葉) が生成されますが、この関数を用いると構文解析のしやすい形に直してくれるのです。

% 通常の定義
A <- [a-z]{3},

% 一文字ずつだと構文木を解析するときに少々面倒・・・
| A
|   |- "a"
|   |- "b"
|   |- "c"

% JOIN(...) を用いた定義
A <- JOIN([a-z]{3}),

% 一つのリーフにまとまって便利！
| A
|   |- "abc"

LOOP(...) は今後実装予定です。
一応紹介すると、a.b.c や a, b, c というような区切り文字が存在する構文で役立つ関数です。

% 通常の書き方
IDChain <- "a" ("." "a")*##,

% LOOP(...) を用いた書き方: JOIN(要素, 区切り)
IDChain <- LOOP("a", "."),

Tips

文字列リテラル

任意の長さの文字列をクォーテーションで囲めばいい気がしてしまいますが注意が必要です。
この例ではパースに失敗してしまいます。

String <- "\"" .* "\"",

文字列の中身として置いたワイルドカードが 2 つめのクォーテーションまで消費してしまうためです。
ということで中身の文字それぞれを「クォーテーション以外の任意の文字」にしてやりましょう。

String <- "\"" (!"\"" .)* "\"",

!"\"" . でクォーテーション以外の任意の一文字を表しますので、括弧で囲んで 0 回以上の繰り返し記号を指定しています。

さいごに

記事を読んでいただきありがとうございました。
これを機に PEG で自作言語を実装してみてはいかがでしょうか。
他にも PEG についての優れた記事などがあるので参考リンクに載せておきます。

補足: FCPEG は将来的に正式リリースする予定です。対応言語も増やしたい・・・

参考リンク

PEG基礎文法最速マスター
- https://kmizu.hatenablog.com/entry/20100203/1265183754
Packrat Parsing のメモリ効率の改善手法
- https://kmizu.github.io/papers/pro_35-mizushima.pdf
PEGパーサを布教してみる
- https://zenn.dev/senk/articles/c462453673ac81