文章出處：http://www.limodev.cn/blog
作者聯系方式：李先靜 <xianjimli at hotmail dot com>
系統程序員成長計劃-文本處理(一)
狀態機(4)
XML解析器
XML（Extensible Markup Language）即可擴展標記語言，也是一種常用的數據文件格式。相對于INI來說，它要復雜得多，INI只能保存線性結構的數據，而XML可以保存樹形結構的數據。先看下面的例子：
<?xml version="1.0" encoding="utf-8"?>
<mime-type xmlns="http://www.freedesktop.org/standards/shared-mime-info" type="all/all">
<!--Created automatically by update-mime-database. DO NOT EDIT!-->
<comment>all files and folders</comment>
</mime-type>
第一行稱為處理指令(PI)，是給解析器用的。這里告訴解析器，當前的XML文件遵循XML 1.0規范，文件內容用UTF-8編碼。
第二行是一個起始TAG，TAG的名稱為mime-type。它有兩個屬性，第一個屬性的名稱為xmlns，值為 http://www.freedesktop.org/standards/shared-mime-info。第二個屬性的名稱為type，值為 all/all。
第三行是一個注釋。
第四行包括一個起始TAG，一段文本和結束TAG。
第五行是一個結束TAG。
XML本身的格式不是本文的重點，我們不詳細討論了。這里的重點是如何用狀態機解析格式復雜的數據。
按照前面的方法，先把數據讀入到一個緩沖區中，讓一個指針指向緩沖區的頭部，然后移動指針，直到指向緩沖區的尾部。在這個過程中，指針可能指向：起始TAG，結束TAG，注釋，處理指令和文本。由此我們定義出狀態機的主要狀態：
1. 起始TAG狀態
2. 結束TAG狀態
3. 注釋狀態
4. 處理指令狀態
5. 文本狀態
由于起始TAG、結束TAG、注釋和處理指令都在字符‘<’和‘>’之間，所以當讀入字符‘<’時，我們還無法知道當前的狀態，為了便于處理，我們引入一個中間狀態，稱為“小于號之后”的狀態。在讀入字符‘<’和‘!’之后，還要讀入兩個‘-’，才能確定進入注釋狀態，為了便于處理，再引入兩個中間狀態“注釋前一”和“注釋前二”。再引入一個“空”狀態，表示不在上述任何狀態中。
狀態轉換函數：
1. 在“空”狀態下，讀入字符‘<’，進入“小于號之后”狀態。
2. 在“空”狀態下，讀入非‘<’非空白的字符，進入“文本”狀態。
3. 在“小于號之后”狀態下，讀入字符‘！’，進入“注釋前一” 狀態。
4. 在“小于號之后”狀態下，讀入字符‘?’，進入“處理指令”狀態。
5. 在“小于號之后”狀態下，讀入字符‘/’，進入“結束TAG”狀態。
6. 在“小于號之后”狀態下，讀入有效的ID字符，進入“起始TAG”狀態。
7. 在“注釋前一” 狀態下，讀入字符‘-’， 進入“注釋前二” 狀態。
8. 在“注釋前二” 狀態下，讀入字符‘-’， 進入“注釋” 狀態。
9. 在 “起始TAG” 狀態、“結束TAG” 狀態 、“文本” 狀態、“注釋”狀態 和“處理指令”狀態結束后，重新回到“空”狀態下。
這個狀態機的圖形表示如下：
下面我們來看看代碼實現：
void xml_parser_parse(XmlParser* thiz, const char* xml)
{
/*定義狀態的枚舉值*/
enum _State
{
STAT_NONE,
STAT_AFTER_LT,
STAT_START_TAG,
STAT_END_TAG,
STAT_TEXT,
STAT_PRE_COMMENT1,
STAT_PRE_COMMENT2,
STAT_COMMENT,
STAT_PROCESS_INSTRUCTION,
}state = STAT_NONE;
thiz->read_ptr = xml;
/*指針從頭移動到尾*/
for(; *thiz->read_ptr != '\0'; thiz->read_ptr++)
{
char c = thiz->read_ptr[0];
switch(state)
{
case STAT_NONE:
{
if(c == '<')
{
/*在“空”狀態下，讀入字符‘<’，進入“小于號之后”狀態。*/
xml_parser_reset_buffer(thiz);
state = STAT_AFTER_LT;
}
else if(!isspace(c))
{
/*在“空”狀態下，讀入非‘<’非空白的字符，進入“文本”狀態。*/
state = STAT_TEXT;
}
break;
}
case STAT_AFTER_LT:
{
if(c == '?')
{
/*在“小于號之后”狀態下，讀入字符‘?’，進入“處理指令”狀態。*/
state = STAT_PROCESS_INSTRUCTION;
}
else if(c == '/')
{
/*在“小于號之后”狀態下，讀入字符‘/’，進入“結束TAG”狀態。*/
state = STAT_END_TAG;
}
else if(c == '!')
{
/*在“小于號之后”狀態下，讀入字符‘！’，進入“注釋前一” 狀態*/
state = STAT_PRE_COMMENT1;
}
else if(isalpha(c) || c == '_')
{
/*在“小于號之后”狀態下，讀入有效的ID字符，進入“起始TAG”狀態。*/
state = STAT_START_TAG;
}
else
{
}
break;
}
case STAT_START_TAG:
{
/*進入子狀態*/
xml_parser_parse_start_tag(thiz);
state = STAT_NONE;
break;
}
case STAT_END_TAG:
{
/*進入子狀態*/
xml_parser_parse_end_tag(thiz);
state = STAT_NONE;
break;
}
case STAT_PROCESS_INSTRUCTION:
{
/*進入子狀態*/
xml_parser_parse_pi(thiz);
state = STAT_NONE;
break;
}
case STAT_TEXT:
{
/*進入子狀態*/
xml_parser_parse_text(thiz);
state = STAT_NONE;
break;
}
case STAT_PRE_COMMENT1:
{
if(c == '-')
{
/*在“注釋前一” 狀態下，讀入字符‘-’， 進入“注釋前二” 狀態。*/
state = STAT_PRE_COMMENT2;
}
else
{
}
break;
}
case STAT_PRE_COMMENT2:
{
if(c == '-')
{
/*在“注釋前二” 狀態下，讀入字符‘-’， 進入“注釋” 狀態。*/
state = STAT_COMMENT;
}
else
{
}
}
case STAT_COMMENT:
{
/*進入子狀態*/
xml_parser_parse_comment(thiz);
state = STAT_NONE;
break;
}
default:break;
}
if(*thiz->read_ptr == '\0')
{
break;
}
}
return;
}
解析并沒有在此結束，原因是像“起始TAG”狀態和“處理指令”狀態等，它們不是原子的，內部還包含一些子狀態，如TAG名稱，屬性名和屬性值等，它們需要進一步分解。在考慮子狀態時，我們可以忘掉它所處的上下文，只考慮子狀態本身，這樣問題會得到簡化。下面看一下起始TAG的狀態機。
假設我們要解析下面這樣一個起始TAG：
<mime-type xmlns=”http://www.freedesktop.org/standards/shared-mime-info” type=”all/all”>
我們應該怎樣去做呢？還是按前面的方法，讓一個指針指向緩沖區的頭部，然后移動指針，直到指向緩沖區的尾部。在這個過程中，指針可能指向，TAG名稱，屬性名和屬性值。由此我們可以定義出狀態機的主要狀態：
1. “TAG名稱”狀態
2. “屬性名”狀態
3. “屬性值”狀態
為了方便處理，再引兩個中間狀態，“屬性名之前”狀態和“屬性值之前”狀態。
狀態轉換函數：
初始狀態為“TAG名稱”狀態
1. 在“TAG名稱”狀態下，讀入空白字符，進入“屬性名之前”狀態。
2. 在“TAG名稱”狀態下，讀入字符‘/’或‘>’，進入“結束”狀態。
3. 在“屬性名之前”狀態下，讀入其它非空白字符，進入“屬性名”狀態。
4. 在“屬性名”狀態下，讀入字符‘=’，進入“屬性值之前”狀態。
5. 在“屬性值之前”狀態下，讀入字符‘“’，進入“屬性值”狀態。
6. 在“屬性值”狀態下，讀入字符‘”’，成功解析屬性名和屬性值，回到“屬性名之前”狀態。
7. 在“屬性名之前”狀態下，讀入字符‘/’或‘>’，進入“結束”狀態。
由于處理指令(PI)里也包含了屬性狀態，為了重用屬性解析的功能，我們把屬性的狀態再提取為一個子狀態。這樣，“起始TAG”狀態的圖形表示如下：
下面我們看代碼實現：
static void xml_parser_parse_attrs(XmlParser* thiz, char end_char)
{
int i = 0;
enum _State
{
STAT_PRE_KEY,
STAT_KEY,
STAT_PRE_VALUE,
STAT_VALUE,
STAT_END,
}state = STAT_PRE_KEY;
char value_end = '\"';
const char* start = thiz->read_ptr;
thiz->attrs_nr = 0;
for(; *thiz->read_ptr != '\0' && thiz->attrs_nr < MAX_ATTR_NR; thiz->read_ptr++)
{
char c = *thiz->read_ptr;
switch(state)
{
case STAT_PRE_KEY:
{
if(c == end_char || c == '>')
{
/*在“屬性名之前”狀態下，讀入字符‘/’或‘>’，進入“結束”狀態。*/
state = STAT_END;
}
else if(!isspace(c))
{
/*在“屬性名之前”狀態下，讀入其它非空白字符，進入“屬性名”狀態。*/
state = STAT_KEY;
start = thiz->read_ptr;
}
}
case STAT_KEY:
{
if(c == '=')
{
/*在“屬性名”狀態下，讀入字符‘=’，進入“屬性值之前”狀態。*/
thiz->attrs[thiz->attrs_nr++] = (char*)xml_parser_strdup(thiz, start, thiz->read_ptr - start);
state = STAT_PRE_VALUE;
}
break;
}
case STAT_PRE_VALUE:
{
/*在“屬性值之前”狀態下，讀入字符‘“’，進入“屬性值”狀態。*/
if(c == '\"' || c == '\'')
{
state = STAT_VALUE;
value_end = c;
start = thiz->read_ptr + 1;
}
break;
}
case STAT_VALUE:
{
/*在“屬性值”狀態下，讀入字符‘”’，成功解析屬性名和屬性值，回到“屬性名之前”狀態。*/
if(c == value_end)
{
thiz->attrs[thiz->attrs_nr++] = (char*)xml_parser_strdup(thiz, start, thiz->read_ptr - start);
state = STAT_PRE_KEY;
}
}
default:break;
}
if(state == STAT_END)
{
break;
}
}
for(i = 0; i < thiz->attrs_nr; i++)
{
thiz->attrs[i] = thiz->buffer + (size_t)(thiz->attrs[i]);
}
thiz->attrs[thiz->attrs_nr] = NULL;
return;
}
記得在XML里，單引號和雙引號都可以用來界定屬性值，所以上面對此做了特殊處理。
static void xml_parser_parse_start_tag(XmlParser* thiz)
{
enum _State
{
STAT_NAME,
STAT_ATTR,
STAT_END,
}state = STAT_NAME;
char* tag_name = NULL;
const char* start = thiz->read_ptr - 1;
for(; *thiz->read_ptr != '\0'; thiz->read_ptr++)
{
char c = *thiz->read_ptr;
switch(state)
{
case STAT_NAME:
{
/*在“TAG名稱”狀態下，讀入空白字符，屬性子狀態。*/
/*在“TAG名稱”狀態下，讀入字符‘/’或‘>’，進入“結束”狀態。*/
if(isspace(c) || c == '>' || c == '/')
{
state = (c != '>' && c != '/') ? STAT_ATTR : STAT_END;
}
break;
}
case STAT_ATTR:
{
/*進入“屬性”子狀態*/
xml_parser_parse_attrs(thiz, '/');
state = STAT_END;
break;
}
default:break;
}
if(state == STAT_END)
{
break;
}
}
for(; *thiz->read_ptr != '>' && *thiz->read_ptr != '\0'; thiz->read_ptr++);
return;
}
處理指令的解析和起始TAG的解析基本上是一樣的，這里只是看一下代碼：
static void xml_parser_parse_pi(XmlParser* thiz)
{
enum _State
{
STAT_NAME,
STAT_ATTR,
STAT_END
}state = STAT_NAME;
char* tag_name = NULL;
const char* start = thiz->read_ptr;
for(; *thiz->read_ptr != '\0'; thiz->read_ptr++)
{
char c = *thiz->read_ptr;
switch(state)
{
case STAT_NAME:
{
/*在“TAG名稱”狀態下，讀入空白字符，屬性子狀態。*/
/*在“TAG名稱”狀態下，‘>’，進入“結束”狀態。*/
if(isspace(c) || c == '>')
{
state = c != '>' ? STAT_ATTR : STAT_END;
}
break;
}
case STAT_ATTR:
{
/*進入“屬性”子狀態*/
xml_parser_parse_attrs(thiz, '?');
state = STAT_END;
break;
}
default:break;
}
if(state == STAT_END)
{
break;
}
}
tag_name = thiz->buffer + (size_t)tag_name;
for(; *thiz->read_ptr != '>' && *thiz->read_ptr != '\0'; thiz->read_ptr++);
return;
}
注釋，結束TAG和文本的解析非常簡單，這里結合代碼看看就行了：
“注釋”子狀態的處理：
static void xml_parser_parse_comment(XmlParser* thiz)
{
enum _State
{
STAT_COMMENT,
STAT_MINUS1,
STAT_MINUS2,
}state = STAT_COMMENT;
const char* start = ++thiz->read_ptr;
for(; *thiz->read_ptr != '\0'; thiz->read_ptr++)
{
char c = *thiz->read_ptr;
switch(state)
{
case STAT_COMMENT:
{
/*在“注釋”狀態下，讀入‘-’，進入“減號一”狀態。*/
if(c == '-')
{
state = STAT_MINUS1;
}
break;
}
case STAT_MINUS1:
{
if(c == '-')
{
/*在“減號一”狀態下，讀入‘-’，進入“減號二”狀態。*/
state = STAT_MINUS2;
}
else
{
state = STAT_COMMENT;
}
break;
}
case STAT_MINUS2:
{
if(c == '>')
{
/*在“減號二”狀態下，讀入‘>’，結束解析。*/
return;
}
else
{
state = STAT_COMMENT;
}
}
default:break;
}
}
return;
}
“結束TAG”子狀態的處理：
static void xml_parser_parse_end_tag(XmlParser* thiz)
{
char* tag_name = NULL;
const char* start = thiz->read_ptr;
for(; *thiz->read_ptr != '\0'; thiz->read_ptr++)
{
/*讀入‘>’，結束解析。*/
if(*thiz->read_ptr == '>')
{
break;
}
}
return;
}
“文本”子狀態的處理：
static void xml_parser_parse_text(XmlParser* thiz)
{
const char* start = thiz->read_ptr - 1;
for(; *thiz->read_ptr != '\0'; thiz->read_ptr++)
{
char c = *thiz->read_ptr;
/*讀入‘>’，結束解析。*/
if(c == '<')
{
if(thiz->read_ptr > start)
{
}
thiz->read_ptr--;
return;
}
else if(c == '&')
{
/*讀入‘&’，進入實體(entity)解析子狀態。*/
xml_parser_parse_entity(thiz);
}
}
return;
}
實體(entity)子狀態比較簡單，這里不做進一步分析了，留給讀者做練習吧