「共通テスト用プログラミング表記」のインタプリタを作った話

作ったもの

https://natsuakane.pythonanywhere.com/DNCLInterpreter/

作った理由

DNCL(共通テスト手順記述標準言語)に関連するサイトはあっても、その後継として作られた「共通テスト用プログラミング表記」に関するサイトはないように思われたので作りました。（ちゃんと調べてないですあったらすいません）
あと、pythonでWebサイトを作リたくなってdjangoを入れてみたので、djangoで作りました。

見た目

制御文もできます。

プログラム

https://github.com/natsuakane/DNCLInterpreter

インタプリタのコードの説明だけします。適当に作ったのでParserのコードとかは汚いです。
読まなくていい人は「最後に」まで飛ばしてください。

Lexer

字句解析器です。

Lexer.py

import re
from typing import List, Tuple

# トークンの種類
TOKEN_SPECIFICATION = [
    ('NUMBER', r'[\+|-]?\d+(\.\d*)?'),          # 整数または浮動小数点数
    ('STRING', r'"(.*)"'),                      # 文字列
    ('ID', r'[A-Za-z_]\w*'),                    # 識別子
    ('OP', r'\*\*|==|!=|<=|>=|([+\-*/%=,<>])'), # 演算子
    ('PARENTHESES', r'[()]'),                   # かっこ
    ('BRACKETS', r'[\[\]]'),                    # 鉤括弧
    ('NEWLINE', r'\r\n|[\r\n]'),                # 改行
    ('SKIP', r'[ \t]+'),                        # スペースとタブ
    ('BLOCK', r'[┃┗]'),                         # 条件分岐とループの塊
    ('OTHERCHARS', r'[\u3040-\u30FF\u4E00-\u9FFF:【】]+'),           # 漢字やひらがななど
]

# エラー処理用の例外クラス
class LexerError(Exception):
    def __init__(self, message):
        super().__init__(message)

# Lexer クラス
class Lexer:
    def __init__(self, code: str):
        self.code = code
        self.line = 1  # 行数の追跡

    def tokenize(self) -> List[Tuple[str, str]]:
        tokens = []
        position = 0
        while position < len(self.code):
            match = None
            for regex_type, regex in TOKEN_SPECIFICATION:
                pattern = re.compile(regex)
                match = pattern.match(self.code, position)
                if match:
                    token_value = match.group(0)
                    if regex_type == 'NEWLINE':
                        self.line += 1  # 改行で行数をインクリメント
                    if regex_type != 'SKIP':  # スキップ以外はトークンに追加
                        tokens.append((regex_type, token_value))
                    position = match.end(0)
                    break
            if not match:
                raise LexerError(f"不明なトークン '{self.code[position]}' at line {self.line}")
        tokens.append(('EOF', ""))
        return tokens

Lexerはすごく楽に書けました(いつも使っているC++に比べて)

Parser

構文解析器です。
謎にエラーが出たので、Parser.pyではなくMyParser.pyにしています。

MyParser.py

from .Expression import Expression

# エラー処理用の例外クラス
class ParserError(Exception):
    def __init__(self, message):
        super().__init__(message)

