广东工业大学PL0扩充课程设计报告陈

课 程 设 计

           课程名称    编译原理                    

           题目名称    PL/0编译器的扩充 

           学生学院    计算机学院        

           专业班级    计算机科学与技术（7） 

           学    号     3110006131                

           学生姓名      陈日燊                       

           指导教师     林 志 毅         

2011 年 1 月 8 日

一．课程设计目的与要求

1、课程设计目的：

在分析理解一个教学型编译程序（如PL/0）的基础上，对其词法分析程序、语法分析程序和语义处理程序进行部分修改扩充。达到进一步了解程序编译过程的基本原理和基本实现方法的目的。

2、课程设计要求：

对PL/0作以下修改扩充：

（1）增加单词：保留字 ELSE，FOR，TO，DOWNTO，RETURN

运算符 +=，-=，++，--，

（2）修改单词：不等号# 改为 <>

（3）增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则。

二．实验环境与工具

（1）计算机及操作系统：PC机，WindowsXP

（2）程序设计语言： VC++ 6.0， C/C++语言

（3）教学型编译程序：PL/0 

三.结构设计方案 

1、结构设计说明：

      PL/0的编译程序以语法分析程序为核心，词法分析程序和代码生成程序都作为一个的过程，当语法分析需要读单词时就用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。此外，用表格管理程序建立变量，常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。

2、各功能模块图示：

3. 各功能模块作用表：

struct tablestruct

{

   char name[al];       /*名字*/

   enum object kind;    /*类型：const，var，array or procedure*/

   int val;             /*数值，仅const使用*/

   int level;           /*所处层，仅const不使用*/

   int adr;             /*地址，仅const不使用*/

   int size;            /*需要分配的数据区空间，仅procedure使用*/

};

4. 保留关键字枚举结构：

enum symbol{

    nul,         ident,       number,         plus,        minus,

    times,         slash,       oddsym,         eql,        neq,

    lss,         leq,           gtr,         geq,        lparen,

    rparen,    comma,           semicolon,     period,   becomes,

    beginsym,     endsym,        ifsym,         thensym,     whilesym,

    writesym,     readsym,       dosym,         callsym,  constsym,

    varsym,     procsym,     elsesym,    forsym,   tosym,

    downtosym,  returnsym,   pluseql,    minuseql, plusplus,

    minusminus,                                                    

};

5.名字表中标识符枚举类型：

enum object{

       constant,         /*常量*/

       variable,         /*变量*/

       procedur,         /*过程*/

};

6.虚拟机

enum fct{                 /* 虚拟机代码*/   

     lit,   opr,   lod,  

     sto,   cal,   inte,

     jmp,   jpc,

};

struct instruction       /* 虚拟机代码结构*/

{

     enum fct f;         /* 虚拟机代码指令*/

     int l;              /* 引用层与声明层的层次表*/

     int a;             /* 根据f的不同而不同*/

};

7. 扩充部分语法描述图：

8. 运行时存储组织和管理

对于源程序的每一个过程（包括主程序），在被调用时，首先在数据段中开辟三个空间，存放静态链SL、动态链DL和返回地址RA。静态链记录了定义该过程的直接外过程（或主程序）运行时最新数据段的基地址。动态链记录调用该过程前正在运行的过程的数据段基址。返回地址记录了调用该过程时程序运行的断点位置。对于主程序来说，SL、DL和RA的值均置为0。静态链的功能是在一个子过程要引用它的直接或间接父过程（这里的父过程是按定义过程时的嵌套情况来定的，而不是按执行时的调用顺序定的）的变量时，可以通过静态链，跳过个数为层差的数据段，找到包含要引用的变量所在的数据段基址，然后通过偏移地址访问它。

　　在过程返回时，解释程序通过返回地址恢复指令指针的值到调用前的地址，通过当前段基址恢复数据段分配指针，通过动态链恢复局部段基址指针。实现子过程的返回。对于主程序来说，解释程序会遇到返回地址为0的情况，这时就认为程序运行结束。

　　解释程序过程中的base函数的功能，就是用于沿着静态链，向前查找相差指定层数的局部数据段基址。这在使用sto、lod、stoArr、lodArr等访问局部变量的指令中会经常用到。

