译者序
由于我最近有一个计划,就是写一个适应性很强的脚本语言,这个语言将主要用来处理剧情,希望能够用于绝大多数需要剧情的游戏.于是最近开始找一些关于script的东西来看看,当我在flipcode看到这篇的overview时,见它提到了unreal的脚本系统和字节码和虚拟机,就开始在没有完全读完的情况下翻译这一系列文章(共9篇).在翻译中加一些注释...希望不要误导您,还有为了丰富原文我也加入了几个自己的程序.因为这是我首次翻译这种系列文章,在脚本引擎方面也缺乏经验,所以难免会有一些不当之处,还请大家批评指正. 

目录
Part I: 概述 
Part II: 词法分析器 
Part III:语法分析器 
Part IV: 符号表 & 语法树 
Part V: 语义检查 & 中间代码生成 
Part VI: 优化 
Part VII:虚拟机(The Virtual Machine) 
Part VIII:可执行代码 
Part IX:高级主题 

版本列表
2000年2月至2000年3月 第一稿

声明
原文发布时间是1999年5月至8月,原文作者是Jan Niestadt 
如果有中文版权的话版权属译者(即燕良)所有 
如果您觉得有用当然可以转载,不过请保持文章的全部内容,如果您有什么修改意见请与译者联系 
暂时不可用作商业用途

Part I:概述
序言

OK,在你的引擎中你想有一个脚本语言.

首先,确定你需要那种脚本语言;Henry Robinson 已经写过了一个各种脚本语言区别的介绍(如果你还没读过就去读一下吧),在这个系列教程中我将讨论一个象虚幻脚本(Unreal script)那样的编译器/虚拟机系统.

下一步,你需要知道两件事:怎样实现那样一个脚本引擎,还有脚本引擎不仅仅是酷而且在实际中十分有用的一些理由.

这里是我想到的一些:

• 有用的新语言特性象状态,隐藏代码(latent code),等等.
• 一个沙盘环境(sandbox environment)不会导致游戏引擎的崩溃.
• 不需要游戏内部引擎的只是或者重新编译游戏引擎就可以编写游戏的内容.
• 完全的独立于平台的脚本代码

但是也有一些不利因素:

• 相对较慢--脚本的运行至少比可执行代码的执行慢15倍.
• 限制--脚本不能用来建立实际的视觉效果(部分原因是它速度的缺点).
• 编写游戏内容的人必须学习一种新的语言.

当然我们不会因为这些就停下来,我们已经准备好实现我们的想法了.现在,从哪里开始呢?


必须阅读的东西

在虚幻(Unreal)发布前很久我就开始了.我浏览他们的技术站点,并且发现了虚幻脚本参考文档(UnrealScript reference document).我当然听说过虚幻脚本,但是并不真正知道他是什么.我阅读了这些文档,觉得一个脚本语言的想法实在是很酷.我要自己写一个,然后连接到一个游戏引擎,以便我的游戏的整个世界都可以轻松的建立新的内容.

幸运的是我有一个学期的编译器构造课程(燕良注:我也刚学了一个学期的编译原理,还考了92分,嘻嘻,不过Julien当时竟然只用两个月就考了98分,佩服,佩服),并且作为一个实际的任务我曾经实现过一个非常非常简单的Pascal编译器.我开始并行工作,更好,编译器.我已经有一个接受C的子集的可工作的版本,但是我用了2周来编码,其内部结构相当的可怕,...我不得不完整的重新设计那东西.我相信你在某些地方有与我相似的经验...现在我依然在做这东西,并且学到了很多关于编译器的知识.

现在,接触一点有用的信息吧.

