簡単なAPLインタプリタを構築しよう - パート1

はじめに まず、Ruslan Spivak氏による「Let's build a simple interpreter」というパスカルインタプリタ構築に関するブログ記事シリーズに感謝の意を表します。このシリーズの冒頭を数年前に読んだことがきっかけで、私はRojプログラミング言語を作成しました。今回は、パスカルとはかなり異なるAPLのインタプリタを構築する目的で、再びこのシリーズを読み返しています。 APLインタプリタを書いて、それについて書いているのは、APLを学ぶ助けになるからです。Pythonのスキルを活かし、向上させることができます。コードを機能させるために行ったことを文書化できます。もしあなたがAPLインタプリタを書きたいと思った場合に、その手助けをすることができます！ LSBASIシリーズを知っている方のために言っておくと、私のLSBASIシリーズの番号付けはSpivak氏のものとは一致しません。これは、このインタプリタではSpivak氏が考慮しなかった、あるいはその逆の事柄を考慮する必要があるためです。なぜなら、APLとパスカルは、ある側面において非常に異なる特性を持っているからです。一方で、始まりはかなり似ており、この記事ではSpivak氏の第8ブログ記事の途中までの内容にほぼ相当する作業を紹介します。 コード このプロジェクトのコードは、このGitHubリポジトリで入手できますので、ぜひスターを付けてください ;) このパートのソースコードは、rgspl1.pyファイルのみです。試してみるためにダウンロードできます。 目指すもの このブログ記事シリーズは、APLインタプリタを構築する私の旅に沿ったものとなり、それが最終目標です！Pythonで書かれた完全に機能するAPLインタプリタを持つことです！それは大変な作業になるでしょう ;) 今日の目標 この記事では、このプロジェクトを開始するための基本を説明します。特に、次のものを備えた単純なAPLステートメントを解析できるようにすることを目指します。 浮動小数点数と整数（正数と負数 - APLでは数値を否定するために¯を使用します。例: ¯3 は -3 です）およびそれらのベクトル。 関数 +-×÷ の単項版と二項版。 通勤/スイッチ演算子 ⍨。 括弧で囲まれた式。 トークナイジング まず最初に行うことは、APLソースコードを取得し、不要なもの（空白など）を取り除き、各文字が何を表すかを見つけることです。例えば、数値を探し、それが整数か浮動小数点数かを判断したり、APLのグリフを見て、それらを名前に紐付けたりします。 今日使用するいくつかのトークンタイプを定義するTokenクラスのコードは次のとおりです。 class Token: """Represents a token parsed from the source code.""" INTEGER = "INTEGER" FLOAT = "FLOAT" PLUS = "PLUS" MINUS = "MINUS" TIMES = "TIMES" DIVIDE = "DIVIDE" NEGATE = "NEGATE" COMMUTE = "COMMUTE" LPARENS = "LPARENS" RPARENS = "RPARENS" EOF = "EOF" # Helpful lists of token types. FUNCTIONS = [PLUS, MINUS, TIMES, DIVIDE] MONADIC_OPS = [COMMUTE] # What You See Is What You Get characters that correspond to tokens. WYSIWYG = "+-×÷()⍨" # The mapping from characteres to token types. mapping = { "+": PLUS, "-": MINUS, "×": TIMES, "÷": DIVIDE, "(": LPARENS, ")": RPARENS, "⍨": COMMUTE, } def __init__(self, type_, value): self.type = type_ self.value = value def __str__(self): return f"Token({self.type}, {self.value})" def __repr__(self): return self.__str__() これらのトークンタイプと__str__および__repr__メソッド（トークンインスタンスをより分かりやすく表示できるようにする）を定義した後、5 + 6のような文字列を[Token(EOF, None), Token(INTEGER, 5), Token(PLUS, +), Token(INTEGER, 6)]のようなトークンのリストに変換できるようにする必要があります。EOFトークン（end-of-fileトークン）がリストの最初の要素であることに注意してください。これは、APLの実行順序であるため、APLソースコードを右から左へトークン化することにしたからです。この決定が後で問題にならないことを願っています！ ところで、私が間違いをたくさん犯すことをここで知らせるのに良い機会かもしれません！もし、ある時点で何かを別の方法で行うというアイデアがあれば、ぜひ試してみて、それがどうだったかを以下のコメントで教えてください。 プログラムに戻ると、Tokenクラスはすでにあります。次に、文字列を受け取り、トークンのリストを構築するTokenizerを定義します。クラスの始まりは次のとおりです。 class Tokenizer: """Class that tokenizes source code into tokens.""" def __init__(self, code): self.code = code self.pos = len(self.code) - 1 self.current_char = self.code[self.pos] def error(self, message): """Raises a Tokenizer error.""" raise Exception(f"TokenizerError: {message}") def advance(self): """Advances the cursor position and sets the current character.""" self.pos -= 1 self.current_char = None if self.pos < 0 else self.code[self.pos] # ... 例えばTokenizer("5 + 6")のような文字列でこのクラスをインスタンス化します。エラー関数は、Tokenizerで問題が発生した場合に例外を発生させるためのヘルパー関数として使用されます。最後に、advance関数は、トークナイザーの「カーソル」を左に移動させ、current_charを保持するヘルパー変数を再定義するちょっとしたユーティリティ関数です。APLコード全体を処理し終え、文字列の終わりに達したとき（右から左へ移動しているので、実際には始まりですが）、処理するものがなくなったことを示すためにcurrent_charをNoneに設定します。 このスケルトンが構築されたので、クラスの残りの部分は次のようになります。 class Tokenizer: # ... def skip_whitespace(self): """Skips all the whitespace in the source code.""" while self.current_char and self.current_char in " ": self.advance() def get_integer(self): """Parses an integer from the source code.""" end_idx = self.pos while self.current_char and self.current_char.isdigit(): self.advance() return self.code[self.pos+1:end_idx+1] def get_number_token(self): """Parses a number token from the source code.""" parts = [self.get_integer()] # Check if we have a decimal number here. if self.current_char == ".": self.advance() parts.append(".") parts.append(self.get_integer()) # Check for a negation of the number. if self.current_char == "¯": self.advance() parts.append("-") num = "".join(parts[::-1]) if "." in num: return Token(Token.FLOAT, float(num)) else: return Token(Token.INTEGER, int(num)) def get_wysiwyg_token(self): """Retrieves a WYSIWYG token.""" char = self.current_char if char in Token.mapping: self.advance() return Token(Token.mapping[char], char) self.error("Could not parse WYSIWYG token.") def get_next_token(self): """Finds the next token in the source code.""" self.skip_whitespace() if not self.current_char: return Token(Token.EOF, None) if self.current_char in "0123456789": return self.get_number_token() if self.current_char in Token.WYSIWYG: return self.get_wysiwyg_token() self.error("Could not parse the next token...") def tokenize(self): """Returns the whole token list.""" tokens = [self.get_next_token()] while tokens[-1].type != Token.EOF: tokens.append(self.get_next_token()) return tokens[::-1] 上記のコードで、式 5 -⍨ ¯2.3 は、print(Tokenizer("5 -⍨ ¯2.3").tokenize()) を実行した場合、[Token(EOF, None), Token(INTEGER, 5), Token(MINUS, -), Token(COMMUTE, ⍨), Token(FLOAT, -2.3)] のようにトークン化されます。信じられませんか？スクリプトを実行して得られるread-eval-print-loopに、式 5 -⍨ ¯2.3 をコピーして貼り付けてみてください。 トークンリストにおける構造の発見 すべてのトークンが得られたら、それらをより構造化された方法で表現したいと考えます。その目的のために、抽象構文木（AST）と呼ばれるものを構築します（Spivak氏のLSBASI第7ブログ記事を参照）。このAST構造により、APLプログラムの解釈がはるかに容易になります。そのために支払う代償は、まずツリーを構築することであり、これはトークンリストを（再び右から左へ）走査し、スカラー、配列、演算子、二項/単項関数が何であるかを決定することによって行います。これが私たちのASTが行う仕事です。その後、プログラムの解釈は非常に簡単になります。ASTの構築方法を知るために、APL言語の部分集合の文法を考案することから始めました。