SGFパーサで四苦八苦
囲碁のプログラムのため、Jison(BisonのJavaScript版)を使ってSGFパーサを書きました。四苦八苦したので、その備忘録。
まず、すんなり書けた第一版。
/*
description: Parses SGF string and generates corresponding object.
note1: This parser doesn't interpret PropValue, returns all as text.
note2: Yout need at least one PropValues in each Property as I didn't understand elist of PropValue in the SGF specification.
*/
%{
/* prologue */
var strict = false; // if true, throw exception when overapping a property in a node.
var debug = true;
function addGameTrees(s, gts){
var n = s;
while (n._children.length == 1)
n = n._children[0];
n._children = gts;
return n;
}
%}
/* lexical grammar */
%lex
%%
\s*"(" return '(';
")"\s* return ')';
\s*";"\s* return ';';
"[" return '[';
"]"\s* return ']';
":" return ':';
\\[\r\n]+ return 'SOFT_LINEBREAK';
\\. return 'ESCAPE_CHAR';
[A-Z] return 'UC_LETTER';
[^();\[\]] return 'OTHER_CHAR';
<<EOF>> return 'EOF';
/lex
%% /* language grammar */
output
: collection EOF
{
if (debug) {
console.log($1);
/*
var n = $1[0];
while (n._children.length > 0) {
console.log(n);
n = n._children[0];
}
*/
}
return $1;
}
;
collection
: gametree
{ $$ = [$1]; }
| collection gametree
{ $1.push($2); $$ = $1; }
;
gametree
: '(' sequence ')'
{ $$ = $2; }
| '(' sequence gametrees ')'
{ $$ = addGameTrees($2, $3); }
;
gametrees
: gametree
{ $$ = [$1]; }
| gametrees gametree
{ $1.push($2); $$ = $1; }
;
sequence
: node
{ $$ = $1; }
| node sequence
{ $1._children.push($2); $$ = $1; }
;
node
: ';'
{ $$ = {_children: []}; }
| node property
{
if (strict == true && typeof $1[$2[0]] !== 'undefined') {
throw new Error('double properties');
} else {
$1[$2[0]] = $2[1];
$$ = $1;
}
}
;
property
: propident propvalues
{ $$ = [$1, $2]; }
;
propident
: UC_LETTER
{ $$ = $1; }
| propident UC_LETTER
{ $$ = $1 + $2; }
;
propvalues
: propvalue
{ $$ = $1; }
| propvalues propvalue
{ var a; if ($1 instanceof Array) a = $1; else a = [$1]; $$ = a.concat($2); }
;
propvalue
: '[' ']'
{ $$ = ''; }
| '[' cvaluetype ']'
{ $$ = $2; }
;
cvaluetype
: text
{ $$ = $1; }
| compose
{ $$ = $1; }
;
compose
: text ':' text
{ var o = {}; o[$1] = $2; $$ = o; }
;
text
: UC_LETTER
{ $$ = $1; }
| OTHER_CHAR
{ $$ = $1; }
| text UC_LETTER
{ $$ = $1 + $2; }
| text OTHER_CHAR
{ $$ = $1 + $2; }
| text SOFT_LINEBREAK
{ $$ = $1; }
| text ESCAPE_CHAR
{ $$ = $1 + $2.slice(1); }
;エスケープ文字の扱いをlex部分でどうやるのか思いつかず、ルールで記述しました。１カ所目をつぶって、その他は、SGFのEBNFを書き下しただけ。
すんなり動きました。
目をつぶった一カ所とは、プロパティの値が空も取りうるelistのサポート。第一版では空はなく、1つ以上の値を持ちます。
空の値をサポートするには、
propvalues
: propvalue
{ $$ = $1; }
| propvalues propvalue
{ var a; if ($1 instanceof Array) a = $1; else a = [$1]; $$ = a.concat($2); }
;を
propvalues
: /* empty */
{ $$ = null; }
| propvalue
{ $$ = $1; }
| propvalues propvalue
{ var a; if ($1 instanceof Array) a = $1; else a = [$1]; $$ = a.concat($2); }
;と替えて終了と思ったのですが、ここから四苦八苦が始まります。
このコードだと、"["をlook a headした時、emptyとしてreduceすることも、shiftすることもできる、ルールが衝突していると怒られます。emptyとしてreduceさせたくないのですが、その方法がわからない。
UPDATE(2014/05/07)
Jisonは「衝突している」というメッセージを出しますが、shift優先でコードを生成していたようです。従って、下記のような汚い変更は不要で、対策は「出力メッセージを気にしない」でした。
結局、トークンにする際に"["とその前のプロパティ名をくっつけるという第一版から見るとずいぶん汚いコードにしました。
/*
description: Parses SGF string and generates corresponding object.
note1: This parser doesn't interpret PropValue, returns all as text.
*/
%{
/* prologue */
var strict = false; // if true, throw exception when overapping a property in a node.
var debug = false;
function addGameTrees(s, gts){
var n = s;
while (n._children.length == 1)
n = n._children[0];
n._children = gts;
return n;
}
%}
/* lexical grammar */
%lex
%%
\s*"(" return '(';
")"\s* return ')';
\s*";"\s* return ';';
"[" return '[';
"]"\s* return ']';
":" return ':';
\s+ return 'WHITE_SPACE';
\\[\r\n]+ return 'SOFT_LINEBREAK';
\\. return 'ESCAPE_CHAR';
[A-Z]+(?=\s*\[) return 'PROPIDENT';
[A-Z]+ return 'EMPTY_PROPIDENT';
[^();\[\]] return 'OTHER_CHAR';
<<EOF>> return 'EOF';
/lex
%% /* language grammar */
output
: collection EOF
{
if (debug) {
console.log($1);
/*
var n = $1[0];
while (n._children.length > 0) {
console.log(n);
n = n._children[0];
}
*/
}
return $1;
}
;
collection
: gametree
{ $$ = [$1]; }
| collection gametree
{ $1.push($2); $$ = $1; }
;
gametree
: '(' sequence ')'
{ $$ = $2; }
| '(' sequence gametrees ')'
{ $$ = addGameTrees($2, $3); }
;
gametrees
: gametree
{ $$ = [$1]; }
| gametrees gametree
{ $1.push($2); $$ = $1; }
;
sequence
: node
{ $$ = $1; }
| node sequence
{ $1._children.push($2); $$ = $1; }
;
node
: ';'
{ $$ = {_children: []}; }
| node property
{
if (strict == true && typeof $1[$2[0]] !== 'undefined') {
throw new Error('double properties');
} else {
$1[$2[0]] = $2[1];
$$ = $1;
}
}
| node WHITE_SPACE property
{
if (strict == true && typeof $1[$3[0]] !== 'undefined') {
throw new Error('double properties');
} else {
$1[$3[0]] = $3[1];
$$ = $1;
}
}
;
property
: EMPTY_PROPIDENT
{ $$ = [$1, null]; }
| PROPIDENT propvalues
{ $$ = [$1, $2]; }
;
propvalues
: propvalue
{ $$ = $1; }
| propvalues propvalue
{ var a; if ($1 instanceof Array) a = $1; else a = [$1]; $$ = a.concat($2); }
;
propvalue
: '[' cvaluetype ']'
{ $$ = $2; }
;
cvaluetype
: text
{ $$ = $1; }
| compose
{ $$ = $1; }
;
compose
: text ':' text
{ var o = {}; o[$1] = $2; $$ = o; }
;
text
: /* empty */
{ $$ = '' }
| text WHITE_SPACE
{ $$ = $1 + $2; }
| text EMPTY_PROPIDENT
{ $$ = $1 + $2; }
| text OTHER_CHAR
{ $$ = $1 + $2; }
| text SOFT_LINEBREAK
{ $$ = $1; }
| text ESCAPE_CHAR
{ $$ = $1 + $2.slice(1); }
;どなたか、もっとすっきりした方法教えてくださーい！