首先,我建议所有想要编写一个编译器的人弄一本龙之书.你们中的大多数(尤其是象我这样的计算机系学生)可能已经知道了这个(燕良注://shake).告诉那些不知道的人,我是在说Aho, Sethi 和 Ullman 所著的<<Compilers - Principles, Techniques and Tools >>(ISBN 0-201-10194-7). 因为他的封面有一条龙,所以得到了龙之书的名字.相信我,所有对编译器有所了解的人都读过这本书(燕良注:国内有卖吗?).

这本书从1986年就不曾修改过,这是因为从60年代编译器的设计基本技术就没有变过.当然,这本书不涉及面向机器的优化,但是有其他书.此外,我们想要编译出字节码(bytecode)而非机器码.

其次,如果你想要得到一个快速实现字节码脚本语言的预览GamaSutra的一篇文章.那是一个值得一读的关于实现Jedi骑士脚本语言的故事.那里的所有的东西我也将涉及,但是那仍然是值得一读的.


我们需要什么

一个编译器基本上包括一下这些组成部分:

• 一个符号表,其中存储所有的符号及其信息,例如类型,范围,等等.
• 一个词法分析器,他的功能是将字符流(例如源文件)转换为记号(例如关键词,操作符等等).
• 一个语法分析器(parser),他的功能是读取记号流,并建立语法树.
• 一个语义检查器,用来检查语法树的语义错误.
• 一个中间代码生成器,用来把语法树转换为中间代码
• 一个优化器,用来优化中间代码
• 一个代码生成器,用来从中间代码生成字节码.
• 最后但不是最少,字节码将要在其上执行的虚拟机

如果你编写完了所有这些组件,组合到一起,它们将成为一个完整的脚本语言系统.


这是全部吗?

受到了一点点打击吗?毕竟决定使用脚本不是那么酷,DLL真的是唯一的路吗?没关系,我将很快讨论每一组件的细节,它们的绝大多数并不是那么困难.建立一个完整的脚本引擎是一个巨大的工作,但是,本质上是构造你自己的代码.

在这个教程的剩余部分我们将开发一个简单的编译器/虚拟机系统.尽管他没有地方象是一个完整的脚本语言,但是他实现了上面提到的所有组件.我在回想一个操作字符串的简单语言.

现在检查上面的连接,了解他们.顺便提一下,感谢所有的评论.

Quote!
"But the plans were on display ..."
"On display? I eventually had to go down to the cellar to find them."
"That's the display department."
"With a torch."
"Ah, well the lights had probably gone."
"So had the stairs."
"But look, you found the notice didn't you?"
"Yes," said Arthur, "yes I did. It was on display in the bottom of a locked filing cabinet stuck in a disused lavatory with a sign on the door saying Beware of the Leopard."

HHG 1:1

Part II:词法分析器
序言

我总是说在学一个东西的时候例子总是不能足够简单.这就是为什么当我想要设计一个包含所有完整编译器应该有的特性的简单的编译器时感到很累.我拼凑了一个字符串处理语言,它使用象C那样的语法,有BASIC那样的功能.下面是用我们的语言的正确编写的一个程序.

就象你看到的,他没有构造象函数,类等等那样的功能,它甚至没有数值类型.这就是最终的东西,但是,他是很容易扩展的.

但是在接触那个之前我们还一很长的路要走--记得上次的组件列表吗?今天我们将实现第一个:词法分析器或称短语分析器.这是一个很好的热身,因为它不是编译器中真正难的部分.

OK,准备好了吗?


是什么,为什么和怎么作

首先我猜你想要知道词法分析器是什么和为什么我们要用它?词法分析器的任务是把源文件的字符流转换成记号流.本质上它查看连续的字符然后把它们识别为"单词".

我们当然可以写一个函数用来把源文件当前位置取得的字符串与我们的所有关键字比较,但是这将是不可忍受的慢.所以我们使用有限自动机来识别单词(燕良注:就是DFA了,设计过程是正则式==>NFA==>DFA==>最小化).如果你不知道它是什么,好吧,你不需要知道(燕良注:如果你想知道,请看本文最后的附注).

关于词法分析器的一个基本情况是我们不需要作实际的艰苦的工作,我们使用一个叫作"LEX"的程序生成词法分析器.这是一个标准的UNIX程序,他也有几个win 32的版本(燕良注:我有一个FLEX.exe).这里有完整的LEX手册的HTML版.

好的,现在你知道了词法分析器作什么和我们将如何制作它.现在你可以下载 *tut2.zip*并且看一眼那些代码.这部分的源程序是string.l(燕良注:LEX源程序)和main.cpp以及几个头文件.请注意ZIP文件中含有目录结构,flex.exe在主目录,这部分的代码在tut2\目录.


LEX规则

LEX需要一些简单的规则来生成我们的词法分析器.在介绍规则之前,先让我们看一下LEX源程序的分段.

<说明部分>包含一些正则式(regular expression )的宏(正则式在LEX手册中有解释,想彻底了解它请看这里).这些告诉LEX我们使用的LETTER,DIGIT, IDENT(标识符,通常定义为字母开头的字母数字串)和STR(字符串常量,通常定义为双引号括起来的一串字符)是什么意思.(燕良注:呵呵,多熟悉呀.)

这部分也可以包含一些初始化代码.例如用#include来使用标准的头文件和前向说明(forward references).这些代码应该再标记"%{"和"%}"之间,你马上将看到我include了一个lexsymb.h 文件.

<规则部分>可以包括任何你想用来分析的代码;我们这里包括了忽略所有注释中字符的功能,传送ID名称和字符串常量内容到主调函数和main函数的功能.

lexsymb.h 文件声明了词法分析器函数将要返回的记号的符号.它还声明了一个'yylval' 共用体(union),用来传送额外的信息(例如标识符的名字)到主调函数;这里我们使用这个特殊的共用体可以使下一部分更清晰些.

现在让我们看一下实际的规则.我使用/* */作注释;LEX是一个相当老的程序,所以它着支持//引导的注释.顺便提一下,我们将使用LEX生成C程序,C++版的LEX程序也有,但是标准的UNIX LEX产生C代码.我们想要使这东西便携,不是吗? (燕良注: LEX源文件 .L--->FLEX--->C源文件,默认文件名是lex.yy.c)

我删去了一些非常简单的规则.就象你看到的那样,每一条规则开始部分是LEX将要识别的样式,接下来是一些代码告诉LEX当规则匹配后作什么(这部分代码可以包含C++代码,因为LEX只是简单把它们的拷贝到输出文件中).记住最顶端的规则被最优先评估,这通常很重要.

头3条规则十分的简单,它们只是识别一个字符串,然后返回相对应记号的符号.你可以改变这些字符串,例如你想使用":="来作赋值操作符.

第4行是第一条有趣的规则:它使用了IDENT宏,它识别不满足前面的条件的字母/数字串.如果匹配,它将调用Identifier()函数,此函数把yytext(保存当前记号的文本)的内容赋复制到一个新字符数组.词法分析器返回ID记号,主调函数可以使用'yylval->str'指针来访问标识符非名称.STR对于字符常量实现同样的功能.

下一行规则处理注释,换行和空白.注意行号将被计数,将来我们在出错信息中将使用它.最后一行告诉LEX如果输入不能满足上面所有的规则(表达式"."的意思是:除了'\n'以外的所有字符),我们应该返回一个错误记号,然后让主调函数决定作什么.

LEX的源程序可以使用下面的命令行来编译成LEX.CPP:
        flex -olex.cpp string.l

ZIP中还包含一个MSVC 6.0 (string.dsp)的Project文件,我相信它在5.0中也能工作,但是我不确定.Project为string.l设置了一个自定义命令行,所以它可以被自动编译.

不幸的是LEX使用一个非标准的头文件,unistd.h,它不能在windows中使用.在主目录中有一个空的unistd.h文件,请添加主目录到include路径中(in MSVC:Tools->Options->Directories->Include).

lex.cpp包含一个满足我们规则的完整的词法分析器.它是那么简单!主程序只是使用词法分析函数读取一个记号,然后显示记号的名字和值(它是ID还是STR).你可以试着加入一些测试数据,然后观察词法分析器如何处理它们;随机的字符序列通常被识别为ID,我们不使用的字符,例如'$'引发一个ERROR_TOKEN.你也可以试试example.str (在主目录).


情况会变好的

好吧,我们现在有了一个可以"读"的程序.遗憾的是它对它读的是什么和这些是否符合我们的标准依然没有概念.它只是接受它知道的一些记号.

看来它需要知道语法,惊人的巧合,语法正是我们下一部分将要讨论的.下一个组件是语法分析器,它的功能是找出程序的结构并且检查语法.

这样就变得真正有趣了.我们将能使程序成为一个编译器,它将接受一些东西,并不只是因为它可以接受几乎所有东西,而是因为它知道这个程序的语法是正确的.我知道你肯定和我一样激动,但是我不得不等到下一部分...

Quote!
"And so it was only with the advent of pocket computers that the startling truth became finally apparent, and it was this:

Numbers written on restaurant bills within the confines of restaurants do not follow the same mathematical laws as numbers written on any other pieces of paper in any other parts of the Universe.

This single fact took the scientific world by storm. It completely revolutionized it. So many mathematical conferences got held in such good restaurants that many of the finest minds of a generation died of obesity and heart failure and the science of maths was put back by years."

HHG 2:7

燕良的附注:词法分析的手工设计举例

程序的功能是把下面这些实常数转换成相应的科学计数表示:

• "Pi"转换成0.314159265359E1
• "E"转换成0.271828182846E1
• "Degree"转换成0.174532E-1
• 一般的实常数按值转换,例如456==>0.3456e4,0.0098==>0.98E-2

设计思路:

Pi,E,Degree可以当作关键字来处理,不是本程序的主要部分,本程序的主要功能是识别一下各种形式的实常数:

• a.
• b.
• a.b
• a.E[+/-]c
• .bE[+/-]c
• a.bE[+/-]c
• aE[+/-]c

识别上述形式实常数的DFA为:

 

参见程序:CONSTANT.zip

Part III:语法分析器
序言

前一部分的执行可以作一件很好的工作:把程序转换成记号.所有的关键词,操作符,分隔符,标识符和常量都被立即识别和报告.然而,你可以输入:

{ this ) = "pointless" + ;

然后程序将只是接受它,并且高高兴兴的产生一个记号的列表.因为它不清楚我们想要允许什么东西(我不知道上面的"语句"要做什么).我们必须能够识别输入程序的语法结构(或者它的缺点).

我们借助语法分析器来作这件事,语法分析器用来找出程序的结构并且检查所有的语法错误.


一点语言理论

我们怎么告诉语法分析器我们的语言是什么样呢?我们可以使用一个叫作BNF范式(Backus-Naur Form )的东西来描述语法(syntax或grammar).这种描述方法使用组成程序的基本概念.举例说明,表达式可以是在其他任何东西之中,标识符或者字符串常量(expressions can be, among other things, identifiers or string constants).在BNF范式中,它可以写成下面的形式:

expression: identifier | string;

一个打印语句或者输入语句:

statement
: PRINT expression END_STMT
| INPUT identifier END_STMT
;

(记住PRINT,INPUT和END_STMT都是词法分析器返回的记号)

现在,一个程序可以被表示成下面这种语句列表的方式:

program: | program statement;

上式说明一个程序可以是空或者由程序加上一个语句构成,这里说的语句是一个递归定义,它可以是一串语句(燕良注:这个文法是左递归的).

那么,我们已经用BNF范式定义的语言包含下面的语句:

print a;
(燕良注:这个语句可以使用下面的推导过程:
program: program statement;
program: program statement;(应用产生式  program: 空)
program: PRINT expression END_STMT;(应用产生式 expression: identifier)
program: PRINT identifier END_STMT;
经过词法分析后上面的语句形成的记号流与此式匹配;
以上是最左推导;下面是最右推导
program: program statement;
program: program PRINT expression END_STMT;
program: program PRINT identifier END_STMT;
program: PRINT identifier END_STMT;
根据上述推导可以画出语法树,对于无二义性的文法,所有的推导画出的语法树都是一样的.)
print "Hello";
input name;

Not legal is:

input "Hello";

通过我们的定义,input语句(燕良注:指产生式statement:INPUT identifier END_STMT;)只能作用于一个标识符,而不能是字符串常量.

我们可以使用BNF范式正规的描述我们的语言的整个语法.注意这些现在还不包含语义,于是这条语句:

a = (b == c);

纵使它没有意义它也将被语法分析器接受(我们正在试图把一个布尔值赋给一个字符串变量).语义将在下一阶段作检查.

太好了,我们现在知道的语言描述法足够来建立我们语法分析器.


看上去很熟悉!

语法分析器也可以用一个外部程序来产生.这个叫作Yacc(一个标准的UNIX工具,就像是LEX);我们将使用一个叫作Bison的改良版(get it?).Bison的手册有又可以在这里(http://www.monmouth.com/~wstreett/lex-yacc/lex-yacc.html)找到.Yacc文件(extension .y) 的分段实际上与LEX文件十分的相似.

<说明部分>包括记号的定义,类型信息,还有在前一部分我们看到的yylval共用体.那就是为什么我们使用一个共用体:Yacc使用同一共用体来在两个不同的"语言概念"之间传递信息,例如表达式,语句,程序.根据这些定义,Yacc为我们产生lexsymb.h(实际上它建立的是parse.cpp.h文件,不过parser.bat把它改名了).

就象LEX文件一样,在这部分同样可以在标记"%{"和"%}"之间包含一些初始化代码.在这部分的教程中没有用到这个功能,但还是可以增加一些你需要的附加的代码.

规则是特定的一些BNF范式,用来解释前一部分.

Yacc有一个恶劣的陷阱,那就是你的语言必须使用LR(1)文法描述...这究竟是什么意思在龙之书中有详细的解释(第4.5,关于自下向上分析),LR(1)文法基本的意思是语法分析器还必须能够在查看当前语法记号或者最多预读一个符号就能说出使用什么样的语法规则.下面的语法规则会产生一个移进/归约冲突(shift/reduce conflict).(关于更多的文法理论可以参见最后我加的附注)

A:
| B C
| B C D
| D E F

冲突产生在当你从输入文件中读了一个'B',而预读符号是'C'时,因为他们可以被组合(这两种产生式最终都将产生一个文法符号);问题是第2个产生式以'D'为结尾,而且第3个以它我起始:当语法分析器读取到了'C',而且预读的是'D'时,它不能决定是否归类为A2或A1后面跟着一个A3(燕良注:请注意我们只预读一个文法符号)!尽管这个完整的文法定义可能根本就没有二义性,但是对于语法分析器它却是有的,因为语法分析器只能预读一个文法符号.Yacc把这种不确定性称为移进/归约冲突或归约/归约冲突.

呵呵,别让这些吓着你.看一下这些规则.最重要的一条可能就是这条语句规则了:

你能看到,这里定义了我们的语言所有的语句类型,后面的代码是告诉语法分析器当发现了每个产生式时应该作什么.我认为这条规则是十分漂亮的.有一件事:"Errorstatement"告诉Yacc当分析一条语句时如果它遇到了一个语法错误后应该作什么(例如一个非法的记号或者一个不合时宜的记号).在这种情况下它会查找下一个END_STMT记号,然后继续分析后面的东西.语法错误会始终报告到在main.cpp中定义的yyerror()函数,所以我们的编译器会使用一个恰当的方法来处理它.如果在你的.y文件中没有提供任何一个错误规则,那么你的语法分析器遇到语法错误就会定下来,这可不是很好.

也许你在奇怪为什么会有这么多的表达式规则呢:expression, equal_expression, assign_expression, concat_expression 和 simple_expression.这是为了描述操作符的优先级.如果语法分析器看到了这个:

if (a == b + c)

它应该知道它不应该先计算a==b然后试着把这个布尔值计算结果与一个字符串变量c相加(燕良注:这里的侧重点不是数据类型,而是算符的优先级).这些不同的表达式规则确定了唯一的语句的语法分析方法.花点时间好好看看它;它能够工作.

另外一个问题是当分析下面的语句时:

if (a == b) if (c == d) e = f; else g = h;

语法分析器不知道else属于那个if语句(内层的还是外层的);它可以认为你的意思是:

if (a == b) {if (c == d) e = f;} else g = h;

但是作为一个所有语言都遵循的惯例,else与内层的if匹配.

因为没有办法通过改变我们的规则来解决这个问题,Yacc将会报告一个移进/归约冲突.这个冲突可以简单的在说明部分加上这行来禁止:

%expect 1

这意味这Yacc应该预期冲突1(Yacc should expect 1 conflict).Yacc将把else与最近的if配对,正象我们想要的那样.这就是它发现任何冲突的默认的解决方法.

一旦你理解了BNF范式,Yacc文件是非常的不解自明的.如果你还有什么不清楚的地方,你可以给我来mail或者在messageboard上提出问题.

Yacc的源文件可以使用这条命令来编译:

bison --defines --verbose -o parse.cpp

如果你得出了什么冲突,看一下输出的parse.cpp文件,那里包含冲动的细节(即使没有错误,那仍然是一个有趣的文件).如果你陷入了任何不能解决的冲突,可能把你的.y文件发给我,我会看一下的.

如果每件事都OK了(在样例代码中应该是这样的),那你在parse.cpp中就得到了一个可工作的语法分析器.我们的主程序要做的就是调用yyparse()函数,这个输入文件就会按我们的要求处理了.

再试试example.str文件,然后看一下它产生的错误.错误?是的,没错,我在第13行最后忘了一个';'.呵呵,它很棒吧?


Whew! 

今天我们作了很多事.我们学习了一些形式语言理论,如何使用Yacc,为什么Yacc对它支持的文法如此的挑剔,如何描述操作符的优先级.在最后,我们制作了一个可以工作的语法分析器.

好吧,我想最难的部分就在后面.如果你理解了这些,休息一下吧.然而,我在LR(1)文法上忽略了很多.给我来信或者发到messageboard让我来澄清那些问题.欢迎任何的问题和评论,让我知道有人在读这些东西.

下面是什么呢?下次我们大概要写两个新的组件:符号表和语法树.到那之后,你有一周来试验这些代码.提示:试着找到一个接受C风格的while语句的编译器.


Quote! 

"The major problem is quite simply one of grammar, and the main work to consult in this matter is Dr Dan Streetmentioner's Time Traveller's Handbook of 1001 Tense Formations. It will tell you for instance how to describe something that was about to happen to you in the past before you avoided it by time-jumping forward two days in order to avoid it. The event will be described differently according to whether you are talking about it from the standpoint of your own natural time, from a time in the further future, or a time in the further past and is further complicated by the possibility of conducting conversations whilst you are actually travelling from one time to another with the intention of becoming your own father or mother."

HHG 2:18


Downloads

Download the tutorial code (tut3.zip) (5k)


燕良的附注:说明一下文中的几个名词

• 关于BNF范式
  文中的
  expression: identifier | string;
  可以读作expression定义为identifier或string.
  这个式子包括两个产生式.
• 关于LR(1)分析原文中提到的不多,所以在这里补充一下.但是完整的语法分析理论恐怕您还是要找本书来看.不过,如果只是想使用工具的话我想看了原文和这里的补充应该差不多了.
  LR(1)分析是自下向上分析的一种,自下向上的分析实际上是最右推导的逆过程,名字中的'L'表示自左向右读入记号,'R'表示最后推导,'1'表示预读一个记号.
  实际上LR(1)分析也好,LL(1)等等各种分析也好,其最终目的都是得出一个状态矩阵.通过这个矩阵程序才能知道下一步该怎么作,动作主要有两种,一是移进,即读入下一记号,二是归约,就是用产生式的左部来代替产生式的右部,其中如果是规约,还要说明用那个产生式归约.
  验证文法的LR(1)性是一件比较复杂的事.本文只讲实现不讲设计,其实设计出好的文法我觉得很有挑战性.:P
• 这篇文章还是挺不错的,语法中的两个难点:操作符优先级和if-else问题都提到了.这是应该注意的地方.

Part IV:符号表 & 语法树
序言

如果我们想要用上两部分我们建立的词法分析器和语法分析器来作些有用的事的话,那么我们需要把我们从程序中收集的的信息存储到数据结构中.这就是下面我们要作的.这包括两个重要的组件: 符号表和语法树.

符号表,顾名思义,它是我们的程序中用来存储所有符号的一个表;在我们这里,包括所有的字符串变量,还有常量字符串.如果你的语言含有函数和类,他们的符号也将被存储的符号表.

语法树是程序结构的一个树形表示;请看下图.在下一部分中我们使用这个表示来生成中间代码.尽管不是必须建立一个语法树(我们已经从语法分析器中得到了所有关于程序结构的信息),但是我认为这可以使编译器更透明(燕良注:原文是tranparent,我猜是拼写错误,所以按transparent译的,不知道那是否是什么术语...),这正是在这个系列文章中我所要达到的目标.



这是包括"真正的"代码的第一部分,在我们观察它之前请让我澄清一点:这些代码在写时应该更易懂而不是结构好.它对于我们这里制作的编译器是合格的,但是如果是一个真正的编译器,你需要作很多不同的东西.当我们碰到这些问题时我会试着说明它们.


在规则之间传递信息

显而易见,我们必须在我们的语法分析器中添加功能;例如,当我们发现一个符号时我们把它送人符号表--但是我们还希望它的"父"规则(事实上使用此标识符的规则)在符号描述中也要能够被访问.

我们在建立一个语法树时需要某些近似的东西:我们需要父规则有一个指针指向他的"孩子结点"(构成父规则的那些规则)

还记得yylval共用体吗?Yacc也使用他在规则之间传递信息.每一个规则能够使用yylval共用体的一个域;这是规则的类型.在string.y的顶部,你能看到类似下面的类型说明:

%type <symbol> identifier string
%type <tnode> statement expression

symbol和tnode是那个共用体的新成员;他们分别描述一个指向符号描述的指针和一个指向语法树的指针.

现在语句的规则象下面这样使用这些类型:

| expression END_STMT {$$ = new TreeNode (EXPR_STMT, $1);}

它的意思是:如果你发现了一个expression语句,构造一个EXPR_STMT类型的新的树结点(并且返回新的结点指针),他带有一个"孩子":组成这个语句的表达式.$$代表一个规则的返回值,$1是规则定义中的第一个符号返回的值(expression).在这里$2没有意义,因为词法分析器没有为END_STMT记号设置一个yylval成员.

我希望这样的解释够清楚了,因为这很重要.本质上,规则是分层的,每一条规则能够返回一个值到"更高层"的规则.

现在让我们看一下符号表和语法树使用什么样的数据结构.


符号表

符号表在我们例子中至包含很少的信息;基本上它只是变量名和它第一次被声明的行.后面我们会使用它来存储更多的数据.

实现非常的简单:它只是当我们取回一个符号时(看一眼symtab.cpp)为符号的描述建立一个单链表(singly-linked list)并且线性的查找这个链表.对于一个真正的编译器,符号表通常被实现为一个binary search tree 或 hash table,以便能够更快的找到符号.

你要作的是当语法分析器发现这个时把我们的符号送入那个表:

我们把字符串常量处理成常量,我们为他们生成一个名字然后把他们送入那个表.注意:一个更高级些的编译器可能会让词法分析器来存储和取回标识符.这是因为复杂的语言中标识符可能有很多不同的含义:变量,函数,类型,等等.词法分析器可以取回标识符的描述,并直接把相应的记号返回给语法分析器.因为我们标识符肯定是变量,所以我们只使用语法分析器来处理他们.


语法树

我为语法树建立了一个非常简单的TreeNode类.它只存储指向孩子的指针和一些附加信息(结点类型,如果可用还有一个符号的连接).看看吧,这没什么复杂的.

象你前面看到的,我们可以从已经验证的语法规则轻松的建立语法树:
 

你会看到在某些时候我们只是无变化的从孩子规则到父规则传递信息;如果你的equal_expression 事实上就是一个assign_expression,就没有必要为它建立一个新的结点;你只使用在assign_expression中建立的那个.记住我们使用这么多表达式规则的唯一的原因是为了清楚的处理操作符的优先级.

编译这部分(和下面的部分)使用与前面相同的方法.程序还是接受语法结构上正确的程序,但是现在转储到它建立的符号表和语法树中.


这真的很cool,但是...

OK,它读程序并且分析它.但是它没有对程序作任何真正聪明或有用的事,不是吗?

是的,依然是.我们还有更多的组件要实现.下一部分将涉及语义检查和中间代码的生成.这将是一条通向编译程序的漫漫长路.

我希望你不要认为它进展的太慢,我只是想要集中到每一个分立的组件,而不是走马观花.如果你很快理解了这些东西,实验一下他们吧.

下次再见.


Quote!

(Part of the Guide entry on the Babel Fish)

"Now it is such a bizarrely improbable coincidence that anything so mindboggingly useful could have evolved purely by chance that some thinkers have chosen to see it as the final and clinching proof of the non-existence of God.

The argument goes something like this: `I refuse to prove that I exist,' says God, `for proof denies faith, and without faith I am nothing.'

`But,' says Man, `The Babel fish is a dead giveaway, isn't it? It could not have evolved by chance. It proves you exist, and so therefore, by your own arguments, you don't. QED.' "

HHG 1:6


Downloads

Download the tutorial code (tut4.zip) (8k)

Part V:语义检查 & 中间代码生成
序言

这次晚了一点...考试真是件可怕的事,它真的妨碍了一些有用的东西.

是的,上次我承诺了结果,你想要得到它们.也许多过你的希望 ;-)

首先是关于这个教程的一个备注.我是想要写一个非常紧凑的解释.所有的信息都在这里,但是常常是每个句子有两个重要的事情..这样作的缺点是是否有些事不大清楚,你可能没有跟上这个教程.当我进行的太快时请告诉我,好让我能够把事情说清楚.

回到这部分.它是关于语义和中间代码的.语义检查将确认你的程序是真正的正确,中间代码将是向虚拟执行(virtual executable)的一个巨大飞跃.

让我们开始检查吧!


检查语法

语义检查不单单是检查程序语法的正确性,它还要确认语句有意义.例如,提供给函数的参数的个数应该是函数所预期的.

语义检查的主要部分是类型检查:决定表达式的类型和报告任何的不一致,如想要比较一个布尔值和一个字符串,或者传给函数错误的参数.

当然,也许你想要允许某些"不一致":例如有人使用了下面的语句

print "a and b equal: " + (a == b);

他的意思可能是表达式(a == b)应该被自动转换成一个字符串,最后成为字符串"true"或"false".这称为强制类型转换.在我们这个简单的编译器中我只允许布尔到字符串的强制转换,但是如果你认为字符串到布尔的强制转换有用,你可以轻松的加上它.

我们的语义检查器的代码并不复杂.我为TreeNode加了一个名为Check()的成员函数(在synttree.cpp文件中),它检查一个结点的语义,我们假定它的所有孩子结点都已经被检查了.Chech()在TreeNode的构造函数中自动调用,所以这个假定是安全的.

检查设置了一个名为rettype的新成员变量,表达式的"返回类型".例如,一个条件,当一个字符串连接另一个字符串时,布尔是它的返回类型.rettype用来检查父结点的语义.CoerceToString函数通过插入一个作为被强制转换的结点的父结点的新结点,COERCE_TO_STR,来强制转换任何的表达式为字符串类型(如果它还不是).

对一个简单的编译器这是很轻松,但是通常它不是这样.如果你的语言包含更多的基本类型,索引(references),数组,类和(操作符)重载,事情很快就变得非常的可怕;如果你希望你的程序能够运行,那么你最好有一个坚实的检查系统.

在一个真正的编译器中它从事更多的工作:有更多的强制转换,你必须计算出要使用哪个重载函数,类型等价不是再是这么平常,等等.

在这儿它是很简单,并且它对于用更多的类型来膨胀这个系统的学习经验很有用,但是在一些地方你应该更接近一般情况.

代码应该足够说明它们.它只执行一些简单的事,如if条件应该是布尔型,赋值表达式应该是字符串,等等.


产生中间代码

中间代码在我们程序中表示为一个有序的图:每一条指令有一个指向下一条指令的指针,跳转有一个指向它的目标指令的指针.

我能想出两个这么做(使用指针)而不是立即产生代码到一个大的数组的两个好处:第一,使用指针便于把代码片段的连接,而且去掉某些指令时不用更新所有的跳转,等等.优化也因此相应的简单了.第二,如果你想要更改虚拟机的一些指令,这使你的编译器更容易改写来适应新的VM,因为你只需改变从中间代码到最终代码的翻译步骤,这相对的简单.
 

于是,基于上面的思想,我们设计了我们的中间代码语言.这个语言的操作码(opcode)将与我们的虚拟机要执行的即使不完全一致也是十分的相似.看一下它们:

enum Opcode {
OP_NOP, // no operation
OP_PUSH, // push string [var]
OP_GETTOP, // get string from top of stack (=assign) [var]
OP_DISCARD, // discard top value from the stack
OP_PRINT, // print a string
OP_INPUT, // input a string [var]
OP_JMP, // unconditional jump [dest]
OP_JMPF, // jump if false [dest]
OP_STR_EQUAL, // test whether two strings are equal
OP_BOOL_EQUAL, // test whether two bools are equal
OP_CONCAT, // concatenate two strings
OP_BOOL2STR, // convert bool to string
JUMPTARGET // not an opcode but a jump target;
// the target field points to the jump instruction
};

你将看到我们的VM是一个堆栈机器(a stack machine):操作码对堆栈中的值进行操作,把值放回堆栈.我想对产生代码和执行代码来说这是都最简单的机器类型了.

一个关于JUMPTARGET操作码的说明:每当我们的代码中有一个(条件)跳转时,它并不指向一条实际的指令而是指向一个有"JUMPTARGET"前缀的指令.这么做的原因是当我们优化时我们必须知道代码中的每个跳转的目的指针,或者我们也许会把一条目的指令优化掉并且混乱(mess up)我们的程序.这些JUMPTARGET将不出现再我们最终的字节码中.

一般而言,所有的操作码操作堆栈顶端的项目.OP_STR_EQUAL从堆栈中弹出顶端的两个项目(必须是字符串),检查它们是否相等,然后把结果的布尔值进栈.你的程序接着可以使用OP_JMPF指令来使用这个结果:如果栈顶的布尔值是false跳转到目标指令(由本指令提供,而不是在栈中),如果栈顶是true就继续执行.

指令被存储到一个非常简单的中间指令类中,它只是保存操作码,一个符号--操作数(例如OP_INPUT),如果需要还有一个跳转目的指令,一个下一指令指针和一个行号.行号实际上只是在使用Show()函数时使代码可读.

现在让我们看看如何产生中间代码(intcode.cpp).通常我们为语法树中的所有子树产生代码.所以main以树根来调用GenIntCode()函数;GenIntCode处理并且返回一个中间代码的起始指针.

先看个简单的例子,INPUT_STMT结点:

case INPUT_STMT:
return new IntInstr (OP_INPUT, root->symbol);

这产生一个新的OP_INPUT指令并且返回它.注意这个指令也是一个长度为1的指令块(block of instructions) ,next指针默认为NULL.

PRINT_STMT更困难一点:

case PRINT_STMT:
blk1 = GenIntCode (root->child[0]);
blk2 = new IntInstr (OP_PRINT);
return Concatenate (blk1, blk2);

首先我们产生代码来计算表达式提供给print语句(root->child[0]).接着我们产生一个新指令OP_PRINT来打印栈顶的字符串.注意我们假设表达式把它的值放到栈顶.当然,我们得自己来保证这一点.最后我们连接两个代码块,然后返回结果.

现在是一个真正难的:IFTHEN_STMT.我产生所有需要的块,然后把它们都连到一起.它检查条件,如果它是false调换到结尾,如果它是true就执行then部分.

case IFTHEN_STMT:
// First, create the necessary code parts
cond = GenIntCode (root->child[0]);
jump2end = new IntInstr (OP_JMPF); // set target below
thenpart = GenIntCode (root->child[1]);
endif = new IntInstr (JUMPTARGET, jump2end);
jump2end->target = endif;

// Now, concatenate them all
Concatenate (cond, jump2end);
Concatenate (jump2end, thenpart);
Concatenate (thenpart, endif);
return cond;

记住root->child[0]是条件子树,root->child[1]是then子树.

好的,如果明白了那个,对与剩余的代码你就没问题了.所有树的结点都使用这个方法翻译.Show()函数显示我们产生的代码.看一下所有这些:

Program:
if (a==b) a; else b;

Intermediate code:
1: OP_NOP
2: OP_PUSH a
3: OP_PUSH b
4: OP_STR_EQUAL
5: OP_JMPF 9
6: OP_PUSH a
7: OP_DISCARD
8: OP_JMP 12
9: JUMPTARGET 5
10: OP_PUSH b
11: OP_DISCARD
12: JUMPTARGET 8

这看上去非常的象汇编代码,是吧?这是因为它就是.它是虚拟汇编(Virtual Assembly),本质上我们只需要写一个汇编程序来产生虚拟执行代码.


Whoa, what happened?

那进行的很快,不是吗?刚才我们还想我们是否将作一些有趣的事,突然我们就产生了虚拟汇编代码.我们几乎完成了.

下次我们将看一下优化(我确信如果你观察这部分的输出你能想到一些).很快我们将产生真正的虚拟机代码--但是我猜我们最好先有一个虚拟机!我们将看到从那我们去哪里.欢迎你发给我一些想法或建议.

Bottom line: some interesting stuff is coming up. Stay tuned!

See you next time.


Quote!

The story so far:

In the beginning the Universe was created.

This has made a lot of people very angry and been widely regarded as a bad move.

HHG 2:1


Downloads

Download the tutorial code (tut5.zip) (10k)

Part VI:优化

你发现BUG了吗?

注意到了前两次的代码的好笑的东西了吗?可能有一个内存漏洞(memory leak)?Emmanuel Astier发现了;他找出了符号表中的一个BUG:当删除符号表时,我只是删除了链表中的第一个实体,而没有删除其他...OK,虽然程序没有崩溃,但是这不是很漂亮.这将在下一个教程中修改.多谢Emmanuel!


序言

我的考试结束了,我现在可能继续了.

在这部分我将涉及优化我们的中间代码的方法.记得吗,我们使用了一个非常简单的代码生成算法,所以那些代码也许相当的需要优化.

因为我们将在一个虚拟机上执行,所以优化变得格外的重要:我们的每一条指令将花费20条CPU指令去执行(很难更少),所以指令越少越好.

注意,我将只讨论与机器无关(machine-independent)的优化;面向机器的优化是一个完全不同的话题,在那里我们必须考虑象流水线效率,寄存器的使用等等这些.并且,当然的,面向机器的优化只有当你的代码在硬件上运行时才需要,这我们不需要.当然,可能有很多的方法来加速执行虚拟机本身,但是我们将在后面讨论.

对不起,这部分没有例子代码.一些优化的想法实现起来都是相当的简单,你将不会在这些问题上碰到麻烦.另外一些更复杂并且需要花大力气来实现.我没有时间来作,所以我只是给出一般的概念.

有两个重要的加速我们的代码的途径.一个是把代码翻译成更少的指令.另一个是制作更多强大的指令.


额外的操作码(Extra Opcodes)

高级的指令(Higher-level instructions)可以在VM上执行的更快,因为堆栈操作和更新指令指针的总开销是(粗略)的相同的.所以我们将忽略RISC并且为外来的代码(exotic instructions)而疯狂!;)

