loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

#

游戏资源包简单设计

     摘要: 一般的资源包文件格式基本上是由包文件头和包内容组成。文件头描述资源包内打包的文件
信息,例如文件名、在资源包里的偏移、大小、压缩加密相关信息等;包内容则是实际文件
打包在一起后的内容,可能直接是未打包前文件连续存放在一起的内容,也可能是相同类型
文件除掉文件头的内容(例如某个资源包里打包的全部是相同格式的图片文件,那么这些图
片文件被打包后包内只需要保存一个图片文件头,包内容全部是直接的图片数据)。   阅读全文

posted @ 2010-06-19 14:59 Kevin Lynx 阅读(4663) | 评论 (5)编辑 收藏

基于栈的虚拟机的实现

上次的编译原理练习中,生成的目标代码是别人写的一个基于寄存器的简单虚拟机。这

回这个简单的基于栈的虚拟机,纯碎是为了弥补上回的练习不足。

基于寄存器(register based)的虚拟机和基于栈(stack based)的虚拟机主要的不同在于

对指令运算的中间值的保存方式。这些中间值包括各种运算的结果值,传给各个指令的参

数等等。前者一般会设置几个寄存器,如累加寄存器;后者则没有寄存器,只有一个用来

保存这些值的栈。例如,这里我实现的SM(stack based machine)中的ADD指令:

ADD:从栈中依次弹出两个数a和b,然后将b+a压栈(b是左操作数)。基于这样一个方

式,SM中大部分指令都不需要操作数,其操作数都直接从栈顶取。因为这个虚拟机仅仅是

用于上回设计的简单语言的运行,即没有函数、只有数字类型、有if和while。在这回练习中

我甚至把逻辑运算符给阉割了,只保留了大于小于之类的关系运算符。以下是该语言计算阶

乘的例子:

read x;
if( x > 0 )
{
fac = 1;
while( x > 0 )
{
  fac = fac * x;
  x = x - 1;
}
write fac;
}
else
{
write 0;
}

基本上同《编译原理与实践》里的例子一样,这样省得我去琢磨语言文法。

不过,SM中还是有一个寄存器,即指令指针寄存器(pc),永远指向将要执行的指令。在实现中,

所有指令都被保存一个数组里,所以pc就是一个指向数组索引的整数值。

SM中有一个简单的内存,只用于保存程序中的全局变量(只有全局变量)。同样,这个虚拟的

内存也被简单地用一个数组来实现,所以,指令中的所有地址,都是数组索引值。

SM的代码文件直接就是指令序列的二进制表示。在这个二进制文件中,内容依次为:操作码(1

字节),操作数(4字节,如果有的话),操作码,操作数,。。。SM读取这样的文件,将这些

指令放进指令数组,然后逐条解释执行,直到遇到空指令。

代码中的test是上面简单提到的编程语言的编译程序,该程序将源代码编译为SM可执行的二进制

文件(sm后缀)。为了方便调试,SM本身可以根据命令行参数输出二进制文件对应的反汇编代码,

这可以方便我调试编译程序的代码生成是否正常工作。同时,当初为了测试SM的正确性,还写了

个简单的汇编程序(sasm),可以把SM的汇编代码转换为二进制文件。

这回我特地在文法中间插入action丢给yacc处理,在赋值语句中一切正常。但是在if中yacc依然

提示警告,看起来应该跟if中的悬挂else二义性有关系。不过通过添加空的文法符号,居然解决了。

不清楚为什么上回死活有问题,诡异了。

 

下载SM

posted @ 2010-04-15 19:56 Kevin Lynx 阅读(7606) | 评论 (0)编辑 收藏

[总结]中间/目标代码生成

语法制导翻译、中间代码生成、目标代码生成在很多时候并不存在严格的划分。对于目标
代码是某个简单的虚拟机代码而言,中间代码完全可以就是目标代码。中间代码生成中结
合了语法制导翻译,讲述了大部分常规的编程语言结构是怎样被翻译成一种接近目标代码
的形式(所谓的中间代码形式)。本身,汇编代码就是对应于机器码的一种字符表示形式,
而中间代码的大部分表示形式--三地址码,也是一种接近汇编代码的形式。

