PEGで文法を書いていると、PEG本来の構文だけでは表現しにくいところが色々と出てきます。思いつくものをざっと上げてみると、
-
字句関連
- 空白文字のスキップ
- ワード全体のマッチ
- 大文字・小文字を区別しない
- 辞書
-
構文関連
- 左再帰
- Metaルール
- 中置演算子
- 文脈依存パース
といったものがあります。実用的なPEGライブラリの多くは、独自にPEGを拡張してこれらの問題の解決にあたっています。
今回は、字句ルールに関連した4項目を調査してみます。それぞれの項目で「通常のPEGによる方法」と「PEGライブラリによる拡張例」を示します。
最後に、実例としてPL/0言語の文法をPEGで定義し、拡張構文の効果を確認してみたいと思います。
空白文字のスキップ
誰もが直面するのはこの問題でしょう。1 + 2の様に字句の間の空白を扱う時の一般的な方法は、「空白文字ルールをトークンの後に付与する」ことです。下記の例では、_が空白文字を表すルールです。
SUM ← NUM ('+' _ NUM)*
NUM ← [0-9]+ _
_ ← [ \t\n]*
この方法の問題は、文法が大きなるにつれて_が至る所に出現し、構文が非常に見にくくなることです。また[0-9]+ _のように、実際のトークン（[0-9]+）が空白ルールのために認識しずらくなります。
Rattler (Whitespace Skipping)
トークンの前後にある%whitespaceにマッチする文字列をスキップします。この機能を使うと_のようなルールを全く書く必要がなくなり、文法が非常に見やすくなります。
%whitespace [ \t\n]*
ワード全体のマッチ
キーワードや変数名などのワードトークンが、意図せずにくっついてしまうことがあります。次の文法を考えてみましょう。
FOO_BAR ← 'foo' _ 'bar'
~_ ← [ \t\r\n]*
_は「0回以上の空白文字の繰り返し」なので、
foo bar;
だけではなく、
foobar;
にも誤ってマッチしてしまいます。
以下の例にあるように、!オペレータを上手に使ってこの問題を回避することができます。
FOO_BAR ← 'foo' __ 'bar'
~_ ← [ \t\r\n]*
~__ ← ![a-z] _
キーワードやindentの数が多くなると、適切な場所に_や__を挿入するのがとても面倒になり、可読性も損なわれてしまいます。
Rattler (Word Literal Expression)
バックオートでLiteralを定義すると、formなどに誤ってマッチすることがなくなります。
for <- `for`
| input | result |
|---|---|
| for | for |
| form | FAIL |
| for-each | for |
| for_each | FAIL |
さらに%word_characterに、任意の「Word Character」を定義することができます。
%word_character [[:alnum:]\-]
for <- `for`
この例では、ハイフンがWord Characterとして定義されているので、for-eachにはマッチしません。
| input | result |
|---|---|
| for | for |
| for-each | FAIL |
大文字・小文字を区別しない
大文字・小文字を区別しないキーワードを定義したい場合、通常のPEGではChoiceを使って表現できますが、似た文字列が繰り返されて美しくありません。
FOO ← 'foo' / 'FOO'
またFoOやfOoなどすべてのケースにマッチさせたい場合は、組み合わせの数が「文字数×文字数」になってしまいます。
PEG.js
'...'iのように、文字列リテラルの後にiを付与することにより、大文字・小文字の区別をなくします。
FOO ← 'foo'i
pointlander/peg
"..."のように、ダブルクオート文字列の場合は、大文字・小文字の区別をなくします。
FOO ← "foo"
辞書
以下の例を見てください。
文 ← 代名詞 'は’ 名詞 'です。'
代名詞 ← '私' / ... / '彼等'
名詞 ← '山田' / ... / 'プログラマ'
代名詞には少数の言葉しか含まれないので問題ありませんが、名詞には膨大な数の言葉があり、Choiceで表すのは現実的ではありません。むしろ名詞の辞書ファイルを読み込みこませる方が現実的かもしれません。しかしPEGには、そのような処理方法を記述する構文はありません。
残念ながら、どの既存のPEGライブラリにも解決策を見つけることはできませんでした。
実例
PL/0の文法を、標準PEGと拡張PEGで記述してみます。
実例用の拡張PEGとして、次の拡張構文を利用してみます。
* %whitespace ー 空白文字のスキップ
* バッククオート文字列 ー ワード全体のマッチ
* iサフィックス ー 大文字・小文字を区別しない
標準PEG
program ← _ block '.' _
block ← const var procedure statement
const ← (('CONST' / 'const') __ ident '=' _ number (',' _ ident '=' _ number)* ';' _)?
var ← (('VAR' / 'var') __ ident (',' _ ident)* ';' _)?
procedure ← (('PROCEDURE' / 'procedure') __ ident ';' _ block ';' _)*
statement ← (assignment / call / statements / if / while / out / in)?
assignment ← ident ':=' _ expression
call ← ('CALL' / 'call') __ ident
statements ← ('BEGIN' / 'begin') __ statement (';' _ statement )* ('END' / 'end') __
if ← ('IF' / 'if') __ condition ('THEN' / 'then') __ statement
while ← ('WHILE' / 'while') __ condition ('DO' / 'do') __ statement
out ← (('OUT' / 'out') __ / ('WRITE' / 'write') __ / '!' _) expression
in ← (('IN' / 'in') __ / ('READ' / 'read') __ / '?' _) ident
condition ← odd / compare
odd ← ('ODD' / 'odd') __ expression
compare ← expression compare_op expression
compare_op ← '=' / '#' / '<=' / '<' / '>=' / '>' _
expression ← sign term (term_op term)*
sign ← [-+]? _
term_op ← [-+] _
term ← factor (factor_op factor)*
factor_op ← [*/] _
factor ← ident / number / '(' _ expression ')' _
ident ← [a-zA-Z] [a-zA-Z0-9]* _
number ← [0-9]+ _
~_ ← [ \t\r\n]*
~__ ← ![a-zA-Z0-9_] _
拡張PEG版
program ← block '.'
block ← const var procedure statement
const ← (`CONST`i ident '=' number (',' ident '=' number)* ';')?
var ← (`VAR`i ident (',' ident)* ';')?
procedure ← (`PROCEDURE`i ident ';' block ';')*
statement ← (assignment / call / statements / if / while / out / in)?
assignment ← ident ':=' expression
call ← `CALL`i ident
statements ← `BEGIN`i statement (';' statement )* `END`i
if ← `IF`i condition `THEN`i statement
while ← `WHILE`i condition `DO`i statement
out ← (`OUT`i / `WRITE`i / '!') expression
in ← (`IN`i / `READ`i / '?') ident
condition ← odd / compare
odd ← `ODD`i expression
compare ← expression compare_op expression
compare_op ← '=' / '#' / '<=' / '<' / '>=' / '>'
expression ← sign term (term_op term)*
sign ← [-+]?
term_op ← [-+]
term ← factor (factor_op factor)*
factor_op ← [*/]
factor ← ident / number / '(' expression ')'
ident ← [a-zA-Z] [a-zA-Z0-9]*
number ← [0-9]+
%whitespace ← [ \t\r\n]*
3つの拡張構文を使用するだけで、可読性がかなり上がったのではないでしょうか。（これらの拡張をサポートする現実のPEGライブラリがあれば是非使いたいです！）
まとめ
PEGで文法を記述する上で直面する問題と、幾つかのPEGライブラリの興味深い取り組みについて調査しました。またPL/0の文法におけるPEG拡張構文の効果についても見ることができました。
次回は、構文ルールを書く際の問題について取り上げる予定です。