让我们观察一些代码.这是example.vasm的一部分,example.str的编译后的版本:

1: OP_NOP
2: OP_PUSH strconst1
3: OP_GETTOP a
4: OP_DISCARD
5: OP_PUSH strconst2
6: OP_GETTOP b
7: OP_DISCARD
8: OP_PUSH a
9: OP_PUSH b
10: OP_CONCAT
11: OP_GETTOP s
12: OP_DISCARD
13: OP_PUSH s
14: OP_PRINT

我应该注意它的一些事情.第一,在这个代码中的三个地方有一个OP_DISCARD跟随在一条OP_GETTOP的情况.我们将它它转换成一条OP_POP来提高速度,这条指令取得栈顶的值并且把它从堆栈中移走.我可以在开始时这么做,但是我想现在这样更简单.

第二,我看到了OP_PUSH; OP_GETTOP; OP_DISCARD两次.. 这是一个向"a = b"这样的简单赋值语句的代码.我们可以为它提供一个特殊的操作码OP_COPY,它把一个变量的值拷贝到另一个中.

第三,在这个程序的完整的代码中有相当多的"double pushes",两个进栈操作在一起.我们一个制作一个单独的OP_PUSH2操作码来加速它.

你或许能想出另外的高级指令.例如,一条连接一个现有字符串OP_CONCATTO操作码(s += "foo";).如果仔细的挑选他们将能够加速执行,所以花写时间来研究你的汇编代码,然后发现优化的可能.

