商务合作:179001057@qq.com

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

技术2022-05-11  0


某平台价值19860元的编程课程资料免费领取【点我领取】


自己写的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)