PEG Linter ー peglint

# PEG Linter ー **peglint**

PEGとGo言語の勉強のために、PEGの構文チェッカー「[PEG Linter ー **peglint**](https://github.com/yhirose/go-peg/tree/master/cmd/peglint) 」を作ってみました。

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

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

## PEGの構文チェック

[Wikipedia](https://en.wikipedia.org/wiki/Parsing_expression_grammar#Examples)にある以下の例をコピペして、`calc.peg`に保存してください。

```peg:calc.peg
Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Value (('*' / '/') Value)*
Value   ← [0-9]+ / '(' Expr ')'
```

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

```bash
$ peglint calc.peg
```

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

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

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

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

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

## ソースコードのチェック

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

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

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

## AST(抽象構文木)モード

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

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

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

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

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

```peg:calc3.peg
# 構文ルール
Expr    ← Sum
Sum     ← Product (SumOpe Product)*
Product ← Value (ProOpe Value)*
Value   ← Number / '(' Expr ')'

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

再度実行してみると、

```bash
 ~/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のオペレータとルールを表示します。(結果が長いので端折ります…)

```bash
$ 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**](https://github.com/yhirose/go-peg) を使って実装されました。**go-peg**には本来のPEGの機能だけでなく、文法定義が楽になる便利な拡張機能が含まれています。機会があれば、これについても書きたいと思います。

PEGについては、以下のとても良い資料を参考にしました。
 
 * [Bryan Fordさんの論文](http://www.brynosaurus.com/pub/lang/peg.pdf)
 * [kmizuさんの「PEG基礎文法最速マスター」](http://kmizu.hatenablog.com/entry/20100203/1265183754)
 * [Wikipediaの記事](https://en.wikipedia.org/wiki/Parsing_expression_grammar)