代码变形(Code Transformations)

优化输出代码的另一个途径是吧一部分代码变形成更快的执行同样任务的某些东西.下面是一个例子.

下面是一些变形代码的算法,节约指令..(saving instructions and thus time)

绝大多数优化集中在优化一些被认为是"基本模块(basic blocks)"的一小段代码.一个基本模块有下面这些性质:你能够在开始时跳转到它里面,并且你只能在它的结尾跳出.所以在这些块的中间没有跳转或者跳转目标(jump targets).这意味着在块之内我们能够确定一件关于我们的变量的值的必然的事情,我们可以利用这个信息来优化代码.举个例子,如果你可以跳转到块内的某处,我们不能确定,t仍然保留着值(a * b - c).

指针带给基本模块优化很多困难,因为你必须确定变量没有通过一个指针被修改,而不是了基本模块的某处通过它的名字被修改.往往你不能确定这点(指向指针的指针就几乎不可能知道什么变量被改变了).


代数上等同(Algebraic identities)

一个优化代码的简单方法是使用产生相同结果的更快版本来替代原来的"天真的"计算.这些"天真的"计算的计算经常采用一个简单的代码产生方案而不是象程序员指定的那样.观察下表,十分明显.

消除通用子表达式(Common subexpression elimination)

这种优化利用某一表达式可能多次使用一小段代码的事实:

