構建一個類似C的解釋器使用Scala

Question

我需要實現類C解釋器。這裏是語法。

Program ::= Commandlist 
Commandlist ::= Command | Command; Commandlist; 
Command ::= Left = Expression | while Expression : Commandlist end | print Left 
Expression ::= Number | (Expression1 + Expression2) | (Expression1 - Expression2) | Left | &Left 
Left ::= Variable | *Left 
Number ::= string of digits 
Variable ::= string of letters 

這裏是解釋器使用的操作樹。

PTREE ::= [ CTREE+ ] 
CTREE ::= Assign(LTREE, ETREE) | While(ETREE, CLIST) | Print(LTREE) 
ETREE ::= Num(String) | Add(ETREE, ETREE) | Sub(ETREE, ETREE) | At(LTREE) | Amph(LTREE) 
LTREE ::= Var(String) | Star(LTREE) 

這裏是實現類C解釋器的代碼。

trait OpTree { 
    sealed abstract class Ltree 
    case class Var(x: String) extends Ltree 
    case class Star(l: Ltree) extends Ltree 

    sealed abstract class Etree 
    case class Num(s: String) extends Etree 
    case class Add(e1: Etree, e2: Etree) extends Etree 
    case class Sub(e1: Etree, e2: Etree) extends Etree 
    case At(l: Ltree) extends Etree 
    case Amph(l: Ltree) extends Etree 

    sealed abstract class Ctree 
    case class Assign(l: Ltree, e: Etree) extends Ctree 
    case class While(e: Etree, c: List[Ctree]) extends Ctree 
    case class Print(l: Ltree) extends Ctree 
} 

import scala.util.parsing.combinator.JavaTokenParsers 

object MiniC extends JavaTokenParsers with OpTree { 
    def parse(source: String): List[Ctree] = 
    parseAll(prog, source) match { 
    case Success(optree,_) => optree 
    case _ => throw new Exception("Parse error!") 
    } 
    def prog: Parser[List[Ctree]] = commlist 
    def commlist: Parser[List[Ctree]] = rep1sep(comm, ";") 
    def comm: Parser[Ctree] = left~("="~>expr) ^^ 
          { case l~e => Assign(l, e) } | 
          "print"~>left ^^ 
          { case l => Print(l) } | 
          ("while"~>expr<~":")~(commlist<~"end") ^^ 
          { case e~cs => While(e, cs) } 
    def expr: Parser[Etree] = wholeNumber ^^ (Num(_)) | 
          "("~>expr~op<~expr")" ^^ 
          { case e1~"+"~e2 => Add(e1, e2) 
           case e1~"-"~e2 => Sub(e1, e2) } | 
           left ^^ (At(_)) | 
          "&"~>left ^^ (Amph(_)) 
    def left: Parser[Ltree] = ident ^^ (Var(_)) | 
          "*"~>left ^^ (Star(_)) 
    def op: Parser[String] = "+" | "-" 

    //Interpreter 
    val memory = scala.collection.mutable.ArrayBuffer.empty[Int] 
    var env = Map.empty[String, Int] 
    def interpretPTREE(p: List[Ctree]): Unit = interpretCLIST(p) 
    def interpretCLIST(cs: List[Ctree]): Unit = 
    for(c <- cs) yield interpretCTREE(c) 
    def interpretCTREE(c: Ctree): Unit = c match { 
    case Assign(l, e) => env + (interpretLTREE(l).toString -> interpretETREE(e)) 
    case Print(l) => 
     if(env.contains(interpretLTREE(l).toString)) println(env(interpretLTREE(l).toString)) 
     else throw new Exception("Error: " + l + " is undefined.") 
     env 
    case While(e, cs) => 
     if (interpretETREE(e) != 0) 
     interpretCTREE(c) 
     else env 
    } 
    def interpretETREE(e: Etree): Int = e match { 
    case Num(s) => s.toInt 
    case Add(e1, e2) => interpretETREE(e1) + interpretETREE(e2) 
    case Sub(e1, e2) => interpretETREE(e1) - interpretETREE(e2) 
    case At(l) => interpretLTREE(l) 
    case Amph(l) => interpretLTREE(l) 
    } 
    def interpretLTREE(l: Ltree): Int = l match { 
    case Var(x) => if (env.contains(x)) env(x) 
        else throw new Exception("Error: " + x + " is undefined.") 
    case Star(l) => if (memory.contains(l)) memory(interpretLTREE(l)) 
        else throw new Exception("Error: " + l + " is undefined.") 
    } 
    def main(args: Array[String]): Unit = { 
    try { 
     val source = args(0) 
     println("input : " + source) 
     val optree = parse(source) 
     println("optree : " + optree) 
     interpretPTREE(optree) 
     println("final memory : " + memory) 
     println("final namespace : " + env) 
    } 
    catch { case e: Exception => println(e)} 
    } 
} 

