CSV解析器實作

CSV解析器實作

     确切地說應該是TSV，即分隔符是Tab而不是Comma。除分隔符之外，CSV與TSV大同小異。

    這裡使用TSV主要原因是：Excel導出的CSV不是Unicode編碼，這樣會導緻某些符号丢失，而導出TXT時，可以選擇Unicode，但格式卻是TSV。

TSV文法可以用以下文法來描述：

p0:P -> Te

p1:T -> RT|ε

p2:R -> CMb

p3:M -> tCM|ε

p4:C -> s|ε

其中各非終結符與終結符的含義為：

P:The Whole TSV File

T:Like foobar

R:One Row in TSV

M:Context among One Row

C:Context of One Cell in Row

e:End Of File

t:Tab

s:String

b:LF or CRLF

ε:EmptyString

該文法是一個正規文法，因為它可以用有限狀态自動機來表示。m0,m1,m2,m3,m4分别為各個産生式對應的自動機。

m01->m012->m0123->m01234是将各産生式自動機組合的過程。

顯然得到最後的m01234是一個有限狀态自動機，該文法是一個正則文法，是可以用正規表達式來描述的。

出于簡化考慮，這裡把顯然沒有必要的兩條ε邊去掉，即到狀态Start與B合并到A中，為各個狀态标上序号後，得到M0.

邊ε的存在會讓程式實作極不美觀，是以使用子集法去掉ε，得到狀态轉換矩陣：

s	t	b	e
012	12	32	012	Accept
12	12	32	012	X
32	32	32	012	X

根據轉換矩陣很容易得到它的對應自動機M1.

下面是TSV的詞法分析器與文法分析器的粗略實作：

#define TOKEN_STRING    0
#define TOKEN_LINEBREAK 2
#define TOKEN_TAB       1
#define TOKEN_EOF       3

#define STATUS_012          0
#define STATUS_32           1
#define STATUS_12           2
#define STATUS_4            3
#define STATUS_X            4

static int GetToken( const wchar_t* pBuff, int* pLen )
{
    int nToken = TOKEN_EOF;
    const wchar_t* pos;

    if ( NULL == pBuff || 0 == pBuff[0] ) 
    {
        *pLen = 0;
        nToken = TOKEN_EOF;
    }
    else
    {
        switch ( pBuff[0] )
        {
            case '\n':
                nToken = TOKEN_LINEBREAK;
                *pLen = 1;
                break;
            case '\r':
                nToken = TOKEN_LINEBREAK;
                *pLen = ('\n' == pBuff[1] ? 2 : 1);
                break;
            case '\t':
                nToken = TOKEN_TAB;
                *pLen = 1;
                break;
            case '"':
                nToken = TOKEN_STRING;
                {
                    pos = pBuff+1;
                    while ( *pos )
                    {
                        if ( '"' == pos[0] && '"' == pos[1] )
                        {
                            pos+=2;
                        }
                        else if ( '"' == pos[0] )
                        {
                            pos++;
                            break;
                        }
                        else
                        {
                            pos++;
                        }
                    }
                    *pLen = pos-pBuff;
                }
                break;
            default:
                nToken = TOKEN_STRING;
                {
                    pos = pBuff+1;
                    while ( true )
                    {
                        wchar_t ch = *pos;
                        if ( 0 == ch || '\t' == ch || '\n' == ch || '\r' == ch )
                            break;
                        else
                            pos++;
                    }
                    *pLen = pos-pBuff;
                }
                break;
        }
    }

    return nToken;
}

// Return value: true: accept, false: grammar error
static bool AutoMachine( const wchar_t* pBuff, vector<vector<wstring>>& table )
{
    static int statusMatrix[3][4] = 
    {
        { STATUS_12, STATUS_32, STATUS_012, STATUS_4 },
        { STATUS_12, STATUS_32, STATUS_012, STATUS_X },
        { STATUS_32, STATUS_32, STATUS_012, STATUS_X },
    };

    table.clear();
    vector<wstring> line;   // Used to store the strings in one row

    int nStatus = STATUS_012;

    const wchar_t* pos = pBuff;
    bool bEpsilon = false;

    int nToken = TOKEN_LINEBREAK;
    int nLastToken = nToken;
    int nLen = 0;
    int tmpStatus;

    while ( STATUS_4 != nStatus && STATUS_X != nStatus )
    {
        nToken = GetToken( pos, &nLen );
        tmpStatus = nStatus;

        nStatus = statusMatrix[nStatus][nToken];

        switch ( nToken )
        {
            case TOKEN_STRING:
                if ( TOKEN_STRING == nLastToken )   // Merge the string at the last element
                    *line.rbegin() += wstring(pos, pos+nLen);
                else
                    line.push_back( wstring(pos, pos+nLen) );
                break;
            case TOKEN_TAB:
                if ( TOKEN_TAB == nLastToken || TOKEN_LINEBREAK == nLastToken )
                    line.push_back( L"" );
                break;
            case TOKEN_LINEBREAK:
                if ( TOKEN_TAB == nLastToken || TOKEN_LINEBREAK == nLastToken )
                    line.push_back( L"" );
                table.push_back( line );
                line.clear();
                break;
        }
		pos += nLen;
        nLastToken = nToken;
    }

    return nStatus == STATUS_4;
}