自己写的CC++编译器Doctors[软件+文档]

    技术2022-05-11  4

    自己写的C/C++编译器Doctors[软件+文档]

     

    http://blog.csdn.net/huyansoft/archive/2009/08/20/4464772.aspx

     

    更新版本1.0.1:该版本解决了之前1.0.0版本中找不到链接库libc.lib的问题,以及IDE下点击Project菜单出现的BUG。下载地址:http://download.csdn.net/source/1597132

     

    Doctors编译器内部实现

    For version 1.0.1

    出处:http://blog.csdn.net/huyansoft

    作者:胡彦

    Copyright(c) 2009,All Rights Reserved

     

    简介:

    Doctors是标准C++语言子集的编译器,它可以将C++源程序编译链接成Win32平台上可执行的EXE文件。代码采用OOP语言完全手写而成,提供了IDE界面和命令行二种使用方式,其设计初衷是为程序提供更多的诊断功能。

     

    本文通过其部分源码,介绍了其设计方法、实现思路、和作者的一些体会。

    本文档可作为编译课程的课外读物,读者可从中了解一个实际编译器的内部构造,补充教材上缺乏的实践知识,加深对抽象理论的理解。对实现类似编译器、解释器的读者也具有直接的参考价值。

     

    ----------------------------------------------------------------------------------------------------------------------

     

    目录

    第一节 初衷和目标

           一 排错工具

           二 多线程

           三 Unicode

     

    第二节 开发方法

           一 为什么不用Yacc和Lex

           (一)Yacc的缺点

                  1库

                  2编程方法和多线程

                  3错误诊断

                  4二义性和错误恢复

           (二)Lex的缺点

                  1状态冗余

                  2紧耦合

                  3行号

                  4效率

           (三)小结

           二 OOP的优缺点

           (一)算法由数据结构表达

           (二)核心多态

           (三)编码反馈出设计的优劣

     

    第三节 整体结构和流程

           一 整体结构

           二 整体流程

           三 编译流程

     

    第四节 词法分析器

           一 记号

           (一)记号的类别

           (二)支持的C++记号

           二 词法分析过程

     

    第五节 数据类型

           一 基本类型

           二 数组类型

     

    第六节 符号表

           一 前端符号表

           (一)构造与析构

           (二)前端符号表的作用

                  1查找名字的定义

                  2存储预分配

           二 后端符号表

           (一)常量表

           (二)变量表

                  1全局变量

                  2静态变量

                  3外部变量

           (三)字符串表

     

    第七节 语法分析器

           一 支持的语法

           二 调整文法

           (一)从产生式到BNF

           (二)消除二义性

           三 抽象语法树的设计

           (一)函数的AST结点

           (二)语句的AST结点

           (三)表达式的AST结点

           四 语法分析过程

           五 语义分析

           六 错误恢复

           (一)错误的应对

                  1词法错误

                  2语义错误

                  3语法错误

           (二)错误恢复机制

                  1继续分析下去

                  (1)假设、虚构

                  (2)忽略、推迟

                  (3)跳跃

                  (4)调整文法

                  2防止误报

     

    第八节 中间代码的设计

           一 中间代码的结构

           二 中间代码具体格式

           (一)赋值

                  1一元赋值

                  2二元赋值

                  3函数调用

                  4数组元素访问

           (二)标号

           (三)跳转

                  1无条件跳转

                  2条件跳转

                  (1)布尔跳转

                  (2)关系跳转

     

    附录:参考资料

     

    ----------------------------------------------------------------------------------------------------------------------

     

    第一节 初衷和目标

    一 排错工具

    在写程序时,你是否犯过下面的错误?

    1

    for(int i=0; i<10; ++i);

    {

      cout<<i<<endl;

    }

    打算输出10个数,可怎么调试循环体都只能执行一次,输出0!是编译器坏了?调试器坏了?累到半死才发现,是增删代码过程中,第一行尾不小心残留了分号,导致循环体为空。

     

    2

    #include "header.h"

    const int MAX_LEN=256;

    准备定义常量MAX_LEN,可是编译器总是报错“missing ';' before 'constant'”,改成“int MAX_LEN;”还是一样,被折腾得要崩溃才发现,原来header.h中有这么一句:#define MAX_LEN 256

     

    3一个复杂表达式中括号不匹配时,编译器会提示“括号不配对”,可这么多的括号,究竟是哪个不匹配呢?要费神去找,类似{}也一样。

     

    这些BUG占用了不少调试时间,可这些低级错误总是一犯再犯,即使熟练者也不例外。因此,一个好用的编译器不仅要报告语法错误,还要能发现程序中潜在的逻辑错误,并且错误信息尽可能准确,对出错位置不但要精确到行,还要精确到列,如果出错的记号是由宏扩展而来,还要提示宏定义的位置。

     

    上面都是设计Doctors的初衷,我期望它成为一个有用的程序排错工具(尽管现在离这个目标还差很远)。

    为了做到这一点,首先要能支持ISO C++大部分语法(很宏伟很遥远的理想)。再次,仅仅完成语义检查是不够的,还要生成中间代码,在中间代码优化过程中执行数据流分析和控制流分析,可以找出更深层的错误,比如VC报告函数“not all control paths return a value”就要控制流分析,并提前发现一些运行时错误,如通过常量折叠和复制传播能发现引用空指针、除数为0的错误。

    要是仅实现诊断功能,完成了优化也就可以了,之所以还有目标代码生成,是想做一次尝试,实现了汇编生成、调用完汇编器、链接器生成可执行文件后,才能知道编译器到底是怎么运作的。此外,前端符号表的设计要考虑后端如何使用,只能掌握汇编语言才能明白运行时存储分配,才能真正理解高级语言机制。

     

    除此之外,我还想实现其它一些想法:

    二 多线程

    现今大部分机器已经是多核CPU了,如果程序能多线程并行地编译多个源文件,就可以放手去做那些耗时的优化和错误分析(越朝将来好处越明显)。还有,编译器中一些函数可能实时被其它模块调用(如IDE也需要识别注释和字符串),总不成一被调用就并发错误吧!

    不知你是否注意到,双核CPU已经有些年头了,可主流编译器仍然是串行编译各个源文件的,为什么呢?因为要实现多线程,首先要消除代码中的全局变量(总不能一个全局变量加一个互斥锁吧),而主流编译器经过这么多年的发展,规模已经相当宠大了,即使是代码原作者要重构掉这些全局变量,也是一件麻烦的事情。

    因此,从一开始就要杜绝全局变量。经过努力,这个版本已经做到了,所有程序没有使用一个全局变量和静态变量(具体做法可参见后续章节)。

    此外,编程语言的运行库要支持多线程。不幸的是,我用的VC2005下C++ I/O流库虽然支持多线程(运行不出错),可速度却慢到无法接受的地步,要解决只有采取其它变通方法,因此,这一想法暂时被搁置。

     

    三 Unicode

    扫描器中难免会用到如isdigit之类的函数,如果不支持Unicode,一旦源程序出现汉字等全角字符,这些函数就会断言失败,反之在Unicode下就没事。还有一次,我的机器由于软件冲突,所有窗口的文字都变成了乱码,只能金山词霸巍然不动,这给我留下了深刻印象。因此,程序全部用Unicode书写了,包括main函数都是宽字符版的。

     

    ----------------------------------------------------------------------------------------------------------------------

     

    第二节 开发方法

    词法分析、语法分析、代码生成等所有模块都是手写的,未使用生成器工具,分析器采用递归下降方法。

    源程序采用标准C++、STL编写,采用OOP风格,仅驱动程序中有少量平台相关的代码,它们被放在单独的源文件中。

     

    一 为什么不用Yacc和Lex

    在讨论它们的缺点之前,让我们先来回顾一下它们的优点:

    1当用户学过编译原理后,便已经掌握正规式和上下文无关文法了,对Yacc和Lex语言也有了解,只要上机调试,学会搭建Yacc和Lex的工作环境,便可以用它们来写扫描器和分析器了。

     

    2在Yacc程序中,产生式与处理过程(语义动作)一一对应,可以将标准C/C++的文法照搬过来稍微调整。若以后语法变了,修改对应产生式的工作量也小。同样,在Lex中,书写和修改正规式比手工打造识别代码要轻松得多。

     

    3采用LR方法时,Yacc事先将语法分析表算好,分析时查表匹配输入串,运行效率高(Lex的DFA状态转换也类似)。

     

    4Yacc支持的文法类型更多(不仅LALR),适应实现不同特征的目标语言。

    总之,Yacc/Lex工具封装了实现扫描器、分析器的常用框架,用它们构造编译器难度低、效率高、易维护。

     

    但为什么不用它们呢?

     

    (一)Yacc的缺点

    1库

    如果我们的程序是用Yacc写的,编译时必须与Yacc库相链接才能运行。虽然大部分Yacc实现都提供了源代码,但在向其它平台移植时总会遇到麻烦。由于程序必须依赖于第三方库(就像走到哪里都得拄拐棍一样),带来沉重的包袱。

     

    2编程方法和多线程

    Yacc/Lex诞生于上世纪70年代,由于历史的局限性,Yacc/Lex程序中必须大量使用全局变量,比如在Lex中,获取匹配的文本要用yytext,传递记号给Yacc用yylval,读写串用yyin/yyout,状态切换用yystart…虽然有些Yacc实现能够生成面向对象和多线程的代码,但那样我们就得舍弃移植性去接受它的“方言”。

     

    3错误诊断

    递归下降分析可以提供准确丰富的诊断信息。比如当一个声明语句错误时,我们可以明确指出是局部变量声明错误,还是函数形参声明错误,只要对应的解析函数多加一个参数就行了。

    可是在Yacc归约到声明语句时,当前语义动作并不知道自己是在一个局部块中,还是在函数声明中,要想知道,只有事先在上层语义动作把属性存进全局变量,在下层语义动作中读取它。

    另一个例子,假若我们用Yacc实现C/C++中的条件编译指令#if…#endif,由于#if…#endif是可以嵌套的,当进入内层#if…#endif时,必须知道外层是否处在编译状态(外层被忽略了内层自然也要忽略),因此必须将属性层层向下传递…

    也就是说在Yacc中,即使采用了LR分析方法,也要借助许多自顶向下技术来弥补它的缺陷(也不能全怪Yacc,幕后黑手是LR)。

     

    4二义性和错误恢复

    Yacc中产生式一旦冲突往往让人不知所措,如果屡次尝试失败,只能在纸上演算LALR的项目集,才能找到冲突的原因,这使得初学者望而生畏。

    又例如,对C++语句int (x); 它既可能是对x的声明语句,也可能是对x强制转换的语句,标准C++规定在这种情况下视为声明,如果用Yacc去解析这一句就会遇到麻烦。

    虽然Yacc的错误恢复是一个妙招(出错时跳至预定记号,并自动匹配非终结符error),可对error的使用不是随心所欲的,写不好就会冲突或报错。

     

    Yacc的这些特征,Lex一样也不少,此外Lex还有自己独到的缺点。

     

    (二)Lex的缺点

    C/C++的词法分析和预处理过程,逻辑上至少分成下面几遍(虽然大部分实现不会真的扫描这么多遍):

    第1遍,字符集转换(例如三联符)

    第2遍,断行续接

    第3遍,识别并处理注释

    第4遍,执行预处理指令(文件包含、条件编译、宏替换)

    第5遍,转义字符替换

    第6遍,相邻字符串拼接

    第7遍,将每个预处理记号转换为词法记号

    在顺序执行了上面逻辑遍后,才能正确识别出一个词法上的记号。

     

    如果我们用Lex去实现,想一两遍完成是不可能了(算法极为繁杂),只有多遍处理,每遍添加一个Lex状态。开始扫描时用BEGIN切换到第一遍状态,处理结果存在文件或字符串中,一遍完了在yywrap()函数中修改yyin为刚才处理结果,再用BEGIN切换到下一遍状态…问题也随之而来:

     

    1状态冗余

    在每一遍过程中又要增加许多状态(比如进入单行还是多行注释)。除前2遍外,每遍都要识别和处理源程序中的字符串(比如一段注释若出现在字符串中就不是注释),但由于每一遍着眼点不同,这些状态的正规式和语义动作是难以复用的(比如第4遍以前识别字符串时,要排除#include”…”的头文件名,而后续状态则不用),结果每遍都要增加类似的状态和正规式,造成了大量冗余(Lex输出的文件中状态数目会相当多)。

     

    2紧耦合

    每组紧密协作的正规式间都是牵一发而动全身的,如果我们无意间修改了一个正规式(哪怕只是一个空白符),就会牵连其它正规式、产生意想不到的匹配结果。

     

    3行号

    当删除一段多行注释、或在断行续接时,其中的换行符同时也要删去,后续遍再统计行号就会错误,只有采用插入特殊字符、修改底层yygetchar函数这种不优雅的方式去解决。

     

    4效率

    前一遍识别了某个记号,只能存放在字符串或文件中,下一遍又得从输入串中逐字符读取、重新装配这个记号,可谓事倍工半。我们也可以将识别出的记号放在一个list中,下一遍直接遍历list,需要时yyunput一下让Lex去匹配,但这样实际上已经半抛弃Lex了。

     

    总之,Lex强迫用户面向字符流工作(而不是记号流),这对于像C/C++逻辑上要多遍扫描的词法分析器而言,并不合适。

     

    (三)小结

    Yacc/Lex为用户编写分析器和扫描器提供了便利的框架,如果用它们写计算器或其它小规模的程序,还是非常便利的。但Yacc/Lex的框架同时也束缚了用户的手脚,如果选择了它们,我们的程序就像小盒子里的爬虫只能做有限的翻滚动作。对实现编译器而言,从长远看还是手写更合适。

     

    二 OOP的优缺点

    OOP的若干好处就不重复了,这里只列举它对编译器的优点:

    (一)算法由数据结构表达

    例如,生成中间代码实际上要遍历整个抽象语法树,在面向过程中我们可能会这样写:

    void Gen(AstNode* pNode)//为AST结点pNode生成中间代码

    {

           if(pNode有子树1)

                  Gen(pNode->子树1);//为子树1生成中间代码

           if(pNode有子树2)

                  Gen(pNode->子树2);//为子树2生成中间代码

           …

    }

    即我们要显式递归调用Gen(可能还要根据pNode的类型强制转换成对应的AST结点,再调用相应的Gen函数)。在OOP中就不用这样了:

    void AstNode::Gen()//为AST结点pNode生成中间代码

    {

           子树1.Gen();//为子树1生成中间代码

           子树2.Gen();//为子树2生成中间代码

           …

    }

    我们没有任何递归调用,只是顺序为各个子树生成代码,但实际上它却实现了遍历操作,因为算法已经由类的数据结构静态确定下来了。

     

    (二)核心多态

    上段程序中的Gen()一定是多态的,比如同样是语句,if与for代码生成方式不同,就会对应不同的Gen函数。

    比较上面2段程序可以看出,多态函数的表述更自然,不需用晦涩的函数指针和强制转换。如果一个模块的主要函数不是多态的,那么这段程序就不能称之为OOP。

    在Doctors中,AST和IR被设计为类的树型继承结构,中间代码、目标代码的生成全部是多态的。也许你会怀疑这是否导致性能的下降?不用担心,C++的设计者早就意识到这一点,在C++中查找一次虚函数是通过类似变址寻址实现的,其耗时与访问一次数据元素相差无几(想想程序中本来就有多少次间接访问?),从实际应用来看,虽然大量调用虚函数,却并未感觉到性能的降低。

     

    (三)编码反馈出设计的优劣

    在C中,使用强制转换是必须的(没什么替代方法),而C++中,当你必须把一个类的指针强制转换为另一个类的、或者必须在某类中增加一个“type”成员再用if去辨别它们时,就应该考虑到是设计上出问题了,要调整类层次结构、引进基类和虚函数使其合理。一段“不优雅”的代码很可能暗示出一个不良的设计。

     

    当然,OOP也有缺点,它将用户的注意力引向了程序的结构,分散了用户在算法上的精力(对于一些纯粹算法似乎更应面向过程),而一些好的算法又可能被埋没在名字空间中了。另一个缺点是,一旦修改了基类的结构,许多子类都会受到牵连。不过总体来说,优点远远大于缺点,在以后的内容中我们会不断地体会到。

     

    ----------------------------------------------------------------------------------------------------------------------

     

    第三节 整体结构和流程

     

    一 整体结构

    所有程序除main函数外,全部划分在下面几个名字空间中,每个名字空间包含若干个类,实现对应模块的功能:

    aegis:内存泄漏检查

    assem:汇编代码生成

    ast:抽象语法树,包括表达式、语句、函数等类族

    driver:驱动程序,包括命令行类,Compile、Assemble 、Link等驱动函数

    err:错误报告

    ir:中间代码,包括赋值、跳转、标号这几个类族

    lex:词法分析器,包括扫描器类、各种记号类

    parser:语法分析器,包括一系列递归下降的解析函数

    pub:一些公共数据

    symtab:符号表与类型,包括各类符号表、基本类型与数组类型

     

    不同名字空间下可以有同名的类,从而有效解决重名问题,否则你会发现很快用完了喜欢的名字。

     

    二 整体流程

    从main函数的源码,可以看出整体流程:

    int wmain(int argc, const wchar_t* argv[])

    {

           using namespace driver;

           CmdLine cmdLine;//命令行对象

           if(!cmdLine.Parse(argc, argv))//解析命令行

           {

                  return -1;//命令行有错误

           }

           if(!Compile(cmdLine))//按命令行的options编译其中的source files

           {

                  return -1;//编译失败

           }

           if(!Assemble(cmdLine)) //将各source files的编译结果汇编成obj文件

           {

                  return -1;

           }

           if(!Link(cmdLine)) //将各obj文件链接成一个可执行文件

           {

                  return -1;

           }

           Run(cmdLine.m_sOutFile);//运行链接出的可执行文件

           return 0;

    }

    Compile函数将源程序编译成Win32下的汇编代码,之后Assemble和Link函数分别调用Microsoft的汇编程序ml和链接程序link,产生最终的可执行文件。为了调试方便,链接后就直接运行这个程序了。

     

    待改进

    增加若干选项,指示分别执行到哪一步停止。

    将整个程序写成动态库,可以被更灵活、高效地调用。如果需要,可另写一带命令行的控制台程序封装这个动态库。

     

    三 编译流程

    从二个重载Compile函数的源码,可以看出编译流程:

    bool Compile(const CmdLine& cmdLine)//依次编译cmdLine中每个源文件

    {

           wcout<<L"/nCompiling .../n";

           bool bRet=true;

           const CmdLine::FileNames& fileNames=cmdLine.m_fileNames;

           for(CmdLine::FileNames::const_iterator iter=fileNames.begin(); iter != fileNames.end(); ++iter)

           {

                  const FileName* pFileName=*iter;

                  if(!Compile(pFileName))//编译这个source file

                  {

                         bRet=false;

                  }

           }

           return bRet;

    }

     

    bool Compile(const FileName* pFileName)//编译pFileName指示的源文件

    {

           const wstring& sSrcFile=pFileName->m_sName;//源文件名

           wifstream srcFile(sSrcFile.c_str());//打开

           if(!srcFile)

           {

                  wcerr<<L"cannot open source file "<<sSrcFile<<endl;

                  return false;

           }

           wcout<<sSrcFile<<endl;

     

           using namespace lex;

           Lexer lex;//词法分析器

     

           using namespace err;

           Err err(lex, wcerr);//错误对象,它默认输出到wcerr(或其它流),生成错误信息时根据lex获得行号

     

           using namespace parser;

           Parser parser(lex, err);//语法分析器,它使用词法分析器lex,错误信息输出到err

     

           Ast ast;//抽象语法树

           Btab symTab;//符号表

           if(!parser.Parse(ast, symTab, srcFile))//解析srcFile,输出ast和symTab,以及错误信息err

           {

                  return false;

           }

     

           Ir ir;//中间代码

           ast.Gen(ir, symTab);//对ast生成中间代码,期间访问symTab

     

           const wstring& sFile=pFileName->Get();

           const wstring sIrFile=sFile+L".ir";

           wofstream irFile(sIrFile.c_str());

           if(irFile)

           {

                  ir.Out(irFile);//输出中间代码到.ir文件

           }

           else

           {

                  wcerr<<L"cannot create Ir file "<<sIrFile<<endl;

           }

     

           const wstring sAsmFile=sFile+L".asm";

           wofstream asmFile(sAsmFile.c_str());//汇编码的输出文件

           if(!asmFile)

           {

                  wcerr<<L"cannot create asm file "<<sAsmFile<<endl;

                  return false;

           }

           using namespace assem;

           Asm winAsm(asmFile);//汇编码对象,内含输出文件asmFile

           ir.Gen(winAsm, symTab);//对ir生成汇编代码到.asm文件,期间访问symTab

     

           return true;

    }

    从上面可以看出,第1遍对输入流语法分析,生成抽象语法树,第2遍对抽象语法树生成中间代码,第3遍对中间代码生成目标代码。为便于检查和对照,生成的中间代码还保存到对应的.ir文件中,汇编代码保存到对应的.asm文件中。

    每个源文件都对应自己的扫描器、分析器、和错误对象,各源文件的运行状态互不干扰,这是实现多线程的基础。每个对象的初始化由构造函数完成,清除由析构函数完成,省去了手动的初始化和清除步骤。

     

    待改进

    加入单独的优化过程,初步打算加入局部优化、活跃变量分析、死代码删除

     

    ----------------------------------------------------------------------------------------------------------------------

     

    第四节 词法分析器

    一 记号

    (一)记号的类别

    用下列枚举常量分别代表不同的记号类别,它们对应语法上的终结符:

    class Token//记号的基类

    {

    public:

    enum

    {

           AND=256,//记号&&

           ARRAY,//表明一个记号是数组类型,即这个标识符是数组名

           BREAK,//关键字break

           DEC,//运算符--

           DO,//关键字do

           ELSE,//关键字else

           END,//表示输入流的结束

           EQ,//记号==

           EXTERN,//关键字extern

           FALSE,//关键字false

           FLOAT,//浮点常量

           FOR,//关键字for

           GE,//记号>=

           ID,//除关键字以外的标识符

           IF,//关键字if

           IN,//关键字cin

           INCH,//关键字getch

           INT,//整型常量

           LE,//记号<=

           LS,//记号<<

           MINUS,//表示负号,供语法分析器使用。词法分析器无法区分负号和减号,它一律返回减号的ASCII值

           NE,//记号!=

           OR,//记号||

           OUT,//关键字cout

           OUTCH,//关键字putch

           RETURN,//关键字return

           RS,//记号>>

           STATIC,//关键字static

           TEMP,//供中间代码生成使用,表示分配的临时变量,以与ID相区别

           TRUE,//关键字true

           TYPE,//int, double, char, bool等基本数据类型

           WHILE,//关键字while

    };

    public:

           const int m_nTag;//记号的类别

    ……

    };

    对于+、=之类的单字符记号,用它们的ASCII值表示其类别。有几个特殊的记号类别:

    ARRAY:表明一个记号是数组类型,即这个标识符是数组名。

    END:当扫描到输入流结束时,向语法分析器返回这个记号。

    MINUS:表示负号,供语法分析器使用。词法分析器不区分负号和减号,它一律返回其ASCII值。

    TEMP:供中间代码生成使用,表示分配的临时变量,以与ID相区别。

     

    (二)支持的C++记号

    class Int: public Token//整型常量

    {

    public:

           const int m_nValue;//对应的整数值

    };

    class Float: public Token//浮点常量

    {

    public:

           const double m_fValue;//对应的实数值

    };

    class IdPunc: public Token//关键字、标识符、标点符号

    {

    public:

           const wstring m_sValue;//对应的字符串

    };

     

    二 词法分析过程

    class Lexer//词法分析器

    {

    private:

           wistream* m_pInStream;//输入流

           wchar_t m_cNext;//下一字符

           int m_nLine;//当前行号

           typedef set<const Token*> Tokens;

           Tokens m_tokens;//记号表

    private:

           const Int* Add(int nValue);//若m_tokens中不存在值为nValue的整数记号,则new一个Int对象加入之,并返回该对象的地址

           const Floating* Add(double fValue);//与上类似,添加一个浮点数记号

           const IdPunc* Add(const wstring& sValue);//与上类似,添加一个标识符等记号

    public:

           const Token* GetNextToken();//返回下一个Token的地址

    ……

    };

    输入流采用了抽象基类istream,这使得源程序不但可以来自文件,还可来自字符串、甚至控制台,而程序不需做任何改动。

    Lexer类里有一张记号表m_tokens,每识别出一个记号看是否在已在表中,不在时才加入,后续模块若要比较二个记号是否相等,只需比较它们的地址,提高了效率。释放工作在Lexer的析构函数里统一完成,防止了泄漏。

    GetNextToken函数提供给语法分析器调用,每调用一次,它从输入流中识别一个整数、浮点数、标识符或其它符号,调用重载了的Add函数,返回其地址(Token*),语法分析器根据其m_nTag可知其类别,必要时转换回原来的Int、IdPunc等类型。

    每个Lexer对象有一个行号成员m_nLine,它记录了当前源文件被扫描到的行号。

    读字符时识别简单的//注释,当遇到连续的//时,便忽略后面的字符,直到读入了换行符。

    当输入流结束时,向语法分析器返回记号END。

     

    待改进

    识别简单的/**/注释

    识别字符常量和字符串文字量记号

    (长远的)加入预处理过程,它向词法分析器返回预处理记号(pp-tokens),每个pp-tokens都含有源文件名、起始行列位置、终止行列位置,若这个pp-tokens由宏扩展而来,还要提供原宏所在位置,使得上层程序能够生成精确的错误信息。

     

    ----------------------------------------------------------------------------------------------------------------------

     

    第五节 数据类型

    一 基本类型

    class Type //基类

    {

    public:

           const int m_nWidth;//该类型的宽度,用于存储分配

           static const Type INT;//int类型

           static const Type DOUBLE; //double类型

           static const Type CHAR; //char类型

           static const Type BOOL; //bool类型

           static const Type VOID; //void类型

    public:

           virtual const Type* GetBottom() const

           {

                  return this;

           }

    ……

    };

    未对每种基本类型单独派生子类,而是定义为一静态常量,这样,当判断一个Type对象是不是整型时,直接将其地址与&Type::INT相比较。

     

    待改进

    增加float, long, short, 等基本类型,可以从Type派生不同的子类,也可用枚举成员来区分。

    增加unsigned无符号类型。

    支持更多的隐式转换。

     

    二 数组类型

    class Array: public Type//一维或多维数组类型

    {

    private:

           const int m_nNum;//元素个数

           const Type* const m_pType;//元素的类型

    public:

           virtual const Type* GetBottom() const//例如double[3][5]的底层类型是double

           {

                  return m_pType->GetBottom();

           }

    ……

    };

    数组类型Array由Type派生,m_pType可以是基本类型,如果它又是数组类型,那这个Array对象便是多维数组。虚函数GetBottom用于获取最底层数组元素的类型,对于基本类型它直接返回自己,对于数组类型,它调用其元素类型的GetBottom,直到某一次调用到了Type:: GetBottom()。

     

    待改进

    加入指针类型,只能支持指针才能处理字符串。

    加入结构类型,它是class的基础。

     

    ----------------------------------------------------------------------------------------------------------------------

     

    第六节 符号表

    符号表不是一张表,而是若干张表的总称,例如对前面Lexer类的记号表,你也可以把它看成一张符号表。

    在Doctors中,符号表有前后端之分,前端不用后端的符号表,后端也不用前端的符号表,它们的特性完全不同。

     

    一 前端符号表

    (一)构造与析构

    前端符号表是语法分析器内部使用的,其中存放函数名、变量名和数组名,分析结束时亦全部销毁。

    class Ftab//前端符号表

    {

    private:

           typedef set<const Name*> Names;

           Names m_names;//标识符列表

           Ftab* m_pPre;//指向外层语句块的Ftab

           int m_nSize;//符号表于当前函数中已分配的大小,用于计算局部变量的偏移地址

    public:

           Ftab(Ftab* pPre=NULL, int nSize=0);

           const Name* Find () const;

           bool InCurLevel () const;

    ……

    };

    当parser开始分析时,它会新建顶层的Ftab(置其m_pPre为NULL),每当遇到函数或全局变量声明时,将其名字加入当前(即顶层)的Ftab。在函数体内,每进入一个语句块(新的作用域),便分配一新Ftab,置其m_pPre为当前Ftab。当离开这个语句块时,释放该Ftab,并置当前Ftab为其m_pPre。分析结束后释放顶层的Ftab。所有Ftab形成一个类似树状的结构。

    也许你会怀疑,分析结束后,所有符号表都释放了,后续阶段要使用些符号怎么办?原因在于,我们释放的是符号表本身,而不是表中的符号,每个符号都是new出来的对象,具有全局生命期。当然,一旦释放后,变量的作用域便无从知晓了。

     

    (二)前端符号表的作用

    1查找名字的定义

    例如,分析器每识别出一个变量定义时,会调用Ftab::InCurLevel ()在当前Ftab中查找该名字,找到时报告“重复定义”的错误,否则仅将该变量名加入当前Ftab(不到外层查找)。这样便支持了“不同作用域的变量重名”。

    当分析器识别出一个变量的引用时,会调用Ftab::Find ()依次由内层向外层Ftab查找该变量,这样便支持了“内层名字遮盖外层的”。

     

    2存储预分配

    刚进入一函数块时,新建Ftab的m_nSize置为0,每向Ftab中加入一变量时,变量的偏移地址设为新当前的m_nSize,再使m_nSize累加上该变量的大小。函数体内每新建一Ftab时,其m_nSize等于外层Ftab的m_nSize。对于如下函数,它的存储分配过程如下所示

    void fun()

    {                          //new tab1; tab1.m_nSize=0

           int i1;             //i1.offset= tab1.m_nSize=0, tab1.m_nSize=4

           {                   // new tab2; tab2.m_nSize=tab1.m_nSize=4

                  int i2;     //i2.offset=tab2.m_nSize=4, tab2.m_nSize=8

           }                   //delete tab2

           {                   // new tab3; tab3.m_nSize=tab1.m_nSize=4

                  int i3;     //i3.offset=tab3.m_nSize=4, tab3.m_nSize=8

           }                   //delete tab3

    }                          //delete tab1

    采用这个方法,i1算出的偏移地址为0,i2为4,i3也为4,即i3分配在原i2的空间,这是合理的,因为进入i3所在块时,i2的生命期已经结束了。如果i2或i3是数组,则节省的空间更可观。

    生成汇编码时,便用Name::offset来寻址局部变量,例如语句i3=0会生成汇编指令“mov dword ptr[ebp+8], 0”,其中8就由offset计算而来。

     

    从上面可以看出,前端符号表具有强烈的作用域特性,而后端符号表恰好相反。

     

    二 后端符号表

    后端符号表是根据目标语言(如汇编)的需要而设置的,它由语法分析器建立,供目标代码生成模块使用,它分成下面几张表:

    class Btab//后端符号表

    {

    public:

           typedef set<const Const*> Consts;

           typedef set<const Name*> Vars;

           typedef set<const wstring> Strs;

           Consts m_consts;//常量表

           Vars m_vars;//变量表

           Strs m_strs;//字符串表

    ……

    };

     

    (一)常量表

    由于Win32汇编不支持浮点型立即数,浮点数必须定义成符号常量才能使用,因此语法分析中每遇到一个浮点常数,便加入常量表(同一浮点数只加入一次),生成汇编码时,在.data段生成定义语句,如

    .data

           double0   real8              2.71828

           double1   real8              3.14159

    由于整数可以作为立即数出现在汇编指令中,故不需定义成符号常量和加入符号表。

     

    (二)变量表

    与前端符号表不同,该表中仅存放那些全局生命期的变量/数组名,其中包括:

    1全局变量

    在生成汇编时用comm指示符定义在数据段中,使其具有外部链接属性,如:

    .data

           comm _g_i: 4

     

    2静态变量

    包括局部静态变量和全局的静态变量,在生成汇编码时以普通方式定义在数据段中,不具备外部链接属性,如:

    .data

           @s_c1 dword ?

     

    3外部变量

    在生成汇编码时用extern指示其是外部链接的,如:

    .data

           extern _g_d: near32

     

    这些名字都由语法分析器在解析过程中加入符号表。

     

    (三)字符串表

    用于存放汇编指令中要用到的字符串常量,生成汇编时定义到数据段,如:

    .data

           str1  byte '%d %g %c ', 0ah, 0

     

    ----------------------------------------------------------------------------------------------------------------------

     

    第七节 语法分析器

     

    一 支持的语法

    其中大写单词是由词法分析器返回的终结符:

     

    program:

           program trans_unit | trans_unit//程序是一组翻译单元(由连接器保证,语法分析器只处理下面的)

    trans_unit:

           decls END | END//翻译单元(通常是一个源文件)或者为终结符END,或者为若干声明加END,END是词法分析器遇输入流结束时的返回值

    decls:

           decls decl | decl

    decl:

           obj_decl | fun_decl_def//声明分为对象声明与函数声明

    obj_decl:

           var_decl | array_decl//对象声明分为变量声明与数组声明

    var_decl:

           storage basic_type ID ;//变量声明为存储类别+变量类型+变量名,语义检查保证basic_type不能是VOID

    storage:

           EXTERN | STATIC |ε//支持extern与static二种存储类别,为空时采用默认的

    basic_type:

           INT | DOUBLE | CHAR | BOOL | VOID//基本类型

    array_decl:

           storage basic_type ID dims ;//数组声明为存储类别+元素类型+数组名+维数,语义检查保证basic_type不能是VOID

    dims:

           dims dim | dim//维数不能为空(至少是一维)

    dim:

           [ INT ]//元素个数仅支持整数

    fun_decl_def:

           fun_decl | fun_def

    fun_decl:

           storage basic_type ID ( params ) ;//函数声明为存储类别+返回类型+函数名+(形参列表); ,返回类型可以是VOID

    params:

           paras |ε//形参列表可以为空

    paras:

           paras , para | para//各形参用逗号分隔

    para:

           basic_type ID//形参为类型+形参名,不支持数组形参,语义检查保证basic_type不能是VOID

    fun_def:

           storage basic_type ID ( params ) fun_body//函数定义为存储类别+返回类型+函数名+(形参列表)+函数体 ,返回类型可以是VOID

    fun_body:

           block//函数体是语句块

    block:

           { obj_decls stmts }//语句块用花括号括起,前面是若干条对象声明(只能集中声明),后面是0或多条语句

    obj_decls:

           obj_decls obj_decl | obj_decl

    stmts:

           stmts stmt | ε

    stmt:

           | select_stmt | loop_stmt | jmp_stmt | expr_stmt | io_stmt | block | ;//语句分为选择语句、循环语句、跳转语句、表达式语句、输入输出语句、块语句、空语句(单个分号)

    select_stmt:

           if_stmt | if_else_stmt//二种选择语句(以后可以加入switch)

    if_stmt:

           IF ( expr ) stmt//语义检查保证expr是布尔表达式

    if_else_stmt:

           IF ( expr ) stmt ELSE stmt//语义检查保证expr是布尔表达式

    loop_stmt:

           for_stmt | while_stmt | do_stmt//三种循环语句

    for_stmt:

           FOR ( expr ; expr ; expr ) stmt//for语句,语义检查保证第2个expr是布尔表达式

    while_stmt:

           WHILE ( expr ) stmt//while语句,语义检查保证expr是布尔表达式

    do_stmt:

           DO stmt WHILE ( expr ) ;//do语句,语义检查保证expr是布尔表达式

    jmt_stmt:

           break_stmt | ret_stmt//跳转语句包括break和return(以后可加入continue和goto)

    break_stmt:

           BREAK ;//break语句为关键字后跟分号

    ret_stmt:

           RETURN ;//return语句为关键字后跟分号

    expr_stmt:

           expr ;//表达式加分号构成表达式语句

    io_stmt:

           putch_stmt | in_stmt | out_stmt//三种输入输出语句

    putch_stmt:

           OUTCH ( expr ) ;//输出字符语句,语义检查保证expr是整型表达式,以与标准库一致

    in_stmt:

           IN ins ; | IN ;//输入语句为终结符IN后跟若干输入项,可没有输入项

    ins:

           ins in | in

    in:

           >> ID//输入项为为“>>变量名”

    out_stmt:

           OUT outs ; | OUT ;//输出语句为终结符OUT后跟若干输出项,可没有输出项

    outs:

           outs out | out

    out:

           << add_sub_expr//输出项为“<<表达式”,之所以用add_sub_expr而不是expr,是为了与C++运算符<<的优先级保持一致,否则会误接受类似“cout<<1>2;”的语句

    expr:

           assign_expr//表达式目前为赋值表达式,以后可改为优级最低的逗号表达式

    assign_expr:

           or_expr assign_opr assign_expr//语义检查保证or_expr是lvalue

    assign_opr:

           =//赋值运算符,以后可加入+=, *=等

    or_expr:

           or_expr || and_expr | and_expr//或表达式,'||'是逻辑或运算符

    and_expr:

           and_expr && eq_expr | eq_expr//与表达式

    eq_expr:

           eq_expr == rel_expr | eq_expr != rel_expr | rel_expr//等于、不等于表达式

    rel_expr:

           add_sub_expr > add_sub_expr | add_sub_expr >= add_sub_expr | add_sub_expr < add_sub_expr | add_sub_expr <= add_sub_expr//四种关系表达式,比==和!=优先级高

    add_sub_expr:

           add_sub_expr + mul_div_expr | add_sub_expr - mul_div_expr | mul_div_expr//加减表达式

    mul_div_expr:

           mul_div_expr * unary_expr | mul_div_expr / unary_expr | unary_expr//乘除表达式

    unary_expr:

           ! factor | - factor | factor//一元表达式,包括逻辑非、取负和因子

    factor:

           INTEGER | FLOAT | TRUE | FALSE | getch | call | lvalue | ( expr )//因子可以是整数、浮点数、布尔常量true/false、输入字符表达式、函数调用表达式、左值、括号表达式

    getch:

           INCH ( )//输入字符表达式为终结符INCH加一对空括号

    call:

           ID ( args ) | ID ( )//函数调用表达式为函数名+(实参列表),实参列表可以为空

    args:

           args , arg | arg//用逗号分隔各个实参

    arg:

           expr//实参是任何表达式

    lvalue:

           ID | array_elem//左值为变量名或数组元素

    array_elem:

           ID subscripts//数组元素为数组名后跟若干个下标

    subscripts:

           subscripts subscript | subscript

    subscript:

           [ expr ]//语义检查保证下标expr是整型表达式

     

    从语法上可以看出,Doctors支持:

    函数先声明后使用,这使得可以调用外部函数(包括部分库函数,只要支持该库函数的声明语句)。

    static函数。

    全局变量/数组。

    static变量/数组,可以是全局或局部的。

    extern变量/数组,可以在全局或局部作用域声明。

    bool类型、布尔常量true和false,以及bool数组。

    数组维数不限,下标是任意整型表达式,使得数组能够用于循环。

    常用的if-else, for, while, do-while, break, return语句。

    赋值运算和函数调用都是表达式,它们可以出现在允许表达式的任何地方。

    模拟C++ I/O对象的输入输入语句cin, cout,“<<”和“>>”的优先级与标准一致。

    模拟函数的getch是表达式,从控制台输入的字符可参与其它运算。以及输出字符语句putch。

    逻辑运算&&, ||, !,和关系运算==, !=, >, >=, <, <=。

    算术运算+, -, *, /,和取负运算。

    用括号更改运算的优先级次序。

     

    语法基本上是标准C++的子集,这使得在Doctors下编译通过的程序,在标准C++编译器下也能通过(当然要带上头文件)。

     

    待改进

    一条语句定义多个变量。

    变量定义时初始化。

    变量和数组边定义边使用。

    支持指针相关的运算符和表达式。

     

    二 调整文法

    按语法写LL分析程序似乎是件让人犯愁的事,因为许多产生式中都存在左递归,而且还要计算许多FIRST集合,下面让我们一一克服。

     

    (一)从产生式到BNF

    要消除左递归,首先要理解这个产生式,否则即使套上公式算出后还是糊里糊涂的。

    让我们先来看“or表达式”的产生式:

    or_expr:

      or_expr || and_expr | and_expr

    它是左递归的,经过思考我们认识到,一个or表达式至少是一个and_expr,或者后面再跟若干个“|| and_expr”。也就是说,一个or表达式是若干个and_expr相或,这样我们可以直接得出递归下降的算法:

    void or()

    {

           and();//识别第1个and_expr

           while(next_token=='||')//如果下一个记号是终结符||,就一直循环

           {

                  get_next_token();//跳过||,看下一个记号

                  and();//识别后面的and_expr

           }

    }

    void and()//与or()类似

    {

           ……

    }

     

    这个算法其实就是or_expr对应的BNF了,现在让我们带入公式验证一下:

    原式:    A->Aa | b              (1)

    结果:    A->bA'           (2)

                  A'->aA' |ε       (3)

    这里,A=or_expr,a= || and_expr,b=and_expr,代入(2)和(3)得

                  or_expr->and_expr or_expr'                (4)

                  or_expr'-> (|| and_expr or_expr') |ε    (5)//变左递归为右递归

    由此,一个or_expr前面是and_expr,后跟(5),而(5)的含义是,要么它为空,要么是若干个"||and_expr",我们假设把它写为

                  or_expr'-> 空,或若干个"||and_expr"               (5)'

    将(5)'代入(4)得

                  or_expr->and_expr (空,或若干个"||and_expr") (6)

    经过一番折腾后,我们终于消除了左递归,如果按(6)写程序,那么恰好对应上面的or()函数。

    其它左递归的产生式,如decls, paras等,都可得出类似的程序,有的更简单一些。当熟练后,就能直接根据产生式写出解析程序了。

     

    (二)消除二义性

    根据FIRST集,每遇到一个终结符(岔路口),决定调用哪个识别函数(往哪走)。事实上,我们并不需要计算所有的FIRST集,只要对产生式加以调整,合并一些公共部分,就可以解决这个问题。

    观察var_decl、array_decl、fun_decl和fun_def,它们都是以存储类别+类型+标识符开头,我们提出这些左公因子:

    decl_head: storage basic_type ID

    fun_head: decl_head ( params )

    有了decl_head和fun_head,上面几个产生式就可以改写为:

    var_decl: decl_head ;

    array_decl: decl_head dims ;

    fun_decl: fun_head ;

    fun_def: fun_head fun_body

     

    这样,识别decl时我们一口气读完decl_head,看下一个记号,如果是分号,就是变量声明,否则,如果是'[' (dims的first集成员),就当作数组声明。否则再一口气读完fun_head的右括号,如果下一记号是分号,就是函数声明,否则认为是函数的定义。

     

    类似地,二义性文法if-else可以改成:

    if_stmt: IF ( expr ) stmt

    if_else_stmt: if_stmt ELSE stmt

    读完第一个stmt后,若下一个是终结符ELSE,则是if-else语句,否则是if语句。

     

    由此可见,写文法也要像写代码一样,尽可能“重用”已有的产生式,合并冗余的产生式,才有助于编写分析程序。

     

    三 抽象语法树的设计

    抽象语法树(以下简称AST)与语法树、语法分析树似乎容易混淆。其区别在于,AST是编译程序内实在要用的,为了简化问题、节省内存,ast省去了一切不必要的成分,例如对下面程序段:

    while(true)

    {

           break;

    }

    对应的语法树可能为:

         while

        

    ( true ) { break ; }

    它含有7个叶结点,而在AST里,一对圆括号、花括号、分号都会被去掉,只留下true和break二个结点。

     

    对语法分析器而言,程序是一组变量和函数的定义,其中变量已由符号表管理,而AST则是若干函数的集合:

    class Ast

    {

    private:

           typedef vector<Fun*> Funs;

           Funs m_funs;//若干个函数体

    ……

    };

    AST的每个结点可分为3类,函数、语句、表达式,它们都从抽象基类AstNode中派生,下面分别介绍。

     

    class AstNode//抽象语法树结点,为其子类提供共同的祖先

    {

    public:

           virtual ~Node();

    ……

    };

     

    (一)函数的AST结点

    class Fun: public AstNode//函数的AST结点

    {

    private:

           const FunDecl* m_pDecl;//函数的声明

           typedef vector<const Stmt*> Stmts;

           Stmts m_stmts;//函数体内的语句序列

          int m_nMaxOffset;//函数内形参和局部变量总字节数的最大值,生成汇编指令时用于分配堆栈空间

    public:

           void Gen(FunIr* pFunIr, Btab& symTab);//为函数体内所有语句生成中间代码

           void UpdateOffset(int nOffset);//更新m_nMaxOffset

    ……

    };

     

    class FunDecl//函数声明

    {

    private:

           Name* m_pName;//函数名,其m_pType成员指示了函数的返回类型

           typedef vector<Name*> Paras;

           Paras m_paras;//形参列表,

    ……

    }

     

    语法分析器每解析一个函数的声明,便分配一FunDecl对象加入顶层符号表,遇到函数调用时到符号表中查找该函数名,这样,即使函数尚未定义,仍然可以调用(比如对于外部函数)。

    每扫描到一个函数体,便分配一Fun对象加入Ast::m_funs,它将是中间代码生成的对象。

     

    (二)语句的AST结点

    class Stmt: public AstNode//语句结点的基类

    {

    private:

           int m_nNextLabel;//该语句下一条语句的标号,生成中间代码时以获得该语句的出口

           static const Stmt NUL;//表示一个空语句或有错的语句,它们在生成中间代码时被忽略

    public:

           virtual void Gen(FunIr* pFunIr, Btab& symTab, int nFirstLabel, int nNextLabel) const;//为该条语句生成中间代码

    ……

    }

     

    各类语句都从stmt继承,并加入自己需要的成份,例如if-else语句结点如下定义:

    class IfElse: public Stmt//if-else语句的AST结点

    {

    private:

           const Expr* m_pExpr;//条件表达式

           const Stmt* m_pStmt1;//条件表达式为真时执行的语句

           const Stmt* m_pStmt2;//条件表达式为假时执行的语句

    public:

           virtual void Gen(FunIr* pFunIr, Btab& symTab, int nFirstLabel, int nNextLabel) const;//为该条语句生成中间代码

    ……

    };

     

    而break语句结点定义为:

    class Break: public Stmt//break语句的AST结点

    {

    private:

           const Stmt* m_pOut;//指向自己外层语句结点(如for, while),生成中间代码时跳往m_pOut->m_nNextLabel

    public:

           virtual void Gen(FunIr* pFunIr, Btab& symTab, int nFirstLabel, int nNextLabel) const;//为该条语句生成中间代码

    ……

    };

     

    其它从stmt继承的AST结点有

    class DoWhile: public Stmt

    class ExprStmt: public Stmt//表达式语句

    class For: public Stmt

    class In: public Stmt//cin语句

    class If: public Stmt

    class Out: public Stmt//cout语句

    class PutCh: public Stmt//putch语句

    class Return: public Stmt

    class While: public Stmt

     

    在分析过程中,函数列表Ast::m_funs的尾结点(假设为curFun)对应当前正在解析的函数,语法分析器每解析出一条语句,便将其AST结点加入列表curFun.m_stmts,列表内的语句将用来生成中间代码。

     

    (三)表达式的AST结点

    class Expr: public AstNode//表达式结点的基类

    {

    private:

           const Type* m_pType;//表达式的类型

           static const Expr ERR;//代表有错的表达式,它可作为一些解析函数的返回值

    public:

           virtual IrAssign* Gen(FunIr* pFunIr) const;//为该表达式生成中间代码

           virtual const wstring GetRep() const;//返回该常量或变量在汇编指令中的表示

    ……

    };

     

    class Const: public Expr//整型常量、浮点常量、布尔常量对应的AST结点

    {

    private:

           static const Const TRUE;//代表布尔常量true

           static const Const FALSE;//代表布尔常量false

           const int m_nNo;//指示该常量在汇编数据段中的序号(仅用于浮点常量)

    public:

           virtual const wstring GetRep() const;//返回该常量在汇编指令中的表示,对布尔常量返回0和1,对浮点常量返回其符号名,其它返回立即数

    ……

    };

     

    class Name: public Expr//变量名、数组名、函数名

    {

    public:

           enum Storage//变量或函数的存储类别

           {

                  STATIC,//静态的

                  EXTERN,//外部的

                  DEFAULT//缺省的,对全局变量和函数默认为extern,对局部变量默认为auto

           };

    private:

           const Storage m_eStorage;//存储类别

           const FunDecl* m_pDecl;//如果是函数名,则该函数的原型

          int m_nOffset;//变量在堆栈中相对位置(偏移量),生成汇编指令时用

           int m_nNo;//若是静态变量,则其编号(不同函数和语句块内可能会定义同名的static变量)

           const bool m_bGlobal;//是否为全局变量

           const int m_bPara;//是否为函数的形参

    public:

           virtual const wstring GetAddr() const;//根据m_nOffset得到局部变量或形参在栈中的地址,如[ebp-4]

           virtual const wstring GetRep() const;//根据局部变量或形参的类型,返回前面带有PTR操作符的寻址串,如dword ptr [ebp-4]

           const wstring GetAsmName() const;//返回该变量在汇编指令中的名字,其格式为:局部变量为[ebp +/- 偏移量]。全局变量和extern变量名字前加下划线,以防止与符号常量重名。静态变量为"@+名字+编号",@用于防止与全局变量、extern变量、符号常量重名,编号在源文件内唯一,以防止不同作用域的静态变量重名

    ……

    };

     

    此外还从Expr派生出表示与、或、非、关系运算的Logic结点,表示算术、赋值、函数调用、数组下标计算的Oper结点,这里就不一一列举了。

     

    待改进

    从Name派生出Var(变量名)和Func(函数名)二个子类。

     

    四 语法分析过程

    class Parser//语法分析器

    {

    private:

           Lexer& m_lex;//使用的词法分析器

           Err& m_err;//错误对象,用于管理错误信息

           Ast* m_pAst;//要输出的抽象语法树

           Btab* m_pBtab;//要输出的后端符号表

           Ftab* m_pNames;//当前作用域的符号表

           const Token* m_pNext;//向前看记号

    public:

      Parser(Lexer& lex, Err& err);//构造分析器

           bool Parse(Ast& ast, Btab& symTab, wistream& inStream);//启动一次分析过程

     

           void NextToken();//调用m_lex.GetNextToken()移入下一个记号

           void Skip();//跳往下一个能使分析继续进行下去的记号,如分号,右花括号

           bool Matched(int nTag, bool bMove=true, wstring sErr=L"");//比较记号m_pNext的类别是不是nTag,否则根据sErr产生错误信息,并根据bMove决定是否移进下一个记号

     

           void ParseDecl();//解析下一个全局的定义或声明(函数、全局变量等)

           void ParseFun(const Token* pToken, const Type* pType, Name::Storage eStorage)//处理函数pToken的声明或定义,其返回类型为pType,存储类别为eStorage

           const Stmt* ParseStmt();//解析下一条语句,返回相应语句子类的AST结点

           const Expr* ParseExpr();//解析下一个表达式,返回相应表达式子类的AST结点

    ……

    };

     

    bool Parser::Parse(Ast& ast, Btab& btab, wistream& inStream)//启动一次分析过程

    {

           m_pAst=*

           m_pBtab=&btab;

           m_lex.Reset(inStream);//预置要扫描的输入流、行号初始化为0

           m_pNames=new Ftab(NULL);//分配当前作用域(顶层)的符号表

     

           m_pNext=m_lex.GetNextToken();//移入第1个记号

           while(m_pNext->m_nTag!=Token::END)//当输入流未结束时

           {

                  ParseDecl();//解析下一个声明

           }

     

           delete m_pNames;//释放当前作用域(顶层)的符号表

           return m_err.m_nErr==0;//根据错误数目m_nErr得知源程序是否有错

    }

     

    从“编译流程”一节的Compile函数可知,构造分析器时传入扫描器,和错误对象:

    Parser parser(lex, err);

    再定义ast和后端符号表:

    Ast ast;

    Btab symTab;

    之后调用Parser::Parse()启动分析过程:

    if(!parser.Parse(ast, symTab, srcFile))

    {

      ……

    }

    从函数ParseDecl()开始,递归向下进行解析,对前述文法中的每个产生式,通常都对应有Parse函数。

    每解析一个出一个表达式,分配对应表达式的AST结点,该结点用于构造其所在语句的AST结点。

    每解析出一条语句,分配对应语句的AST结点(如for),加入当前函数的AST结点。

    每解析一个函数,分配一Fun结点,加入m_pAst->m_funs。

    当分析完成后,便建立了一棵以m_pAst为根的抽象语法树,后端要使用的符号也包含在symTab中。

     

    五 语义分析

    在Doctors中,语义检查是在语法分析同时完成的,这样做主要原因是:

    1在设计AST时,我们期望解析出抽象语法树能够提供给其它软件使用(比如一个代码格式化工具),不能输出有错误的AST。

     

    2否则在语法分析后,要遍历这颗AST,进行单独的语义检查。由于AST结构的复杂性,当查出一个错误的AST结点后,要将它从千丝万缕的枝叶中剥离出来再delete掉是不容易的。

     

    事实上,边解析边检查是自然的,比如识别了一个赋值表达式后,立刻检查左、右值类型是否匹配,不匹配时忽略这个表达式。与其分配有病AST结点再想办法释放,不如不分配这个结点。

    只要采取了适当的错误恢复机制(见下节),语义错误并不会打乱预定的分析过程。

     

    六 错误恢复

    (一)错误的应对

    从分析器角度而言,源程序中的错误可分为:

    1词法错误

    的词法分析器常常将不识别标点记号返回给语法分析器,负责任的词法分析器应尽量将非法记号修补正确,如字符串末尾缺少引号时自动补上。

     

    2语义错误

    通常,语义错误对分析过程并不构成威协,例如对赋值句i=j; 如果i与j类型不匹配,当前函数只需返回错误标志&Stmt::NUL,通知上层函数忽略这条语句,后者便可以从容识别后续的记号流。

     

    3语法错误

    对于简单的分析程序,是按照其“自我欲望”来工作的,它每读取一个记号,便与“内心期望的”相比较,一旦比较不符,便造成了“心理错位”,即使后面的记号流完全合法,也可能会报告一大堆错误,例如分析器遇到关键字if时,它会按预定的步骤匹配:

    (1) match(“if”)

    (2) match(左括号)

    (3) match(表达式)

    (4) match(右括号)

    (5) match(语句)

    假若输入串是if 3>2) stmt,它可能会拿3去匹配第2项,发现不匹配,再拿>去匹配第3项,仍然不匹配,接着拿2和右括号分别匹配第4、5项。由于缺少了一个左括号,导致分析器接而连三地报告虚假的错误,因此,语法错误对分析过程是致命的。

     

    (二)错误恢复机制

    一旦源程序中出现上述错误,错误恢复机制期望做到:

     

    1继续分析下去

    如果发现一个错误就停止分析,似乎被认为太懒惰了,为能够继续下去,Doctors中采取了以下几种方法:

    (1)假设、虚构

    例如对:

    intt i;//类型标识符写错了,假设其为整型

    例如对:

    int fun;

    void fun(){}//名字已被占用,为该函数生成一个不存在的名字(如fun2)

     

    (2)忽略、推迟

    例如对:

    cout  3  5;//二次缺少了分隔符<<,忽略之

    对:

    while(b)//假设b未定义

    {

           cout<<true;

    }

    当发现b未定义时,仍然继续向下识别后面的语句块,完成后向上层函数返回&Stmt::NUL,以表示该while语句有错误。

     

    (3)跳跃

    发生错误时跳到下一个特殊记号,在下面叙述。

     

    (4)调整文法

    从上面可知,语法错误会扰乱后续输入串的识别,而语义错误通常不会,因此在设计文法时可以放宽某些产生式,使一些语法错误转化为语义错误。例如Doctors中要求if的条件应是布尔表达式,如果我们将if的产生式写为:

    if_stmt: IF ( or_expr ) stmt

    这当然正确,但它在面对输入串if(a=3)时会误报一堆错误。反之,如果我们将产生式改为:

    if_stmt: IF ( expr ) stmt

    则该串便能正常解析,之后再用一段语义例程去检查表达式“a=3”是否为布尔类型、报错、再从容识别后面的语句。

     

    待改进

    当一个标识符未定义时,到记号表中查找一个与它最匹配的,并假设就是它,例如

    iff(3>5)

    {

        bol flag;

        flagg=tru;

    }

    采用此法,记号if, bool, flag, true都能正确被识别,从而有效解决用户录入程序时的疏误。至于查找时匹配的方法,可以统计每个字符出现概率。

     

    2防止误报

    为防产生无价值的错误信息,当遇到非法记号时,立刻从错误状态中恢复过来是很有必要的,可考虑以下几种方法:

    (1)不移入下一记号,将下一个语法元素与这个记号相比较,例如

    putch 97);//少打了一个左括号

    当匹配了putch后,它发现下一记号97与期望中的左括号不符,便忽略这次比较,将记号97与内心期望的下一语法元素(表达式)相比较,结果顺序匹配,便从错误中恢复过来了。

     

    但此法对另一个输入串却行不通:

    putch{97);//误写为左花括号

    i=(1+2)*3;

    当左花括号不匹配’(‘后,它会不断将该左花括号与表达式、右括号、分号相匹配(都不符),结果误匹配了下一句中的左括号,这显然是不期望的。最坏的情况是,如果源程序下面没有左括号了,那么分析程序可能会死锁,所以该法只能有限制地使用。

     

    (2)移入下一记号,将下一记号与当前语法元素相比较,例如

    putch(();//多打了一个左括号,缺少了97

    采用此法可以忽略多出左括号的错误(且不会造成死锁),但对缺少的表达式又无能为力了。

     

    (3)放弃当前语句,不断移入,直到看见了能使分析继续进行下去的记号,通常有

    分号’;’(语句结束符)

    右括号’)’(函数调用和表达式结束符)

    右花括号’}’(语句块结束符)

    这虽然漏报了一些错误,但误报的数量明显减少了,此法用在表达式解析中十分有效。

    遗憾的是,如果函数声明中有错,那么该函数体中每条语句都成为“不期望的”,没什么有效办法能够“跳到下个函数”。

     

    可见,上面的方法都有其局限性,源程序中的错误千变万化,很难找到包治百病的良药,有时编译器只能采取一些无奈的方法:

    (1)将某些错误宣布为“致命”的,如#include指定的头文件打不开时,中止当前文件的解析。

    (2)达到一定错误次数后停止分析,例如,一个正常程序通常不会有100处错误,否则分析器很可能已陷入错误泥潭了。

     

    ----------------------------------------------------------------------------------------------------------------------

     

    第八节 中间代码的设计

    一 中间代码的结构

    与AST中每个函数结点相对应,中间代码(以下简称IR)首先是函数的列表:

    class Ir//中间表示

    {

    private:

           typedef vector<const FunIr*> FunIrs;

           FunIrs m_funIrs;//若干函数的list

    public:

           void Out(wostream& outStream) const;//输出所有中间代码到outStream

           void Gen(Asm& asms, const Btab& symTab) const;//对所有中间代码生成汇编指令

    ……

    };

     

    其中每个FunIr才是中间代码的list:

    class FunIr//中间代码中的函数

    {

    private:

           typedef list<const IrCode*> Codes;

           Codes m_codes;//若干条中间代码的list

           int m_nLabelNo;//函数内当前的标号数量

           int m_nTempNo;//函数内当前临时变量的数量

           AstFun* m_pAstFun;//在IR生成过程中,如果分配了临时变量,则需要更新m_pAstFun->m_nMaxOffset

    public:

           void Add(const IrCode* pIrCode);//添加一条Ir

           void AddLabel(int nLabel);//添加一条标号Ir

           void AddJmp(int nLabel);//添加一条无条件跳转Ir

           void Out(wostream& outStream) const;//输出函数内所有IR到outStream

           void Gen(Asm& asms, const Btab& symTab) const;//对函数内所有IR生成汇编指令

    ……

    };

     

    class IrCode//所有中间代码的抽象基类

    {

    public:

           virtual ~IrCode();

           virtual void Out(wostream& outStream) const=0;//以易读的方式输出该条中间代码

           virtual void Gen(Asm& asms, const Btab& symTab, const FunDecl* pDecl) const=0;//为该条中间代码生成汇编指令

    ……

    };

     

    二 中间代码具体格式

    中间代码具体有二十多种格式,但它们都隶属于赋值、标号、跳转这3种。

    (一)赋值

    class IrAssign: public IrCode//赋值中间码(抽象基类),它仅指出被赋值的变量

    {

    private:

           const Name* m_pDst;//被赋值的变量

           bool m_bReserved;//当该条IR的结果不会使用时,该IR是否必须保留(例如函数调用必须保留,即使其返回值未被使用),该成员用于IR优化

    ……

    };

     

    赋值操作又分为以下4种

    1一元赋值

    class UnaryAssign: public IrAssign//一元赋值(抽象基类),即只有一个源操作数的赋值

    {

    private:

           const Expr* const m_pSrc;//源操作数

    ……

    };

    一元赋值的具体类有:

    Mov:执行m_pDst=m_pSrc

    Neg:执行m_pDst= - m_pSrc

    以后还可加入其它一元运算对应的IR,如取地址、类型转换等。

     

    2二元赋值

    class BinaryAssign: public IrAssign//二元赋值(抽象基类),即有二个源操作数的赋值

    {

    private:

           const Expr* const m_pSrc1;//源操作数1

           const Expr* const m_pSrc2;//源操作数2

    ……

    };

    二元赋值的具体类有:

    Add:执行m_pDst=m_pSrc1+m_pSrc2

    Sub:执行m_pDst=m_pSrc1-m_pSrc2

    Mul:执行m_pDst=m_pSrc1*m_pSrc2

    Div:执行m_pDst=m_pSrc1/m_pSrc2

    以后还可加入其它运算对应的IR,如求余、位运算等。

     

    3函数调用

    class Call: public IrAssign//函数调用,它的“源操作数”是函数名和实参列表,返回值保存在IrAssign::m_pDst中

    {

    private:

           const FunDecl* const m_pDecl;//指向要调用函数的声明

           typedef vector<const Expr*> Args;

           Args m_args;//实参列表,无实参时列表为空

    public:

           virtual void Out(wostream& outStream) const;//提供了实现

           virtual void Gen(Asm& asms, const Btab& symTab, const FunDecl* pDecl) const;//提供了实现

           virtual int PushArg(Asm& asms, const Expr* pArg) const;//生成实参pArg的值入栈的汇编指令,子类InIr重载了该函数,将pArg的地址入栈

           virtual int PushAfterArgs(Asm& asms, const Btab& symTab) const;//在各个实参入栈后、call指令前执行的操作,子类InIr和OutIr重载了该函数,以将格式串的地址入栈

    ……

    };

    从Call中又派生出InIr(输入cin)、OutIr(输出cout)、GetCh(输入字符)、PutCh(输入字符),从Call继承的Gen函数会自动为它们生成调用对应库函数的汇编指令序列。

     

    4数组元素访问

    class ArrayAccess: public IrAssign//数组访问操作m_pArray[m_pIndex](抽象基类)

    {

    public:

           const Expr* const m_pIndex;//偏移量

           const wstring GenElemAddr(Asm& asms, const Name* pArray) const;//根据数组首地址nBase、元素偏移地址m_pIndex,及元素类型pElemType,生成将元素有效地址放入ebx的指令,并返回元素寻址字符串,如dword ptr[ebx]

    ……

    };

    从ArrayAccess又派生出ReadArray(读数组元素)和WriteArray(写数组元素),它们在生成IR时共享基类的方法。

     

    (二)标号

    class LabelIr: public IrCode//标号中间码

    {

    private:

           const int m_nLabel;//标号由一个整数指定

    public:

           virtual void Out(wostream& outStream) const;//输出”L”+m_nLabel

           virtual void Gen(Asm& asms, const Btab& symTab, const FunDecl* pDecl) const;//生成当前汇编文件中唯一的标号,格式为"L"+m_nLabel+函数名

    ……

    };

    当一条中间代码带有标号时,在其前面放置一条LabelIr中间码,作为各种跳转IR的目标。

    也许你意识到,每条中间码可能都会对应标号,为什么不在每个中间代码类中添加一个Label成员呢?这主要是考虑到以后的优化,在优化过程中,一些IR会被删去,如果要删除一条带有标号(假定为N)的IR,我们必须到其下一条IR,获得其标号(假定为M),再将所有跳往N的IR的跳转目标修改为M,这样即麻烦又易错。

    现在将标号从IR中抽出来后,优化时只需删除要删的IR,所有标号IR原地不动。而且带标号的IR毕竟是少数,不需要每条IR都加一个Label成员。

     

    (三)跳转

    class IrJmp: public IrCode//跳转IR(抽象基类)

    {

    private:

           int m_nLabel;///目标标号由一个整数指定

    ……

    };

    跳转IR又分为无条件跳转和条件跳转二大类:

     

    1无条件跳转

    class Jmp: public IrJmp//无条件跳转

    {

    public:

           virtual void Out(wostream& outStream) const;//输出”goto L”+m_nLabel

           virtual void Gen(Asm& asms, const Btab& symTab, const FunDecl* pDecl) const;//生成汇编指令jmp,它转向标号m_nLabel

    };

     

    从无条件跳转又派生出二种return中间码,它们在代码生成时共享基类的方法:

    class RetIr: public Jmp//对应无返回值的return语句,return也要做无条件跳转

    {

    public:

           virtual void Out(wostream& outStream) const;//输出“return”

           //继承基类的Gen()实现

    ……

    };

     

    class Ret: public RetIr//对应有返回值的return语句

    {

    private:

           const Expr* const m_pExpr;//返回值,可以是常量、变量或表达式

    public:

           virtual void Out(wostream& outStream) const;//输出“return”+m_pExpr

           virtual void Gen(Asm& asms, const Btab& symTab, const FunDecl* pDecl) const;//先生成将m_pExpr的值放入EAX或浮点栈顶的指令,再调用基类的Gen()生成无条件跳转指令

    ……

    };

     

    2条件跳转

    class CondJmp: public IrJmp//条件跳转(抽象基类)

    {

    public:

           virtual CondJmp* Reverse()=0;//条件翻转

    };

     

    从条件跳转又派生出:

    (1)布尔跳转

    class BoolJmp: public CondJmp//布尔跳转(抽象基类)

    {

    private:

           const Expr* const m_pSrc;//根据何值做布尔判断

           const wstring m_sName;//源操作数与0相比较后,执行的跳转指令

    public:

           virtual void Gen(Asm& asms, const Btab& symTab, const FunDecl* pDecl) const;//为该布尔跳转生成汇编指令

    ……

    };

    布尔跳转有2种具体类:

    Jz:m_pSrc为0时跳转

    Jnz:m_pSrc非0时跳转

     

    (2)关系跳转

    class RelJmp: public CondJmp//关系跳转(抽象基类)

    {

    private:

           const Expr* const m_pSrc1;//源操作数1

           const Expr* const m_pSrc2;//源操作数1

           const wstring m_sIntName;//若源操作数是整型的(整型比较),则对应的跳转指令,如JG,JGE

           const wstring m_sFloatName;//若源操作数是浮点型的(浮点型比较),则对应的跳转指令,如JP,JNP

           const int m_nTestVal;//若源操作数是浮点型的(浮点型比较),则在执行跳转指令m_sFloatName前,test指令要测试的值

    public:

           virtual void Gen(Asm& asms, const Btab& symTab, const FunDecl* pDecl) const;//为该整型或浮点型关系跳转生成汇编指令

    ……

    };

    关系跳转对应6种具体类:

    Jg:m_pSrc1>m_pSrc2时跳转

    Jge:m_pSrc1>=m_pSrc2时跳转

    Jl:m_pSrc1<m_pSrc2时跳转

    Jle:m_pSrc1<=m_pSrc2时跳转

    Je:m_pSrc1==m_pSrc2时跳转

    Jne:m_pSrc1!=m_pSrc2时跳转

     

    它们的界面都类似,具体代码就不一一列举了。

     

    从上面可以看出,AST关注的对象是表达式、语句、函数这些高层语法结构,到了中间代码层后,关注对象已经被分解为赋值、跳转、标号这些低级结构了(这当然是出于优化的需要),到了目标代码层会变为指令串这类更低级的结构。

     

    由于篇幅有限,所有内容只能介绍到这里,如果要进一步了解IR的生成,可以看编译器输出的.ir文件。

    从上面各IR类的成员和函数,也许你已联想到目标代码的生成方式,以及运行时全局、静态、局部变量和数组的存储分配,这可进一步看编译器输出的.asm文件。

     

    ----------------------------------------------------------------------------------------------------------------------

     

    附录:参考资料

    1 龙书

    2 ISO-IEC 14882

    3 ISO-IEC 9899

     

    [全文完]

     


    最新回复(0)