入力されたプログラムを構文解析し、下図のような構文木を構築し（必ずしも実行に必要としないノードは構築を省略する場合あり）、入力ケースごとに変数・定数の初期値が設定され、この構文木を(制御構文を除き、基本的には)根から順番に辿るように実行します。

StLang の実行環境サンプル（後述）は、 Lark を用いて実装しています。

Lark - a parsing toolkit for Python : https://github.com/lark-parser/lark

入力されたプログラムから構文木への変換は以下のようなルールで行われます。

EBNF（拡張バッカス・ナウア記法） + 正規表現 + α による（パーサジェネレータ Lark 向け）StLang構文定義:

?start: program
program: statements "return" value lineends
?value: number | const_k | const_n | variable
number: /[0-9]+/
const_k: "K"
const_n: "N"
variable: "$" var_ident
var_ident: /[0-9]/
?statements: statement*
?statement: assignment | branching | repeating | lineend
assignment: "$" var_ident "=" expression lineend
?expression: value | add | sub | mul | div | rem
add: value "+" value
sub: value "-" value
mul: value "*" value
div: value "/" value
rem: value "%" value
branching: "if" condition lineend statements "end" lineend
repeating: "while" condition lineend statements "end" lineend
?condition: eq | ne | ge | le | gt | lt
eq: value "==" value
ne: value "!=" value
ge: value ">=" value
le: value "<=" value
gt: value ">" value
lt: value "<" value
?lineends: lineend* ST_COMMENT?
?lineend: ST_COMMENT? CR? LF
ST_COMMENT: "#" /[^\n]*/
CR : /\r/
LF : /\n/
WS_INLINE: (" "|/\t/)+
%ignore WS_INLINE

