转实现一个脚本引擎.doc

转 实现一个脚本引擎译者序由于我最近有一个计划,就是写一个适应性很强的脚本语言,这个语言将主要用来处理剧情,希望能够用于绝大多数需要剧情的游戏.于是最近开始找一些关于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.Thats the display department.With atorch.Ah,well the lights had probably gone.So had the stairs.But look,you found the notice didnt you?Yes,said Arthur,yes Idid.It was on display in the bottom of alocked filing cabinet stuck in adisused lavatory with asign on the door saying Beware of the Leopard.HHG 1：1 Part II：词法分析器序言我总是说在学一个东西的时候例子总是不能足够简单.这就是为什么当我想要设计一个包含所有完整编译器应该有的特性的简单的编译器时感到很累.我拼凑了一个字符串处理语言,它使用象C那样的语法,有BASIC那样的功能.下面是用我们的语言的正确编写的一个程序.printPlease enter your name；input name；if(name=Jan)/string comparison name=my creator；/string assignment happy=yes；printThank you,+name+！n+/string concatenationYouve just made asimple program very happy！；就象你看到的,他没有构造象函数,类等等那样的功能,它甚至没有数值类型.这就是最终的东西,但是,他是很容易扩展的.但是在接触那个之前我们还一很长的路要走-记得上次的组件列表吗?今天我们将实现第一个：词法分析器或称短语分析器.这是一个很好的热身,因为它不是编译器中真正难的部分.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)ifreturn IF；=return ASSIGN；return END_STMT；IDENTIdentifier()；/*identifier：copy name*/return ID；STRStringConstant()；/*string constant：copy contents*/return STRING；/EatComment()；/*comment：skip*/nlineno+；/*newline：count lines*/WSPACE/*whitespace：(do nothing)*/.return ERROR_TOKEN；/*other char：error,illegal token*/我删去了一些非常简单的规则.就象你看到的那样,每一条规则开始部分是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 ageneration died of obesity and heart failure and the science of maths was put back by years.HHG 2：7燕良的附注：词法分析的手工设计举例程序的功能是把下面这些实常数转换成相应的科学计数表示：Pi转换成0.314159265359 E1E转换成0.271828182846 E1Degree转换成0.174532 E-1一般的实常数按值转换,例如456=0.3456 e4,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附送另一个程序,识别C语言源程序的LEX源程序./*燕良编写*2000年1月*拿出这个程序来主要是因为原文中只有一个LEX程序,*不便与比较阅读.*/digit0-9letterA-Za-zother_char！-id(letter|_)(letter|digit|_)*string(letter|digit|other_char)+int_numdigit+%|t|n+auto|double|int|struct|break|else|long|switch|case|enum|register|typedef|char|extern|return|union|const|float|short|unsigned|continue|for|signed|void|default|goto|sizeof|do|if|static|while|mainUpper(yytext,yyleng)；printf(%s,NULLn,yytext)；(！-)*printf(CONST_string,%sn,yytext)；-?int__num?(E+|-?int_num)?printf(CONST_real,%sn,yytext)；0x?int_numprintf(CONST_int,%sn,yytext)；,|；|(|)|-|.|！|+|-|*|&|sizeof|/|%|+|-|=|=|=|！=|&|&|+=|-=|*=|/=|%=|=|=|&=|=|=|=printf(%s,NULLn,yytext)；idprintf(ID,%sn,yytext)；digit(letter)+printf(error1：%sn,yytext)；%#include ctype.h Upper(char*s,int l)int i；for(i=0；i l；i+)si=toupper(si)；yywrap()return 1；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；根据上述推导可以画出语法树,对于无二义性的文法,所有的推导画出的语法树都是一样的.)printHello；input name；Not legal is：inputHello；通过我们的定义,input语句(燕良注：指产生式statement：INPUT identifier END_STMT；)只能作用于一个标识符,而不能是字符串常量.我们可以使用BNF范式正规的描述我们的语言的整个语法.注意这些现在还不包含语义,于是这条语句：a=(b=c)；纵使它没有意义它也将被语法分析器接受(我们正在试图把一个布尔值赋给一个字符串变量).语义将在下一阶段作检查.太好了,我们现在知道的语言描述法足够来建立我们语法分析器.看上去很熟悉！语法分析器也可以用一个外部程序来产生.这个叫作Yacc(一个标准的UNIX工具,就像是LEX)；我们将使用一个叫作Bison的改良版(get it?).Bison的手册有又可以在这里(找到.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 CD|D EF冲突产生在当你从输入文件中读了一个B,而预读符号是C时,因为他们可以被组合(这两种产生式最终都将产生一个文法符号)；问题是第2个产生式以D为结尾,而且第3个以它我起始：当语法分析器读取到了C,而且预读的是D时,它不能决定是否归类为A2或A1后面跟着一个A3(燕良注：请注意我们只预读一个文法符号)！尽管这个完整的文法定义可能根本就没有二义性,但是对于语法分析器它却是有的,因为语法分析器只能预读一个文法符号.Yacc把这种不确定性称为移进/归约冲突或归约/归约冲突.呵呵,别让这些吓着你.看一下这些规则.最重要的一条可能就是这条语句规则了：statement：END_STMTputs(Empty statement)；|expression END_STMTputs(Expression statement)；|PRINT expression END_STMTputs(Print statement)；|INPUT identifier END_STMTputs(Input statement)；|if_statementputs(If statement)；|compound_statementputs(Compound statement)；|error END_STMTputs(Error statement)；你能看到,这里定义了我们的语言所有的语句类型,后面的代码是告诉语法分析器当发现了每个产生式时应该作什么.我认为这条规则是十分漂亮的.有一件事：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 1conflict).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 Streetmentioners Time Travellers 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 atime in the further future,or atime 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,)；它的意思是：如果你发现了一个expression语句,构造一个EXPR_STMT类型的新的树结点(并且返回新的结点指针),他带有一个孩子：组成这个语句的表达式.$代表一个规则的返回值,是规则定义中的第一个符号返回的值(expression).在这里没有意义,因为词法分析器没有为END_STMT记号设置一个yylval成员.我希望这样的解释够清楚了,因为这很重要.本质上,规则是分层的,每一条规则能够返回一个值到更高层的规则.现在让我们看一下符号表和语法树使用什么样的数据结构.符号表符号表在我们例子中至包含很少的信息；基本上它只是变量名和它第一次被声明的行.后面我们会使用它来存储更多的数据.实现非常的简单：它只是当我们取回一个符号时(看一眼symtab.cpp)为符号的描述建立一个单链表(singly-linked list)并且线性的查找这个链表.对于一个真正的编译器,符号表通常被实现为一个binary search tree或hash table,以便能够更快的找到符号.你要作的是当语法分析器发现这个时把我们的符号送入那个表：identifier：ID$=st.Find()；if($=NULL)/doesnt exist yet；create it$=new SymDesc(,STR_VAR,NULL,lineno)；st.Add($)；我们把字符串常量处理成常量,我们为他们生成一个名字然后把他们送入那个表.注意：一个更高级些的编译器可能会让词法分析器来存储和取回标识符.这是因为复杂的语言中标识符可能有很多不同的含义：变量,函数,类型,等等.词法分析器可以取回标识符的描述,并直接把相应的记号返回给语法分析器.因为我们标识符肯定是变量,所以我们只使用语法分析器来处理他们.语法树我为语法树建立了一个非常简单的TreeNode类.它只存储指向孩子的指针和一些附加信息(结点类型,如果可用还有一个符号的连接).看看吧,这没什么复杂的.象你前面看到的,我们可以从已经验证的语法规则轻松的建立语法树：equal_expression：expression EQUAL assign_expression$=newTreeNode(EQUAL_EXPR,)；|assign_expression$=；你会看到在某些时候我们只是无变化的从孩子规则到父规则传递信息；如果你的equal_expression事实上就是一个assign_expression,就没有必要为它建立一个新的结点；你只使用在assign_expression中建立的那个.记住我们使用这么多表达式规则的唯一的原因是为了清楚的处理操作符的优先级.编译这部分(和下面的部分)使用与前面相同的方法.程序还是接受语法结构上正确的程序,但是现在转储到它建立的符号表和语法树中.这真的很cool,但是.OK,它读程序并且分析它.但是它没有对程序作任何真正聪明或有用的事,不是吗?是的,依然是.我们还有更多的组件要实现.下一部分将涉及语义检查和中间代码的生成.这将是一条通向编译程序的漫漫长路.我希望你不要认为它进展的太慢,我只是想要集中到每一个分立的组件,而不是走马观花.如果你很快理解了这些东西,实验一下他们吧.下次再见.Quote！(Part of the Guide entry on the Babel Fish)Now it is such abizarrely 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 Iexist,says God,for proof denies faith,and without faith Iam nothing.But,says Man,The Babel fish is adead giveaway,isnt it?It could not have evolved by chance.It proves you exist,and so therefore,by your own arguments,you dont.QED.HHG 1：6 Downloads Download the tutorial code(tut4.zip)(8k)Part V：语义检查&中间代码生成序言这次晚了一点.考试真是件可怕的事,它真的妨碍了一些有用的东西.是的,上次我承诺了结果,你想要得到它们.也许多过你的希望；-)首先是关于这个教程的一个备注.我是想要写一个非常紧凑的解释.所有的信息都在这里,但是常常是每个句子有两个重要的事情.这样作的缺点是是否有些事不大清楚,你可能没有跟上这个教程.当我进行的太快时请告诉我,好让我能够把事情说清楚.回到这部分.它是关于语义和中间代码的.语义检查将确认你的程序是真正的正确,中间代码将是向虚拟执行(virtual executable)的一个巨大飞跃.让我们开始检查吧！检查语法语义检查不单单是检查程序语法的正确性,它还要确认语句有意义.例如,提供给函数的参数的个数应该是函数所预期的.语义检查的主要部分是类型检查：决定表达式的类型和报告任何的不一致,如想要比较一个布尔值和一个字符串,或者传给函数错误的参数.当然,也许你想要允许某些不一致：例如有人使用了下面的语句printa and bequal：+(a=b)；他的意思可能是表达式(a=b)应该被自动转换成一个字符串,最后成为字符串true或false.这称为强制类型转换.在我们这个简单的编译器中我只允许布尔到字符串的强制转换,但是如果你认为字符串到布尔的强制转换有用,你可以轻松的加上它.我们的语义检查器的代码并不复杂.我为TreeNode加了一个名为Check()的成员函数(在synttree.cpp文件中),它检查一个结点的语义,我们假定它的所有孩子结点都已经被检查了.Chech()在TreeNode的构造函数中自动调用,所以这个假定是安全的.检查设置了一个名为rettype的新成员变量,表达式的返回类型.例如,一个条件,当一个字符串连接另一个字符串时,布尔是它的返回类型.rettype用来检查父结点的语义.CoerceToString函数通过插入一个作为被强制转换的结点的父结点的新结点,COERCE_TO_STR,来强制转换任何的表达式为字符串类型(如果它还不是).对一个简单的编译器这是很轻松,但是通常它不是这样.如果你的语言包含更多的基本类型,索引(references),数组,类和(操作符)重载,事情很快就变得非常的可怕；如果你希望你的程序能够运行,那么你最好有一个坚实的检查系统.在一个真正的编译器中它从事更多的工作：有更多的强制转换,你必须计算出要使用哪个重载函数,类型等价不是再是这么平常,等等.在这儿它是很简单,并且它对于用更多的类型来膨胀这