a = a + (b - 1);
c = c + (b - 1);

这里(b-1)是一个通用子表达式并且可被再次使用(第二个(b-1)表达式可以被"消除").

t = b - 1; // 把子表达式存储到一个临时变量中
a = a + t;
c = c + t;

为了检测通用子表达式,你需要构造一个出现在你表达式中基本模块的有向无环图(DAG,directed acyclic graph).每次你遇到一个新的表达式(例如,语法树中一个更高的结点),你检查在这个基本模块的它是否已经出现在表达式DAG中.当这个图完成时你能很容易的看出那个子表达式使用了多次,这样你就可以把它们的值存入一个链式变量,并且再次使用它.上图是一个例子.


循环的优化(Loop optimizations)

一个众所周知的程序员的格言"程序90%的时间花费在执行10%的代码上",尽管这个百分比每个程序都不同,但是每个人都会同意绝大多数运行时间花费在一个内层循环上.

所以如果我们能使用某种方法优化这些循环,我们就能节省很多的时间...好吧,有很多中优化循环的方法;我将简单的讨论他们中的两个,代码移动和变量归纳(code motion and induction variables).

代码移动类似与子表达式消除,但是不是在一个基本模块中,它在循环开始前计算表达式并且在循环的整个过程中使用这个值.

while ( i <= limit-2 )