简单来说,词法分析阶段将字符整理为单词;语法分析则将这些代码整理为一种层次结构
(识别了程序代码要表达的意思);那么,在接下来的阶段里,则是将这些层次结构翻译
为线性结构。也就是类似于汇编代码这种格式。这种格式容易被机器识别:机器只需要顺
序地一条一条地取指令并执行之即可。这种简单直接性也使得要实现类似的虚拟机变得容
易。

翻译过程并不需要先生成语法树,在语法分析阶段的语法识别过程中,即可以对应地翻译。
因为无论是自顶向下还是自底向上的语法分析,都可以先去识别叶子节点。在自顶向下中,
可以使用语法树(并不真实存在)的后续遍历,使得叶子节点先于父节点翻译;而在自底
向上的分析中,因为其本身就是先识别叶子节点(所谓的规约),所以可以更自然地翻译。

因为我也是想实践下这些东西,所以还是使用lex/yacc来进行练习,省得自己去写词法和
语法分析。不过在使用yacc的过程中,经常会出现一些shift/reduce conflicts的警告/错
误,解决这些问题也费了不少时间。不过,也可能是我对LALR细节不熟悉,加之于文法本
身写的有问题,才弄得如此折腾。现在我觉得上下文无关文法在整个编译原理理论中非常
重要。一个好的文法可以准确无误地描述一种编程语言的语法,还可以指导编译器的开发。
当然,大部分常规的语言都可以找到现成的文法。

例子程序构造了一个简单的翻译程序,支持简单的算术表达式、整数变量、if、while、以
及仅用于if和while的逻辑表达式。为了省力,虚拟机用的是《编译原理与实践》中现成的。
目标代码也就直接是该虚拟机对应的代码。该虚拟机主要有5个寄存器:指令指针寄存器、
2个累加寄存器、全局变量基址寄存器、临时变量基址寄存器。这里的临时变量不同于编
程语言说的临时变量,它是表达式计算的临时值,例如a+b+c,a+b的结果值就可以被实现
为存储到一个临时值中。

对于算术表达式,其实翻译起来很简单。主要是if/while和逻辑表达式的翻译。逻辑表达
式的翻译例子中我甚至没有处理短路代码:a && func(1)中如果已经计算出a为false了,
就没必要计算func(1)了。这可能是受限于yacc,暂不深究。对于if和while,则主要涉及
到所谓的“回填”技术。

回填主要是应对向前跳转这种问题。例如在if的代码生成中,需要测试if的逻辑表达式的
真假,如果为假,则需要跳转到then-part之后。这里的then-part也就是if为真时要执行
的代码序列。而这个跳转指令具体要跳到哪里,则需要在生成完then-part之后才能确定。
回填的解决方法,就是预留下这个跳转指令的位置,等到then-part生成完了,得到了具
体的跳转位置,再回去填写那个跳转指令。

在这个问题上,yacc也让我折腾了一番。在if文法中:

selection_statement
: IF '(' logical_or_expr ')' {
  // 本来想在这里预留这个跳转指令的位置
} statement %prec IFX {
   }

结果,yacc又给我conflicts和never reduced之类的警告,并且最终生成的代码也不正常
(果然是无法忽略的警告)。看起来,yacc似乎不支持在文法内部添加action。通过一个
空文法符号效果一样。对于这个问题,我甚至莫名其妙地在某个晚上的梦里当面问了yacc
的作者。他肯定地告诉我:支持,当然支持(中文)。今天仔细地在yacc文档里找了下,
还真支持。而且对于空符号的使用,似乎也有些规则:$Sign: {action }。

后来解决这个问题的方法,算是我取巧了:
selection_statement
: IF '(' logical_or_expr IfBracket statement %prec IFX { ....}
IfBracket
: ')' {
     // 邪恶地利用了这个括号
   }
另外,因为需要支持嵌套的if/while,还专门使用了一个栈,用于保存这些需要回填的预留地址。

 

下载例子

posted @ 2010-04-09 20:22 Kevin Lynx 阅读(8020) | 评论 (2)编辑 收藏

