yecc/leex を使ってみる

yacc/lex のようなツールは、いろんなプログラミング環境向けにあります。Erlang にも yecc/leex というツールがありますので、今日はそれをちょっと使ってみるみたいな。それにしても e がくどいですね。

Step1: まずは構文解析

まずはHelloWorld 的な位置づけの、電卓を書いてみます。とりあえず構文のみ。

prs.yrl

Nonterminals
lines line expression term block.

Terminals
integer
'(' ')' '+' '-' '*' '/' '~n'.

Rootsymbol lines.

lines -> line.
lines -> lines line.

line -> expression '~n'.

expression -> term.
expression -> expression '+' term.
expression -> expression '-' term.

term -> block.
term -> term '*' block.
term -> term '/' block.

block -> '(' expression ')'.
block -> integer.

yecc の構文は yacc を踏襲しない独自なものになっています。押さえるべきは、

Token が {token-name, line-num} というタプルであることが期待されていること。(token-name は atom であればよい)。
Nonterminal で非終端要素、 Terminals で終端要素を教えてあげて、 RootSymbols でルートシンボルを指定する
あとは還元規則を書くだけ。

ビルドは、Erl からやる場合はこんな感じ。

1> y(prs).
{ok,"prs.erl"}
2> c(prs).
{ok, prs}

生成された prs.erl を見ればわかりますが、parse/1 という関数がつくられているので、これに入力を渡してあげます。まだスキャナーが無いので、タブル直打ちで実行させてみましょう。

3> prs:parse([{integer, 1}, {'+',1}, {integer,1}, {'*',1}, {integer, 1}, {'~n',1}]).
{ok,'$undefined'}

一応エラーにならずに実行されました。

Step2: 計算をさせてみる

それだけだと何にも意味がないので、処理をつけていく。トークンは、{トークン種別, 行数, …好きに使ってね…} という構成なので、3要素目にたとえば数値を入れるとかして使う。

prs.yrl

Nonterminals
lines line expression term block.

Terminals
integer
'(' ')' '+' '-' '*' '/' '~n'.

Rootsymbol lines.


lines -> line.
lines -> lines line.

line -> expression '~n' : io:format("(ans) ~w~n", ['$1']).

expression -> term                : '$1'.
expression -> expression '+' term : '$1' + '$3'.
expression -> expression '-' term : '$1' + '$3'.

term -> block                     : '$1'.
term -> term '*' block            : '$1' * '$3'.
term -> term '/' block            : '$1' / '$3'.

block -> '(' expression ')'       : '$2'.
block -> integer                  : element(3, '$1').

構文木を構築せずにその場で計算してたり、一行毎に結果を標準出力に出したりしているなんともアレゲな感じですが、ゆるしてください。

意味値は '$1' で参照します。注意すべきは 1オリジン。ここいらへんは yacc と一緒です。

15> y(prs).                                                                    
{ok,"prs.erl"}
16> c(prs).                                                                    
{ok,prs}    
17> prs:parse([{integer, 1, 3}, {'+',1}, {integer,1,2}, {'*',1}, {integer, 1,5}, {'~n',1}]).
(ans) 13
{ok,'$undefined'}

Step3:Lexarを書く

leex をつかって字句解析器を作ります。まぁ、意外性のない感じです。

scn.xrl

Definitions.

INT = [0-9]+
WHITESPACE = [\s\t]


Rules.

{INT}         : {token, {integer, TokenLine, list_to_integer(TokenChars) }}.
\+            : {token, {'+', TokenLine}}.
\-            : {token, {'-', TokenLine}}.
\*            : {token, {'*', TokenLine}}.
\/            : {token, {'/', TokenLine}}.
\(            : {token, {'(', TokenLine}}.
\)            : {token, {')', TokenLine}}.
\n            : {token, {'~n', TokenLine}}.
{WHITESPACE}+ : skip_token.

Erlang code.

TokenLine でそのToken のいる行数がとれ、skip_token で飛ばしたいものを指定します*1。

Lexerのコードを作るには leex:file/1 を使います。 yecc みたいにy(). 的な erl 上の短縮名はないみたい。

40> leex:file('scn.xrl').
{ok,"./scn.erl"}
41> c(scn).   
{ok,scn}
42> scn:string("42+2 * 3").
{ok,[{integer,1,42},
     {'+',1},
     {integer,1,2},
     {'*',1},
     {integer,1,3}],
    1}
43>

せっかくなので、さっき作ったパーザーとくっつけてみます。srn:string/1 で文字列から字句解析。

86> prs:parse(element(2, scn:string("(1+1)\n"))).
(ans) 2
{ok,'$undefined'}

ファイルから読み込むのはイカのような感じ。

calc.txt

1 + 1
3 + 4 * 5
(6 + 7) * 8

file:read_file/1 で読み込んだ内容を binary_to_list/1 で文字列化して testscn:string/1 に食べさせる。