变为

t = limit - 2;
while ( i <= t )

可是,循环也许没有很多的不变的表达式.它们经常使用的是一个循环技术器,并且这个技术器被频繁的使用在计算中,例如数组下标,等等.那就是变量归纳能帮我们的了.

如果j是我们的循环技术器,并且每次循环中都计算j*4,我们可以使用一个变量归纳,然后把这个乘法替代为加法:

for (j = 0; j < n; j++) {
.... (j * 4) ....
}

变为:

t = 0;
for (j = 0; j < n; j++) {
.... t ....
t += 4;
}


跳转的消除(Jump elimination)

有时你能够通过观察跳转的目的块来消去一个跳转.例如,你可能有:

1: jmp 7
...
7: str_equal
8: jmpf 10
9: ...

你可以从目的块拷贝代码,然后节省一个跳转(如果条件为假):

1a: str_equal // | 目的块的拷贝
1b: jmpf 10 // |
1c: jmp 9 // 如果条件为真,跳转到9
...
7: str_equal
8: jmpf 10
9: ...

你要决定为了消除一个跳转你将要复制多大一部分代码,但是在内层循环中它能省很多时间.

下次的东西...

这些信息使你的程序变得更有效率了.可是编译器优化是一个非常复杂的领域,我们只涉及到了非常少的一点.龙之书讨论了更多,所以如果你感兴趣,就去看它吧 .

下次我们将建立我们虚拟机,然后也许产生我们的虚拟机代码吧.那时我们就终于可以执行一个程序了.


Quote!

Somewhere on the wall a small white light flashed.

"Come," said Slartibartfast, "you are to meet the mice. Your arrival on the planet has caused considerable excitement. It has already been hailed, so I gather, as the third most improbable event in the history of the Universe."

"What were the first two?"

"Oh, probably just coincidences," said Slartibartfast carelessly.

HHG 1:30


Part VII:虚拟机(The Virtual Machine)

序言

我们已经在Part V产生了中间代码,并且我们想要把它转换成可执行代码,好让我们能够执行一个程序.但是我已经决定要先建立一个虚拟机,这样我们可以知道该如何处理产生可执行代码.

虚拟机当然是一个脚本引擎中非常重要的组件.我们的代码将在它那里执行,所以它最好快一些.但是这里我将不把焦点集中到速度上.

Oh yeah:这部分结束后,你将完全免费的得到我那令人惊奇的堆栈模板(Amazing Stack Template),也不需要额外的小费.并且你将得到一个为这部分特别编写的很酷的字符串类,它完成至少5个精密的工作.那是你的物有所值的东西.

但是,首先是一个不同机器类型的说明.在Part V我只是说了我们的VM将是什么种类,没有说明其它的可能.Andy Campbell询问我关于这方面的其它可能性,并且我想其他人也许会感兴趣.


机器类型

以前说过,我们的机器将是一个堆栈机器(stack machine).在真实的机器中,堆栈CPU被用于早期的计算机(并且今天依然在一些简单的设备中使用).缺点是需要很多的堆栈操作:每个操作数需要一个PUSH,每个结果需要一个POP.尽管你直接使用这个结果来进行下面的计算,所以那不总是必须的.

现在的大多数CPU有寄存器(数量非常有限的存储位置)来进行操作而不是堆栈;堆栈依然在函数传递参数时使用.可以只在寄存器上操作的机器被称为load/store机器,因为你必须load每个你用到的值,然后在你计算完后store每个结果.

某些处理器只操作内存数据;没有堆栈,也没有寄存器.使用这种处理器的机器被称为三地址机器(three-address machines),因为绝大多数指令有三个地址操作数(例如 ADD dest,src1,src2).由于内存带宽的限制,我认为他们不会在很多硬件中使用,但是他是虚拟机的一个选择.

对于虚拟机,堆栈机器非常容易实现,因为当你计算一个表达式时不需要临时变量来存储中间结果;你把所有东西放入堆栈(它与你处理一个后缀表达式的方法十分相似).虽然我将在这里使用临时变量.后面还有更多内容.

