PEG Linter ー peglint

PEGとGo言語の勉強のために、PEGの構文チェッカー「PEG Linter ー peglint 」を作ってみました。

次のコマンドで、$GOPATH/bin に peglint がインストールされます。

$ go get github.com/yhirose/go-peg/cmd/peglint

PEGの構文チェック

Wikipediaにある以下の例をコピペして、calc.pegに保存してください。

calc.peg

Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Value (('*' / '/') Value)*
Value   ← [0-9]+ / '(' Expr ')'

構文チェックをしてみます。

$ peglint calc.peg

何も起こらず、つまり正常終了しました。次に意図的にエラーを入れてみます。

Expr    ← Sum Hello
Sum     ← Product (('+' / '-') Product)*
Product ← Value (('*' / '/') Value)*
Value   ← [0-9]+ / '(' Expr ')'

一行目のSumの後にHelloを追加してcalc2.pegに保存し、再度チェックしてみると、

calc2.peg

$ peglint calc2.peg
1:17 'Hello' is not defined.

と、今度はエラーメッセージが出力されました。

ソースコードのチェック

-s 'string'オプションを使って、PEGで定義された言語のソースコードをチェックすることができます。

$ peglint -s "2*(3+5)/4" calc.peg
$ peglint -s "(hello world)" calc.peg
1:2 syntax error

-f 'path'オプションを使うと、ソースファイルをチェックします。

AST(抽象構文木)モード

-astオプションを付けると、ASTを表示します。

$ peglint -s "2*(3+5)/4" -ast calc.peg
+ Expr
  + Sum
    + Product
      + Value
      + Value
        + Expr
          + Sum
            + Product
              + Value
            + Product
              + Value
      + Value

さらに-optオプションを付けると、冗長なノードを除いたASTを表示します。

$ peglint -s "2*(3+5)/4" -ast -opt calc.peg
+ Product
  + Value
  + Sum
    + Value
    + Value
  + Value

PEGを調整して、演算子や数字などのトークンを独立したルールとして切り出し、calc3.pegとしてみましょう。

calc3.peg

# 構文ルール
Expr    ← Sum
Sum     ← Product (SumOpe Product)*
Product ← Value (ProOpe Value)*
Value   ← Number / '(' Expr ')'

# 字句ルール
SumOpe  ← ('+' / '-')
ProOpe  ← ('*' / '/')
Number  ← [0-9]+

再度実行してみると、

 ~/Dropbox/Projects/go-peg-tutorial$ peglint -s "2*(3+5)/4" -ast -opt calc3.peg 
+ Product
  - Number ("2")
  - ProOpe ("*")
  + Sum
    - Number ("3")
    - SumOpe ("+")
    - Number ("5")
  - ProOpe ("/")
  - Number ("4")

ASTの葉ノードにToken文字列が表示され、式の構造が格段に掴みやすくなりました。

Traceモード

PEGパーサーの動作は「再帰下降構文解析」になります。-traceオプションを付けると、解析時に辿ったPEGのオペレータとルールを表示します。(結果が長いので端折ります…)

$ peglint -s "2*(3+5)/4" -trace calc3.peg
pos:lev	rule/ope
-------	--------
0:0	[Expr]
0:1	  reference
0:2	    [Sum]
0:3	      sequence
0:4	        reference
0:5	          [Product]
0:6	            sequence
0:7	              reference
0:8	                [Value]
0:9	                  prioritizedChoice
0:10	                    reference
0:11	                      [Number]
0:12	                        oneOrMore
0:13	                          characterClass
1:13	                          characterClass
1:7	              zeroOrMore
1:8	                sequence
1:9	                  reference
1:10	                    [ProOpe]
1:11	                      prioritizedChoice
1:12	                        literalString
2:9	                  reference
2:10	                    [Value]
2:11	                      prioritizedChoice

[以下に続く...]

まとめ

peglintを用いて、PEG文法ファイルの作成とチェックを簡単に行うことができました。さらに複雑な文法にチャレンジして、既存のプログラミング言語のPEGファイルを作成したり、オリジナル言語の文法を設計するのも楽しいと思います。

今後の課題は「エラーハンドリングの質の向上」です。(現在調査中ですが、なかなか大変そうですね…)

このツールは、Go言語用PEGライブラリ go-peg を使って実装されました。go-pegには本来のPEGの機能だけでなく、文法定義が楽になる便利な拡張機能が含まれています。機会があれば、これについても書きたいと思います。

PEGについては、以下のとても良い資料を参考にしました。