60> test:parse(element(2, testscn:string(binary_to_list(element(2, file:read_file('calc.txt')))))).
(ans) 2
(ans) 23
(ans) 104
{ok,'$undefined'}

Step4: 曖昧性と衝突の解決

Reduce/Recude 衝突と Shift/Reduce 衝突

LR(1) の構文解析の仕組みは、いっぱい本がでていますので、ホントはそちらを読むのが良いかと思いますが、とりあえず「どんな規則をかけばよいのか」「どんな規則を書いたらだめなのか」を説明します。

生成されるパーザーは、トークンを順番に喰っていき(これをシフト(Shift)という)、喰ったトークン列が還元規則の左側にマッチするとき右側に還元(Reduce)される
左辺側に還元(Reduce)するときには、ただ一つの可能性しか内容に書く。そうしないと Reduce/Reduce Conflict が起こる
シフト(Shift)すべきか還元(Reduce)すべきかわからなくなるときも Shift/Reduce Conflict が起こる

もうすこし補足すると LR(1) の 1 は、「一つ先読み」という意味なので、2番目3番目のやつは「一つ先読みしても/一つ先読みしたら」どっちをやればいいのかわからなくなるということ。

Reduce/Reduce衝突はたとえばこれ

err1.yrl

Nonterminals target block.
Terminals a b c.
Rootsymbol target.

target -> a b c.
target -> block.

block -> a b c.

10> y(err1).
err1.yrl: Parse action conflict scanning symbol '$end' in state 5:
   Reduce to target from a b c (rule 1 at line 5)
      vs.
   reduce to block from a b c (rule 3 at line 8).
err1.yrl: Warning: conflicts: 0 shift/reduce, 1 reduce/reduce
error

a b c と食べた時、どちらの還元規則を適用すればいいか、パーザーにはわかりません。これはエラーになります。

Shift/Reduce 衝突はこんな感じ。

err2.yrl

Nonterminals target block.
Terminals a b c d.
Rootsymbol target.

target -> a b c d.
target -> block d.

block -> a b c.

12> y(err2).
err2.yrl: Warning: conflicts: 1 shift/reduce, 0 reduce/reduce
{ok,"err2.erl"}

a b c と来た場合、その後 d をシフトすべきか、 a b c をblock に還元すべきかわかりません。これは、警告になります。

shift/reduce 衝突はよ中置演算での数式と、ぶら下がり else が典型的です。たとえば以下の様な規則において、"a + b - c" という入力があったとき a + b の次のアクションとして、"a + b" を式に還元すべきか、- c をシフトすべきかわかりません。

err3.yrl

Nonterminals exp.
Terminals integer '+' '-'.
Rootsymbol exp.

exp -> integer         : element(3, '$1').
exp -> exp '+' exp     : {'+', '$1', '$3'}.
exp -> exp '-' exp     : {'-', '$1', '$3'}.

26> y(err3).
err3.yrl: Warning: conflicts: 4 shift/reduce, 0 reduce/reduce
{ok,"err3.erl"}

ちなみにこの警告を無視するとどうなるかというと、右結合として処理されます。

28> err3:parse([{integer,0,"1"}, {'+',0}, {integer,0,"2"}, {'-',0}, {integer,0,"3"}]).  
{ok,{'+',"1",{'-',"2","3"}}}

これを避けるため、Step1 では term という非終端要素を用意して、二項演算子の右辺と左辺を別の要素として定義しているわけですね。（さらに、* と / の優先度を実現するために block という要素も作って３段構えになっています）

結合規則と優先順の指定（優先順位規則）

本質的には上記のように逃げる（というより構文としてちゃんと定義してあげる）のが正しいのですが、それは結構めんどくさいことも多いので、Yacc のようなパーザジェネレータはトークンに対してどちらに結合するのかと、その優先順位を指定することが出来るオプションが設けられていることが多いです。もちろん yecc にもありますので、それを使ってみます。

prs.yrl

Nonterminals
lines line expression uminus.

Terminals
integer
float
'(' ')' '+' '-' '*' '/' '~n'.

Left  300 '+' '-'.
Left  400 '*' '/'.
Unary 500 uminus.

Rootsymbol lines.

lines -> line           : ['$1'].
lines -> lines line     : '$1' ++ ['$2'].

line -> expression      : io:format("(ans1) ~w~n", ['$1']), '$1'.
line -> expression '~n' : io:format("(ans2) ~w~n", ['$1']), '$1'.

expression -> expression '+' expression : '$1' + '$3'.
expression -> expression '-' expression : '$1' - '$3'.
expression -> expression '*' expression : '$1' * '$3'.
expression -> expression '/' expression : '$1' / '$3'.
expression -> '(' expression ')'        : '$2'.
expression -> integer                   : element(3, '$1').
expression -> float                     : element(3, '$1').
expression -> uminus                    : '$1'.