我不清楚三地址机器是否可能有一个优点;速度是最重要的一个,尽管我尝试了两者,我能肯定的说出哪个在优化中做了更少的计算...我想优化三地址代码更容易,所以也许这是这种机器的一个优点.

JAVA表面上使用一个堆栈机器(我听说是这样,我对JAVA VM不熟).


一件虚拟的非常容易的事(A Virtual Piece of Cake)

我们的虚拟机对象根本就不复杂.它的最重要的成员有:一个指令数组,一个字符串表和一个堆栈.它有三个主要的接口函数:Reset,Read和Execute.

指令数组存储我们的程序包含的指令.指令类简单极了,看上去就像我们在Part 5中的中间代码使用的一样.

字符串表只是一个指针数组,它可以是NULL或者一个当前使用的字符串.这可能是一个程序的变量,或者一个堆栈中的临时变量.

我们的堆栈是由整数组成的.它们指向字符串表,使我们知道什么字符串现在在堆栈中.为什么我使用整数,而不是字符串类的指针呢?因为我想保持事物的简单(为了读者,也为了我自己):记住我们有时也想让堆栈存储布尔值,所以我们不得不建立一个存储字符串指针或布尔值的'stack item'类...现在我们只是使用一个整数:如果它是非负数,我们知道它指向一个字符串,如果它是负数它就是一个布尔值.它是脏的代码,但是他有利于工作并且每个人都可以理解它.不要在家试它,不要在一个真正的项目中使用它.

现在是接口函数.'Reset'重新初始化VM.它是一个很简单的函数.

'Read'将要在程序中读取.下次我们将改变这个函数让他从stdin中读取,但是现在它里面有一个测试程序.如果你喜欢就改写它--只是小心的让程序保持正确,不要让我们的VM崩溃.

'Execute'执行当前在内存中的程序.这也是一个简单的函数:它有一个指令指针,它察看一个指令,然后使用一个switch语句执行正确的代码.关于临时变量的一个说明:每当我们把一个变量放到堆栈,我们需要它的一个拷贝:我们不能只是把在字符串表中的变量的索引值进栈,因为他们的值可能改变并且接着堆栈中的值也会改变.这就是为什么几乎每个堆栈操作都使用NewTempCopy和DelTempCopy.

一点关于优化VM的说明:我们应该确保我们的堆栈操作尽可能的快;我们的堆栈模板不是特别的快.在字符串操作上也一样.一般而言,我们应该使通用的case快.最好把所有普通的优化技术应用到VM上.

关于VM还有很多要说:存储分配(allocation schemes),垃圾收集(garbage collection),保持他们稳定和高速,但是我想我将推延到下一部分.
 

下一次

下一次我们将最终执行代码.然后我们就完成了我们的简单的脚本引擎.之后我可能给出一个复杂的真实的脚本引擎的概貌,并且讨论所需的主题.


Quote! 

"Come," called the old man, "come now or you will be late."

"Late?" said Arthur. "What for?"

"What is your name, human?"

"Dent. Arthur Dent," said Arthur.

"Late, as in the late Dentarthurdent," said the old man, sternly. "It's a sort of threat you see." Another wistful look came into his tired old eyes. "I've never been very good at them myself, but I'm told they can be very effective."

HHG 1:22


Downloads

Download the tutorial code (tut7.zip) (5k)


Part VIII:可执行代码

序言

我们有了执行我们的程序的所有需要的东西,除了...可执行代码.我们已经有了中间代码,并且它已经非常接近我们的虚拟机能理解的东西了.所以我们必须作的是一个中间代码和可执行代码之间的快速的翻译步骤.

为什么这需要是一个分离的步骤?就象你看到的,翻译实际上涉及到把我们的字符串放到一个数组中,并且为符号表提供他们的索引而不是指针.我们上次已经做了跳转目的,所以他们将不再改变.所以这是一个简短的部分,代码改变不大.

也许对于我们,建立中间代码不是严格的需要.但是写一个更高级的编译器时,有这样一个分离是非常有用的,在实际的机器码之前更多的'概念上的'阶段:它简化代码优化;你可以不困难的重新定义你的编译器到另一个机器.


最后一步

当你阅读这部分的代码时,你将在几个地方看到到我的懒惰,它使我写了真正罪恶的代码.

举个例,我把编译器和虚拟机组合到了一个程序中,并且我传送"中间代码"给虚拟机,这不是很恰当的方法.你也许想要你的编译器来处理每件事直到可执行代码产生,然后也许存储可执行代码到一个文件,然后让你的VM读取&执行这个文件.

在我们这里,VM中的Read()函数首先从我们的符号表中取得所有的字符串,然后把他们放入字符串数组.然后它线性的通览代码,并且一行接一行的翻译它们.我们所使用的特殊的跳转目的指令只被转换成NOP指令,它应该被优化掉.

Oh,我做得一个显著的可恶的事是我用来自编译器的符号表来存储虚拟机的字符串表索引(使用符号表的新成员PutNo()/GetNo())...它是非常简单的找到字符索引的方法,但是我同意模块化的程序设计是全然不同的...


它工作了!我简直不能相信!

嗨,你真的可以使用这个编译器/虚拟机的结合体来执行一个程序!你大概几乎放弃了它,不是吗?好吧,继续尝试例子.这部分有源码可以下载...他们应该正确执行.这很有趣吧.

好的,那就是我们曾经为之工作的东西.一个小小的语言,尽管它自身不是很有用,但是它表现了很酷的东西--你现在学习了建立你自己的脚本引擎的足够的东西.
 

现在发生了什么?

经过了这样一个难以置信的极限(啊咳)我相信你有一点感觉空虚和不知所措.我们将从这里去到哪里?

我将可能作一个或更多的part介绍一些高级的主题,也许谈到为这个语言增加函数,类,多态,等等.让我知道你对什么感兴趣.

尽管将不再有代码--每个人都可以取得这个简单的编译器并且扩充它.或者,更好,写一个你自己的.The world's your oyster!
 

Quote!

"More importantly, a towel has immense psychological value. For some reason, if a strag (strag: non-hitch hiker) discovers that a hitch hiker has his towel with him, he will automatically assume that he is also in possession of a toothbrush, face flannel, soap, tin of biscuits, flask, compass, map, ball of string, gnat spray, wet weather gear, space suit etc., etc. Furthermore, the strag will then happily lend the hitch hiker any of these or a dozen other items that the hitch hiker might accidentally have "lost". What the strag will think is that any man who can hitch the length and breadth of the galaxy, rough it, slum it, struggle against terrible odds, win through, and still knows where his towel is is clearly a man to be reckoned with."

HHG 1:3
 

Downloads

Download the tutorial code (tut8.zip) (15k)


Part IX:高级主题

序言

现在你已经玩了一下那个完成的脚本例子,也许你实现了一些新特性,或许当我们将要接触新东西时你在疑惑.

请允许我提醒您,这些好东西里的绝大部分都需要大量的工作(这些我将不再提供例子代码).我将讨论几个高级的脚本主题,给出如何实现(我的想法)的一般想法.

第一个:


A lockup-resistent VM(不会翻,晕倒....)

前一段时间Joseph Hall给了我一个处理无限循环(infinite-looping)的脚本代码的很好的想法.他的思想是:每次调用虚拟机时给他最大数量的操作码去执行,并且如果下一帧它还没有完成时让它继续执行;这是虚拟的等价与CPU优先级多任务.这种方法使你的游戏引擎在脚本代码挂起时可以保持运行;它可以自动检测脚本是一个不变的循环并且重起VM.

现在,让我们看看我们可以怎么样扩展我们的语言:


函数

在你的脚本语言中增加函数是非常困难的,它引入了参数和局部变量的概念.为了他们需要使用堆栈.在一个函数调用前程序把参数入栈.然后函数在同一堆栈中预留空间给它的局部变量.然后执行函数,使用预留的堆栈空间来读写值.在我们的简单的编译器中,我们仅仅从栈顶进栈和退栈,但是现在你也可以访问堆栈中间的内存地址.