[总结]语法制导翻译/语义分析

语义分析理论中并没有语法和词法分析阶段中那么多算法。如同整个编译原理里大部分理论
一样,其都是为实践编码提供理论支持,从而可以让实现简单机械地进行---语法制导翻译
也正是出于这个目的:通过建立理论,使得从语法树翻译到中间代码(或者虚拟机代码)更
为简单。

个人理解,语法制导翻译就是在文法中加上属性和各种动作,这些动作基本也就是这里的“
翻译”;而语义分析,则是在整个过程所要进行的一些上下文相关的分析动作(如类型检查
)。

罗列一些概念:

- 属性:就是语法树各个节点上所需要的“值”,例如对于算术表达式a=b+c,在其语法树
中,每一个节点都会有一个数字属性。属性明显不止包含数字/值这些东西,某个节点包含
哪些具体属性完全取决于编译器实现的需要。对于表达式a=b如果需要检查a和b的类型是否
可以赋值(如在c语言中,struct XXX b就无法传给int a),就需要在其节点中附加类型属
性。---这里举的例子也正是一种语义分析行为。

- 综合属性:某个节点的属性依赖于其子节点的属性,这种属性计算起来很简单,尤其在递
归下降分析程序中。

- 继承属性:某个节点的属性依赖于其父节点或者其兄弟节点。这个属性计算起来要稍微麻
烦一些,需要一种属性传递机制。在上一篇LL分析法的练习程序中,就使用了一个“值栈”
来传递属性。

- 依赖图:上面提到属性之间的依赖,在一棵语法中,通过箭头描绘出这种依赖关系就得到
依赖图,说白了就是拿来方便看的,无视。

- 语法制导定义(SDD):学编译原理最烦的就是这些定义,一句话里总觉得有若干未知概
念,尤其在翻译比较烂的时候。我觉得这个SDD就是在文法中穿插了若干属性和翻译动作的
表示。

- S属性的SDD:如果一个SDD的每一个属性都是综合属性,那它就是S属性的。

- L属性的SDD:无视了,就是夹杂着综合属性和继承属性的SDD,不过继承属性有诸多条件
限制,大致上就是其某个属性的依赖关系仅限于其左兄弟或者父节点。

其实这一切都并非它看上去的那么繁杂。在有了语法分析的基础上,因为马上涉及到翻译为
中间代码(甚至会直接翻译为虚拟机代码),在这个阶段直接把代码中会做的事情书写到文
法里,就得到了SDD。按照这个SDD,就可以较为机械地对应写出代码。另一方面,在实际中
为了处理不同的翻译问题,如类型检查、各种控制语句的翻译,直接参考相关的资料,看看
别人怎么处理的就行了。

练习程序是一个简单地处理c语言定义变量、定义struct类型的代码。因为c语言里的变量会
附带类型属性,用于类型检查之类的问题,所以程序中保存这些变量的符号表自然也要保存
其类型。定义新的struct类型我这里直接建立了一个类型表,用于存储所有的类型:基本类
型和程序员自定义类型。

练习程序直接使用了lex和yacc来生成词法和语法分析模块,通过直接在文法文件里(*.y)的
文法中穿插各种动作来完成具体的处理逻辑。本来我最开始是想个类型检查程序的,起码可
以检查一般的类型不匹配错误/警告,不过后来仅仅做了变量/类型定义,就发现有一定代码
量了,索性就懒得做下去了。

下载例子

posted @ 2010-03-28 20:19 Kevin Lynx 阅读(10140) | 评论 (3)编辑 收藏

[总结]LL(1)分析法及其实现

LL(1)分析法和递归下降分析法同属于自顶向下分析法。相对于递归下降而言,LL通过显示
地维护一个栈来进行语法分析,递归下降则是利用了函数调用栈。

LL分析法主要由分析栈、分析表和一个驱动算法组成。其实LL的分析算法还是很容易懂的,
主要就是一个匹配替换的过程。而要构造这里的分析表,则还涉及计算first集和follow集
的算法。

1

个人觉得龙书在解释这些算法和概念时都非常清楚细致,虽然也有人说它很晦涩。

