用C语言实现SGF格式围棋棋谱解析器


这是本人（liigo）独立实现的SGF格式围棋棋谱文件解析器，本文介绍其实现细节。网络上肯定可以找到完善的开源的SGF解析器，这是毋庸置疑的，我不直接使用它们，也不参考它们的实现代码，而是自己独立编码实现，是有原因的，因为我想自己重复发明轮子，并且认为这样更有助于提高我的编码能力。（关于我的“一定要学会重复发明轮子”的不成熟的论调，今后我将会专门撰文表述。）
　　我（liigo）开发的这个SGF解析器，采用基于事件的简单API，类似于XML解析器中的SAX(Simple API for XML)。这种解析器的核心是：由用户事先提供一系列回调函数，解析器在解析的过程中，依次调用相关的回调函数并传入相应参数，用户程序在回调函数中做出相应的处理。此类解析器属于轻量级的解析器，解析速度快，占用内存少，结构清晰易于实现，只是相对来说不如基于DOM的解析器方便使用。
　　SGF格式，Smart Game Format，被设计用来记录多种游戏类棋谱的通用格式，在围棋领域被发扬光大，是用于描述围棋棋谱的最重要也最通用的形式。它是纯文本的、基于树（TREE）的结构，便于识别、存储和传输。其格式简洁实用，也非常易于编程解析。SGF格式官方规范网址为：http://www.red-bean.com/sgf/。（说到围棋棋谱，不得不赞叹一下，它只需用一幅图就可以完整还原一盘棋从始至终的风云变幻；作为对比，象棋一幅图只能描述对弈中某一时刻的场景。）
　　SGF的主要结构由树（GameTree）、节点序列（Sequence）、节点（Node）、属性（Property）等组成。其中“属性”为最重要的基本单位，它由属性标识（PropIdent）和属性值（PropValue）组成。由分号“;”分隔的多个属性，称为节点。多个节点顺序排列称为节点序列。由括号“(”“)”括起来的节点序列，称为树，树中可包含子树。SGF的EBNF定义如下（参见html#ebnf-def">http://www.red-bean.com/sgf/sgf4.html#ebnf-def）：
view plaincopy to clipboardprint?
Collection = GameTree { GameTree }   
GameTree   = "(" Sequence { GameTree } ")"  
Sequence   = Node { Node }   
Node       = ";" { Property }   
Property   = PropIdent PropValue { PropValue }   
PropIdent  = UcLetter { UcLetter }   
PropValue  = "[" CValueType "]"  
CValueType = (ValueType | Compose)   
ValueType  = (None | Number | Real | Double | Color | SimpleText | Text | Point  | Move | Stone)  
Collection = GameTree { GameTree }
GameTree   = "(" Sequence { GameTree } ")"
Sequence   = Node { Node }
Node       = ";" { Property }
Property   = PropIdent PropValue { PropValue }
PropIdent  = UcLetter { UcLetter }
PropValue  = "[" CValueType "]"
CValueType = (ValueType | Compose)
ValueType  = (None | Number | Real | Double | Color | SimpleText | Text | Point  | Move | Stone) 
　　以下是一个简单的有一定代表性的SGF文本，先让大家有一个感性认识：
+ expand sourceview plaincopy to clipboardprint?
(;FF[4]GM[1]SZ[19]FG[257:Figure 1]PM[1]   
PB[Takemiya Masaki]BR[9 dan]PW[Cho Chikun]   
WR[9 dan]RE[W+Resign]KM[5.5]TM[28800]DT[1996-10-18,19]   
EV[21st Meijin]RO[2 (final)]SO[Go World #78]US[Arno Hollosi]   
;B[pd];W[dp];B[pp];W[dd];B[pj];W[nc];B[oe];W[qc];B[pc];W[qd]   
(;B[qf];W[rf];B[rg];W[re];B[qg];W[pb];B[ob];W[qb]   
(;B[mp];W[fq];B[ci];W[cg];B[dl];W[cn];B[qo];W[ec];B[jp];W[jd]   
;B[ei];W[eg];B[kk]LB[qq:a][dj:b][ck:c][qp:d]N[Figure 1]   
  
;W[me]FG[257:Figure 2];B[kf];W[ke];B[lf];W[jf];B[jg]   
(;W[mf];B[if];W[je];B[ig];W[mg];B[mj];W[mq];B[lq];W[nq]   
(;B[lr];W[qq];B[pq];W[pr];B[rq];W[rr];B[rp];W[oq];B[mr];W[oo];B[mn]   
(;W[nr];B[qp]LB[kd:a][kh:b]N[Figure 2]   
  
;W[pk]FG[257:Figure 3];B[pm];W[oj];B[ok];W[qr];B[os];W[ol];B[nk];W[qj]   
;B[pi];W[pl];B[qm];W[ns];B[sr];W[om];B[op];W[qi];B[oi]   
(;W[rl];B[qh];W[rm];B[rn];W[ri];B[ql];W[qk];B易做图;W[sk];B[sh];W[og]   
;B[oh];W[np];B[no];W[mm];B[nn];W[lp];B[kp];W[lo];B[ln];W[ko];B[mo]   
;W[jo];B[km]N[Figure 3])   
  
(;W[ql]VW[ja:ss]FG[257:Dia. 6]MN[1];B[rm];W[ph];B[oh];W[pg];B[og];W[pf]   
;B[qh];W[qe];B[sh];W[of];B[sj]TR[oe][pd][pc][ob]LB[pe:a][sg:b][si:c]   
N[Diagram 6]))   
  
(;W[no]VW[jj:ss]FG[257:Dia. 5]MN[1];B[pn]N[Diagram 5]))   
  
(;B[pr]FG[257:Dia. 4]MN[1];W[kq];B[lp];W[lr];B[jq];W[jr];B[kp];W[kr];B[ir]   
;W[hr]LB[is:a][js:b][or:c]N[Diagram 4]))   
  
(;W[if]FG[257:Dia. 3]MN[1];B[mf];W[ig];B[jh]LB[ki:a]N[Diagram 3]))   
  
(;W[oc]VW[aa:sk]FG[257:Dia. 2]MN[1];B[md];W[mc];B[ld]N[Diagram 2]))   
  
(;B[qe]VW[aa:sj]FG[257:Dia. 1]MN[1];W[re];B[qf];W[rf];B[qg];W[pb];B[ob]   
;W[qb]LB[rg:a]N[Diagram 1]))  
(;FF[4]GM[1]SZ[19]FG[257:Figure 1]PM[1]
PB[Takemiya Masaki]BR[9 dan]PW[Cho Chikun]
WR[9 dan]RE[W+Resign]KM[5.5]TM[28800]DT[1996-10-18,19]
EV[21st Meijin]RO[2 (final)]SO[Go World #78]US[Arno Hollosi]
;B[pd];W[dp];B[pp];W[dd];B[pj];W[nc];B[oe];W[qc];B[pc];W[qd]
(;B[qf];W[rf];B[rg];W[re];B[qg];W[pb];B[ob];W[qb]
(;B[mp];W[fq];B[ci];W[cg];B[dl];W[cn];B[qo];W[ec];B[jp];W[jd]
;B[ei];W[eg];B[kk]LB[qq:a][dj:b][ck:c][qp:d]N[Figure 1]
;W[me]FG[257:Figure 2];B[kf];W[ke];B[lf];W[jf];B[jg]
(;W[mf];B[if];W[je];B[ig];W[mg];B[mj];W[mq];B[lq];W[nq]
(;B[lr];W[qq];B[pq];W[pr];B[rq];W[rr];B[rp];W[oq];B[mr];W[oo];B[mn]
(;W[nr];B[qp]LB[kd:a][kh:b]N[Figure 2]
;W[pk]FG[257:Figure 3];B[pm];W[oj];B[ok];W[qr];B[os];W[ol];B[nk];W[qj]
;B[pi];W[pl];B[qm];W[ns];B[sr];W[om];B[op];W[qi];B[oi]
(;W[rl];B[qh];W[rm];B[rn];W[ri];B[ql];W[qk];B易做图;W[sk];B[sh];W[og]
;B[oh];W[np];B[no];W[mm];B[nn];W[lp];B[kp];W[lo];B[ln];W[ko];B[mo]
;W[jo];B[km]N[Figure 3])
(;W[ql]VW[ja:ss]FG[257:Dia. 6]MN[1];B[rm];W[ph];B[oh];W[pg];B[og];W[pf]
;B[qh];W[qe];B[sh];W[of];B[sj]TR[oe][pd][pc][ob]LB[pe:a][sg:b][si:c]
N[Diagram 6]))
(;W[no]VW[jj:ss]FG[257:Dia. 5]MN[1];B[pn]N[Diagram 5]))
(;B[pr]FG[257:Dia. 4]MN[1];W[kq];B[lp];W[lr];B[jq];W[jr];B[kp];W[kr];B[ir]
;W[hr]LB[is:a][js:b][or:c]N[Diagram 4]))
(;W[if]FG[257:Dia. 3]MN[1];B[mf];W[ig];B[jh]LB[ki:a]N[Diagram 3]))
(;W[oc]VW[aa:sk]FG[257:Dia. 2]MN[1];B[md];W[mc];B[ld]N[Diagram 2]))
(;B[qe]VW[aa:sj]FG[257:Dia. 1]MN[1];W[re];B[qf];W[rf];B[qg];W[pb];B[ob]
;W[qb]LB[rg:a]N[Diagram 1])) 
　　熟悉编写文本解析器的程序员朋友应该都清楚，根据EBNF定义，编写对应的解析器，是相当简单和直观的，貌似只是一项翻译性的工作。本人实现SGF解析器，再次印证了这个观点，大部分情况下，我只是按部就班地将EBNF翻译为C语言代码而已，呵呵。
　　我首先设计了“SGFParseContext”结构，用于保存解析器工作期间的相关数据：
view plaincopy to clipboardprint?
typedef struct _tagSGFParseContext   
{   
        void* pUserData;   
        int treeIndex;   
  
        PFN_ON_TREE pfnOnTree;   
        PFN_ON_TREE_END pfnOnTreeEnd;   
        PFN_ON_NODE pfnOnNode;   
        PFN_ON_NODE_END pfnOnNodeEnd;   
        PFN_ON_PROPERTY pfnOnProperty;   
  
        char idBuffer[16];   
        char* valueBuffer;   
        int valueBufferSize;   
}   
SGFParseContext;  
typedef struct _tagSGFParseContext
{
        void* pUserData;
        int treeIndex;

补充：软件开发 , C语言 ,