Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2108540
  • 博文数量: 413
  • 博客积分: 10926
  • 博客等级: 上将
  • 技术积分: 3862
  • 用 户 组: 普通用户
  • 注册时间: 2006-01-09 18:14
文章分类

全部博文(413)

文章存档

2015年(5)

2014年(1)

2013年(5)

2012年(6)

2011年(138)

2010年(85)

2009年(42)

2008年(46)

2007年(26)

2006年(59)

分类: LINUX

2011-12-23 16:04:52

转载时请注明出处和作者联系方式
文章出处:http://www.limodev.cn/blog
作者联系方式:李先静

系统程序员成长计划-文本处理(一)

状态机(4)

XML解析器

XML(Extensible Markup Language)即可扩展标记语言,也是一种常用的数据文件格式。相对于INI来说,它要复杂得多,INI只能保存线性结构的数据,而XML可以保存树形结构的数据。先看下面的例子:




all files and folders

第一行称为处理指令(PI),是给解析器用的。这里告诉解析器,当前的XML文件遵循XML 1.0规范,文件内容用UTF-8编码。

第二行是一个起始TAG,TAG的名称为mime-type。它有两个属性,第一个属性的名称为xmlns,值为 。第二个属性的名称为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:

我们应该怎样去做呢?还是按前面的方法,让一个指针指向缓冲区的头部,然后移动指针,直到指向缓冲区的尾部。在这个过程中,指针可能指向,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)子状态比较简单,这里不做进一步分析了,留给读者做练习吧。

阅读(1821) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~