编译原理课设尝试(二)——PL/0编译器改写

花了点时间,终于把PL/0整个编译器的源码分析了一遍,接下来就是上手对这个编译器进行改造的过程了。

我决定首先尝试将PL/0编译器的源码从C转到C++上,然后划分成多文件,再准备开始改。先从课设作业要求开始,最终的目标是完成PL/0的完整文法支持。

已经完成的部分我用删除线在下面标出来。

在github上开了个仓库,准备存放改写后的代码,以及用于记录整个过程:
https://github.com/jcf94/pl0_compiler

下面先看一下拓展后的PL/0文法。

PL/0可拓展的完整文法

  • Program → Block .

  • Block → [ConstDecl][TypeDecl][VarDecl][FuncDecl] begin Stmt {; Stmt } end

  • ConstDecl → const ConstDef {, ConstDef} ;

  • ConstDef → ident = number

  • TypeDecl → type TypeDef {TypeDef }

  • TypeDef → ident = TypeExp ;

  • TypeExp → integer | real | Boolean | array ‘[’number .. number‘]’ of TypeExp

  • VarDecl → var VarDec {VarDec }

  • VarDec → ident {, ident} : Type ;

  • Type → integer | real | boolean | ident

  • FuncDecl → FuncDec { FuncDec }

  • FuncDec → procedure ident [ ( ForParal ) ]; Block ; | function ident [ ( ForParal ) ] : Type ; Block ;

  • ForParal → ident : Type {; ident : Type }

  • Stmt → IdentRef := Exp | if Exp then Stmt | if Exp then Stmt else Stmt | begin Stmt {; Stmt } end | while Exp do Stmt | exit | ε | call ident [ ( ActParal ) ] | write ( Exp {, Exp } ) | read (IdentRef {, IdentRef } )

  • IdentRef → ident [ ‘[’Exp‘]’ { ‘[’Exp‘]’ } ]

  • ActParal → Exp {, Exp }

  • Exp → SimpExp RelOp SimpExp | SimpExp

  • RelOp → = | <> | < | > | <= | >=

  • SimpExp → [+ | - ] Term {+ Term | - Term | or Term}

  • Term → Factor {* Factor | / Factor | div Factor | mod Factor | and Factor}

  • Factor → IdentRef | number | ( Exp ) | not Factor | ident [ ( ActParal ) ] | odd (SimpExp) | true | false

课设要求

课设要求上给出了8个题目:

  • 给PL/0语言增加C语言形式的/∗ …… ∗/的注释。

  • 给PL/0语言增加带else子句的条件语句和exit语句。exit语句作为while语句的非正常出口语句。若处于多层while语句中,则它只作为最内层while语句的非正常出口。若它没有处于任何while语句中,则是一个错误。

  • 给PL/0语言增加输入输出语句。

  • 给PL/0语言增加带参数的过程,参数传递按值调用方式。

  • 给PL/0语言增加布尔类型,并且布尔类型的表达式按短路方式计算。

  • 给PL/0语言增加数组类型。

  • 给PL/0语言增加函数类型。

  • 给PL/0语言增加实数类型。

改写过程记录

  • 多文件改写

  • 添加C语言形式的注释功能,支持//注释一行和/* */的段注释

修改词法分析器的getsym()部分即可,要注意的是除法也是/符号

  • 添加else子句

这里有个比较容易出错的问题,即PL/0中对分号的处理与C中稍微有些区别,并不是所有的语句后面都会有分号。查看文法可知,block后跟点或分号,常量、变量定义的最后要有分号,出现多条并列的stmt时需要用分号来分隔(而最后一条stmt可能是不需要带分号的)。

这一点从文法分析中对分号semicolon的处理上也可以看出来。

因此else子句只要继续按照文法进行扩展即可:

if Exp then Stmt | if Exp then Stmt else Stmt

else前面应该是没有分号的。

首先将else加入保留字,norwwordwsym都要作相应修改,注意原代码中用了二分查找,所以保留字的顺序也要作相应调整。

在文法分析中if语句部分的后面加上对else的判定即可。

最后还要处理一下若遇到一个语句开头部分直接是else的错误反馈。

  • 添加exit语句

同样先将exit加入保留字,然后在stmt中增加对exit的支持。

一个exit语句其实就是jmp跳转到while的末尾即可,一个while中可能出现多个exit,而且while本身也是可以嵌套多层的,因此这里可以采用栈的结构exitlist保存下每个exit产生的jmp语句的位置。

等到一个while块结束时,再根据exitlist把所有jmp语句缺少的地址给补上。

  • 添加输入输出语句

首先看一下输入输出部分的文法:

write ( Exp {, Exp } ) | read (IdentRef {, IdentRef } )

write是括号中跟一个或多个exp,read是括号中跟一个或多个IdentRef。

由于还没有作其他的拓展,这里的IdentRef只是变量名,后面拓展成数组等等之后就有更多的东西了,比较麻烦…我在想是不是要先把IdentRef单独先分出来,以便于以后的工作。

首先继续添加关键字,原本的sym用的是unsigned long类型,大小有点不够,所以把所有的sym都改成unsigned long long类型。

statbegsys中把read和write都加上。

然后在stmt中完成对read和write的处理即可。

有了read和write之后,接下来对PL/0编译器的各种测试和调试都可以先通过这两个来完成啦,简直是赞。

  • 添加true和false支持

为后面添加boolean类型作准备

  • 添加not/and/or/div/mod支持

事实上由于类型还没改,到这里为止编译器还只能支持整数,这里的div和原本的除法是一样的。

  • 添加integer/boolean类型定义

enum object这个枚举类型中把integer和boolean都加上。

添加类型定义需要涉及到的修改的地方比较多,比如VarDec的定义:

VarDec → ident {, ident} : Type ;

PL/0不像C语言那样先写下类型,后面再跟变量名,而是刚好反过来,因此这里新加一个enterlist的结构,识别出ident之后先把对应的符号表位置存入enterlist,然后等类型识别完毕后再改上去。

各个位置涉及到变量值的都需要修改,另外在变量的使用过程中还需要增加运算类型是否匹配的检查。我增加了一个运算操作用来整理boolean型变量的数据,即非零的全变成1。

这个编译器中运行时直接用的是C的数组作为数据栈,所以对于不同类型变量的存储其实是大大简化了的,因为随便怎么写都能存下来,大不了最后我把运行栈整个改成double数组就能同时支持整数和浮点数了,而实际要生成真正的汇编语言的话,需要考虑到的东西很多,还要看是不是跟机器也相关等等。

这里还是仅作实验学习吧…

额,各种问题都是相当麻烦,详细的就不记录了,改着改着都改忘了。

  • boolean运算的短路方式

or前面是1,则后面部分不再计算;and前面是0,则后面部分不再计算。

本来想是不是生成中间代码时就直接跳了,但是值的计算是到运行时才完成的,编译阶段根本不知道结果,所以要修改的部分应该是在中间代码生成时加上判断跳转的指令。

这里遇到点小麻烦,本来以为已经完成了这部分,结果调试时不对。

翻解释器的代码出来看之后惊奇地发现jpc结束后居然是要栈顶减1的…这样我原来想的就有问题了。
明天再想想怎么解决吧。


待续…

0%