　　类PCODE代码解释执行的部分通过循环和简单的case判断不同的指令，做出相应的动作。当遇到主程序中的返回指令时，指令指针会指到0位置，把这样一个条件作为终至循环的条件，保证程序运行可以正常的结束。

9. 扩充赋值运算：+= 和 -= 设计：

对于+=、-=、*=和/=赋值运算符，在程序中出现的情况只有如下一种，文法的EBNF 表示为：

赋值语句::= <标识符> [  += | -=  ] <表达式>

（1）扩充的语法描述见结构设计中的 PL/0 分程序和主要语句的语法描述中的描述图；

（2）分析区别赋值运算符采用：读标识符后再读一个字符，后根据读到的字符转去不同的赋值语句执行。

（3）中间代码生成情况：+=运算符，其他赋值运算符架构是一样的，只是执行加法改为相应的算数运算。

    else if(sym==pluseql)                                 //检测到+＝符号

    {

        i=position(id,*ptx);                             //把类x+=3的x的地址取出来

        gendo(lod,lev-table[i].level,table[i].adr);      /*找到变量地址并将其值入栈*/

        getsymdo;

        if(sym==semicolon)

        {

            getsymdo;

        }

        memcpy(nxtlev,fsys,sizeof(bool)* symnum);

        expressiondo(nxtlev,ptx,lev);

        gendo(opr,0,2);

        if(i!=0)

        {

            gendo(sto,lev-table[i].level,table[i].adr);

        }

    }

    else if(sym==minuseql)                                  //检测到-＝符号                

    {

        i=position(id,*ptx);                              //把类x-=3的x的地址取出来

        gendo(lod,lev-table[i].level,table[i].adr);      /*找到变量地址并将其值入栈*/

        getsymdo;

        if(sym==semicolon)

        {

            getsymdo;

        }

        memcpy(nxtlev,fsys,sizeof(bool)* symnum);

        expressiondo(nxtlev,ptx,lev);

        gendo(opr,0,3);

        if(i!=0)

        {

            gendo(sto,lev-table[i].level,table[i].adr);                    

        }

    }

10.扩充语句（Pascal的FOR语句）:

①FOR <变量>:=<表达式> TO <表达式> DO <语句>

②FOR <变量>:=<表达式> DOWNTO <表达式> DO <语句>

     其中，语句①的循环变量的步长为1，

语句②的循环变量的步长为-1

For i:= E1 to E2  do S1 循环语句ALGOL等价于：

          i:= E1;

         goto OVER;

AGAIN ：i:= i+1

OVER ： if iBegin S1;

goto again end;

注意程序中基础用到循环控制变量i，因此 entry（i）必须被保存下来，而Pascal这样的语言中，循环变量在循环外也是可见的，本次扩充约定循环步长为 1或者-1。具体需要在程序staement（）添加for的句法判断：

else if(sym==forsym)      //检测到for语句