# Parser クラス
class Parser:
    def __init__(self, tokens: list[tuple[str, str]]):
        self.tokens = tokens
    
    def factor(self, token_num: int) -> tuple[int, Expression]:
        type = self.tokens[token_num][0]
        content = self.tokens[token_num][1]

        if type == 'NUMBER':
            return (token_num + 1, Expression('NUMBER', [int(content)]))
        elif type == 'STRING':
            return (token_num + 1, Expression('STRING', [content]))
        elif type == 'ID':
            if self.check_operator(token_num + 1, ["["]):
                new_token_num, subscript = self.assign(token_num + 2)
                self.token(new_token_num, "]")
                return (new_token_num + 1, Expression('ELM', [Expression('VAR', [content]), subscript]))
            
            return (token_num + 1, Expression('VAR', [content]))
        elif type == 'OTHERCHARS':
            if content == "【外部からの入力】":
                return (token_num + 1, Expression('INPUT', []))

            if self.check_operator(token_num + 1, ["("]):
                params = []
                new_token_num = token_num + 2

                while not self.check_operator(new_token_num, [")"]):
                    new_token_num, expression = self.assign(new_token_num)
                    params.append(expression)

                    if self.check_operator(new_token_num, [")"]):
                        continue
                    if self.check_operator(new_token_num, [","]):
                        new_token_num += 1
                        continue
                    raise ParserError("不明なトークンです。1{0}".format(self.tokens[new_token_num]))
                
                return (new_token_num + 1, Expression('FUNC', [content] + params))
            return (token_num + 1, Expression('VAR', [content]))
        elif content == "[":
                params = []
                new_token_num = token_num + 1

                while not self.check_operator(new_token_num, ["]"]):
                    new_token_num, expression = self.assign(new_token_num)
                    params.append(expression)

                    if self.check_operator(new_token_num, ["]"]):
                        continue
                    if self.check_operator(new_token_num, [","]):
                        new_token_num += 1
                        continue
                    raise ParserError("不明なトークンです。2{0}".format(self.tokens[new_token_num]))
                
                return (new_token_num + 1, Expression('ARRAY', params))
        elif content == "(":
            new_token_num, expression = self.assign(token_num + 1)
            self.token(new_token_num, ")")
            return (new_token_num + 1, expression)
        else:
            raise ParserError("不明なトークンです。3{0}".format(content))
    
    def power(self, token_num: int) -> tuple[int, Expression]:
        new_token_num_left, left = self.factor(token_num)

        if self.check_operator(new_token_num_left, ["**"]):
            new_token_num_right, right = self.power(new_token_num_left + 1)
            return (new_token_num_right, Expression('OP', ["**", left, right]))
        
        return (new_token_num_left, left)
    
    def mlt_or_div(self, token_num: int) -> tuple[int, Expression]:
        new_token_num_left, left = self.power(token_num)

        while self.check_operator(new_token_num_left, ["*", "/", "%"]):
            new_token_num_right, right = self.power(new_token_num_left + 1)
            left = Expression('OP', [self.tokens[new_token_num_left][1], left, right])
            new_token_num_left = new_token_num_right
        
        return (new_token_num_left, left)
    
    def add_or_sub(self, token_num: int) -> tuple[int, Expression]:
        new_token_num_left, left = self.mlt_or_div(token_num)

        while self.check_operator(new_token_num_left, ["+", "-"]):
            new_token_num_right, right = self.mlt_or_div(new_token_num_left + 1)
            left = Expression('OP', [self.tokens[new_token_num_left][1], left, right])
            new_token_num_left = new_token_num_right
        
        return (new_token_num_left, left)
    
    def compare(self, token_num: int) -> tuple[int, Expression]:
        new_token_num_left, left = self.add_or_sub(token_num)

        while self.check_operator(new_token_num_left, ["==", "!=", "<", ">", "<=", ">="]):
            new_token_num_right, right = self.add_or_sub(new_token_num_left + 1)
            left = Expression('OP', [self.tokens[new_token_num_left][1], left, right])
            new_token_num_left = new_token_num_right
        
        return (new_token_num_left, left)
    
    def logicalnot(self, token_num: int) -> tuple[int, Expression]:
        if self.check_operator(token_num, ["not"]):
            new_token_num, child = self.logicalnot(token_num + 1)
            return (new_token_num, Expression('OP', ["not", child]))
        
        new_token_num, child = self.compare(token_num)
        return (new_token_num, child)
    
    def logicaland(self, token_num: int) -> tuple[int, Expression]:
        new_token_num_left, left = self.logicalnot(token_num)

        while self.check_operator(new_token_num_left, ["and"]):
            new_token_num_right, right = self.logicalnot(new_token_num_left + 1)
            left = Expression('OP', ["and", left, right])
            new_token_num_left = new_token_num_right
        
        return (new_token_num_left, left)
    
    def logicalor(self, token_num: int) -> tuple[int, Expression]:
        new_token_num_left, left = self.logicaland(token_num)

        while self.check_operator(new_token_num_left, ["or"]):
            new_token_num_right, right = self.logicaland(new_token_num_left + 1)
            left = Expression('OP', ["or", left, right])
            new_token_num_left = new_token_num_right
        
        return (new_token_num_left, left)
    
    def assign(self, token_num: int) -> tuple[int, Expression]:
        new_token_num_left, left = self.logicalor(token_num)

        if self.check_operator(new_token_num_left, ["="]):
            new_token_num_right, right = self.assign(new_token_num_left + 1)
            return (new_token_num_right, Expression('OP', ["=", left, right]))
        
        return (new_token_num_left, left)
    
    def statement(self, token_num: int) -> tuple[int, Expression]:
        if self.check_operator(token_num, ["もし"]):
            block_list = []
            condition_exps = []

            new_token_num, condition_exp = self.assign(token_num + 1)
            new_token_num = self.token(new_token_num, "ならば:")
            new_token_num = self.token(new_token_num, "\r\n")
            level = self.count_level(new_token_num)
            new_token_num, expressions = self.block(new_token_num, level, True)

            condition_exps.append(condition_exp)
            block_list.append(expressions)

            while self.check_operator(new_token_num, ["そうでなくもし"]):
                new_token_num, condition_exp = self.assign(new_token_num + 1)
                new_token_num = self.token(new_token_num, "ならば:")
                new_token_num = self.token(new_token_num, "\r\n")
                new_token_num, expressions = self.block(new_token_num, level, True)

                condition_exps.append(condition_exp)
                block_list.append(expressions)

            if self.check_operator(new_token_num, ["そうでなければ:"]):
                new_token_num = self.token(new_token_num + 1, "\r\n")
                new_token_num, expressions = self.block(new_token_num, level)

                condition_exps.append(None)
                block_list.append(expressions)

            return new_token_num, Expression('STMT', ["if", condition_exps, block_list])
        
        elif self.check_operator(token_num + 1, ["を"]):
            var = Expression('VAR', [self.tokens[token_num][1]])
            new_token_num = self.token(token_num + 1, "を")
            new_token_num, start_value = self.assign(new_token_num)
            new_token_num = self.token(new_token_num, "から")
            new_token_num, stop_value = self.assign(new_token_num)
            new_token_num = self.token(new_token_num, "まで")
            new_token_num, step_value = self.assign(new_token_num)

            if self.check_operator(new_token_num, ["ずつ増やしながら繰り返す:"]):
                new_token_num = self.token(new_token_num, "ずつ増やしながら繰り返す:")
                new_token_num = self.token(new_token_num, "\r\n")
                level = self.count_level(new_token_num)
                new_token_num, block = self.block(new_token_num, level)

                return new_token_num, Expression('STMT', ["forup", var, start_value, stop_value, step_value, block])
            elif self.check_operator(new_token_num, ["ずつ減らしながら繰り返す:"]):
                new_token_num = self.token(new_token_num, "ずつ減らしながら繰り返す:")
                new_token_num = self.token(new_token_num, "\r\n")
                level = self.count_level(new_token_num)
                new_token_num, block = self.block(new_token_num, level)

                return new_token_num, Expression('STMT', ["fordown", var, start_value, stop_value, step_value, block])
            else:
                raise ParserError("for文が適切に終わっていません。")
            
        new_token_num, expression = self.assign(token_num)
        if self.check_operator(new_token_num, ["の間繰り返す:"]):
            new_token_num = self.token(new_token_num, "の間繰り返す:")
            new_token_num = self.token(new_token_num, "\r\n")
            level = self.count_level(new_token_num)
            new_token_num, block = self.block(new_token_num, level)

            return new_token_num, Expression('STMT', ["while", expression, block])
        elif self.check_operator(new_token_num, ["のすべての値を"]):
            new_token_num = self.token(new_token_num, "のすべての値を")
            new_token_num, val = self.assign(new_token_num)
            new_token_num = self.token(new_token_num, "にする")

            return new_token_num, Expression('STMT', ["resetarray", expression, val])

        return new_token_num, expression
    
    def program(self, token_num: int) -> tuple[int, Expression]:
        new_token_num = token_num
        stmts = []
        while self.tokens[new_token_num][0] != 'EOF':
            new_token_num, stmt = self.statement(new_token_num)
            stmts.append(stmt)
            if self.check_operator(new_token_num, [","]):
                new_token_num = self.token(new_token_num, ",")
            while self.check_operator(new_token_num, ["\r\n"]):
                new_token_num = self.token(new_token_num, "\r\n")
        
        return 0, Expression('PROGRAM', [stmts])
                                                         
    def check_operator(self, token_num: int, operators: list[str]) -> bool:
        if token_num >= len(self.tokens):
            return False

        flag = False
        for operator in operators:
            flag = self.tokens[token_num][1] == operator or flag
            
        return flag
    
    def token(self, token_num: int, token: str) -> int:
        if self.check_operator(token_num, [token]):
            return token_num + 1
        raise ParserError("不明なトークンです。{0}\n正しいトークンは {1}。".format(self.tokens[token_num], token))
    
    def block(self, token_num: int, level: int, iscontinuation: bool = False) -> tuple[int, list[Expression]]:
        new_token_num = token_num
        expressions: list[tuple[int, Expression]] = []
        while True:
            for l in range(level - 1):
                new_token_num = self.token(new_token_num, "┃")

            if(self.check_operator(new_token_num, ["┗"])):
                new_token_num = self.token(new_token_num, "┗")
                new_token_num, exp = self.assign(new_token_num)
                expressions.append(exp)
                return (new_token_num, expressions)
            
            try:
                new_token_num = self.token(new_token_num, "┃")
                new_token_num, stmt = self.statement(new_token_num)
                new_token_num = self.token(new_token_num, "\r\n")
                expressions.append(stmt)
            except ParserError as e:
                if iscontinuation:
                    return new_token_num, expressions
                raise ParserError("文の終わりが見つかりません。")
            
    def count_level(self, token_num: int) -> int:
        level = 0
        while self.check_operator(token_num + level, ["┃", "┗"]):
            level += 1
        if level == 0:
            raise ParserError("ブロックが見つかりません。")
        return level
        