class StLangInterpreter(lark.visitors.Interpreter):
    """StLang Interpreter"""
    def __init__(self, k=0, n=0) -> None:
        super().__init__()
        assert 0 <= int(k) < 2**64 and 0 <= int(n) < 2**64, "OutOfRangeNumber"
        self.env = { 'C': 0, 'K': int(k), 'N': int(n), '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0 }
    def program(self, tree) -> int:
        self.visit(tree.children[0]) # statements
        return self.visit(tree.children[1]) # value
    def number(self, tree) -> int:
        ret = int(tree.children[0].value)
        assert 0 <= ret < 2**64, "OutOfRangeNumber"
        return ret
    def const_k(self, _tree) -> int:
        return self.env['K']
    def const_n(self, _tree) -> int:
        return self.env['N']
    def variable(self, tree) -> int:
        return self.env[self.visit(tree.children[0])]
    def var_ident(self, tree) -> str:
        return str(tree.children[0].value)
    def assignment(self, tree) -> None:
        self.env['C'] += 1
        assert self.env['C'] <= 1000, "StepLimitExceed"
        self.env[self.visit(tree.children[0])] = self.visit(tree.children[1])
    def add(self, tree) -> int:
        ret = self.visit(tree.children[0]) + self.visit(tree.children[1])
        assert 0 <= ret < 2**64, "OutOfRangeNumber"
        return ret
    def sub(self, tree) -> int:
        ret = self.visit(tree.children[0]) - self.visit(tree.children[1])
        assert 0 <= ret < 2**64, "OutOfRangeNumber"
        return ret
    def mul(self, tree) -> int:
        ret = self.visit(tree.children[0]) * self.visit(tree.children[1])
        assert 0 <= ret < 2**64, "OutOfRangeNumber"
        return ret
    def div(self, tree) -> int:
        lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
        assert 0 < rhs, "OutOfRangeNumber"
        return lhs // rhs
    def rem(self, tree) -> int:
        lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
        assert 0 < rhs, "OutOfRangeNumber"
        return lhs % rhs
    def branching(self, tree) -> None:
        self.env['C'] += 1
        assert self.env['C'] <= 1000, "StepLimitExceed"
        if self.visit(tree.children[0]): # condition
            self.visit(tree.children[2]) # statements
    def repeating(self, tree) -> None:
        while True:
            self.env['C'] += 1
            assert self.env['C'] <= 1000, "StepLimitExceed"
            if not self.visit(tree.children[0]): # condition
                break
            self.visit(tree.children[2]) # statements
    def eq(self, tree) -> bool:
        return self.visit(tree.children[0]) == self.visit(tree.children[1])
    def ne(self, tree) -> bool:
        return self.visit(tree.children[0]) != self.visit(tree.children[1])
    def ge(self, tree) -> bool:
        return self.visit(tree.children[0]) >= self.visit(tree.children[1])
    def le(self, tree) -> bool:
        return self.visit(tree.children[0]) <= self.visit(tree.children[1])
    def gt(self, tree) -> bool:
        return self.visit(tree.children[0]) > self.visit(tree.children[1])
    def lt(self, tree) -> bool:
        return self.visit(tree.children[0]) < self.visit(tree.children[1])

StLang の構文と処理の解説と、 EBNF（拡張バッカス・ナウア記法） + 正規表現 を主に用いた構文定義、Lark によるインタプリタの実装例を併記します。ソースコード全体は $1000$ 行以下の構文 program で記述されていなければなりません。ソースコードが以下のように再帰的に定義された、正しい構文で記述されていない場合、WAとなります。

プログラムを実行するコンピュータは、非負整数の列 $(V_0,V_1,V_2,\ldots,V_9)$ および非負整数 $C$ をもつとします。

テストケース毎に、テストケースから与えられた $K,N$ の値が定数値K,Nに設定され、変数 $V_0$～$V_9$ ($0～$9) の値は $0$ に初期化され、実行ステップカウンター $C$ の値は $0$ に初期化されます。実行中に $C$ の値が $1000$ より大きくなった場合、WAとなります。

    def __init__(self, k=0, n=0) -> None:
        super().__init__()
        assert 0 <= int(k) < 2**64 and 0 <= int(n) < 2**64, "OutOfRangeNumber"
        self.env = { 'C': 0, 'K': int(k), 'N': int(n), '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0 }

構文定義の行頭に ? が付いているのは、構文木上でノードの構成を省略するものに付けられたもので、ここでは、子要素の実装をそのまま用いるため、それ自体では直接の機能実装が行われないものに適用しています。

"～" で囲まれている部分は、字句文字列である事を表す

/～/ で囲まれている部分は、正規表現による文字列マッチングの指定

? を後に付けた場合、 0回～1回 繰り返されることを示す（つまり、省略可能である事を示す）

* を後に付けた場合、 0回以上 繰り返されることを示す（省略可能な繰り返し）

+ を後に付けた場合、 1回以上 繰り返されることを示す（繰り返し）

| で併記した場合、いずれか1つが選ばれること (choice) を示す

/[0-9]+/ の正規表現は、数字1文字以上の文字列に当てはまることを示す

/[0-9]/ の正規表現は、数字1文字の文字列に当てはまることを示す

"#" /[^\n]*/ は、 # 文字から始まる、改行文字を含まない任意長の文字列に当てはまることを示す

/\r/ の正規表現は、キャートリッジリターン制御文字に当てはまることを示す

/\n/ の正規表現は、改行文字に当てはまることを示す

(" "|/\t/)+ は、半角空白文字もしくは水平タブ文字1文字以上に当てはまることを示す

• start: 【概要】構文木のroot nodeの指定 【処理】 program の実行

  ?start: program

• program: 【概要】プログラム全体の定義 【処理】 statements を実行した後に value の値を出力して終了する

  program: statements "return" value lineends

      def program(self, tree) -> int:
          self.visit(tree.children[0]) # statements
          return self.visit(tree.children[1]) # value
  

• value: 【概要】整数値 【構文】number, const_k, const_n, variable のいずれか 【処理】いずれか対応する値を返す

  ?value: number | const_k | const_n | variable

• number: 【概要】10進整数値 【例外】値が $0$ 以上 $2^{64}-1=18446744073709551615$ 以下でなければ WA

  const_k: 【概要】定数 $K$ 【処理】テストケース毎に決まった値を返す

  const_n: 【概要】定数 $N$ 【処理】テストケース毎に決まった値を返す

  variable: 【概要】変数値【処理】変数 $V_0$ ～ $V_9$ のうち、 var_ident に対応する値を返す

  var_ident: 【概要】変数識別子【構文】1桁の整数【処理】$V_0$ ～ $V_9$ の変数への対応を示す

  number: /[0-9]+/
  const_k: "K"
  const_n: "N"
  variable: "$" var_ident
  var_ident: /[0-9]/
  

      def number(self, tree) -> int:
          ret = int(tree.children[0].value)
          assert 0 <= ret < 2**64, "OutOfRangeNumber"
          return ret
      def const_k(self, _tree) -> int:
          return self.env['K']
      def const_n(self, _tree) -> int:
          return self.env['N']
      def variable(self, tree) -> int:
          return self.env[self.visit(tree.children[0])]
      def var_ident(self, tree) -> str:
          return str(tree.children[0].value)
  

• statements: 【概要】ブロック文【構文】0行以上の statement からなる 【処理】 含まれる statement ごとに順番に実行する

  ?statements: statement*

• statement: 【概要】文【構文】assignment, branching, repeating, 空行（もしくはコメント行） のいずれかからなる 【処理】対応するものを実行する

  ?statement: assignment | branching | repeating | lineend

• assignment: 【概要】代入

  【処理】変数 var_ident に、 expression を評価した値(符号なし64bit整数)を代入する

  代入が行われる毎に $C$ の値が $1$ 加算される【例外】$C$ の値が $1000$ より大きくなると WA

  assignment: "$" var_ident "=" expression lineend

      def assignment(self, tree) -> None:
          self.env['C'] += 1
          assert self.env['C'] <= 1000, "StepLimitExceed"
          self.env[self.visit(tree.children[0])] = self.visit(tree.children[1])
  

• expression: 【概要】整数値の評価【処理】 value, add, sub, mul, div, rem のいずれか対応するものを評価した値を返す

  ?expression: value | add | sub | mul | div | rem

• add: 【概要】加算 $a+b$ 【例外】結果の値が $0$ 以上 $2^{64}-1=18446744073709551615$ 以下でなければ WA

  sub: 【概要】減算 $a-b$ 【例外】結果の値が $0$ 以上 $2^{64}-1=18446744073709551615$ 以下でなければ WA

  mul: 【概要】乗算 $a\times b$ 【例外】結果の値が $0$ 以上 $2^{64}-1=18446744073709551615$ 以下でなければ WA

  div: 【概要】除算 $\lfloor a/b\rfloor$ 【例外】除数が $0$ だと WA

  rem: 【概要】剰余算 $a-b\lfloor a/b\rfloor$ 【例外】除数が $0$ だと WA

  add: value "+" value
  sub: value "-" value
  mul: value "*" value
  div: value "/" value
  rem: value "%" value
  

      def add(self, tree) -> int:
          ret = self.visit(tree.children[0]) + self.visit(tree.children[1])
          assert 0 <= ret < 2**64, "OutOfRangeNumber"
          return ret
      def sub(self, tree) -> int:
          ret = self.visit(tree.children[0]) - self.visit(tree.children[1])
          assert 0 <= ret < 2**64, "OutOfRangeNumber"
          return ret
      def mul(self, tree) -> int:
          ret = self.visit(tree.children[0]) * self.visit(tree.children[1])
          assert 0 <= ret < 2**64, "OutOfRangeNumber"
          return ret
      def div(self, tree) -> int:
          lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
          assert 0 < rhs, "OutOfRangeNumber"
          return lhs // rhs
      def rem(self, tree) -> int:
          lhs, rhs = self.visit(tree.children[0]), self.visit(tree.children[1])
          assert 0 < rhs, "OutOfRangeNumber"
          return lhs % rhs
  

• branching: 【概要】分岐(if)

  【処理】condition の評価(bool) が true であれば statements を実行する

  condition が評価される時に $C$ の値が $1$ 加算される 【例外】$C$ の値が $1000$ より大きくなると WA

  branching: "if" condition lineend statements "end" lineend

      def branching(self, tree) -> None:
          self.env['C'] += 1
          assert self.env['C'] <= 1000, "StepLimitExceed"
          if self.visit(tree.children[0]): # condition
              self.visit(tree.children[2]) # statements
  

• repeating: 【概要】繰り返し(while)

  【処理】condition の評価(bool) が true である間 statements を繰り返し実行する

  condition が評価される毎に $C$ の値が $1$ 加算される 【例外】$C$ の値が $1000$ より大きくなると WA

  repeating: "while" condition lineend statements "end" lineend

      def repeating(self, tree) -> None:
          while True:
              self.env['C'] += 1
              assert self.env['C'] <= 1000, "StepLimitExceed"
              if not self.visit(tree.children[0]): # condition
                  break
              self.visit(tree.children[2]) # statements
  

• condition: 【概要】比較演算 【処理】eq, ne, ge, le, gt, lt のいずれか対応するものの評価(bool)を返す

  ?condition: eq | ne | ge | le | gt | lt

• eq: 【概要】EQual 【処理】2つの value の値が等しいなら true、さもなくば false

  ne: 【概要】Not Equal 【処理】2つの value の値が異なるなら true、さもなくば false

  ge: 【概要】Greater than or Equal to 【処理】1番目のvalue は 2番目のvalue 以上なら true、さもなくば false

  le: 【概要】Less than or Equal to 【処理】1番目のvalue は 2番目のvalue 以下なら true、さもなくば false

  gt: 【概要】Greater Than 【処理】1番目のvalue は 2番目のvalue より 大なり なら true、さもなくば false

  lt: 【概要】Less Than 【処理】1番目のvalue は 2番目のvalue より 小なり なら true、さもなくば false

  eq: value "==" value
  ne: value "!=" value
  ge: value ">=" value
  le: value "<=" value
  gt: value ">" value
  lt: value "<" value
  

      def eq(self, tree) -> bool:
          return self.visit(tree.children[0]) == self.visit(tree.children[1])
      def ne(self, tree) -> bool:
          return self.visit(tree.children[0]) != self.visit(tree.children[1])
      def ge(self, tree) -> bool:
          return self.visit(tree.children[0]) >= self.visit(tree.children[1])
      def le(self, tree) -> bool:
          return self.visit(tree.children[0]) <= self.visit(tree.children[1])
      def gt(self, tree) -> bool:
          return self.visit(tree.children[0]) > self.visit(tree.children[1])
      def lt(self, tree) -> bool:
          return self.visit(tree.children[0]) < self.visit(tree.children[1])
  

• lineends: 【概要】return 文より後の program 末尾【構文】0回以上の lineend、 1回以下の改行なしコメント文字列 【処理】何の処理も行わない

  ?lineends: lineend* ST_COMMENT?

• lineend: 【概要】行末（コメント文字列が含まれる場合あり） 【構文】ST_COMMENT, CR は省略可【処理】何の処理も行わない

  ?lineend: ST_COMMENT? CR? LF

• ST_COMMENT: 【概要】コメント文字列【構文】"#" 文字以降、改行文字を除く行末までをコメント文字列と見なす【処理】何の処理も行わない

  ST_COMMENT: "#" /[^\n]*/

• CR: 【概要】キャートリッジリターン制御文字【処理】何の処理も行わない

  LF: 【概要】改行文字【処理】何の処理も行わない

  CR : /\r/
  LF : /\n/
  

• WS_INLINE: 【概要】行内の空白文字類【構文】半角空白、水平タブ制御文字 のいずれか【処理】何の処理も行わない

  WS_INLINE: (" "|/\t/)+

• 【構文】行内の空白文字類を無視

  %ignore WS_INLINE

以下の字句を使用することができます。ただし、[0-9]は任意の1文字の数字を、[0-9]+は1文字以上の任意の数字の列を、.*は0文字以上の改行を除く任意の文字の列を、\nは改行を表します。

• [0-9]+
• K
• N
• $
• [0-9]
• +
• -
• *
• /
• %
• if
• while
• end
• ==
• !=
• >=
• <=
• >
• <
• =
• return
• #
• .*
• \n

また、半角スペース（ ）は無視されます。改行は無視されないことに注意してください。

構文は以下のように再帰的に定義されます。ソースコード全体は構文programで記述されていなければなりません。

上で定義した字句はダブルクォーテーションで囲んで表すこととし、字句または構文の結合を空白区切りで表すものとします。また、は空文字列であるとします。

• programは、以下のように定義される。
  • statements "return" value lineends
• statementsは、以下のいずれかである。
  • statement statements
• statementは、以下のいずれかである。
  • lineend
  • assignment
  • branching
• assignmentは、以下のように定義される。
  • "$" "[0-9]" "=" expression lineend
• branchingは、以下のように定義される。
  • control condition lineend statements "end" lineend
• controlは、以下のいずれかである。
  • "if"
  • "while"
• expressionは、以下のいずれかである。
  • value
  • value "+" value
  • value "-" value
  • value "*" value
  • value "/" value
  • value "%" value
• conditionは、以下のいずれかである。
  • value "==" value
  • value "!=" value
  • value ">=" value
  • value "<=" value
  • value ">" value
  • value "<" value
• valueは、以下のいずれかである。
  • number
  • "K"
  • "N"
  • variable
• numberは、以下のものである。
  • "[0-9]+"
• variableは、以下のものである。
  • "$" var_ident
• var_identは、以下のものである。
  • "[0-9]"
• lineendsは、以下のいずれかである。
  • "#" ".*"
  • lineend lineends
• lineendは、以下のいずれかである。
  • "\n"
  • "#" ".*" "\n"

ソースコードが正しい構文で記述されていない場合、WAとなります。

次に、numberを数値リテラルとして評価します。記述された数字の列を非負整数として解釈したとき $0$ 以上 $2^{64}-1=18446744073709551615$ 以下でなければ、WAとなります。

プログラムを実行するコンピュータは、非負整数の列 $(V_0,V_1,V_2,\ldots,V_9)$ および非負整数 $C$ をもつとします。初期値は全て $0$ です。

"K"は $K$ の値、 "N"は $N$ の値を表す定数です。これらの値は各ケースごとに決まります。

variableについて、 $i$ を数字としたとき、"$i"は $V_i$ の値を表す変数です。

number、"K"、"N"、variableの値は、valueに引き継がれます。

値 $a$ をもつvalueであるaと値 $b$ をもつvalueであるbを考えます。a operator bの形であるexpressionについて、その値は

• operatorが"+"の場合、 $a+b$
• operatorが"-"の場合、 $a-b$
• operatorが"*"の場合、 $a \times b$
• operatorが"/"の場合、 $\lfloor a / b\rfloor$
• operatorが"%"の場合、 $a-b\lfloor a / b\rfloor$

また、a comparator bの形であるconditionは

• comparatorが"=="の場合、 $a=b$ であるかどうか
• comparatorが"!="の場合、 $a\neq b$ であるかどうか
• comparatorが">="の場合、 $a\geq b$ であるかどうか
• comparatorが"<="の場合、 $a\leq b$ であるかどうか
• comparatorが">"の場合、 $a\gt b$ であるかどうか
• comparatorが"<"の場合、 $a\lt b$ であるかどうか

プログラムはprogramのstatementsで記述された処理を行った後に、valueとして指定された値を返して終了します。返された値が与えられた $K,N$ に対する $a_N$ でない場合、WAとなります。

lineend と endcomment については、内容は無視され、何も処理を行いません。

statementsについて、の形であれば何も処理を行いません。statement statementsの形であれば、statementで記述された処理を行った後、statementsの処理に移ります。

assignmentは、variable の var_ident に対応する $V_i$ の値をexpressionのもつ値に変更します。また、 $C$ の値が $1$ 大きくなります。

"if" condition statements "end"の形のbranchingについて、まずconditionの値にかかわらず、 $C$ の値が $1$ 大きくなります。 次に、conditionの値が真である場合のみstatementsで記述された処理が行われます。

"while" condition statements "end"の形のbranchingについて、conditionの値が真である限り、 $C$ の値を $1$ 大きくしてstatementsで記述された処理を行うことを繰り返します。 conditionの値が偽になった場合、 $C$ の値が $1$ 大きくなり、このbranchingの処理は終了します。

$C$ の値が $1000$ より大きくなった場合、WAとなります。