{

    getsymdo;

    if(sym==ident)

    {

        i=position(id,*ptx);

        if(i==0) error(11);

        else

        {

            if(table[i].kind!=variable) //赋值语句中，赋值号左部标识符属性应是变量

            {

                error(12);i=0;

            }

            else

            {

                getsymdo;

                if(sym!=becomes) error(13);             //赋值语句左部标识符后应是赋值号:=

                else getsymdo;

                memcpy(nxtlev,fsys,sizeof(bool)*symnum); 

                nxtlev[tosym]=true;                     //后跟符to和downto

                nxtlev[downtosym]=true;

                expressiondo(nxtlev,ptx,lev);            //处理赋值语句右部的表达式E1

                gendo(sto,lev-table[i].level,table[i].adr);      //保存初值

                switch(sym)

                {

                case tosym:           //步长为的向上增加

                        getsymdo;

                        cx1=cx;       //保存循环开始点

                            //将循环判断变量取出放到栈顶

                        gendo(lod,lev-table[i].level,table[i].adr);                                           memcpy(nxtlev,fsys,sizeof(bool)*symnum);    //处理表达式E2

                        nxtlev[dosym]=true;                         //后跟符do

                        expressiondo(nxtlev,ptx,lev);

    /*判断循环变量条件，比如for i:=E1 to E2 do S中，判断i是否小于E2，如小于等于，继续循环，大于的话，跳出循环*/        

                        gendo(opr,0,13);             //生成比较指令，i是否小于等于E2的值

                        cx2=cx;                      //保存循环结束点

//生成条件跳转指令，跳出循环，跳出的地址未知

                        gendo(jpc,0,0);                        

if(sym==dosym)               //处理循环体S

                        {

                            getsymdo;

                            statement(fsys,ptx,lev);  //循环体处理

                               //增加循环变量步长为

                                 //将循环变量取出放在栈顶

                            gendo(lod,lev-table[i].level,table[i].adr);                                          gendo(lit,0,1);                            //将步长取到栈顶

                            gendo(opr,0,2);                            //循环变量加步长

//将栈顶的值存入循环变量

                            gendo(sto,lev-table[i].level,table[i].adr); 

                            gendo(jmp,0,cx1);                 //无条件跳转到循环开始点

/*回填循环结束点的地址，cx为else后语句执行完的位置，它正是前面未定的跳转地址*/

                            code[cx2].a=cx;                        

}

                         else

                         {

                            error(29);    //for语句中少了do

                         }

                        break;

                case downtosym:            //步长为的向下减少

                        getsymdo;

                        cx1=cx;            //保存循环开始点

//将循环判断变量取出放到栈顶                            

                        gendo(lod,lev-table[i].level,table[i].adr);                                           memcpy(nxtlev,fsys,sizeof(bool)*symnum);      //处理表达式E2

                        nxtlev[dosym]=true;                           //后跟符do

                        expressiondo(nxtlev,ptx,lev);

    /*判断循环变量条件，比如for i:=E1 downto E2 do S中，判断i是否大于等于E2，如大于等于，继续循环， 小于的话，跳出循环*/

                                                                                                       gendo(opr,0,11);   //生成比较指令，i是否大于等于E2的值

                        cx2=cx;            //保存循环结束点

//生成条件跳转指令，跳出循环，跳出的地址未知                

                        gendo(jpc,0,0);                    

                        if(sym==dosym)     //处理循环体S

                        {

                            getsymdo;

                            statement(fsys,ptx,lev);   //循环体处理

                              //增加循环变量步长为

//将循环变量取出放在栈顶

                            gendo(lod,lev-table[i].level,table[i].adr);                                          gendo(lit,0,1);                       //将步长取到栈顶

                            gendo(opr,0,3);                            //循环变量加步长

//将栈顶的值存入循环变量

                            gendo(sto,lev-table[i].level,table[i].adr);                                          gendo(jmp,0,cx1);     //无条件跳转到循环开始点

/*回填循环结束点的地址，cx为else后语句执行完的位置，它正是前面未定的跳转地址*/

                            code[cx2].a=cx;                        

}

                        else 

                        {

                            error(29);//for语句中少了do

                        }

                        break;

                }

            }

        }

    }

    else 

    {

        error(19);         //for语句后跟赋值语句，赋值语句左部是变量，缺少变量

    }

}

11. 增加运算：++ 和 -- ：

对于++和--运算符，扩充时要注意存在++,--有两个情况：1、作为语句的时候；2、作为表达式中的因子的时候.

(1) 作为语句的时候，有四种情况:

         A++  ++A   A--   --A

文法的 EBNF 表示形式为：

<自增自减语句>::=<标识符>[ ++ | -- ] | [ ++ | -- ]<标识符>

(2) 作为因子的时候，有两种情况

 a++和 a--作为因子，比如：b:=a++*a--;语句

++a 和--a 作为因子，比如：b:= --a+2*++a;语句

文法的 EBNF 表示形式为：

<表达式>::=...[ ++ | -- ]<标识符>|<标识符>[ ++ | -- ]...

其中的...表示前后都可以有其他的项或因子

(1)作为语句 ++ -- 符号分为以下两种情况考虑:

情况1对于自增自减符号置后的只需要在判断+= -=后面添加句法分析即可：

