Erlang 付属のパーサジェネレータ Yecc を使ってみた

erlang yecc

Yacc なんかと同じ LALR(1) パーサジェネレータである Yecc を、ちょっと興味がわいてみたので使ってみた。ルール記述ファイルの形式は次のようにまったく Yecc 独自のものとなっている。Yacc よりはわかりやすいかも。

%% コメントは『%%』で始める
%% 以下「1個以上」の意味で『…』(3点リーダ) を使う。
%% 宣言の終わりを表す『.』(半角) はそのものを記述する。
%% 終端ルールにおいて、トークン名はルール名と同様に扱われる。

Header 《ヘッダ》 .
Expect 《予期される shift/reduce の数》 .
Nonterminals 《非終端ルール》 《非終端ルール》… .
Terminals 《終端ルール》 《終端ルール》… .
Left 《優先度》 《ルール》 《ルール》… .
Right 《優先度》 《ルール》 《ルール》… .
Unary 《優先度》 《ルール》 《ルール》… .
Rootsymbol 《ルートのルール》 .

《ルール》 -> 《ルール》 《ルール》… : 《Erlangの式》 .
《ルール》 -> 《ルール》 《ルール》… : 《Erlangの式》 .
《ルール》 -> 《ルール》 《ルール》… : 《Erlangの式》 .

Erlang code.
《Erlangのコード》

「a, b, c」のようなカンマ区切りのリストのパーサを書いてみる。もちろん LR パーサなので左再帰でないといけない。

test.yrl:

Nonterminals list.
Terminals item ','.
Rootsymbol list.

list -> item.
list -> list ',' item.

.yrl のファイルは erlc にそのまま渡すことで .erl にコンパイルできる。

$ erlc test.yrl

もしくはシェルで y(ファイル名) としてもよい。

できたモジュールは parse/1 という関数を提供している。この関数の引数に {トークン名, 行番号} というタプルのリストを渡してやることでパースできる。

Erlang R13B02 (erts-5.7.3) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [kernel-poll:false]

Eshell V5.7.3  (abort with ^G)
1> y(test).
{ok,"test.erl"}
2> c(test).
{ok,test}
3> test:parse([{item, 1}]).
{ok,'$undefined'}
4> test:parse([{item, 1}, {',', 1}, {item, 1}]).
{ok,'$undefined'}
5> test:parse([{item, 1}, {',', 1}, {hoge, 1}]).    
{error,{1,test,["syntax error before: ","hoge"]}}
6> test:parse([{item, 1}, {',', 1}]).           
{error,{1,test,["syntax error before: ",[]]}}
7>

意味値 (semantic value) は「'$1'」「'$2'」のような形式で表される。終端ルールの意味値は、パーサに渡されるタプルそのものとなっている。このタプルの 3 番目以降の要素はパーサに無視されるので、そこにトークン値を入れておく。

たとえば、

Nonterminals list.
Terminals item ','.
Rootsymbol list.

list -> item : [ element(3, '$1') ] .
list -> list ',' item : [ element(3, '$3') | '$1' ] .

Erlang code.
-import(lists).
-export([parse_csv/1]).
parse_csv(Tokens) ->
    case parse(Tokens) of
        { ok, Result } -> { ok, lists:reverse(Result) } ;
        _Else          -> _Else
    end .

こうしておいて、

Erlang R13B02 (erts-5.7.3) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [kernel-poll:false]

Eshell V5.7.3  (abort with ^G)
1> y(test).
{ok,"test.erl"}
2> c(test).
{ok,test}
3> test:parse_csv([{item, 1, "a"}, {',', 1}, {item, 1, "b"}]).
{ok,["a","b"]}

こんな感じにできるということ。

あとは字句解析をサクッと書いて

Nonterminals list.
Terminals item ','.
Rootsymbol list.

list -> item : [ element(3, '$1') ] .
list -> list ',' item : [ element(3, '$3') | '$1' ] .

Erlang code.
-import(lists).
-export([parse_csv/1]).

tokenize(String) -> lists:reverse(tokenize(String, [])) .

tokenize([], Tokens)         -> Tokens ;
tokenize([$,|Rest], Tokens)  -> tokenize(Rest, [{',', 1} | Tokens]) ;
tokenize([$\s|Rest], Tokens) -> tokenize(Rest, Tokens) ;
tokenize([$\t|Rest], Tokens) -> tokenize(Rest, Tokens) ;
tokenize([C|Rest], Tokens)   ->
    {Rest_, Token} = scan_component(Rest, [C]) ,
    tokenize(Rest_, [{item, 1, Token} | Tokens]) .

scan_component([$,|Rest], Buf) -> {[$,|Rest], lists:reverse(Buf)} ;
scan_component([], Buf)        -> {[], lists:reverse(Buf)} ;
scan_component([C|Rest], Buf)  -> scan_component(Rest, [C|Buf]) .

parse_csv(String) ->
    case parse(tokenize(String)) of
        { ok, Result } -> { ok, lists:reverse(Result) };
        _Else          -> _Else
    end.

こんな感じに。

Erlang R13B02 (erts-5.7.3) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [kernel-poll:false]

Eshell V5.7.3  (abort with ^G)
1> y(test).
{ok,"test.erl"}
2> c(test).
{ok,test}
3> test:parse_csv("a"). 
{ok,["a"]}
4> test:parse_csv("a, b").
{ok,["a","b"]}
5> test:parse_csv("a, b, c").
{ok,["a","b","c"]}
6> test:parse_csv("a, b, c, def").
{ok,["a","b","c","def"]}