Создайте язык программирования с помощью Scala Parser Combinators

Давайте немного рассмотрим эту «программную» функцию. Вы заметите, что возвращаемое значение — Parser [Program]. Сняв сложность, мы на самом деле просто возвращаем экземпляр класса Program, который мы определим позже. Этот класс Program является одним из простых старых классов Scala, которые относятся к шагу 3. Итак, вы заметите, что каждое из этих правил будет просто возвращать экземпляр одного из этих классов, каждый из которых представляет собой конструкцию в нашем языке программирования.

Следующая часть этого правила гласит (rep (function) <~ («main» ~ «:»)) . Это означает, что у нас может быть повторяющийся список функций (например, rep (function)  ) на нашем языке. Затем за этим списком функций следует основное: зарезервированное слово. Затем следует кодовый блок. Обратите внимание, что кодовый блок и функция — это просто правила парсера, которые мы определим позже в нашем парсере.

Последняя часть этого правила — ^^ {…}.  Оператор ^^ в Scala просто сообщает парсеру, что ниже приведен код Scala, который мы хотим выполнить при запуске этого правила парсера. Код Scala внутри {…} просто возвращает экземпляр класса Program, конструктор которого принимает список функций и кодовый блок.

Теперь мы можем повторить этот процесс для каждого правила парсера. Каждое правило будет определять грамматику (или разрешенные ключевые слова и текст), а также тип возвращаемого значения. Когда вы думаете о языке программирования, он содержит такие конструкции, как циклы, условные выражения, вызовы функций и т. Д. Итак, если мы добавим правила синтаксического анализа для каждой из этих конструкций, мы получим следующий SmallLanguageParser:

class SmallLanguageParser extends StandardTokenParsers {
  lexical.reserved += ("var", "println", "loop", "times", "endloop", "if",
    "then", "else", "endif", "func", "return", "endfunc", "main")
  lexical.delimiters += ("*", "/", "%", "+", "-", "(", ")", "=",
    "<", ">", "==", "!=", "<=", ">=", ",", ":")

  def program: Parser[Program] = (rep(function) <~ ("main" ~ ":")) ~ codeblock ^^ {
    case f ~ c => new Program(f, c)
  }

  def function: Parser[Function] = ("func" ~> ident) ~ ("(" ~> arguments) ~
    (")" ~> codeblock) ~ opt(returnStatement) <~ "endfunc" ^^ {
      case a ~ b ~ c ~ None => new Function(a, b, c, Number(0))
      case a ~ b ~ c ~ d => new Function(a, b, c, d.get)
    }

  def returnStatement: Parser[Expr] = "return" ~> expr ^^ {
    e => e
  }

  def arguments: Parser[Map[String, Int]] = repsep(ident, ",") ^^ {
    argumentList =>
      {
        (for (a <- argumentList) yield (a -> 0)) toMap
      }
  }

  def codeblock: Parser[List[Statement]] = rep(statement) ^^ { a => a }

  def statement: Parser[Statement] = positioned(variableAssignment | outStatement |
    loopStatement | ifStatement | functionCall | outStatement) ^^ { a => a }

  def variableAssignment: Parser[VariableDefinition] = "var" ~> ident ~ "=" ~
    positioned(functionCall | expr) ^^ { case a ~ "=" ~ b => { new VariableDefinition(a, b) } }

  def outStatement: Parser[PrintStatement] = "println" ~> positioned(expr) ^^ {
    case a => new PrintStatement(a)
  }

  def loopStatement: Parser[LoopStatement] = ("loop" ~> iterations <~ "times") ~
    codeblock <~ "endloop" ^^ {
      case i ~ s => {
        new LoopStatement(i, s)
      }
    }

  def ifStatement: Parser[IfStatement] = conditional ~ codeblock ~
    opt("else" ~> codeblock) <~ "endif" ^^ {
      case a ~ b ~ c => {
        c match {
          case None => new IfStatement(a, b, List())
          case _ => new IfStatement(a, b, c.get)
        }
      }
    }

  def conditional: Parser[Condition] = "if" ~ "(" ~> condition <~ ")" ~ "then"

  def condition: Parser[Condition] = positioned(expr) ~
    ("<" | ">" | "==" | "!=" | "<=" | ">=") ~ positioned(expr) ^^ {
      case a ~ b ~ c => {
        new Condition(b, a, c)
      }
    }

  def iterations: Parser[Int] = numericLit ^^ { _ toInt }

  def functionCall: Parser[FunctionCall] = ((ident) <~ "(") ~
    functionCallArguments <~ ")" ^^ {
      case a ~ l => new FunctionCall(a, l)
    }

  def functionCallArguments: Parser[Map[String, Expr]] =
    repsep(functionArgument, ",") ^^ {
      _ toMap
    }

  def functionArgument: Parser[(String, Expr)] = (ident <~ "=") ~ expr ^^ {
    case a ~ b => (a, b)
  }

  def expr: Parser[Expr] = term ~ rep(("+" | "-") ~ term) ^^ {
    case a ~ List() => a
    case a ~ b => {
      def appendExpression(c: Operator, p: Operator): Operator = {
        p.left = c
        p
      }

      var root: Operator = new Operator(b.head._1, a, b.head._2)

      for (f <- b.tail) {
        var parent =
          f._1 match {
            case "+" => new Operator("+", null, f._2)
            case "-" => Operator("-", null, f._2)
          }

        root = appendExpression(root, parent)
      }

      root
    }
  }

  def term: Parser[Expr] = multiplydividemodulo ^^ { l => l } | factor ^^ {
    a => a
  }