/*************后置自增符号 a++ a--类型添加代码****************************/

        else if(sym==plusplus)                                 //检测到后置++符号

        {

                gendo(lit,0,1);

                gendo(lod,lev-table[i].level,table[i].adr);  /*找到变量地址并将其值入栈*/

                gendo(opr,0,2);                             //执行加操作，

                if(i!=0)

                {

                     gendo(sto,lev-table[i].level,table[i].adr);

                }    

                getsymdo;

        }

        else if(sym==minusminus)                               //检测到后置--符号

        {

                gendo(lod,lev-table[i].level,table[i].adr);  /*找到变量地址并将其值入栈*/

                gendo(lit,0,1);                            

                gendo(opr,0,3);                               //执行减操作，

                if(i!=0)

                {

                     gendo(sto,lev-table[i].level,table[i].adr);

                }    

                getsymdo;                

        }                    

情况2对于++ --前置的需要添加因子开始符号：

        facbegsys[plusplus]=true;      /***增加符号++开始因子plusplus***/

    facbegsys[minusminus]=true;    /***增加符号--开始因子minusminus***/

/***************前置自增符号 ++a - -a类型添加代码****************************/

if(sym==plusplus)

{

    getsymdo;

    if(sym==ident)                                              //后面跟的是变量

    {

        i=position(id,*ptx);

        if(i==0)

        {

            error(11);

        }

        else

        {

            if(table[i].kind!=variable)                         //++后没跟变量，出错

            {

                error(12);

                i=0;

            }

            else                                             //++后跟变量，处理生成中间代码

            {

                if(table[i].kind==variable)

                {

                    gendo(lod,lev-table[i].level,table[i].adr);//先取值到栈顶

                    gendo(lit,0,1);                            //将值为入栈

                    gendo(opr,0,2);                            //加法，即+1，栈顶加次栈顶

                    gendo(sto,lev-table[i].level,table[i].adr);//出栈取值到内存

                    getsymdo;

                }

            }

        }

    }

}

else if(sym==minusminus)

{

    getsymdo;

    if(sym==ident)                                             //后面跟的是变量

    {

        i=position(id,*ptx);

        if(i==0)

        {

            error(11);

        }

        else

        {

            if(table[i].kind!=variable)                        //--后没跟变量，出错

            {

                error(12);

                i=0;

            }

            else                                             //--后跟变量，处理生成中间代码

            {

                if(table[i].kind==variable)                    //后跟变量

                {

                    gendo(lod,lev-table[i].level,table[i].adr);//先取值到栈顶

                    gendo(lit,0,1);                            //将值为入栈

                    gendo(opr,0,3);                            //加法，即-1，栈顶减次栈顶

                    gendo(sto,lev-table[i].level,table[i].adr);//出栈取值到内存

                    getsymdo;

                }

            }

        }

    }

}

（2）作为因子的时候也有两种情形考虑：

 添加int factor(bool*fsys,int *ptx,int lev)函数如下：