基本は普通のプログラミング言語開発と同じです。
block -> 文 -> 式 -> factor

Expression

Parserで生成するプログラムを表すクラスです。

Expression.py

import math
import random

# エラー処理用の例外クラス
class ExpressionError(Exception):
    def __init__(self, message):
        super().__init__(message)

# 変数管理用のクラス
class Environment:
    __variables: dict[str, any] = {}
    
    @staticmethod
    def get(var: str):
        return Environment.__variables[var]
    
    @staticmethod
    def set(var: str, val: any):
        Environment.__variables[var] = val

# 入出力管理用のクラス
class IOProcess:
    __output: list[str] = []
    __input: list[any] = []
    __index: int = 0

    @staticmethod
    def init():
        IOProcess.__output.clear()
        IOProcess.__input.clear()
    
    @staticmethod
    def input(s: str):
        def try_convert_to_float(value):
            try:
                return float(value)
            except ValueError:
                return value
        IOProcess.__input = s.split("\r\n")
        IOProcess.__input = list(map(try_convert_to_float, IOProcess.__input))
        IOProcess.__index = 0

    @staticmethod
    def output(s: str):
        IOProcess.__output.append(s)

    @staticmethod
    def get_input() -> any:
        IOProcess.__index += 1
        return IOProcess.__input[IOProcess.__index - 1]

    @staticmethod
    def get_output():
        return IOProcess.__output

