Python デザインパターン サンプルコード Interpreter
結城 浩「Java言語で学ぶデザインパターン入門」をPython化
Python3(3.11)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
◆◆Interpreter パターンの使われる場面◆◆GoFのC++サンプルもこの Java サンプルも BNF（後述）の規則で書かれた言語の翻訳である。
狭義の interpreter の代表はマイクソフトの BASIC のような逐次翻訳言語である。しかし，Java サンプルは広義のマクロ言語であり（キーボードマクロではない），結城氏はミニ言語と呼んでいる。
広義のマクロ言語とは，まとまりのある1つの処理単位というか動作単位というかサブルーチンみたいなものに1つの単語を割り当てて，この単語を並べてプログラムの構成することをいう。構成要素を替えることなく単語を並び替えることにより様々な処理や動作に対応することができる。
応用は，言語の文法を作るというよりも，マクロと処理単位の相性により適用先を考えた方がよいと考える。
（2023-11-19）Python3.11で動作確認済み
◆◆Interpreter パターンとは◆◆
GoFによれば，Interpreter パターンの目的は， 「言語に対して，文法表現と，それを使用して文を解釈するインタプリタを一緒に定義する。」
GoFによれば，Interpreter パターンは，次のような場合に使うことができる。
ステートメントがアブストラクト・シンタックスツリーとして表現できるような言語を解釈する際に Interpreter パターンを使う。Interpreter パターンは次のような場合に適用するのがもっとも適している。
・文法が単純な場合。文法が複雑な場合には文法を表現するクラス階層が大きくなり，管理できなくなる。そのような場合には，パーザジェネレータのようなツールの方が適している。パーザジェネレータでは，アブストラクト・シンタックスツリーを構築せずに表現を解釈するので，メモリと処理時間を節約することができる。
・効率が重要な関心事ではない場合。もっとも効率的なインタプリタは，通常は，構文解析木を直接解釈するのではなく，最初に別の形に変換するように実装されている。たとえば，正規表現はしばしば状態機械に変換される。しかし，そのような場合でも，Interpreter パターンを適用して変換を実装することができる。
GoFによれば，Interpreter パターンの関連するパターンは次のようなものである。
Composite パターン：アブストラクト・シンタックスツリーは，Composite パターンのインスタンスである。
Flyweight パターン：アブストラクト・シンタックスツリー内で終端記号を共有する方法を示している。
Iterator パターン：インタプリタが構造内を走査する際に Iterator オブジェクトを使うことができる。
Visitor パターン：アブストラクト・シンタックスツリー内の各ノードの振る舞いを1つのクラスにまとめて持たせるために，使うことができる。
◆◆Interpreter パターンのサンプルのクラス構成◆◆
ソースコードは巻末にあり，ソースファイルはこのWebの左上隅にありダウンロードできます。
Node
(parse)
↑ ↑ ↑ ↑ ↑
ProgramNode CommandListNode CommandNode RepeatCommandNode PrimitiveCommandNode
(parse) (parse) (parse) (parse) (parse)
Context StringTokenizer
(nextToken, currentToken, skipToken, currentNumber) (nextToken, hasMoreTokens)
class Node は，抽象クラスでありテンプレートです。
class ProgramNode, CommandListNode, CommandNode, RepeatCommandNode, PrimitiveCommandNode は，parse 構文解析の具象メソッドを実装します。BNF（後述）の文法規則の1つが1つのクラスになっています。
class Context は，構文解析を進めます。
class StringTokenizer は Java では utilクラスですが，同じ機能を Python で実装している。
◆◆BNF の文法規則◆◆
サンプルで使うミニ言語の文法を示します。その文法の表記法は BNF（Backus-Naur Form：バッカス・ナウル・フォーム）と呼ばれるものです。これでミニ言語の文法を表現したものが次のものです。
1 2 3 4 5 6
<program> ::= program <command list> <command list> ::= <command>* end <command> ::= <repeat command> | <primitive command> <repeat command> ::= repeat <number> <command list> <primitive command> ::= go | right | left <number> ::= ???
上のものはすべてトークン（ソースコードの単語）を定義したものです。
1行目は，
<program>とはトークン program の後にコマンドの列<command list>が続いたものである
2行目は，
<command list>とは<command>が0個以上繰り返したあとトークン end が続いたものである
3行目は，
<command>とは繰り返しコマンド<repeat command>または基本コマンド<primitive command>のいずれかである（ | は or を表す）
4行目は，
<repeat command>とはトークン repeat のあとに繰り返し回数<number>が続き，さらにコマンドの列<command list>が続いたものである
5行目は，
<primitive command>とは go または right または left である
<number>の定義は意外と複雑であり，とりあえず，自然数だということにします。
◆◆ミニ言語で書いたプログラム◆◆
サンプルプログラムの標準出力の結果を示します。
text = "program end" node = [program []] text = "program go end" node = [program [go]] text = "program go right go right go right go right end" node = [program [go, right, go, right, go, right, go, right]] text = "program repeat 4 go right end end" node = [program [[repeat 4 [go, right]]]] text = "program repeat 4 repeat 3 go right go left end right end end" node = [program [[repeat 4 [[repeat 3 [go, right, go, left]], right]]]]
text = が与えられたミニ言語のプロクラム（ソースコード）であり，node = が翻訳結果です。
このミニ言語は，ラジコンの車を制御するものです。使われているトークンのうち，制御のマクロとして機能しているのは，基本コマンドの go，right，left だけです。残りはプログラムを意味のある構文にする機能を果たしています。
基本コマンドの意味は使用者が任意に定義すればよいものですが，ここでは次のようにします。
go：一定距離を走りそして停まる
right：その場で右へ90度ターンする
left：その場で左へ90度ターンする
◆◆Interpreter パターンの実装◆◆
◆◆メインルーチン
ミニ言語のソースコードは外部ファイルで与えられます。メインルーチンのコードは外部ファイルを読み込む典型的な書き方です。これは1行ずつ読み込みます。サンプルはプログラムとして1行で完結していますので，この1行をプリントしてそれから翻訳します。
翻訳プログラムのスタートのさせ方は，構文ツリーの最上位である ProgramNode クラスをインスタンス化してそれのメソッド parse（構文解析）を Context クラスを引数にして呼びます。
ProgramNode クラスのように BNF で表記された文法の規則1つ1つがクラスになっていて共通のメソッド parse（構文解析）を持っています。Context クラスは構文解析を進めるメソッドを持っていて，それのコンストラクタ（引数でインスタンス化されたとき起動）では次のトークン（ソースコードの単語）を読み込みます。
◆◆ProgramNode クラス
（<program> ::= program <command list>）
ミニ言語の最初は program のはずなのでそれを読み飛ばします。それが無かったら例外が出ます。そして次に<command list>があるはずなので，CommandListNode クラスをインスタンス化してそれのメソッド parse を context を引数にして呼びます。あとは呼ばれたクラスに任せます。
このように1つの文法の規則を1つのクラスで実装するとバグが少ないプログラムを書くことができます。デメリットは非常に複雑な文法の規則は実装しにくいということです。
◆◆CommandListNode クラス
（<command list> ::= <command>* end）
次にあるはずの command を保持するためにリストを用意します。そしてトークンによって3つに分岐します。
トークンがなかったら例外を出します。
トークンが end であったら読み飛ばします。
上の2つ以外でしたらそれは command なので CommandNode クラスをインスタンス化してそれのメソッド parse を context を引数にして呼びます。あとは呼ばれたクラスに任せます。
◆◆CommandNode クラス
（<command> ::= <repeat command> | <primitive command>）
トークンが repeat であったら RepeatCommandNode クラスをインスタンス化してそれのメソッド parse を context を引数にして呼びます。あとは呼ばれたクラスに任せます。
トークンがそれ以外であったらPrimitiveCommandNode クラスをインスタンス化してそれのメソッド parse を context を引数にして呼びます。あとは呼ばれたクラスに任せます。
◆◆RepeatCommandNode クラス
（<repeat command> ::= repeat <number> <command list>）
トークン repeat を呼び飛ばし，Context クラスのメソッド currentNumber により数値を読み込み，そして再び CommandListNode クラスを呼びます。
◆◆PrimitiveCommandNode クラス
（<primitive command> ::= go | right | left）
このクラスでは翻訳はしません。トークンが定義した3つに含まれているかチェックしているだけです。そうでなければ例外を出します。
翻訳を担うクラスの説明は以上です。トークンを読み込むのは Context クラスの各メソッドであり，それらは説明が不要なくらい単純な機能です。
さて，翻訳の結果は中間言語と言われるものでさらに翻訳を進めるためになくてはならないものです。基本コマンドだけがさらに処理単位（または動作単位）としてまとまりのあるプログラムに翻訳されていきます。残りのトークンは階層構造（またはツリー構造）を表現しているだけです。この構造は普通は再帰呼び出しで実装します。
◆◆ソースコード◆◆
このWebページの左上隅からダウンロードできます。
1つのソースファイル，1つのミニ言語のソースプログラムがあります。
・Interpreter；Interpreter パターンのPythonサンプル
・program.txt；ミニ言語のソースプログラム
【Interpreter】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import sys
from abc import ABCMeta, abstractmethod
import re
class Node(metaclass=ABCMeta):
@abstractmethod
def parse(self, context):
pass
# <program> ::= program <command list>
class ProgramNode(Node):
def __init__(self):
self.commandListNode = None
def parse(self, context):
context.skipToken("program")
self.commandListNode = CommandListNode()
self.commandListNode.parse(context)
def __str__(self): # インスタンスをprintすると呼ばれる
return "[program {}]".format(self.commandListNode)
# <command list> ::= <command>* end
class CommandListNode(Node):
def __init__(self):
self.list = []
def parse(self, context):
while True:
if not context.currentToken():
raise ParseException("Missing 'end'")
elif context.currentToken() == "end":
context.skipToken("end")
break
else:
commandNode = CommandNode()
commandNode.parse(context)
self.list.append(commandNode)
def __str__(self): # インスタンスをprintすると呼ばれる
return "[{}]".format(", ".join([str(el) for el in self.list]))
# <command> ::= <repeat command> | <primitive command>
class CommandNode(Node):
def __init__(self):
self.node = None
def parse(self, context):
if context.currentToken() == "repeat":
self.node = RepeatCommandNode()
self.node.parse(context)
else:
self.node = PrimitiveCommandNode()
self.node.parse(context)
def __str__(self): # インスタンスをprintすると呼ばれる
return str(self.node)
# <repeat command> :== repeat <number> <command list>
class RepeatCommandNode(Node):
def __init__(self):
self.number = None
self.commandListNode = []
def parse(self, context):
context.skipToken("repeat")
self.number = context.currentNumber()
context.nextToken()
self.commandListNode = CommandListNode()
self.commandListNode.parse(context)
def __str__(self): # インスタンスをprintすると呼ばれる
return "[repeat {} {}]".format(self.number, self.commandListNode)
# <primitive command> ::= go | right | left
class PrimitiveCommandNode(Node):
def __init__(self):
self.name = ""
def parse(self, context):
self.name = context.currentToken()
context.skipToken(self.name)
if self.name not in ("go", "right", "left"):
raise ParseException("{} is undefined".format(self.name))
def __str__(self): # インスタンスをprintすると呼ばれる
return self.name
class Context(object):
def __init__(self, text):
self.currentToken_ = None
self.tokenizer = StringTokenizer(text)
self.nextToken()
def nextToken(self):
# 次のトークンを得る（次のトークンに進む）
if self.tokenizer.hasMoreTokens():
self.currentToken_ = self.tokenizer.nextToken()
else:
self.currentToken_ = None
return self.currentToken_
def currentToken(self):
# 現在のトークンを得る（次のトークンへは進まない）
return self.currentToken_
def skipToken(self, token):
# 現在のトークンをチェックしてから次のトークンを得る
# （次のトークンに進む）
if token != self.currentToken_:
raise ParseException( \
"Warning: {} is expected, but {} is found" \
.format(token, self.currentToken_)
)
self.nextToken()
def currentNumber(self):
# 現在のトークンを数値として得る（次のトークンへは進まない）
try:
number = int(self.currentToken_)
except ValueError as e:
raise ParseException("Warning: {} ".format(e))
return number
class StringTokenizer(object): # Javaではutilクラス
def __init__(self, text): # トークンに分割
self.tokens = re.split("[ \t\n\r\f]", text) #正規表現で分割
def nextToken(self):
# 次のトークンを得る（次のトークンに進む）
token = self.tokens[0]
self.tokens = self.tokens[1:]
return token
def hasMoreTokens(self):
# 次のトークンがあるかどうかを調べる
return len(self.tokens) > 0
class ParseException(Exception): # 引数が使える自作例外
pass
def main():
with open("program.txt") as reader: # ファイル読み込みの典型的な書き方
for text in reader:
text = text.strip() # 文字列の前後から空白文字を削除
sys.stdout.write('text = "{}"\n'.format(text))
node = ProgramNode() # 構文ツリーの最上位
node.parse(Context(text))
sys.stdout.write("node = {}\n".format(node))
if __name__ == '__main__':
main()
"""
text = "program end"
node = [program []]
text = "program go end"
node = [program [go]]
text = "program go right go right go right go right end"
node = [program [go, right, go, right, go, right, go, right]]
text = "program repeat 4 go right end end"
node = [program [[repeat 4 [go, right]]]]
text = "program repeat 4 repeat 3 go right go left end right end end"
node = [program [[repeat 4 [[repeat 3 [go, right, go, left]], right]]]]
"""
以上