/********************如果因子可能出现b:=a++或b:=a--类型的处理******************/        if(sym==plusplus)

    {

            gendo(lit,lev-table[i].level,1);            //将值为入栈

            gendo(opr,lev-table[i].level,2);            //加法，即+1，栈顶加次栈顶

            gendo(sto,lev-table[i].level,table[i].adr); //出栈取值到内存

            gendo(lod,lev-table[i].level,table[i].adr); //取值到栈顶

            gendo(lit,0,1);

            gendo(opr,0,3);                             //栈顶值减

            getsymdo;

    }

    else if(sym==minusminus)

    {

            gendo(lit,lev-table[i].level,1);            //将值为入栈

            gendo(opr,lev-table[i].level,3);            //减法，即-1，栈顶减次栈顶

            gendo(sto,lev-table[i].level,table[i].adr); //出栈取值到内存

            gendo(lod,lev-table[i].level,table[i].adr);

            gendo(lit,0,1);

            gendo(opr,0,2);                             //栈顶值加

            getsymdo;

    } /********************************************************************************/

    /************如果因子是表达式的时候,则有可能是包含++a或者--a，如b:=++a或b:=--a ********/

    else if(sym==plusplus)

    {

            getsymdo;

            if(sym==ident)

            {

                getsymdo;

                i=position(id,*ptx);

                if(i==0)

                {

                    error(11);

                }

                else

                {

                    if(table[i].kind==variable)  //变量

                    {

                                                                   //先加后再用a

                        gendo(lod,lev-table[i].level,table[i].adr);//先取值到栈顶

                        gendo(lit,0,1);//将值为入栈

                        gendo(opr,0,2);//加法，即+1，栈顶加次栈顶

                        gendo(sto,lev-table[i].level,table[i].adr);//出栈取值到内存

                        gendo(lod,lev-table[i].level,table[i].adr); //取值到栈顶                    }

                }

            }

    }

    else if(sym==minusminus)

    {

            getsymdo;

            if(sym==ident)

            {

                getsymdo;

                i=position(id,*ptx);

                if(i==0)

                {

                    error(11);

                }

                else

                {

                    if(table[i].kind==variable)  //变量

                    {

                                                                   //先减后再用a

                        gendo(lod,lev-table[i].level,table[i].adr);//先取值到栈顶

                        gendo(lit,0,1);                            //将值为入栈

                        gendo(opr,0,3);                        //减法，即-1，栈顶减次栈顶

                        gendo(sto,lev-table[i].level,table[i].adr);//出栈取值到内存

                        gendo(lod,lev-table[i].level,table[i].adr); //取值到栈顶                    }

                }

            }

            testdo(fsys,facbegsys,23);                /*因子后有非法符号*/

    }

    /************************结束**********************************************/

四.程序测试

1.扩充赋值运算：+= 和 -=

        测试文件 “test3.pl”

       运行结果：

结果分析：

  a = 9 ，b = 3 , a+=b 结果为 12，正确，扩充成功！

2.扩充语句（Pascal的FOR语句）:

测试文件“test4.pl0”

运行结果：

结果分析：

  For i=1 to 5 do “sum+=iwrite(i)” 结果i= 1，2，3，4，5, Sum= 6

  For i=5 downto 1 do  write(i) 结果i= 5，4，3，2，1

  For循环功能扩充成功！

3.增加运算：++ 和 --。

  测试文件“test5.pl0”

   运行结果：

     结果分析：

       a = 9 b = 8  c = 7 d = 6

       f =  a++  故输出write（f）= 9，输出write（a）= 10

       ++b 输出write（b）= 9

       c--  输出write（c）= 6

       e = - -d  输出write（e）= 5，输出write（d）= 5

       ++ --功能符号测试通过！

五. 实验总结

本次课程设计主要是在读懂课本附带的PL/0 编译器程序C语言版本后进行扩展和修改相关程序功能。

通过课程设计，我对编译器的工作原理和实现机制有了实际的了解和认识，进一步培养的编译技术的设计思想，仔细阅读 PL/0 的编译程序C语言版本代码，对词法分析，句法分析在编程技巧和实际意义有了深刻的理解，从枯燥的理论学习到现在实际应用过程对于我自身知识面的提升是巨大的。语法分析、句法分析在编译原理中处于核心的地位，如何正确有效的对它们分析提取决定了编译后期工作方向，当然中间代码的如何有效的生成在编译中也是个不小的难题，特别是其中堆栈的运用，当然在理论上对于它们的理解程度大小也是决定设计调试

难度的高低。

   扩展 += -= 符号相对比较简单，只需要在语句分析模块接着赋值符号的判断添加就可以，对于for循环也是类似，只需要在语句分析模块添加对于for关键字的判断，当然要注意后继符号to 还是 downto的判断以决定步长递增还是递减。完成了基本功能扩展，我尝试了++ --符号的添加，这两个符号添加比较复杂，大体讲有两个用途情况，一个就是用在用户标识符，另一个就是在因子上也可能用到该功能，需要添加因子的功能判断，具体来讲这两个符号又有两种实现形式，分别是后置符号和前置符号，后置符号类似前面的+= -= 直接添加判断即可，前置符号则除了要添加++ --的开始因子符号集外，还得在语句分析模块添加功能处理！

  总的来说，经历了数次的调试，功能扩展算是完成了，这次课程设计使我受益匪浅，除了更深了解了编译技术，还培养了发现问题、分析问题、解决问题的能力！