用C编写游戏：解析S表达式

在过去的几周里，我一直在努力想办法存储我的游戏配置。一开始，我开始使用XML，这很好，因为我可以流式传输文件，而不是将整个文件加载到内存中，但我不喜欢XML，因为我宁愿尽可能独立于库，理想情况下，我的SDL是我唯一需要担心的跨平台依赖项。

因此，在一段时间内，我将游戏配置转换为如下所示的纯文本格式。这种格式实际上没有特定的结构，我基本上模仿了XML名称空间的思想，所以我仍然可以将其作为流读取，而不必担心类似命名属性之间的冲突。

SP：Sprite sp：X 32 sp：Y 104 AN：动画AN：Texture"；sets/idle.bmp"；AN：Frame-Length 2 AN：Frame-Width 24 AN：Frame-Height 24 AN：Frame-span 5 AN：Loop 0。

不过，它感觉有点欠缺，在过去的几个月里，我真的喜欢上了Common Lisp。最后，我真的希望看到我的数据结构更像这样。

(：Sprite((：Sprite：X 32：Y 104：Animations((：Animation：Texture"；Assets/idle.bmp"；：Frame-Length 2：Frame-Width 24：Frame-Height 24：Frame-span 5：Loop 0)。

所以我想我应该拓展一下思路，构建一个s表达式解析器。以下是我如何解决该解决方案的说明。

我承认我基本上是一个自学成才的程序员，没有正规的计算机科学背景。因此，当数据结构和算法对我试图解决的特定问题有用时，我倾向于学习它们。

这就是说，我对s表达式是如何构造的理解使我实现了链表。下面是基本结构。

枚举SNodeType{list，string，Symbol}struct SNode{struct SNode*Next；enum SNodeType type；Union{struct SNode*list；char*value；}}。

在我的程序中，解析后的s表达式是由SNode组成的链表。SNode结构是一个带标签的联合，它要么包含一个值(开始的字符串或符号)，要么包含另一个SNode列表。这种结构形成了一个可遍历的内存中树。

因此，为了实际解析出表达式，我决定使用fscanf，因为它允许基本的模式匹配。

Struct SNode*parse(file*fp){struct SNode*ail，*head=null；char c；while((c=fgetc(Fp))！=EOF){struct SNode*node=null；if(c=='；)'；){//在表达式分隔符的末尾停止递归；}Else if(c=='；('；){//在表达式开头开始递归node=calloc(1，sizeof(Struct SNode))；node->；type=list；node->；list=parse(Fp)；}Else if(！Isspace(C)){ungetc(c，fp)；char buffer[512]；if(c='；"；'；){//如果(fscanf(fp，"；\"；%511[^\"；]\"；"；，buffer)){node=calloc(strlen(Buffer)+1，sizeof(Struct SNode))，则读取以双引号结尾的字符串。Type=string；strcpy(node->；value，buffer)；}}Else{//如果(fscanf(fp，"；%511[^()\t\r\n\v\f]"；，buffer)){node=calloc(strlen(Buffer)+1，sizeof(Struct SNode))；node->；type=Symbol；strcpy(node-&。}//追加节点if(node！=null){if(head==null){//Initialize the Head Head=Tail=Node；}Else{//将节点追加到Tail=Tail->；Next=Node；}//返回列表头部返回Head；}。

这很有效。不过，我后来确实注意到，解析器的这个迭代不能正确读取空字符串。我还想介绍浮点型和整型数据类型，因为这些数据类型目前只是标记为符号。

接下来，我创建了两个函数来确定字符串是浮点型还是整型。

Int IS_FLOAT(char*str){char*ptr=null；strtod(str，&；ptr)；return！*ptr；}int is_INTEGER(char*str){char*ptr=null；strtol(str，&；ptr，10)；return！*ptr；}。

然后，我更新了解析函数，在回退到符号之前尝试确定类型。

//如果(fscanf(fp，"；%511[^()\t\r\n\v\f]"；，buffer)){node=calloc(strlen(Buffer)+1，sizeof(Struct SNode))；strcpy(node->value，buffer)；if(is_INTEGER(node->value)){node-&>；type=INTEGER)，则读取以空格或圆括号结尾的符号(fscanf(fp，"；%511[^()\t\r\n\v\f]"；)){node=calloc(strlen(Buffer)+1，sizeof(Struct SNode))；值){node->；type=Float；}否则{node->；type=Symbol；}}。

此后，解析器能够成功地标记数字类型。值本身仍然存储为字符串，不过我认为游戏应该负责处理该转换。

尽管我从来没想过我的游戏会从s表达式中读入一个空字符串，我也不希望这成为解析器的一个限制。解决这个问题意味着我将不得不放弃fscanf。使用fscanf读取字符串的限制是其格式模式要求引号之间至少有一个字符。在空字符串的情况下，引号之间没有任何东西可供它捕获，因此它会错误地解析表达式的其余部分。

我最后提出的解决方案稍微长了一点，但它的性能可能比fscanf更好。

}ELSE IF(c=='；"；'；){int length=0；char buffer[512]；//在((c=fgetc(Fp))！='；"；'；&；&；length<；511){Buffer[Length]=c；Length++；}Buffer[Length]='；\0'；；Node=calloc(1，sizeof(Struct SNode))；node->；type=string；node->；value=calloc(length+1，sizeof(Char))；strcpy(node->；value，buffer)；}。

为了与这种解析方法保持一致，我还更新了解析数字和符号的逻辑。我在执行此操作时发现的一个关键问题是，我必须记住将终止符放回原处，否则解析器不会关闭当前列表，后续的符号也会出现在错误的列表中。

}Else if(！Isspace(C)){int length=1；char buffer[512]={c}；//当(！Is_Terminator(c=fgetc(Fp))&；&；length<；511){Buffer[Length]=c；Length++；}Buffer[Length]='；\0'；；//将终止符放回ungetc(c，fp)；node=calloc(1，sizeof(Struct SNode))；node->；value=calloc(length+1，sizeof(Char))；IF(IS_INTEGER(NODE->VALUE)){NODE-&>；type=INTEGER；}ELSE IF(IS_FLOAT(NODE-&>VALUE)){NODE-&>；TYPE=FLOAT；}ELSE{NODE-&>；TYPE=符号；}}。

进行了这些更改后，解析函数现在以其当前形式相当健壮。

//递归解析来自文件流struct结构SNode*parse_sexpr_file(file*fp)的s表达式{//使用链表，节点被附加到列表尾部，直到我们//到达列表终止符，在该位置返回列表头部。Struct SNode*ail，*head=null；int c；While((c=fgetc(Fp))！=EOF){struct SNode*node=null；if(c=='；)'；){//终止列表递归中断；}Else if(c=='；('；){//开始列表递归节点=calloc(1，sizeof(Struct SNode))；node->；type。List=parse_sexpr_file(Fp)；}Else if(c=='；"；'；){int length=0；char buffer[buffer_size]；//读取到字符串终止符While((c=fgetc(Fp))！='；"；&；&；length<；buffer_size-1){buffer[length]=c；length++；}buffer[Length]='；\0'；；node=calloc(1，sizeof(Struct SNode))；node->；type=string；node->；value=calloc(length+1，sizeof(Char))；strcpy(node-&>；value，buffer)；}如果(！Isspace(C)){int length=1；char buffer[buffer_size]={c}；//当(！Is_Terminator(c=fgetc(Fp))&；&；length<；buffer_size-1){Buffer[Length]=c；Length++；}Buffer[Length]='；\0'；；//将终止符放回ungetc(c，fp)；node=calloc(1，sizeof(Struct SNode))；node->；value=calloc(length+1，sizeof(char。值，缓冲区)；IF(IS_INTEGER(NODE->VALUE)){NODE-&>；TYPE=INTEGER；}ELSE IF(IS_FLOAT(NODE-&>VALUE)){NODE-&>；TYPE=FLOAT；}ELSE{NODE-&>；TYPE=SYMBOL；}}IF(NODE！=NULL){IF(HEAD==NULL){//初始化列表Head=Tail=node；}ELSE{//将节点追加到列表Tail=Tail->；Next=Node；}返回Head；}。

我需要做的最后一件事是编写一个递归函数来释放由SNode树动态分配的内存。看起来是这样的。

//递归释放节点分配的内存void snode_free(struct SNode*node){struct SNode*tmp；While(node！=null){tmp=node；if(node->；type==list){snode_free(node->；list)；}false{//释放当前值free(node->；value)；node-&>；value=null；}node=node-&>；next；//释放当前节点。TMP=空；}}。

最后，我对解析器的结果真的很满意，我将解决方案反汇编到如果需要的话，我可以很容易地用其他语言实现它的级别(或者我只是觉得无聊)。如果您想使用或派生解析器，请查看我的c-sexpr-parser存储库。