摘要: 无聊之际用C#写了一个弹性物体碰撞模拟玩玩。这个想法源自与前几天上机课有人想我在机房做一个透视投影的程序，于是就立刻写了个投影并弄了个线框球上去跳。结果我就想，如果物体有弹性会怎么样呢？回到宿舍就实践想法。
这个程序是2D的，用C#主要是因为GDI+写起来比较方便，至少比可怜的MFC好用，虽然C#的东西又慢又占用CPU使用率。我发誓.NET的Timer肯定不是用WM_TIMER消息搞的，空转占用CPU都那么高，而且用Sleep还降低不了。过高的CPU占用率持续过久会导致CPU温度升高……
程序现在还有点问题。譬如物理引擎经典问题：浮点误差和碰撞穿透。现在还没100%处理好，虽然绝大多数情况下是没什么事。第二个就是因为弹性超出了我的物理知识范围，所以碰撞的速度更高暂时乱写，等过几天有空解一个三元二次方程组之后再改改代码。
先放截图三张，等程序改好了之后再把代码弄出来。这个东西很好玩的，嘿嘿。考虑了重力哦。
阅读全文
posted @
2008-06-05 09:30 陈梓瀚(vczh) 阅读(5693) |
评论 (9) |
编辑 收藏
摘要: 依然是上一篇文章的程序，换了C#写。 在Vczh Free Script 2.0的接口里面，我力求让C++和.NET两种语言的接口都趋于一致。目前达到了这个目标，C#仅仅比C++多了两个辅助函数。插件那一部分是相当难写啊。Vczh Free Script 2.0的C++接口允许插件和脚本交替调用。脚本引擎是本地代码，做到跟C...
阅读全文
posted @
2008-05-29 19:57 陈梓瀚(vczh) 阅读(2222) |
评论 (5) |
编辑 收藏
今天做好了Vczh Free Script 2.0的一个新插件，这个插件可以直接插入class并接管成员调用、构造函数和析构函数等调用。
一、在C++中插入一个类VczhClass和函数write、writeln、read和collect：
1 class VczhClass : public FsClass
2 {
3 protected:
4 public:
5 VczhClass(FsPlugin* Plugin):FsClass(Plugin,L"interpreter_debug")
6 {
7 }
8
9 FsePluginInvoke CallConstructor(int ClassID , FsObject* Parameters , int ParamCount , FsObject& ErrorMessage , FsObject& Result)
10 {
11 GetConsole()->Write(L"VczhClass is creating.\r\n");
12 AddExternalMember(ClassID,L"MethodA",0);
13 AddExternalMember(ClassID,L"MethodB",1);
14 AddExternalMember(ClassID,L"MethodC",2);
15 return fsSuccess;
16 }
17
18 FsePluginInvoke CallMember(int ClassID , int ExternalMemberID , FsObject* Parameters , int ParamCount , FsObject& ErrorMessage , FsObject& Result)
19 {
20 switch(GetMemberID(ExternalMemberID))
21 {
22 case 0:
23 GetConsole()->Write(L"VczhClass::MethodA is invoking.\r\n");
24 break;
25 case 1:
26 GetConsole()->Write(L"VczhClass::MethodB is invoking.\r\n");
27 break;
28 case 2:
29 GetConsole()->Write(L"VczhClass::MethodC is invoking.\r\n");
30 break;
31 }
32 return fsSuccess;
33 }
34
35 void CallDestructor(int ClassID)
36 {
37 GetConsole()->Write(L"VczhClass is destroying.\r\n");
38 }
39 };
40
41 class VczhConsole : public FsPlugin
42 {
43 protected:
44 FsObject FWrite;
45 FsObject FWriteLine;
46 FsObject FRead;
47 FsObject FCollect;
48 VczhClass* FVczhClass;
49
50 VUnicodeString Transform(const FsObject& Value)
51 {
52 return Value.GetReadableString().w_str();
53 }
54 public:
55 VczhConsole(FsEngine* Engine , VUnicodeString CodePath):FsPlugin(Engine,L"interpreter")
56 {
57 FWrite =Engine->CreateExternalResource();
58 FWriteLine =Engine->CreateExternalResource();
59 FRead =Engine->CreateExternalResource();
60 FCollect =Engine->CreateExternalResource();
61
62 GetEnvironment().SetFixedVariable(L"write",FWrite);
63 GetEnvironment().SetFixedVariable(L"writeln",FWriteLine);
64 GetEnvironment().SetFixedVariable(L"read",FRead);
65 GetEnvironment().SetFixedVariable(L"collect",FCollect);
66 GetEnvironment().SetVariable(L"apppath",Engine->CreateString(CodePath.Buffer()));
67 GetEnvironment().SetFixedVariable(L"vmpath",Engine->CreateString(GetConsole()->GetAppPath().Buffer()));
68
69 #ifdef _DEBUG
70 FVczhClass=new VczhClass(this);
71 GetEnvironment().SetFixedVariable(L"VczhClass",FVczhClass->GetCtor());
72 #else
73 FVczhClass=0;
74 #endif
75 }
76
77 ~VczhConsole()
78 {
79 if(FVczhClass)
80 {
81 delete FVczhClass;
82 }
83 }
84
85 FsePluginInvoke Invoke(int ExternalID , FsObject* Parameters , int ParamCount , FsObject& ErrorMessage , FsObject& Result)
86 {
87 if(ExternalID==FWrite.GetExternalID())
88 {
89 for(VInt i=0;i<ParamCount;i++)
90 {
91 GetConsole()->Write(Transform(Parameters[i]));
92 }
93 return fsSuccess;
94 }
95 else if(ExternalID==FWriteLine.GetExternalID())
96 {
97 for(VInt i=0;i<ParamCount;i++)
98 {
99 GetConsole()->Write(Transform(Parameters[i]));
100 }
101 GetConsole()->Write(L"\r\n");
102 return fsSuccess;
103 }
104 else if(ExternalID==FRead.GetExternalID())
105 {
106 for(VInt i=0;i<ParamCount;i++)
107 {
108 GetConsole()->Write(Transform(Parameters[i]));
109 }
110 VUnicodeString Read;
111 GetConsole()->Read(Read);
112 Result=GetOwnedEngine()->CreateString(Read.Buffer());
113 return fsSuccess;
114 }
115 else if(ExternalID==FCollect.GetExternalID())
116 {
117 int* Buffer=0;
118 int Count=GetOwnedEngine()->CollectGarbage(Buffer);
119 FsReleaseBuffer(Buffer);
120 return fsSuccess;
121 }
122 else
123 {
124 return fsGiveUp;
125 }
126 }
127 };
二、书写测试用的脚本代码：
1 func()
2 {
3 a=VczhClass.new();
4 a.MethodA();
5 a.MethodB();
6 a.MethodC();
7 }();
8 collect();
这里构造了一个VczhClass并调用了三个成员函数。结束之后，这种写法保证a再也不可被访问到，于是调用collect进行垃圾收集（垃圾收集是自动的，但是要触发条件很难，所以给了个函数进行强制收集）的时候就可以把a手机掉。
三、运行结果：
1 VczhClass is creating.
2 VczhClass::MethodA is invoking.
3 VczhClass::MethodB is invoking.
4 VczhClass::MethodC is invoking.
5 VczhClass is destroying.
四、如果a的成员被保存起来了怎么办呢？
1 b=null;
2 func()
3 {
4 a=VczhClass.new();
5 a.MethodA();
6 a.MethodB();
7 a.MethodC();
8 b=a.constructor;
9 }();
10 collect();
五、结果是因为b还能继续使用，所以a就不会销毁（垃圾收集器解决了这个问题）：
1 VczhClass is creating.
2 VczhClass::MethodA is invoking.
3 VczhClass::MethodB is invoking.
4 VczhClass::MethodC is invoking.
到了这里，一个直接往脚本中插入类的演示就结束了。接下来就是对这个插件进行测试，并且在相应的.NET接口上添加这样的支持。
posted @
2008-05-28 22:50 陈梓瀚(vczh) 阅读(1602) |
评论 (0) |
编辑 收藏
各位读者们，《构造正则表达式引擎》新鲜出炉啦！
《构造正则表达式引擎》 这篇文章描述了纯匹配正则表达式和具有高级功能（正向预查，反向预查，匿名捕获，命名捕获，命名检查和贪婪循环等）的正则表达式各自用来匹配正则表达式的算法。
如果大家在书写好的正则表达式的时候出现了麻烦，或者在开发自己的正则表达式的时候遇到障碍，那不妨读一读这篇文章。不过对于没读过下面这篇文章的朋友，如果不是很熟悉编译原理关于DFA和NFA的知识，那么建议首先阅读下面这篇文章。
《构造可配置词法分析器》 这篇文章描述了如何从简单的正则表达式构造ε-NFA，并且一步一步转换到DFA的算法，而且还提出了一种可配置词法分析器的可能的实现方法。学习《编译原理》的朋友们，如果在状态机那里遇到什么问题的话，那么不妨读一读这篇文章。
上面这两篇文章是我在学习《编译原理》之后
开发正则表达式引擎的心得体会，在这里与大家分享，共同进步。
posted @
2008-05-21 23:06 陈梓瀚(vczh) 阅读(109497) |
评论 (36) |
编辑 收藏
摘要: 这篇短文的Idea来源于一篇论文。这篇论文的题目是Higier-Order Functions for Parsing，Graham Hutton写的。论文中使用了一种叫Miranda的函数式语言来讲述如何使用高阶函数开发语法分析器。
高阶函数很多语言都支持，譬如JavaScript啊，C#的lambda expression啊，或者是我自己做的语言Vczh Free Script 2.0。不过Miranda是惰性计算的语言，我们常用的语言都不具有惰性计算的特性。因此我阅读了这篇文章之后，自己用Vczh Free Script 2.0写了一个等价的小规模的语法分析器。结构跟论文中所提到的那个有所区别，不过相同的经验可以直接应用在JavaScript里面或其它语言（例如Python等）的lambda expression里。C#我不知道行不行，没去考证。
这里首先要解决一个问题，就是如何引用没被定义的名字的问题。譬如如下文法：
Term=
| "(" Exp ")"
Fa 阅读全文
posted @
2008-05-21 00:57 陈梓瀚(vczh) 阅读(8141) |
评论 (5) |
编辑 收藏
这个新的Syngram包含了三个工具，分别是正则表达式、词法分析器和语法分析器。
正则表达式分纯、安全和贪婪三种。纯正则表达式仅仅用于匹配，速度非常快（以前的测试表明一秒钟可以匹配44万次），但是没有预查和捕获等功能。安全和贪婪两种正则表达式则是通过不同的搜索方法来匹配字符串的内容，虽然慢了一点，不过有了预查和捕获等功能。之前的文章有提到过关于一个少回溯多捕获的测试用例下的速度。安全分析法回溯将会占用很多时间，而贪婪分析法则回溯基本是没什么消耗的。
词法分析器则可以输入不同的正则表达式，然后将字符串切割成匹配和不匹配的段落，并告诉你匹配的部分实际上是匹配了哪一条正则表达式。这个功能在分析很多字符串的时候都是相当好用的。
至于语法分析器，则是实现了一个上下文无关文法库。语法 阅读全文
posted @
2008-05-19 00:56 陈梓瀚(vczh) 阅读(1628) |
评论 (4) |
编辑 收藏posted @
2008-05-18 06:42 陈梓瀚(vczh) 阅读(1670) |
评论 (3) |
编辑 收藏 在撰写了《构造可配置词法分析器》之后，我陆续收到了不少读者的来信，不过大多数都是要求源代码的。这篇文章原先是发布在自己的百度空间的，不过现在那个地方已经不打算写技术相关的东西了。而且由于cppblog的一些用户也转载了那篇文章，因此不打算再在这里重复贴了。
由于大多数读者都向我发邮件要求源代码，因此我想到，上一篇文章虽然把所有的原理都说明白了，不过关于实现相关的数据结构的那些细节却都没说出来。对与那些真的想实现自己的正则表达式引擎的人来说，可能还不能从文章中得到所有问题的解决方法。不过鉴于本人一贯来不想把所有的细节问题都说得太过于繁琐（留点问题给读者想也是好的，不然文章就没起到带动学习的作用了），因此作出决定：接下来的几天如果有空的话还要撰写一篇新的文章。
新的文章将着眼于【如何实现正则表达式引擎】这个话题，续《构造可配置词法分析器》的内容继续讨论。在这篇文章之中，我打算把使用DFA构造的正则表达式引擎的实现方法稍微描述一下（因为实际上难度不大），然后再花比较大的篇幅来讲述实现正向预查、反向预查、匿名获取、命名获取和子表达式引用的方法。文章中还会描述这篇文章中所提及的优化正则表达式的方法（招太多口水了，看来不写也会有很多人不高兴的，这是文化问题）。
敬请等待。
posted @
2008-05-16 05:11 陈梓瀚(vczh) 阅读(1902) |
评论 (6) |
编辑 收藏
1：大家在学习数据结构的时候，实践的方法通过（多选）
A：做习题
B：学习STL和Boost等
C：尝试自己开发一套模板库
2：大家在学习编译原理的时候，实践的方法通过（多选）
A：做习题
B：学习flex、yacc/bison和ANTLR等
C：尝试自己开发过编译器（特别指字符串处理部分，指令部分不在本题目考虑范围内）
D：尝试自己开发与flex、yacc/bison或ANTLR等价的工具（不拘泥于形式）
3：如果上面的题目选择了C或者D，那么（单选，自己独立开发程序而不是在团队中开发时）
A：自己需要的时候使用自己的库
B：自己需要的时候使用别人的库
4：如果第一题选择了B，那么（单选，自己独立开发程序而不是在团队中开发时）
A：选择编译器或IDE推荐的库（MFC或其他，跟STL或Boost有交集的库）
B：选择STL、Boost等
注意：
本人不倾向于向别人建议上面的任何观点，仅作调查。
勿人身攻击，欢迎评论。
写出自己的答案的同时请写出自己开发的时候经常使用的操作系统和编译器等工具。
posted @
2008-05-14 19:14 陈梓瀚(vczh) 阅读(1746) |
评论 (10) |
编辑 收藏
第一道题，把字符串中相连的重复字符处理成一个。例如aaabbcddcc处理成abcdc。因为寒假的时候才往Vczh Free Script 2.0中添加了一个Mark-Compact Collector，因此算法也就模仿了一下Mark-Compact Collector，也就是把所有该删掉的字符换成'\0'，依次读取并跟右边最近的非'\0'字符置换一直到完。
第二道题，已知数列中有1、2、3三种数字，并且可以两两置换。求最小置换次数的方法让数列递增。
我用了这样的方法：
·找到并保存每一个位置中应该存放的数字，也就是一1、2、3的数目都跟数列相同的递增数列bi。
·遍历ai，找到ai≠bi的i并做如下处理：
·寻找aj使得j>i且bi＝aj且bi≠bj
·在这些j中寻找k使得bk＝ai
·如果k非空则让m∈k，否则让m∈j并让下一步的k的势最大
·置换ai和am
一个好像很和谐但是事实上不知道和谐不和谐的证明：
j>i且bi＝aj且bi≠bj这个条件是必定满足的。如果不满足，则很容易证明ai和bi中1、2、3的数目不完全相同。
k非空使得一次置换产生了两个正确的结果。
对于每一次置换，如果让m1∈j且{m1}∩k为空，m2∈k，则有
选择m1而不是m2有可能减少、保持或增大下一次置换中k的势；
选择m2则下一次置换中k的势不变。
这样的话，选择m1最好的结果就是让这次置换不影响全部的置换，最坏的结果是增加了置换的次数；
选择m2则不会影响全部的置换。
因此只需每一次都尽量选择m2中的值，对于k∩j为空的情况，则计算所有j得到的下一步的k的势dj，选择最大的j即可。
第三道题，华容道解谜器。只好弄了个宽度优先搜索。
以上纯属YY。
P.S.
·选择题里面有一道问ABCDEFGHIJ的全排列中满足A在B前面的数量有多少？答案：因为A和B是对称的，因此对于任意一个确定的A和B的位置的集合，A在B前的概率是0.5，因此答案为10!/2。
·同时拥有操作系统、开发工具、数据库引擎、办公软件、游戏平台等多项业务的某著名软件公司的招聘活动我也参加了一次，结果发现经营着世界最大的搜索业务的某公司和同时拥有操作系统、开发工具、数据库引擎、办公软件、游戏平台等多项业务的某著名软件公司【好像】有一个特点。经营着世界最大的搜索业务的某公司喜欢出最优解题目，同时拥有操作系统、开发工具、数据库引擎、办公软件、游戏平台等多项业务的某著名软件公司喜欢出最高速题目。而且经营着世界最大的搜索业务的某公司很喜欢去在位于广州市海珠区珠江河畔的某著名大学，而同时拥有操作系统、开发工具、数据库引擎、办公软件、游戏平台等多项业务的某著名软件公司则很喜欢去位于广州市五山的某著名理工大学。
posted @
2008-05-12 10:59 陈梓瀚(vczh)|
编辑 收藏