first集和follow集的计算,抛开书上给的严密算法,用人的思维去理解(对于compiler
compiler则需要用程序去构造这些集合,这是让计算机去理解),其实很简单:

1、对于某个非终结符A的first集(first(A)),简单地说就是由A推导得到的串的首符号的
集合:A->aB,那么这里的a就属于first(A),很形象。
2、follow(A),则是紧随A的终结符号集合,例如B->Aa,这里的a就属于follow(A),也很形
象。

当然,因为文法符号中有epsilon,所以在计算上面两个集合时则会涉及到一种传递性。例
如,A->Bc, B->epsilon,B可以推导出epsilon,也就是基本等同于没有,那么first(A)中
就会包含c符号。

在了解了first集和follow集的计算方法后,则可以通过另一些规则构造出LL需要的分析表。

编译原理里总有很多很多的理论和算法。但正是这些理论和算法,使得编译器的实现变得简
单,代码易维护。

在某个特定的编程语言中,因为其文法一定,所以对于其LL(1)实现中的分析表就是确定的
。我们也不需要在程序里动态构造first和follow集合。

那么,要实现一个LL(1)分析法,大致步骤就集中于:设计文法->建立该文法的分析表->编
码。

LL分析法是不能处理左递归文法的,例如:expr->expr + term,因为左递归文法会让对应
的分析表里某一项存在多个候选式。这里,又会涉及到消除左递归的方法。这个方法也很简
单,只需要把文法推导式代入如下的公式即可:

A -> AB | C 等价于:A -> CX, X -> BX | epsilon

最后一个问题是,如何在LL分析过程中建立抽象语法树呢?虽然这里的LL分析法可以检查文
法对应的语言是否合法有效,但是似乎还不能做任何有意义的事情。这个问题归结于语法制
导翻译,一般在编译原理教程中语法分析后的章节里。

LL分析法最大的悲剧在于将一棵在人看来清晰直白的语法树分割了。在递归下降分析法中,
一个树节点所需要的属性(例如算术运算符所需要的操作数)可以直接由其子节点得到。但
是,在为了消除左递归而改变了的文法式子中,一个节点所需要的属性可能跑到其兄弟节点
或者父节点中去了。貌似这里可以参考“继承属性”概念。

不过,综合而言,我们有很多业余的手段来处理这种问题,例如建立属性堆栈。具体来说,
例如对于例子代码中计算算术表达式,就可以把表达式中的数放到一个栈里。

例子中,通过在文法表达式中插入动作符号来标识一个操作。例如对于文法:
expr2->addop term expr2,则可以改为:expr2->addop term # expr2。当发现分析栈的栈
顶元素是'#'时,则在属性堆栈里取出操作数做计算。例子中还将操作符压入了堆栈。

下载例子,例子代码最好对照arith_expr.txt中写的文法和分析表来看。

PS,最近在云风博客中看到他给的一句评论,我觉得很有道理,并且延伸开来可以说明我们
周围的很多现象:

”很多东西,意识不到问题比找不到解决方法要严重很多。比如one-pass 这个,觉得实现
麻烦不去实现,和觉得实现没有意义不去实现就是不同的。“

对于以下现象,这句话都可以指明问题:
1、认为造轮子没有意义,从不考虑自己是否能造出;
2、常告诉别人某个技术复杂晦涩不利于团队使用,却并不懂这个技术;
3、笼统来说,【觉得】太多东西没有意义,虽然并不真正懂这个东西。

posted @ 2010-03-15 21:33 Kevin Lynx 阅读(9433) | 评论 (2)编辑 收藏

修改tolua++代码支持插入预编译头文件

tolua++自动生成绑定代码时,不支持插入预编译头文件。虽然可以插入直接的C++代码例如
,如$#include xxxx,但插入位置并没有位于文件头。对于使用预编译头的大型工程而言,
尤其是某个绑定代码依赖了工程里其他很多东西,更万恶的是预编译头文件里居然包含很多
自己写的代码时,支持插入预编译头文件这个功能很重要。

说白了,也就是要让tolua++在生成的代码文件开头插入#include "stdafx.h"。

