◇技術的制限を理想 と勘違い：yaccを継ぐ者

単なる技術的な制限に過ぎないものをそれが理想だと勘違いしてしまうことが あります。

構文解析ツールyaccと、構文解析論の話しです。

 yacc

yaccというのは文法定義を与えるとその定義に沿って入力文を解析する ツールです。（少し正確に言うとyaccは入力を解析 するプログラムを生成します）

yaccに与える文法定義法は簡単にすると次のような形です。

   // 例-1
   a : b c d
   e : f
   g : h i

構文の名前があり、その後ろにコロン、その後ろに構文要素が並びます。改行は 意味を持っておらず、

   a : b c d e : f g : h i

でも同じです。

実はyaccではこの形式の文を取り扱うことができないのです。自分自身の入力 となる文であるにも関わらずです。

 yaccとLR(1)とLR(2)

yaccはLR(1)という文法レベルのツールです。ある要素を取り扱うときに その１個先を読めば取り扱い法が定まるというものです。

例えば、次のような文だとしましょう。

   // 例-2
   a : b c d ;
   e : f ;
   g : h i ;

例-1との違いは、定義の終わりに必ずセミコロンがあるというものです。

この文で"d"の位置づけを考えましょう。dは１個先の";"を読めば、要素並び の最後であり、これで要素並びが終わることが分かります。

例-1ではどうでしょう？

dの１個先のeを読んだだけでは、要素並びの終わりかどうかは決定できません。 eの後に":"でなくfが来るとdは要素並びの途中として取り扱わなければなりません。

この文は２個先を読めば文法的位置づけが定まるLR(2)レベルなのです。

 yaccにLR(2)定義を与えた解析失敗例

実際に例-2に相当する構文定義をyaccに与えて、入力を解析させてみます。

%{
#include "test_4_y.h"
%}
%%
[ \t\n]*              ; // 空白
[a-zA-Z][a-zA-Z0-9_]* {
                        fprintf(stdout,"TOKEN:\"%s\"\n",yytext);
                        yylval.sval= (char*)strdup(yytext);
                        return NAME;
                      }
.                     {
                        fprintf(stdout,"TOKEN:\"%s\"\n",yytext);
                        return yytext[0];
                      }
//------------------- yaccによる構文定義
%{
#include <stdio.h>
int yywrap()               { return 1; }
void yyerror(const char* s){ fprintf(stderr,"%s\n",s);  }
int main(char**args)       { yyparse(); }
%}
%union { char *sval; }
%TOKEN <sval> NAME
%type  <sval> name
%start defs
%%
defs : def               { fprintf(stdout,"  defs:def\n"); }
     | defs def          { fprintf(stdout,"  defs:defs def\n"); }
def  : NAME ':' list     { fprintf(stdout,"  def:\"%s\" : list ;\n",$1);
                           free($1); }
list : /* null */        { fprintf(stdout,"  list:/* null */\n"); }
     | list NAME         { fprintf(stdout,"  list:list \"%s\"\n",$2);
                           free($2); }
//-------------------- 動作
TOKEN:"a"
TOKEN:":"
  list:/* null */
TOKEN:"b"
  list:list "b"
TOKEN:"c"
  list:list "c"
TOKEN:"d"
  list:list "d"
TOKEN:"e"
  list:list "e" <-- e も要素並びにしている
TOKEN:":"
syntax error    <-- 要素並びの後ろに":"が来るので構文エラー
test_4_y < test_4.txt

 解析可能ツールでの解析例

