CS143：编译原理实验PA1

PA1报告：Stack Machine

实验内容

基于cool语言实现一个可执行若干指令的stack machine，要求实现的栈机可以满足以下命令：

CommandMeaning
int将该整数压入栈
s将字符s压入栈
e根据栈顶元素执行相关命令，具体见下
d打印当前栈中元素（from top to bottom）
x该stack machine正常退出

对于"e"指令的执行，目前分为以下三种情况：

  • 当栈顶元素为"s"时，将"s"弹出，并将下面的两个元素进行交换
  • 当栈顶元素为"+“时，将”+"弹出，并将下面两个元素弹出求和后将和放回栈中
  • 当栈顶元素为int或栈顶元素为空时，不做任何处理

实验步骤

  1. 实验环境配置

    • 安装必要的包：
      apt-get install flex bison build-essential csh libxaw7-dev lib32stdc++6
    • 下载课程所需根文件夹(student-dist)并移动到虚拟机中
    • 将/bin目录添加到环境变量：
      export PATH=/home/user/workspace/bin:$PATH。
      注意这里仅仅是再当前打开的终端添加环境变量，该终端结束后，环境变量失效，在这里我们修改/etc/environment,将…/bin目录放入其中，即可永久生效1

  2. 实验理论准备

    • 阅读cool-manual2，掌握cool的基本语法
    • 阅读部分源码，熟悉代码如何书写，这里主要看了/examples下的
      atoi.cl, book_list.cl, graph.cl list.cl
    • 梳理栈结构与所需要的实现的功能：
      判空，长度，出栈，入栈，遍历等等

  3. 代码设计与实现

    • 采用面向对象方式进行代码设计，涉及到的类的结构图如下：

      在这里插入图片描述

    • 代码总的设计思路是，终端读入字符到StackMachine，然后StackMachine根据字符产生相应种类的StackCommand，StackMachine再执行这些相关的指令并维护自身所持有的栈。下面我们按照书写顺序来分析各个Class的代码。流程图见下：

      在这里插入图片描述

    • StackCommand：这里注释给出了该类的features含义。该类是让StackMachine执行的命令的载体，方便后续进行命令的扩展。

    class StackCommand {
	(*
      cName:         The name or string of command.
      cType:         It is designed to classify different command, but now we just need use "case".
      getName():     To get cName.
      getType():     To get cType.
      init(String):  Use a string to name command.
   *)
   cName : String;
   cType : Int;
   getName() : String {
      cName
   };
   getType() : Int {
      cType
   };
   init(commandName : String) : StackCommand {
      {
         cName <- commandName;
         self;
      }
   };   
};
    • StackExecuteCommand/StackDisplayCommand/StackStopCommand
      这里给出了三种命令，分别是执行、打印、停止的命令，这三个命令没有引入新的属性和方法，只是继承了StackCommand，并改写了cType的值，其实后面并没有用到。
    
class StackExecuteCommand inherits StackCommand {
   init(comandName : String) : StackCommand{
      {
         self@StackCommand.init(comandName);
         cType <- 0;
         self;
      }
   };
};
class StackDisplayCommand inherits StackCommand {
   init(comandName : String) : StackCommand{
      {
         self@StackCommand.init(comandName);
         cType <- 1;
         self;
      }
   };
};
class StackStopCommand inherits StackCommand {
   init(comandName : String) : StackCommand{
      {
         self@StackCommand.init(comandName);
         cType <- 2;
         self;
      }
   };
};
    • StackPushCommand中添加了一个属性"elem"，用来记录要被添加到栈中的元素（element），该命令就是来让StackMachine将需要push到栈中的元素push进去，因此需要额外引入“elem”属性。
    class StackPushCommand inherits StackCommand {
   elem : Element;      (*The element will be pushed into the stack.*)
   getElem() : Element {elem};
   initPC(comandName : String , e : Element) : StackCommand{
      {
         self@StackCommand.init(comandName);
         cType <- 3;
         elem <- e;
         self;
      }
   };
};
    • Element是栈中存放的数据类型，最开始是想要把字符串直接放入的，但是考虑到放入栈中的只能有数据和操作符（Data and Operation），并且后续可能有多种Data和Operation，因此我们定义了Element类，用来存入栈中。
    class Element {
   (*
      eName:         The name of element.
      eType:         The type of element. It is designed to classify different element but now we just need use "case".
      getName():     To get eName.
      getType():     To get eType.
      init():        Use a string to init the eName.
   *)
   eName : String;
   eType : Int;
   getName() : String {
      eName
   };
   getType() : Int {
      eType
   };
   init(elementName : String) : Element{
      {
         eName <- elementName;
         self;
      }
   };
};
    • Operation类指的是操作符，增加了新的属性"opNumber"，以及对应的获取方法getOpNum()。opNumber属性是用来表示该操作符的操作数，本次实验操作符"s"和"+"均为双目运算符；同时代码添加了initOp()方法，用来初始化一个操作符。
    class Operation inherits Element {
   opNumber : Int;
   getOpNum() : Int {
      opNumber
   };
   initOp(elementName : String , operationNumber : Int) : Operation{
      {
         self@Element.init(elementName);
         eType <- 0;
         opNumber <- operationNumber;
         self;
      }
   };
};
    • Data类就是数据类型，可以有多个具体的数据类型继承，但是这里为了简便，仅采用一个属性"dType"用来表示数据类型，这里用0表示Int型，同时增加了initData()方法，用来初始化一个数据。
     (*
  *   The types of data means:
  *   0 : int;
  *)