你需要为函数使用两个特殊的操作码:CALL和RETURN.CALL是一个无条件的跳转,它吧指令指针保存到堆栈中.RETURN读取那个被存储的指令指针,然后跳回CALL后面的指令.

要做的一件最符合逻辑的事是让调用者(不是该函数)把参数从堆栈中移走参数;毕竟最初是调用者把他们放进来的.这也考虑到一个"输出参数(output parameters)"的简单机制:函数改变一个参数的然后调用者把这个值存入一个变量.一个函数的返回值也可以看作是一个输出参数.

函数的信息头可以存储到一个符号表中.使用他们,你可以存储它的参数和局部变量(可以每个是一个分离的符号表实体).在代码生成的过程中,你可以在符号表中存储函数的起始地址.

重载(Overloading)
函数的重载可以是一个语言中非常好的特性,但是实现它可能很棘手的.问题是如何通过提供的参数类型来正确的从可能的函数头信息中找到一个恰好匹配的函数来调用.在这种情况下,你将不得不强制某些参数到不同的类型来得到一个完全的匹配.问题是什么参数需要强制转换和把它们转换到什么类型.大多数编译器试着比较调用和可能的选择,然后选择一个需要最少强制转换的.一些编译器允许双重强制转换(例如:bool->int,然后int->unsigned),这使麻烦更复杂,我建议保持简单.

操作符可能看作是一个用不同语法调用的函数;如果用这种方法来处理你的操作符(不要真把它们作成函数(慢),而是inline函数或者宏),你可以轻松的扩展函数重载到操作符重载.
 

类

如果你想要在你的语言中实现类,正确的决定你想要支持那些特性.支持完整的C++类,包括多继承,访问控制,动态束定,虚函数,等等是非常困难的,我建议不要在一开始就处理所有这些.一个带有单继承的简单的类系统是一个很好的起点,如果需要的话你以后可以扩展它.

类和结构体是符合数据类型:他们包含多个数据成员,并且连接到一定数量的方法或者成员函数.你可以在你的符号表中存储一个成员列表,它与其他分离的成员符号表实体相连接.这可以使你简单的找到结构中某个成员的偏移量.

继承
单继承相对的简单:当你在一个对象中查找一个成员时,检查这个成员是否在子类中;如果不是就检查它的父类.子类的存储布局很简单:首先你存储父类,然后是他的子类,其他子类,等等.这样向下的束定被隐藏:你可以处理向处理一个Animal的指针一样处理一个Cat的指针,这个的意思是你的程序可以访问更少的成员,但是指针的地址不需要改变.

多继承,当调用一个成员函数或者访问一个数据成员时,它带来了二义性问题.思考这个:两个类B和C是统一个类--类A的子类.然后建立一个类D源于类B和类C这两个类.现在,如果类A有一个公有成员函数DoSomething,当成员在一个D类型的对象中调用DoSomething时,你不能知道调用两个DoSomething中的哪个:一个是B的A部分,另一个是C的A部分..好吧,也许看图可以更清楚.



 

虚函数
虚函数是建立多态的一个方法;例如一个Animal类包含一个虚函数MakeSound(),一个子类Cat和Dog都各自用不同的方法实现一个这个函数(我想让你考虑如何正确的实现他们).于是当你调用一个Animal对象的MakeSound函数时,你不知道(并且不需要知道)是那种动物在发出声音.

虚函数函数使用一个所谓的vtable来实现.当父类声明一个函数为virtual时,它在那个类中增加了vtalbe.每个子类现在取得他们自己版本的vtable,这样,不同的函数调用基于那个对象实际的类型,尽管在调用者看来这些table之间并没有区别.

动态束定
动态束定可以很便利:例如,在UnrealScript中你不仅仅可以向下束定一个对象(把它束定到它的父类型),而且可以向上束定(束定一个对象到它的子类),如果这个对象的确是子类的对象.这意味着你需要一个方法来决定一个Parent类型的对象实际上是向下束定的一个Child1对象(在这种情况它可以被向上束定),或者是一个Child2对象(在这种情况它不可以被向上束定).在最新的C++编译器中你可以使用dynamic_cast<...>操作符.怎么觉得这个呢?每个对象都将必须有一个独一无二的号码,也许是一个类的表和他们的父类的索引.使用这个号码,你可以断定它到底是那种对象.

类型变量(Type variables)
类型变量允许类型的变量.这允许你动态建立一个变量类型的对象.举个例子,你有一个游戏,一个敌人走了进来,两个同样的敌人走了出去.你可能会看到一个包含所有可能的敌人的巨大的switch语句,但是这不是很好扩展.所以你可以存储敌人的类型,告诉游戏使用这个类型建立一个怪物.这是一些假想的语言代码:

TypeVar<Enemy> enemytype; // A type variable
enemytype = typeof (monster); // Get the monster's type
Enemy *newmonster = new enemytype; // Create a new monster of the same type

你可以传递类型变量到一个函数;这将使得他们很有可塑性,你可以使用同一个函数来建立和处理很多不同类型的对象.

为了类型变量,你需要扩充类和他们的父类的表来包含每个类型的大小;否则你将没法动态建立他们.


Game-specific language constructs

UnrealScript(据我所知)是第一个提出了两个在游戏中非常有用的特性的语言:状态和隐藏代码.

状态
UnrealScript中的类可以有几种状态;一个对象总是在一个确定的状态.基于对象处在那个状态,为这个对象执行不同的函数.所以如果这个对象是一个敌人并且它处在Angry的状态,Angry版本的SeePlayer函数将被执行,这个敌人将可是攻击玩家.如果这个敌人处在一个Frightened的状态,另一个SeePlayer函数(使用同样的参数类型)将被调用,使得敌人逃跑.

状态并不是非常难加入,尽管它的确需要一些工作;状态是一个额外的类成员(不可见),并且每当调用特定的状态函数时恰当的函数版本将被执行.这可以使用一个使用状态号码为索引的跳转表来轻松实现.

状态可以有它们自己的函数外的代码,在UnrealScript中是状态代码.这可以方便的与下一个构思相结合:隐藏的函数.

隐藏的函数(latent code)
隐藏的函数相当的难实现,但是非常的酷:一个隐藏的函数花费一些游戏时间来执行;换句话说,这个过程可以起动一个函数等待或者激活那个等待或者激活一个人物,当这个动画完成后代码继续执行.这是一个AI脚本很好的特性.

隐藏代码带来的另一个问题是本质上它与其他代码并行执行.偶尔隐藏代码被执行,然后它又被停止.所以我们必须记住隐藏代码的指令指针.并且当对象改变它的状态时,你将也需要执行其他的隐藏代码.

我们可以看到UnrealScript唯一提供隐藏代码的原因是为了调用状态代码,而不是普通函数:假设隐藏函数可以在任何地方被调用,每个对象本质上可以有很多的并行执行的"线程"..这可能需要大量的记录并且将变慢.而且也将产生同步问题:一个对象的线程将把一个成员变量设为某个特定的值,然后一个其他的线程变为活动后再次修改它...如果你想允许它将需要实现一个完整的多线程系统.
 

That's it for now.. 

我希望这可以激发你的想象力.有许多特性你的脚本语言可以实现;如果你想完成它你将限制自己为某一个.

这可能是这个系列教程的最后以部分.我乐于写它.如果你觉得在一些地方还不够,让我知道,也许我将写一个额外的部分.当然,如果你有其他的一些问题我也乐于听你说.

Good luck, and keep on scripting! ;-)


Quote! 
"He stared at it for some time as things began slowly to reassemble themselves in his mind. He wondered what he should do, but he only wondered it idly. Around him people were beginning to rush and shout a lot, but it was suddenly very clear to him that there was nothing to be done, not now or ever. Through the new strangeness of noise and light he could just make out the shape of Ford Prefect sitting back and laughing wildly.

A tremendous feeling of peace came over him. He knew that at last, for once and for ever, it was now all, finally, over."

HHG 5:25