今天也要加油啊江同学

从零开始的CX编译器

从零开始的CX编译器

大学最后一个大作业了。我校课程里难得质量较高的project,记录一下。

首先说一下语法定义。这是一个类C的语言,词法和语法是给好了的(但是只有基础功能,后续要自己加)

要求是完成词法分析,语法分析,出错处理,代码生成和解释程序。最终实现程度除了上述要求外,增加了一些运算符,以及case,for,break,continue,exit ,do…while,repeat…until语句,数据类型上加了个double。

接下来说一下过程。

词法分析阶段:

使用flex。flex的规则是:最长匹配原则。如果有多个规则满足最长匹配规则,那么选择最靠前的那一个。这里注意一下lex的匹配规则里,{xxx}用来表示非终结符,[]中的必须要是终结符。例如{LETTER}({LETTER}|{DIGIT})* 就可以表示identifer,但是{LETTER}[{LETTER}{DIGIT}]*就不奏效。

lex 中如果没有写main 函数,-ll会自动帮我们生成main,比如:gcc lex.yy.c -ll。

另外注意,letter和digit不应该被识别。也就是说单个字母和数字也应该被识别成identifier和number。

语法分析阶段:

使用bison。根据project给定的语法规则写出来就行了。然后和lex结合:

先用yacc -d cx.y命令生成y.tab.h;然后在lex中添加这个头文件,再cc lex.yy.c y.tab.c -o cx 完事。

其中yacc -d中-d的含义如下:

  • ‘-d’ ,’–defines’ : 编写额外的输出文件,它们包含这些宏定义:语法中定义的标记类型名称,语义的取值类型 YYSTYPE, 以及一些外部变量声明。如果解析器输出文件名叫 ‘name.c’, 那么 ‘-d’ 文件就叫做 ‘name.h’。 如果你想将 yylex 定义放到独立的源文件中,你需要 ‘name.h’, 因为 yylex 必须能够引用标记类型代码和 yylval变量。

YACC中的语义分析:

在书写动作时,大括号内写的是C代码或者YACC伪变量。当识别一条YACC规则时,规则中的每个符号都拥有一个值,除非它被参数改变。这些值由YACC保存在一个与分析栈保持平行的值栈(value stack)中,每个在栈中的符号值都可以使用以$开始的伪变量来引用。另外,在yacc的声明阶段,可以使用%union来确定yylval的类型。

标识符表和错误处理:

标识符表的结构书上只有name和kind两个属性,但是 我们的语言的variable可能有几种不同的类型,如int,bool,double等,因此需要在这个基础上再增加type类型。(之后加了const语法后还要加一个kind类型)到这为止词法和语法分析就结束了。通过在yacc中添加一些简单的语义分析我们已经可以进行一些基本的运算,比如实现一个计算器的功能等等。但是这样一个程序是不具备真正的语义分析的能力的。比如面对if else, while等语句,现在只能说判断是否符合语法规则,并能给出语法树,但是做不到语义分析。语义分析接下来要结合解释程序进行,也就是利用我们的中间代码来解释执行。

解释程序的构造:

接下来就是解释程序的构造。我们的目的是研究一种适用的目标代码生成系统,将它嵌入到现有的语法分析程序中,使之扩充成能生成目标代码程序的程序。我们采用书上的PL/0的指令格式并加以扩充。因为变量类型不同,这里的程序存储器code的结构和书上稍有不同。lit指令会传递数过来,包括int,double和bool类型。在指令中我们统一使用double存储,但因此我们要记录下这个数的类型,以便可以进行诸如double+int的类型转换。又因为数据栈的操作由中间代码控制,因此我们要在中间代码里添加数的类型,再传递给数据存储器,在解释指令时使用。在解释执行代码的时候,我们是从前往后依次处理code数组中的中间代码的,这个顺序的有效性由语法分析过程确定。因为我们使用的yacc采用的是lalr(1)的分析方法,这种自下而上的分析方法会将中间代码以一种后缀式的形式产生。这让我想起之前做过一个scheme(一种lisp方言)的编译器,当时其实没有写解释程序,直接根据语法分析的结果就做了分析,就是凭借着scheme天生的后缀表达的形式。关于语义解释的顺序还要注意一点,如果语义动作在语法动作中间,例如stmt:IF LP bexpr RP {cx1 = cx;gen(jpc,0,0,int_t); break; }stmt{code[cx1].a = cx;} SEMI,语义动作执行的顺序是bexpr部分的语义,本规则的第一条语义动作,stmt部分的语义,第二条语义。这时候还发现了一个很有趣的事情:语义位置的不同还会影响到移进规约和规约规约冲突;关于这个问题,查了一下,stackoverflow上也有人有相同的问题;原来这种Mid-Rule Actions(MRAs)会让解析器不得不提前判断是shift还是reduce;因此要减少使用MRAs。https://stackoverflow.com/questions/46871475/warning-rule-useless-in-parser-due-to-conflicts-1-empty

在写pcode的时候又遇到一个问题,sto指令中需要有变量在数据栈中的位置,但目前我们还得不到这个位置。因此我们要在标识符表table数组中加上一个属性addr,存放标识符在数据栈中的地址。接下来进行语句的翻译。这里先处理if语句。首先要求里给的if,while等语句有一点小错误,stmt后不需要以分号为结尾;修改后if遇到上述提到的MRAs的问题,这里将语法规则修改为:

<stmt> ∷= if (<bexpr>) <stmt>|elses

elses ::= ELSE stmt|

就可以解决移进规约冲突导致else后的语句无法被规约的问题。

再处理while语句;与书上的pl0类似,记录下while里的expr以及stmt的地址,不满足expr则跳转,stmt后无条件跳转回expr即可。到这一步为止,就满足了作业的基本要求:我们用这样的一个语言也可以实现一些基本的程序,如求最小公倍数,1-100的素数,阶乘等等。接下来对我们的语言进行扩展,让它支持更多的功能。

Switch case语句:仿照c语言。这里偷懒没实现default的功能。switch case的关键在于两个不同的跳转:一个是常规跳转,如果case不满足则跳过stmts;另外一种是如果满足了case之后要跳过接下来所有的case直接执行所有的stmts。对于第二种情况,书上的pcode的指令是不够的,因此我们额外设计了几个指令来实现这一功能。

break语句:拿一个栈记录下来跳转的位置就可以了。在循环,switch等条件结束的时候在栈内回标地址即可。

continue语句:与break类似。注意一下如果continue要跳到的地方在continue 语句之前,那么就不用回标,而是要在读到那个地方的时候就需要记录下来。例如:do while语句,repeat until语句。

for语句:总共有四个跳转语句。不满足rel的时候直接跳转到最后,满足跳转到stmt前,以及stmt结束后跳转回rel,第三个语句跳转到第二个语句前。需要三个tag来记录语句的位置。因为有可能for嵌套的情况,因此也要用一个栈来维护。

Do while/repeat until:没什么好多说。continue那里注意一下。

const:添加三条const type id assign expr semi。之前提到的table中的kind用来出错处理。

添加double:修改一下词法语法。因为我们数据栈里实际上存的都是double,因此在一些指令里要根据id的类型不同操作进行简单修改。例如:read,opr中的指令。

到这为止就完成了一个编译器。代码放在github上:

https://github.com/XinyuJiang/CXCompiler

xinyu