👻
Python Larkでインタプリタを作る（四則演算、変数定義、if、whileまで）
Pythonの構文解析ライブラリLarkを使って、簡単なインタプリタを作成する。
実装は四則演算、変数定義、if、whileまで。
引数の実装がやや面倒だったので関数定義は実装していない。
install
Larkでは、.lark拡張子の文法ファイルに文法を定義すると構文解析を自動で行なってくれる。文法ファイルはBNFの一種と言えるEBNGという記法で表記できる他、正規表現を用いることもできる。かなり簡単にparserが書ける印象。
pip install Lark-parser --upgrade
文法定義
grammar.larkというファイルを作成し、文法を定義する。
grammar.lark
program: statement+
?statement: bool_expr ";"
| assignment ";"
| if_state
| while_state
| "{" statement+ "}"
assignment: symbol "=" bool_expr
if_state : "/IF" bool_expr "/THEN" statement ["/ELSE" statement] "/ENDIF"
while_state : "/WHILE" bool_expr "/DO" statement "/ENDWHILE"
?bool_expr: expr
| eq
| neq
| gr
| ls
eq : expr "==" expr
neq : expr "!=" expr
gr : expr ">" expr
ls : expr "<" expr
?expr: term
| add
| sub
add : expr "+" term
sub : expr "-" term
?term : factor
| mul
| div
mul : term "*" factor
div : term "/" factor
factor : number | variable | "(" bool_expr ")"
variable : symbol
number : /[0-9]+/
symbol : /[a-zA-Z_][0-9a-zA-Z_]*/
?で記述した要素はtreeのノードとしては反映されない。
numberやsymbolについては公式提供のものを使って
number : SIGNED_NUMBER
symbol : WORD
%import common.WORD
%import common.SIGNED_NUMBER
としてもよい。
実行処理系
これを用いてプログラムを実際に読み取ってみる。
interpreter.py
#python3 interpreter.py {program_file}で実行
import sys
from lark import Lark
from lark.visitors import Interpreter
env = {}
# インタプリタの本体
class MyInterpreter(Interpreter):
def program(self, tree):
ret=None
for c in tree.children:
ret=self.visit(c)
return ret
def assignment(self,tree):
value=self.visit(tree.children[-1])
name=self.visit(tree.children[0])
env[name] = value
return value
def if_state(self, tree):
cond = self.visit(tree.children[0])
if cond:
return self.visit(tree.children[1])
elif len(tree.children)>=3:
return self.visit(tree.children[2])
else:
return None
def while_state(self, tree):
cond = self.visit(tree.children[0])
if(cond):
self.visit(tree.children[1])
self.visit(tree)
return None
def eq(self,tree):
return int(self.visit(tree.children[0]) == self.visit(tree.children[1]))
def neq(self,tree):
return int(self.visit(tree.children[0]) != self.visit(tree.children[1]))
def gr(self,tree):
return int(self.visit(tree.children[0]) > self.visit(tree.children[1]))
def ls(self,tree):
return int(self.visit(tree.children[0]) < self.visit(tree.children[1]))
def add(self, tree):
return int(self.visit(tree.children[0]) + self.visit(tree.children[1]))
def sub(self, tree):
return int(self.visit(tree.children[0]) - self.visit(tree.children[1]))
def mul(self, tree):
return int(self.visit(tree.children[0]) * self.visit(tree.children[1]))
def div(self, tree):
return int(self.visit(tree.children[0]) // self.visit(tree.children[1]))
def factor(self, tree):
return self.visit(tree.children[0])
def number(self, tree):
return int(tree.children[0].value)
def symbol(self, tree):
return str(tree.children[0])
def variable(self, tree):
name = self.visit(tree.children[0])
return env[name]
args = sys.argv
file_name = args[1]
with open("./grammar.lark", encoding="utf-8") as grammar:
with open("./"+file_name,encoding="utf-8") as file:
text=file.read().replace("\n","").replace(" ","").replace("\t","") #改行、スペース、タブは排除
parser = Lark(grammar.read(),start="program") #根はprogram
tree = parser.parse(text)
result = MyInterpreter().visit(tree)
print(result)
LarkのInterpreterを用いた。
parser = Lark(grammar.read(),start="program") #根はprogram
にて決めた通り、根をprogramとして読み取って木構造としている。そこから先、逐次visit関数を用いて子要素にアクセスする。
Larkには同様の機能がTransformerやVisitorにもあるが、Interpreterはvisitが呼ばれない限り自動的にはノードを評価しない点がこれらと異なる、らしい。
実行結果
program
x=1;
/WHILE
x<100
/DO
x=x+1;
/ENDWHILE
/IF
x==100
/THEN
x=1000;
/ELSE
x=0;
/ENDIF
x;
python3 interpreter.py program
1000
正しく処理ができた。
参考にしたサイト
最後の記事は関数定義まで実装している。
Discussion