yaccとは異なるLR(n)レベルのツールによる解析例を載せます。nというのは 先読み数に制限がないということを表しています。 (このツールはLR手法を使っているわけではありませんが、LR(n)レベルの構文 を取り扱えるという意味でLR(n)レベルと記述しました）

このツールは複数ルート候補管理可能でルートが一つに定まった部分から 決定していくという単純なものです。構文定義には繰り返し{...}とオプション 指定[...]を可能としています。yaccとは異なり、構文の入り口、出口も 決定単位となっています。

//---------------------------------- 定義
@         ::= ?"[ \t\n\u3000]+" 
@         ::= ?"//.*$" 
@NAME     ::= ?"[a-zA-Z][0-9a-zA-Z]*" 
defs      ::= { def } 
def       ::= NAME ":" name-list
name-list ::= [{ NAME }]
//---------------------------------- 実行結果
入力      構文解析結果
a         <defs>　　　　　　　　　　　※1
          |  <def>
          |  |  <NAME text="a" />　   ※1
:         
b         |  |  <name-list>  　　　　 ※2
c         |  |  |  <NAME text="b" />　※2
d         |  |  |  <NAME text="c" />
e         |  |  |  <NAME text="d" />
:         |  |  </name-list>　　　　　※3
          |  </def>
          |  <def>
          |  |  <NAME text="e" />     ※3
f         |  |  <name-list>
g         |  |  |  <NAME text="f" />
:         |  |  </name-list>
          |  </def>
          |  <def>
          |  |  <NAME text="g" />
h         |  |  <name-list>
i         |  |  |  <NAME text="h" />
< EOF >   |  |  |  <NAME text="i" />
          |  |  </name-list>
          |  </def>
          </defs>
※1:aを読んだ時点でdefs入り口、def入り口も確定
※2:bを読んだだけではbの位置が確定できないのは、もし後ろに":"が来ると
　　bは要素並びの一つではなく、新たなdefの名前だから。
※3:":"を読んで"d"で要素並びが終わり、"e"が新たなdefの名前であること
　　が確定する。

このツールはオツアンドサンズで"オツライブラリ-symphonie"という名で仮公開されています。

• パッケージotsu.symphonieの説明

ライブラリ全体の説明は

• オツライブラリ

にあります。
オツアンドサンズのホームページは

• オツアンドサンズ

です。

 yaccはなぜLR(2)を自分の入力文に採用したか

実はyaccは例-1の形式の他に例-2の形式も受け付けるようになっています。

もし、例-2のLR(1)形式しか許さないとすればyaccの入力形式をyaccの入力 形式自身で表すことができ美しい感じがしますが、なぜそうしなかったの でしょう？

yacc自身の入力部はyaccで作られる訳ではないのでLR(1)にこだわる必要 は全くありません。極めて単純なリスト形式でしかないので、解析 手順を書き下ろすのも簡単です。

yaccとしては変にLR(1)にこだわって、入力を見づらくするより、 もっと良い形式を採用した結果LR(2)になったのです。

つまり、yaccはLR(1)のツールなんだけど、必ずしもLR(1)は理想的 なものではない事を自ら示しているのです。

これは非常にすばらしい技術的な姿勢だと思います。

提供する機能は必ずしも理想ではない。理想ではなくても 非常に役に立つ。

現実的な技術とはそういうものです。

 本題：後につづく者は。。。

yaccはLR(1)が理想ではないことを自ら示しています。

ところが、後にづづく者はyaccで考えが止まってしまうため、

• LR(1)こそ機械文法の理想　×

だという完全に誤った思想に陥ってしまいがちです。

「LR(1)が人間が見ても分かりやすい」などと言い出す。
そうではないことをyaccは示しているのです。

「大概のコンパイラ言語はLR(1)で定義されます。従ってLR(1)が 解析できれば十分」などと言い出す。
そうではないのです。それは単にyaccがLR(1)で、かつyaccが極めて 役に立つツールだったため、LR(1)文法を超える定義をしなく なっただけなのです。

新しい機械言語を設計する場合LR(1)レベルに抑えることは現実的 なことです。
しかし、それはツールの問題であって、構文理論の問題では ないのです。

yaccはすばらしいツールですが、構文理論を考える人間が yaccにとらわれてはなりません。
yaccベースの記述は理論ではなくHowToです。

＃＃＃　ところで　

「勘違いする」とは言いますが「勘違う」とは言いませんよね。

「すれ違う」とは言っても「すれ違いする」とは言わない。

どちらも「勘違い」「すれ違い」という名詞での扱いはする。

 2010/3/12

実例につかったツールへのリンク追加