class Data inherits Element {
   dType : Int;
   getType() : Int {
      dType
   };
   initData(elementName : String , dataType : Int) : Data{
      {
         self@Element.init(elementName);
         eType <- 1;
         dType <- dataType;
         self;
      }
   };
};
    • 目前为之，我们已经分析了两个主要的类：StackCommand和Element，下面简要分析Stack的组成。这里参考的是list.cl中列表的实现，有点类似于c语言中的链表，因此我们也是通过实现一个链表，然后通过对链表的维护，实现一个栈，这里栈中基本的数据类型就是Element。
    • Link/LinkCons：这两个类主要是为了构成链表，如同c语言中结构体Node来实现链表，具体可以参考/examples/list.cl
    class Link {
   isNil() : Bool {true};
   head() : Element {{abort();new Element.init("NULL");}};
   tail() : Link {{abort();self;}};
   setRest(r : Link) : Link {{abort(); new LinkCons.init(head(),tail());}};
   cons(e : Element) : Link {
      (new LinkCons).init(e,self)
   };

};
class LinkCons inherits Link{
   elem : Element;
   rest : Link; 
   isNil() : Bool {false};
   head() : Element {elem};
   tail() : Link {rest};
   setRest(r : Link) : Link{
      rest <- r
   };
   init(e : Element , s : Link) : Link{
      {
         elem <- e;
         rest <- s;
         self;
      }
   };
};
    • Stack：Stack继承IO，是为了方便输出。这里主要是通过对链表的维护来实现的。具体支持的方法如下
      • 判断是否为空： isNil()
      • 获取顶部元素： top()
      • 弹出顶部元素： pop()
      • 压入元素： push()
      • 获取长度： getLength()
      • 打印栈中元素： display()
    class Stack inherits IO{
   top : Element;
   link : Link;
   length : Int;
   isNil() : Bool{link.isNil()};
   getLength() : Int{length};
   top() : Element {top};
   pop() : Bool {
      let temp : Link , void : Link in {
         if isNil() then false
         else {
            temp <- link.tail();
            link.setRest(void);
            link <- temp;
            if length = 1 then 1 else top <- link.head() fi;
            length <- length - 1;
            true;
         } fi;
      }
   };
   push(e : Element): Bool {
      {
         link <- link.cons(e);
         top <- e;
         length <- length + 1;
         true;
      }
   };
   init() : Stack {
      {
         link <- (new Link);
         length <- 0;
         top <- (new Element);
         self;
      }
   };
   display() : Stack {
      {
         let i : Int <- 0 , l : Link <- link in {
            while i < length loop {
               out_string(l.head().getName());
               out_string("\n");
               i <- i + 1;
               l <- l.tail();
            } pool;
         };
         self;
      }
   };
};
    • StackMachine：该类实现对命令和元素的创建、执行以对栈的维护和操作。该类主要支持的方法如下：
      • elementCreate(String): 根据读入的字符串创建相关的元素（操作符或者数据）
      • commandCreate(String): StackCommand类的工厂函数，用来创建相应的命令
      • execute(StackCommand): 用来执行相关命令如停止、打印、Push、执行。这里指的一提的是，对于StackExecuteCommand，我们会根据顶部元素为Operation（执行executeOp()方法）或Data（执行executeData()方法）执行不同的操作。
      • run(): StackMachine的运行函数，用来显示"<"、创建命令、执行命令等。
    class StackMachine inherits IO {
   stack : Stack;

   init() : StackMachine {
      {
         stack <- (new Stack).init();
         self;
      }
   };

   commandCreate(cmdString : String) : StackCommand{
      if cmdString = "e" then {
         new StackExecuteCommand.init(cmdString);
      } else if cmdString = "d" then {
         new StackDisplayCommand.init(cmdString);
      } else if cmdString = "x" then {
         new StackStopCommand.init(cmdString);
      } else {
         new StackPushCommand.initPC(cmdString,elementCreate(cmdString));
      } fi fi fi
   };

   elementCreate(cmdString : String) : Element {
      if cmdString = "+" then (new Operation).initOp(cmdString,2) else
      if cmdString = "s" then (new Operation).initOp(cmdString,2) else
      (new Data).initData(cmdString,0) fi fi
   };

   execute(scmd : StackCommand) : Bool {
      let state_code : Bool in 
      {   
      case scmd of 
         temp : StackExecuteCommand => {
            if stack.isNil() then 1 else
            let elem : Element , i : Int in {
               elem <- stack.top();
               stack.pop();
               case elem of 
                  op : Operation => execute_op(op);
                  data : Data => execute_data(data);
               esac;
            } fi;
            state_code <- true;           
         };
         temp : StackDisplayCommand => {
            stack.display();
            state_code <- true;
         };
         temp : StackStopCommand => {
            state_code <- false;
         };
         temp : StackPushCommand => {
            stack.push(temp.getElem());
            state_code <- true;
         };
      esac;
      state_code;
      }
   };

   execute_op(op : Operation) : StackMachine{
      {
         if op.getOpNum() = 2 then {
            let ad : Int , bd : Int , at : Int , bt : Int , c : Int , d : Int in {
               if op.getName() = "+" then {
                  ad <- (new A2I).a2i(stack.top().getName());
                  at <- stack.top().getType();
                  stack.pop();
                  bd <- (new A2I).a2i(stack.top().getName());
                  bt <- stack.top().getType();
                  stack.pop();
                  c <- ad+bd;
                  if at < bt then d <- at else d <- bt fi;
                  stack.push(new Data.initData((new A2I).i2a(c),d));
               } else if op.getName() = "s" then {
                  let a : Element , b : Element in {
                     a <- stack.top();
                     stack.pop();
                     b <- stack.top();
                     stack.pop();
                     stack.push(a);
                     stack.push(b);
                  };
               } else {
                  out_string("No operation: ");
                  out_string(op.getName());
                  out_string("\n");
               }fi fi;
               
            };
         } else if op.getOpNum() = 1 then {
            op.getOpNum();
         } else {
            op.getOpNum();
         } fi fi ;
         self;
      }
   };

   execute_data(data : Data) : StackMachine{
      self
   };

   run() : StackMachine {
      {
         let cmd : StackCommand , str : String in {
            let state_code : Bool <- true in {
               while state_code loop {
                  out_string(">");
                  str <- in_string();
                  cmd <- commandCreate(str);
                  state_code <- execute(cmd);
               } pool;
            };
         };
         self;
      }
   };
};
    • Main：程序的入口，只需创建一个StackMachine并运行它即可
    class Main inherits IO {

   machine : StackMachine;

   main() : Object {
      {
         machine <- (new StackMachine).init();
         machine.run();
      }

   };
};

实验运行和结果

  1. 通过键入实验中给的示例，可以正常运行
  2. 实验结果截图：

实验总结

对于本次实验，两个重点：

  1. cool的学习与使用
  2. 实现一个Stack Machine

对于cool语言的学习，目前仅仅学到了基础语法和class的使用，对于后面讲的那些类型判断和检测还有其他比较深入的东西还未尝接触。通过对cool的学习和使用，我感觉cool语言已经是比较完善的面向对象语言了，并且也不算复杂，熟悉之后很容易掌握，但是也有一部分缺点，就比如对一些局部变量的使用，必须使用let语句进行限定，不够便捷等等。总结来说，简单易懂但不够方便。

对Stack Machine的实现上，这本身其实是一个很简单的任务，只需创建一个存储字符串的栈结构，然后进行对栈进行相应操作即可，这里我们之所以采用这么复杂的方法，是为了方便指令的扩展以及其他操作的扩展，同时也使得代码更容易理解，更容易维护等等。

  1. 参考博客：https://blog.csdn.net/lau_jw/article/details/126053815 ↩︎

  2. 参考翻译：https://blog.csdn.net/weixin_30455067/article/details/97515361 ↩︎