uminus -> '-' expression                : io:format("(minus~w)", ['$2']),  -1 * '$2'.

scn.xrl

Definitions.

INT = [0-9]+
WHITESPACE = [\s\t]


Rules.
{INT}\.{INT}  : {token, {float,   TokenLine, list_to_float(TokenChars) }}.
{INT}         : {token, {integer, TokenLine, list_to_integer(TokenChars) }}.
\+            : {token, {'+', TokenLine}}.
\-            : {token, {'-', TokenLine}}.
\*            : {token, {'*', TokenLine}}.
\/            : {token, {'/', TokenLine}}.
\(            : {token, {'(', TokenLine}}.
\)            : {token, {')', TokenLine}}.
\n            : {token, {'~n', TokenLine}}.
{WHITESPACE}+ : skip_token.

Erlang code.

calc.erl

-module(calc).
-export([from_string/1, from_file/1]).

from_string( String ) ->
    {ok, Tokens, _} = scn:string(String),
    {ok, AnsList}   = prs:parse(Tokens),
    AnsList.

from_file( FileName )->
    {ok, F} = file:read_file(FileName),
    from_string(binary_to_list(F)).

解説

Left  300 '+' '-'.
Left  400 '*' '/'.
Unary 500 uminus.

の部分が結合規則になります。どのように結合するか（あるいはしないか）を Left Right Nonassoc で指定します。その次の数値は優先順位になります。数字の大きい方が優先順位が高いです。

Left と Right の働きは以下を見るとわかりやすいかな。

test1.yrl

Nonterminals exp.
Terminals integer '+' '-'.
Rootsymbol exp.

Left 100 '+' '-'.

exp -> integer         : element(3, '$1').
exp -> exp '+' exp     : {'+', '$1', '$3'}.
exp -> exp '-' exp     : {'-', '$1', '$3'}.

test2.yrl

Nonterminals exp.
Terminals integer '+' '-'.
Rootsymbol exp.

Right 100 '+' '-'.

exp -> integer         : element(3, '$1').
exp -> exp '+' exp     : {'+', '$1', '$3'}.
exp -> exp '-' exp     : {'-', '$1', '$3'}.

3> test1:parse([{integer,0,"1"}, {'+',0}, {integer,0,"2"}, {'-',0}, {integer,0,"3"}]).
{ok,{'-',{'+',"1","2"},"3"}}
6> test2:parse([{integer,0,"1"}, {'+',0}, {integer,0,"2"}, {'-',0}, {integer,0,"3"}]).
{ok,{'+',"1",{'-',"2","3"}}}

ちなみに

test3.yrl

Nonterminals exp.
Terminals integer '+' '-'.
Rootsymbol exp.

Nonassoc 100 '+' '-'.

exp -> integer         : element(3, '$1').
exp -> exp '+' exp     : {'+', '$1', '$3'}.
exp -> exp '-' exp     : {'-', '$1', '$3'}.

にすると、

9> test3:parse([{integer,0,"1"}, {'+',0}, {integer,0,"2"}, {'-',0}, {integer,0,"3"}]).
{error,{0,test3,["syntax error before: ","'-'"]}}

とエラーになります。これは例えば C言語で、 "A < B < C" がエラーになるのを期待するようなケースですね。

よく単行演算の '-' をゴニョゴニョするために使われる Yacc の %prec に相当するものはなさそうで、そのかわりUnarry を使うようです。 %prec は他にもいろいろできちゃうので、よくないな、と廃止されたんじゃないかな、とか思ったり。

もし、

Left  300 '+' '-'.
Left  400 '*' '/'.
Unary 100 uminus.

のようにしてパーザーを生成させると

83> calc:from_string("-3+2").       
(minus6)(ans1) -5
[-5]

となり-(3+2)となるのがわかります。

まとめ

優先順位規則の適用は、シンプルに shift/reduce衝突を解決でき、すっきりとした文法記述を実現するスマートな手段に思えます。しかし、それが効果的に振る舞う状況は限られており、その実態は goto 文のように厄介な極まりない難読文法を作ってしまいがちです。

lex & yacc プログラミングの 3.5.1 より引用すると、

文法中で発生するすべてのシフト/還元衝突は優先順位規則を使用することで解消することが出来る。しかしながら、この考え方はけっして頭のいい方法ではない。数式文法中の衝突の原因は簡単に理解できるので、優先順位規則がもたらす効果も明白であった。ほかの場合でも、優先順位規則はシフト/還元衝突の問題を解消してくれるが、優先順位規則が文法にもたらす影響というものは、一般には判断しづらい。
優先順位を使うのは次の二つの場合にとどめるように忠告しておく。数式文法中と if-then-else形式の文法中での「懸垂 else (dangling else)」を解消する場合である。これ以外の場合には、できるならば、文法を修正して衝突を解消したほうがいい。

なんてことが書いてあります。ゴールデンハンマーしないように気をつけたいところです。