  // note that "rep" returns a List
  def multiplydividemodulo: Parser[Expr] = factor ~ rep(("*" | "/" | "%") ~ factor) ^^ {

    case a ~ List() => a
    case a ~ b => {
      def appendExpression(e: Operator, t: Operator): Operator = {
        t.left = e.right
        e.right = t
        t
      }

      var root: Operator = new Operator(b.head._1, a, b.head._2)
      var current = root

      // for each of these, i'm just building up the parse tree
      for (f <- b.tail) {
        var rightOperator =
          f._1 match {
            case "*" => Operator("*", null, f._2)
            case "/" => Operator("/", null, f._2)
            case "%" => Operator("%", null, f._2)
          }

        current = appendExpression(current, rightOperator)
      }

      root
    }
  }

  def factor: Parser[Expr] = numericLit ^^ { a => Number(a.toInt) } |
    "(" ~> expr <~ ")" ^^ { e => e } |
    ident ^^ { new Identifier(_) }

  def parseAll[T](p: Parser[T], in: String): ParseResult[T] = {
    phrase(p)(new lexical.Scanner(in))
  }
}

class Interpreter(program: Program) {
  var currentScope = new Scope("global", null)

  def run() {
    walk(program.statements)
  }

  private def getVariable(ident: Identifier): Expr = {
    var s: Scope = currentScope

    while ((!s.name.equals("global")) && !s.variables.contains(ident.name)) {
      s = s.parentScope
    }

    if (s.variables.contains(ident.name)) s.variables(ident.name)
    else {
      sys.error("Error: Undefined variable " + ident.name +
        " at position [" +
        ident.pos.column + "] on line: " +
        ident.pos.line)
    }
  }

  private def calculateExpr(e: Expr): Int = {
    e match {
      case Number(value) => value
      case Identifier(name) => {
        calculateExpr(getVariable(e.asInstanceOf[Identifier]))
      }
      case Operator(op, left, right) => {
        op match {
          case "*" => calculateExpr(left) * calculateExpr(right)
          case "/" => calculateExpr(left) / calculateExpr(right)
          case "%" => calculateExpr(left) % calculateExpr(right)
          case "+" => calculateExpr(left) + calculateExpr(right)
          case "-" => calculateExpr(left) - calculateExpr(right)
        }
      }
    }
  }

  private def isConditionTrue(condition: Condition): Boolean = {
    val a = calculateExpr(condition.left)
    val b = calculateExpr(condition.right)

    condition.op match {
      case "==" => (a == b)
      case "!=" => (a != b)
      case "<=" => (a <= b)
      case "<" => (a < b)
      case ">=" => (a >= b)
      case ">" => (a > b)
    }
  }

  private def executeFunction(f: Function, arguments: Map[String, Expr]) {
    currentScope = new Scope(f.name, currentScope)

    for (v <- arguments) currentScope.variables(v._1) = v._2

    walk(f.statements)

    currentScope = currentScope.parentScope
  }

  private def walk(tree: List[Statement]) {
    if (!tree.isEmpty) {
      tree.head match {
        case FunctionCall(name, values) => {
          val f = program.functions.filter(x => x.name == name)

          if (f.size < 1) sys.error("Error: Undefined function '" +
            name + "' being called at position [" +
            tree.head.pos.column + "] on line: " +
            tree.head.pos.line)
          else {
            executeFunction(f(0), values)

            walk(tree.tail)
          }
        }
        case VariableDefinition(name, value) => {
          // push this variable into scope
          if (value.isInstanceOf[FunctionCall]) {
            val functionCall = value.asInstanceOf[FunctionCall]
            val function = program.functions.filter(x => x.name == functionCall.name)

            // check if proc is defined and if not throw an error
            if (function.size < 1) sys.error("Error: Undefined function '" +
              functionCall.name + "' being called at position [" +
              tree.head.pos.column + "] on line: " +
              tree.head.pos.line)
            else {
              executeFunction(function(0), functionCall.values)

              currentScope = currentScope.parentScope

              // assign the return value of the function to the variable
              currentScope.variables(name) = function(0).returnValue
            }
          } else {
            currentScope.variables(name) = value
          }

          walk(tree.tail)
        }
        case PrintStatement(value) => {
          println(calculateExpr(value))
          walk(tree.tail)
        }
        case LoopStatement(iterations, statements) => {
          currentScope = new Scope("", currentScope)

          for (i <- 0 until iterations) walk(statements)

          currentScope = currentScope.parentScope

          walk(tree.tail)
        }
        case IfStatement(condition, trueBranch, falseBranch) => {
          currentScope = new Scope("", currentScope)

          if (isConditionTrue(condition)) walk(trueBranch) else walk(falseBranch)

          currentScope = currentScope.parentScope

          walk(tree.tail)
        }
        case _ => ()
      }
    }
  }
}

class Condition(val op: String, val left: Expr, val right: Expr)

object SmallLanguage {
  def main(args: Array[String]) {
    val inputFile = Source.fromFile("scripts/program.small")
    val inputSource = inputFile.mkString

    val parser = new SmallLanguageParser
    parser.parseAll(parser.program, inputSource) match {
      case parser.Success(r, n) => {
        val interpreter = new Interpreter(r)

        try {
          interpreter.run
        } catch {
          case e: RuntimeException => println(e.getMessage)
        }
      }
      case parser.Error(msg, n) => println("Error: " + msg)
      case parser.Failure(msg, n) => println("Error: " + msg)
      case _ =>
    }
  }
}