# Expression クラス
class Expression:
    def __init__(self, type: str, children: list):
        self.type = type
        self.children = children

    def evaluate(self):
        if self.type == 'NUMBER':
            return self.children[0]
        elif self.type == 'STRING':
            return self.children[0]
        elif self.type == 'VAR':
            return Environment.get(self.children[0])
        elif self.type == 'FUNC':
            if self.children[0] == "要素数":
                return len(self.children[1].evaluate())
            elif self.children[0] == "整数":
                return round(self.children[1].evaluate())
            elif self.children[0] == "乱数":
                return random.random()
            elif self.children[0] == "表示する":
                s = "".join(map(lambda c : str(c.evaluate()), self.children[1:]))
                IOProcess.output(s)
        elif self.type == 'INPUT':
            print('INPUT')
            return IOProcess.get_input()
        elif self.type == 'ARRAY':
            contents = []
            for content in self.children:
                contents.append(content.evaluate())
            return contents
        elif self.type == 'ELM':
            return (self.children[0].evaluate())[self.children[1].evaluate()]
        elif self.type == 'OP':
            if self.children[0] == "**":
                return math.pow(self.children[1].evaluate(), self.children[2].evaluate())
            elif self.children[0] == "*":
                return self.children[1].evaluate() * self.children[2].evaluate()
            elif self.children[0] == "/":
                return self.children[1].evaluate() / self.children[2].evaluate()
            elif self.children[0] == "%":
                return self.children[1].evaluate() % self.children[2].evaluate()
            elif self.children[0] == "+":
                child1 = self.children[1].evaluate()
                child2 = self.children[2].evaluate()
                if type(child1) == str or type(child2) == str:
                    return str(child1) + str(child2)
                return child1 + child2
            elif self.children[0] == "-":
                return self.children[1].evaluate() - self.children[2].evaluate()
            elif self.children[0] == "==":
                return self.children[1].evaluate() == self.children[2].evaluate()
            elif self.children[0] == "!=":
                return self.children[1].evaluate() != self.children[2].evaluate()
            elif self.children[0] == "<":
                return self.children[1].evaluate() < self.children[2].evaluate()
            elif self.children[0] == ">":
                return self.children[1].evaluate() > self.children[2].evaluate()
            elif self.children[0] == "<=":
                return self.children[1].evaluate() <= self.children[2].evaluate()
            elif self.children[0] == ">=":
                return self.children[1].evaluate() >= self.children[2].evaluate()
            elif self.children[0] == "not":
                if self.children[1].evaluate() == 0:
                    return 1
                else:
                    return 0
            elif self.children[0] == "and":
                if self.children[1].evaluate() == 0 or self.children[2].evaluate() == 0:
                    return 0
                else:
                    return 1
            elif self.children[0] == "or":
                if self.children[1].evaluate() == 0 and self.children[2].evaluate() == 0:
                    return 0
                else:
                    return 1
            elif self.children[0] == "=":
                if self.children[1].type != 'VAR':
                    raise ExpressionError("=の左辺が変数ではありません")
                Environment.set(self.children[1].children[0], self.children[2].evaluate())
                return self.children[2].evaluate()
            
        elif self.type == 'STMT':
            if self.children[0] == "if":
                for i, block in enumerate(self.children[1]):
                    if not (self.children[1][i] is None or self.children[1][i].evaluate() == 0):
                        for j, expression in enumerate(self.children[2][i]):
                            expression.evaluate()
                        return None
                    elif self.children[1][i] is None:
                        for j, expression in enumerate(self.children[2][i]):
                            expression.evaluate()
                        return None
                return None
            
            elif self.children[0] == "forup":
                var = self.children[1]
                start_value = self.children[2]
                stop_value = self.children[3]
                step_value = self.children[4]
                block = self.children[5]
                for i in range(start_value.evaluate(), stop_value.evaluate() + 1, step_value.evaluate()):
                    if var.type != 'VAR':
                        raise ExpressionError("変数が指定されていません。")
                    Environment.set(var.children[0], i)
                    for stmt in block:
                        stmt.evaluate()
                return None
            
            elif self.children[0] == "fordown":
                var = self.children[1]
                start_value = self.children[2]
                stop_value = self.children[3]
                step_value = self.children[4]
                block = self.children[5]
                for i in range(start_value.evaluate(), stop_value.evaluate() - 1, -step_value.evaluate()):
                    if var.type != 'VAR':
                        raise ExpressionError("変数が指定されていません。")
                    Environment.set(var.children[0], i)
                    for stmt in block:
                        stmt.evaluate()
                return None
            
            elif self.children[0] == "while":
                con = self.children[1]
                block = self.children[2]
                while con.evaluate() != 0:
                    for stmt in block:
                        stmt.evaluate()
                return None
            
            elif self.children[0] == "resetarray":
                array_name = self.children[1]
                val = self.children[2]
                if array_name.type != 'VAR':
                    raise ExpressionError("変数が指定されていません。")
                array = Environment.get(array_name.children[0])
                array = list(map(lambda x : val.evaluate(), array))
                Environment.set(array_name.children[0], array)
                return None

        elif self.type == 'PROGRAM':
            for stmt in self.children[0]:
                stmt.evaluate()
            return 0

Environmentクラスは変数管理用クラス、IOProcessは入出力管理用クラスです。

実行する

execute.py

lexer = Lexer(code)
try:
    tokens = lexer.tokenize()
except LexerError as e:
    result += str(e)

parser = Parser(tokens)
try:
    IOProcess.init()
    IOProcess.input(input_data)
    _, program = parser.program(0)
    program.evaluate()
    result += "正常に実行されました\r\n"
    for o in IOProcess.get_output():
        result += "{0}\r\n".format(o)
except ParserError as e:
    result += str(e)

最後に

インタプリタがあれば共通テスト用プログラミング表記（なが）も楽勝ですね！（問題はそんなに難しくないけど）
問題があったらコメントで教えてください。