修改代码其实很简单。tolua++分析pkg文件及生成代码文件其实都是通过lua代码完成的。
在src/bin/lua目录下,或者在源代码里toluabind.c里(把对应的lua代码直接以ASCII码值
复制了过来)即为这些代码。

首先修改package.lua里的classPackage::preamble函数,可以看出该函数会生成一些代码
文件头,模仿着即可写下如下代码:

if flags['I'] then
   output( '#include "..flags['I'] )
end

从上下文代码可以看出flags是个全局变量,保存了命令行参数。

然后修改tolua.c代码文件,让其往lua环境里传入命令行参数:

case 'I':setfield(L,t,"I",argv[++i];break;

本来,这样修改后基本就可以让tolua++支持通过命令行指定是否插入预编译头:
tolua++ -o test.cpp -H test.h -I stdafx.h test.pkg

不过事情并非很顺利,通过开启TOLUA_SCRIPT_RUN宏来让tolua++通过src/bin/lua下的lua
代码来完成功能,结果后来发现basic.lua似乎有问题。无奈之下,只好用winhex之类的工
具把修改过的package.lua转换为unsigned char B[]置于toluabind.c里,即可正常处理。

posted @ 2010-02-28 20:58 Kevin Lynx 阅读(4848) | 评论 (0)编辑 收藏

简要实现正则表达式匹配字符串

之所以说是“简要实现”一方面是因为算法不算高深,算法的实现也不精致,甚至连我对其的理解也不够本质。

我只不过不想在工作若干年后还是一个只会打字的程序员。学点什么东西,真正精通点什么东西才对得起喜欢

技术的自己。

 

附件中的代码粗略实现了《编译原理》龙书中的几个算法。包括解析正则表达式,建立NFA,然后用NFA去匹

配目标字符串;或者从NFA建立DFA,然后匹配。解析正则表达式我用了比较繁琐的方法,有词法和语法分析

过程。词法分析阶段将字符和一些操作符整理出来,语法分析阶段在建立语法树的过程中对应地建立NFA。

当然,因为语法树在这里并没有用处,所以并没有真正地建立。

 

从正则表达式到NFA比较简单,很多编译原理书里都提到过,如:s|t表达式对应于下面的NFA:

1

代码中用如下的结构描述状态和状态机中的转换:

#define E_TOK (0)

/* transition */
struct tran
{
    char c;
    struct state *dest;
    struct tran *next;
};

struct state
{
    /* a list of transitions */
    struct tran *trans;
    /* inc when be linked */
    int ref;
};

即,每一个状态都有一个转换列表,每个转换都有一个目标状态(即该转换指向的状态)以及转换字符。

貌似通过以上方法建立出来的状态机每个状态最多只会有2个转换?

 

建立好NFA后,由NFA匹配目标字符串使用了一种构造子集法(《编译原理》3.7.2节):

2

这个算法里针对NFA的几个操作,如e-closure、move等在由NFA转换DFA时也被用到,因此代码里单独

做了封装(state_oper.c)。这个算法本质上貌似就是一次步进(step)多个状态。

 

至于由NFA转DFA,则是相对简单的子集构造法:

3

在我以前编译原理课考试的前一天晚上(你懂的)我就对这些算法颇为疑惑。在以后看各种编译

原理教材时,我始终不懂NFA是怎么转到DFA的。就算懂了操作步骤(我大学同学曾告诉我这些步骤,虽然

不知道为什么要那样做),一段时间后依然搞忘。很喜欢《编译原理》龙书里对这个算法最本质的说明:

 

4

 

源代码我是用GCC手工编译的,连makefile也没有。三个test_XXX.c文件分别测试几个模块。test_match.c

基本依赖除掉test外所有c文件,全部链接在一块即可。当然,就经验而言我知道是没几个人会去折腾我的这些

代码的。这些在china的领导看来对工作有个鸟用的代码读起来我自己也觉得费力,何况,我还不伦不类地用了

不知道算哪个标准的c写了这些。

 

你不是真想下载。对于这种代码,有BUG是必然的,你也不用在此文若干个月后问我多少行是什么意思,因为

那个时候我也忘了:D。

posted @ 2010-02-20 14:53 Kevin Lynx 阅读(5799) | 评论 (4)编辑 收藏

静态库中全局变量的初始化问题

 

在我自己写的一个工厂类实现中,每个产品会注册创建接口到这个工厂类。工厂类使用这些
注册进来的创建接口来完成产品的创建。其结构大致如下:

product *factory::create( long product_type )
{
    creator c = m_creators[product_type];
    return c();
}

factory::instance().register( PRODUCT_A_TYPE, productA::create );
...
factory::instance().create( PRODUCT_A_TYPE );

这个很普通的工厂实现中,需要写上很多注册代码。每次添加新的产品种类时,也需要修改
这些的注册代码。而恰好,这些注册代码可能会被放在一个统一的地方。为了消除这个地方
,我使用了偶然间看到的<Modern C++ design>里的做法:

const bool _local = factory::instance().register( PRODUCT_A_TYPE,...

也就是说,通过对全局常量_local的自动初始化,来自动完成对该产品的注册。

结果,因为这些代码全部被放置于一个静态库。最终的代码文件结构大致为:

lib
    - product_a.cpp : 定义了全局常量_local
    - product_a.h
    - factory.cpp
    - factory.h
exe
    - main.cpp

现在看起来世界很美,因为factory甚至不知道世界上还有个跟上层逻辑相关的product_a。
这种模块耦合几乎为0的结构让我窃喜。

悲剧的事情首先发生于,开VC调试器,发现打在product_a.cpp里的断点失效。就是那个总
是提示说没有为该文件加载调试符号。开始还不在意,以为又是代码和调试符号文件不匹配
的原因,折腾了好久,不得其果。

后来分析了下,发现这个调试提示,就像我开着调试器打开了一个非本工程的代码文件,而
断点就打在这个文件里一样。也就是说,VC把我product_a.cpp当成不是这个工程里的代码
文件。

按照这个思路写些实验代码,最终发现问题所在:VC链接器根本没链接进product_a.cpp里
的代码。表现出来的情况就是,该编译单元里的全局常量(全局变量一样)根本没有得到初
始化,因为我跟到factory::register并没有被调用到。为什么VC不链接这个编译单元对应
的目标文件?或者说,为什么VC不初始化这个全局常量?

原因就在于,product_a.cpp太独立了。一个在整个编译链接阶段都无法确定该文件是否被
使用的文件,VC就直接不链接了。相反,当在factory.cpp里写下类似代码:

void test()
{
    product_a obj;
}

虽然说test函数不会被调用,一切情况也变得正常了。好了,不扯了,给最后我的结论:

1、如果静态库中某个编译单元在编译阶段被确认为它并没有被外部使用,那么当这个静态
库被链接进可执行文件时,链接器忽略掉该编译单元里的代码,那么,链接器自然也不会为
该编译单元里出现的全局变量常量生成初始化代码(关于这部分初始化代码可以阅读
<linker and loader>一书);
2、上面那条结论存在一种传染性,意思是,当可执行文件里的代码使用到静态库中文件A里
的代码,A里又有地方使用到B里的代码,那么B依然会被链接。这种依赖性,应该可以让编
译器在编译阶段就发现(显然,上面我举的例子里,factory只有在运行期间才会依赖到
product_a.cpp里的代码)

posted @ 2010-01-17 19:34 Kevin Lynx 阅读(15247) | 评论 (19)编辑 收藏

lua_yield为什么就必须在return表达式中被调用

 

很早前在折腾挂起LUA脚本支持时,接触到lua_yield这个函数。lua manual中给的解释是:

This function should only be called as the return expression of a C function。

而这个函数一般是在一个注册到LUA环境中的C函数里被调用。lua_CFunction要求的原型里
,函数的返回值必须返回要返回到LUA脚本中的值的个数。也就是说,在一个不需要挂起的
lua_CFunction实现里,也就是一个不需要return lua_yield(...的实现里,我应该return
一个返回值个数。

但是为什么调用lua_yield就必须放在return表达式里?当时很天真,没去深究,反正发现
不按照lua manual里说的做就是不行。而且关键是,lua manual就不告诉你为什么。

最近突然就想到这个问题,决定去搞清楚这个问题。侯捷说了,源码面前了无秘密。我甚至
在看代码之前,还琢磨着LUA是不是操作了堆栈(系统堆栈)之类的东西。结果随便跟了下
代码真的让我很汗颜。有时候人犯傻了真的是一个悲剧。诺简单的一个问题会被人搞得很神
秘:

解释执行调用一个注册进LUA的lua_CFunction是在ldo.c里的luaD_precall函数里,有如下
代码:

    n = (*curr_func(L)->c.f)(L);  /* do the actual call */
    lua_lock(L);
    if (n < 0)  /* yielding? */
      return PCRYIELD;
    else {
      luaD_poscall(L, L->top - n);
      return PCRC;
    }

多的我就不说了,别人注释写得很清楚了,注册进去的lua_CFunction如果返回值小于0,这
个函数就向上层返回PCRYIELD,从名字就可看出是告诉上层需要YIELD。再找到lua_yield函
数的实现,恰好该函数就返回-1。

要再往上层跟,会到lvm.c里luaV_execute函数,看起来应该就是虚拟机在解释执行指令:

      case OP_CALL: {
        int b = GETARG_B(i);
        int nresults = GETARG_C(i) - 1;
        if (b != 0) L->top = ra+b;  /* else previous instruction set top */
        L->savedpc = pc;
        switch (luaD_precall(L, ra, nresults)) {
          case PCRLUA: {
            nexeccalls++;
            goto reentry;  /* restart luaV_execute over new Lua function */
          }
          case PCRC: {
            /* it was a C function (`precall' called it); adjust results */
            if (nresults >= 0) L->top = L->ci->top;
            base = L->base;
            continue;

对于PCRYIELD返回值,直接忽略处理了。

posted @ 2010-01-17 19:32 Kevin Lynx 阅读(3798) | 评论 (0)编辑 收藏

低耦合模块间的通信组件:两个模板

用途

在一个UI与逻辑模块交互比较多的程序中,因为并不想让两个模块发生太大的耦合,基本目标是
可以完全不改代码地换一个UI。逻辑模块需要在产生一些事件后通知到UI模块,并且在这个通知
里携带足够多的信息(数据)给接收通知的模块,例如UI模块。逻辑模块还可能被放置于与UI模
块不同的线程里。

最初的结构

最开始我直接采用最简单的方法,逻辑模块保存一个UI模块传过来的listener。当有事件发生时,
就回调相应的接口将此通知传出去。大致结构如下:

 /// Logic
 class EventNotify
 
{
 
public:
  
virtual void OnEnterRgn( Player *player, long rgn_id );
 }
;

 
/// UI
 class EventNotifyImpl : public EventNotify
 
{
 }
;

 
/// Logic
 GetEventNotify()->OnEnterRgn( player, rgn_id );

 

但是,在代码越写越多之后,逻辑模块需要通知的事件越来越多之后,EventNotify这个类开始
膨胀:接口变多了、不同接口定义的参数看起来也越来越恶心了。

改进

于是我决定将各种事件通知统一化:

 

struct Event
{
 
long type; // 事件类型
  // 附属参数
}
;

 

这样,逻辑模块只需要创建事件结构,两个模块间的通信就只需要一个接口即可:

void OnNotify( const Event &event );

但是问题又来了,不同的事件类型携带的附属参数(数据)不一样。也许,可以使用一个序列化
的组件,将各种数据先序列化,然后在事件处理模块对应地取数据出来。这样做总感觉有点大动
干戈了。当然,也可以使用C语言里的不定参数去解决,如:

void OnNotify( long event_type, ... )

其实,我需要的就是一个可以表面上类型一样,但其内部保存的数据却多样的东西。这样一想,
模块就能让事情简单化:

 

template <typename P1, typename P2>
class Param
{
public:
 Param( P1 p1, P2 p2 ) : _p1( p1 ), _p2( p2 )
 
{
 }

 
 P1 _p1;
 P2 _p2;
}
;

template 
<typename P1, typename P2>
void OnNotify( long event_type, Param<P1, P2> param );

GetNotify()
->OnNotify( ET_ENTER_RGN, Param<Player*long>( player, rgn_id ) );
GetNotify()
->OnNotify( ET_MOVE, Param<longlong>( x, y ) );

 

在上面这个例子中,虽然通过Param的包装,逻辑模块可以在事件通知里放置任意类型的数据,但
毕竟只支持2个参数。实际上为了实现支持多个参数(起码得有15个),还是免不了自己实现多个
参数的Param。

幸亏我以前写过宏递归产生代码的东西,可以自动地生成这种情况下诸如Param1、Param2的代码。
如:

 

#define CREATE_PARAM( n ) \
 template 
<DEF_PARAM( n )> \
 
struct Param##n \
 
{ \
  DEF_PARAM_TYPE( n ); \
  Param##n( DEF_FUNC_PARAM( n ) ) \
  
{ \
   DEF_MEM_VAR_ASSIGN( n ); \
  }
 \
  DEF_VAR_DEF( n ); \
 }


 CREATE_PARAM( 
1 );
 CREATE_PARAM( 
2 );

 

即可生成Param1和Param2的版本。其实这样定义了Param1、Param2的东西之后,又使得OnNotify
的参数不是特定的了。虽然可以把Param也泛化,但是在逻辑层写过多的模板代码,总感觉不好。

于是又想到以前写的一个东西,可以把各种类型包装成一种类型---对于外界而言:any。any在
boost中有提到,我只是实现了个简单的版本。any的大致实现手法就是在内部通过多态机制将各
种类型在某种程度上隐藏,如:

 

        class base_type
        
{
        
public:
            
virtual ~base_type()
            
{
            }

            
virtual base_type *clone() const = 0;
        }
;
        
        template 
<typename _Tp>
        
class var_holder : public base_type
        
{
        
public:
            typedef _Tp type;
            typedef var_holder
<type> self;
        
public:
            var_holder( 
const type &t ) : _t( t )
            
{
            }


            base_type 
*clone() const
            
{
                
return new self( _t );
            }

        
public:
            type _t;
        }


这样,any类通过一个base_type类,利用C++多态机制即可将类型隐藏于var_holder里。那么,
最终的事件通知接口成为下面的样子:

void OnNotify( long type, any data );

OnNotify( ET_ENTER_RGN, any( create_param( player, rgn_id ) ) );其中,create_param
是一个辅助函数,用于创建各种Param对象。

事实上,实现各种ParamN版本,让其名字不一样其实有点不妥。还有一种方法可以让Param的名字
只有一个,那就是模板偏特化。例如:

 

template <typename _Tp>
struct Param;

template 
<>
struct Param<void()>;

template 
<typename P1>
struct Param<void(P1)>

template 
<typename P1, typename P2>
struct Param<void(P1,P2)>

 

这种方法主要是通过组合出一种函数类型,来实现偏特化。因为我觉得构造一个函数类型给主模版,
并不是一种合情理的事情。但是,即使使用偏特化来让Param名字看起来只有一个,但对于不同的
实例化版本,还是不同的类型,所以还是需要any来包装。

实际使用

实际使用起来让我觉得非常赏心悦目。上面做的这些事情,实际上是做了一个不同模块间零耦合
通信的通道(零耦合似乎有点过激)。现在逻辑模块通知UI模块,只需要定义新的事件类型,在
两边分别写通知和处理通知的代码即可。

PS:
针对一些评论,我再解释下。其实any只是用于包装Param列表而已,这里也可以用void*,再转成
Param*。在这里过多地关注是用any*还是用void*其实偏离了本文的重点。本文的重点其实是Param:

 

OnNotify( NT_ENTER_RGN, ang( create_param( player, rgn_id ) ) );

->
void OnNotify( long type, any data )
{
 Param2
<Player*long> ParamType;
 ParamType 
*= any_cast<ParamType>&data );
 Player 
*player = p->p1;
 
long rgn_id = p->p2;
}




下载相关代码

posted @ 2009-08-23 09:55 Kevin Lynx 阅读(6279) | 评论 (18)编辑 收藏

仅列出标题
共12页: First 3 4 5 6 7 8 9 10 11 Last