本方案的曖昧部分是interpretCTREE，所述interpretETREE和interpretLTREE的定義部分。如果我的

y = 4; z = &y; x = (7 + *z); *z = (y + 1) 

參數運行這個程序optree的程序結果應該是這樣的：

List(Assign(Var("x"),Num("4")), 
    Assign(Var("z"),Amph(Var("y"))), 
    Assign(Var("x"),Add(Num("7"),Star(Var("z")))), 
    Assign(Star(Var("z")),Add(Var("y"),Num("1")))) 

不過，我有一個結果是這樣的：

List(Assign(Var("x"),Num("4")), 
    Assign(Var("z"),Amph(Var("y"))), 
    Assign(Var("x"),Add(Num("7"),At(Star(Var("z"))))), 
    Assign(Star(Var("z")),Add(At(Var("y")),Num("1")))) 

加，我想查看內存的值和env，但結果中包含錯誤消息。

java.lang.Exception: Error: y is undefined. 

那麼，我該如何解決這個問題，以獲得正確的選擇權，內存的最終價值和環境？

Answer 1

的問題（一次明顯的代碼錯誤是固定的），似乎在這裏躺

def interpretCTREE(c: Ctree): Unit = c match { 
    case Assign(l, e) => env + (interpretLTREE(l).toString -> interpretETREE(e)) 
    /* ... */ 

根據l是Var(x)或Star(l)，這應該表現不同。

如果l是Var(x)，那麼，如果環境不包含x，應創建一個新的存儲位置，環境應進行相應的更新，然後將值interpretETREE(e)應存放在這個位置。

如果l是Star(l)，則應該評估l並且值interpretETREE(e)應該存儲在通過該評估獲得的存儲位置處。

另外，在我看來，程序創建的選擇是正確的，而第一個提到的（「應該看起來像這個」）不符合語法。

我試圖想出下面的一些固定代碼（沒有保證給出，我沒有正確測試它）。我所做的更改由評論標記。另外請注意，您的interpretCTREE和相關方法的編寫方式好像它們會返回一個環境一樣，但由於未使用此方法，因此我省略了該部分。

trait OpTree { 
    sealed abstract class Ltree 
    case class Var(x: String) extends Ltree 
    case class Star(l: Ltree) extends Ltree 

    sealed abstract class Etree 
    case class Num(s: String) extends Etree 
    case class Add(e1: Etree, e2: Etree) extends Etree 
    case class Sub(e1: Etree, e2: Etree) extends Etree 
    // typo fixed, "class" forgotten 
    case class At(l: Ltree) extends Etree 
    case class Amph(l: Ltree) extends Etree 

    sealed abstract class Ctree 
    case class Assign(l: Ltree, e: Etree) extends Ctree 
    case class While(e: Etree, c: List[Ctree]) extends Ctree 
    case class Print(l: Ltree) extends Ctree 
} 

import scala.util.parsing.combinator.JavaTokenParsers 

object MiniC extends JavaTokenParsers with OpTree { 
    // Parser 
    def parse(source: String): List[Ctree] = 
    parseAll(prog, source) match { 
    case Success(optree,_) => optree 
    case _ => throw new Exception("Parse error!") 
    } 
    def prog: Parser[List[Ctree]] = commlist 
    def commlist: Parser[List[Ctree]] = rep1sep(comm, ";") 
    def comm: Parser[Ctree] = left~("="~>expr) ^^ 
          { case l~e => Assign(l, e) } | 
          "print"~>left ^^ 
          { case l => Print(l) } | 
          ("while"~>expr<~":")~(commlist<~"end") ^^ 
          { case e~cs => While(e, cs) } 
    // typo fixed "~" forgotten in "expr~op~expr" 
    def expr: Parser[Etree] = wholeNumber ^^ (Num(_)) | 
          "("~>expr~op~expr<~")" ^^ 
          { case e1~"+"~e2 => Add(e1, e2) 
           case e1~"-"~e2 => Sub(e1, e2) } | 
           left ^^ (At(_)) | 
          "&"~>left ^^ (Amph(_)) 
    def left: Parser[Ltree] = ident ^^ (Var(_)) | 
          "*"~>left ^^ (Star(_)) 
    def op: Parser[String] = "+" | "-" 

    //Interpreter 
    // new: fix some memory size (for test purposes) 
    val MEMORY_SIZE = 16 
    val memory = new Array[Int](MEMORY_SIZE) 
    // new: represents first unused memory address 
    var allocatedMemorySize = 0 
    var env = Map.empty[String, Int] 
    // new: simple memory allocation 
    def allocateMemory(variableName : String) { 
    env += (variableName -> allocatedMemorySize) 
    allocatedMemorySize += 1 
    } 
    def interpretPTREE(p: List[Ctree]) { 
    interpretCLIST(p) 
    } 
    def interpretCLIST(cs: List[Ctree]) { 
    for(c <- cs) interpretCTREE(c) 
    } 
    def interpretCTREE(c: Ctree) { 
    c match { 
     case Assign(l, e) => 
     // new: allocate memory for variables if necessary 
     l match { 
      case Var(x) => if (!env.contains(x)) allocateMemory(x) 
      case _ => 
     } 
     // new: store evaluated expression at evaluated address 
     memory(interpretLTREE(l)) = interpretETREE(e) 
     // new: handling print 
     case Print(l) => 
     println(memory(interpretLTREE(l))) 
     // new: handling while properly 
     case While(e, cs) => 
     while (interpretETREE(e) != 0) 
      interpretCLIST(cs) 
    } 
    } 
    def interpretETREE(e: Etree): Int = e match { 
    case Num(s) => s.toInt 
    case Add(e1, e2) => interpretETREE(e1) + interpretETREE(e2) 
    case Sub(e1, e2) => interpretETREE(e1) - interpretETREE(e2) 
    // new: at returns the value that is stored in memory at the address represented by l 
    case At(l) => memory(interpretLTREE(l)) 
    // new: amph returns the address that is represented by l 
    case Amph(l) => interpretLTREE(l) 
    } 
    // new: evaluates l to memory address it represents 
    def interpretLTREE(l: Ltree): Int = l match { 
    case Var(x) => if (env.contains(x)) 
        env(x) 
        else 
        throw new Exception("Error: " + x + " is undefined.") 
    case Star(l) => val memoryLocation = interpretLTREE(l) 
        if (0 <= memoryLocation && memoryLocation < MEMORY_SIZE) 
         memory(memoryLocation) 
        else 
         throw new Exception("Error: " + l + " is out of memory bounds.") 
    } 
    def main(args: Array[String]): Unit = { 
    try { 
     val source = args(0) 
     println("input : " + source) 
     val optree = parse(source) 
     println("optree : " + optree) 
     interpretPTREE(optree) 
     // new: nicer printing of memory 
     println("final memory : " + (memory mkString ",")) 
     println("final namespace : " + env) 
    } 
    catch { case e: Exception => println(e)} 
    } 
} 

最後，這裏有一個簡單的測試程序計算斐波那契數

scala MiniC "i = 5; x = 1; y = 1; print x; while i: i = (i - 1); z = y; y = (x + y); x = z; print x end; print y"