lex/yaccでプログラミング言語を作るにはC言語を使う必要があるため、メモリ管理等の面でなかなか敷居が高いです。一方、PythonではPLYというlex/yaccのPython実装のライブラリが存在し、簡単にプログラミング言語を作成することができます。ということで、PLYを使ってプログラミング言語を作ってみました。
今回は以下の機能を作っていきます。サンプルコードはこちら。
- ステートメントの順次実行
- 四則演算
- グローバル変数のセット
PLYの利点
PLYを使う利点は以下になります。- トークン保持に関する共用体の定義を省略できる
- 処理内容をPythonで書け、文法上のメリットがある＋メモリ管理をしなくて良い
lex/yaccについて
lex/yaccやプログラミング言語作成に関する記事に関しては以下が詳しいです。全体的な流れとしては以下の3ステップになります。
- lexによるトークナイズ
- yaccによる構文木生成
- ステートメントの実行
ply.lexによるトークナイズ
まず、グローバル領域にtokens変数を定義します。これらはlex、yaccから読み込むので別ファイルにすると良いです。コメントに記載されている通り、tokens変数が定義されていないとエラーになります。# List of token names. This is always required
tokens = (
'INT',
'DOUBLE',
'ADD',
'SUB',
'MUL',
'DIV',
'IDENT',
'NEWLINE',
'ASSIGN',
'STRVALUE',
'EQUAL',
)
トークンは文法上意味のある最小単位になります。
次にstates変数を定義します。
states = (
('string', 'exclusive'),
('comment', 'exclusive'),
)
states変数を定義すると、stateに依存した字句解析が可能になります。例えば、コメント内で変数定義をしても無視されますが、コメント外では変数定義の処理をする必要があります。また、文字列内も同様に変数定義は無視して文字列として解釈する必要があります。このように文字列内やコメント内での字句解析は、それ以外の字句解析と処理を変える必要があります。それに利用するのがstateになります。例えばダブルクォーテーションが来たときに、以降は文字列として解釈し、再びダブルクォーテーションの文字列が来たときは文字列として解釈しない状態にする、というようなことが実現できます。
次にトークンの定義をします。トークンは正規表現を直接設定する方法と関数を定義する方法の２つがあります。いずれもt_{token名}で定義します。
t_ADD = r'\+'
t_SUB = r'-'
t_MUL = r'\*'
t_DIV = r'\/'
t_ASSIGN = r'='
以下は関数で設定する方式です。トークンの値を無視しない場合は必ず引数のtをreturnしてください。
def t_IDENT(t):
r'[a-zA-Z][a-zA-Z0-9]*'
t.type = reserved.get(t.value, 'IDENT')
return t
def t_DOUBLE(t):
r'([1-9][0-9]*|0)\.[0-9]+'
try:
t.value = float(t.value)
except ValueError:
print "Line %d: double value %s is too large" % t.lineno, t.value
t.value = 0
return t
def t_INT(t):
r'[1-9][0-9]*|0'
try:
t.value = int(t.value)
except ValueError:
print "Line %d: integer value %s is too large" % t.lineno, t.value
t.value = 0
return t
単純な正規表現で問題ない場合は変数設定の方式で、予約語を判定するなどのロジックが必要だったり、字句解析時に何か処理をしたい場合（例えば改行コードを見つけたら行番号をインクリメントするなど）は関数定義の方式を使います。変数定義の場合は、正規表現で最長マッチしたトークンが利用され、関数定義の場合は定義した順にマッチングをかけていき、最初にマッチした関数のトークンが利用されます。DOUBLEの定義がINTより前に来ているのは、DOUBLEを先に定義しないと数字列は全てINTとして評価されてしまうからです。
また、変数（上記ではIDENT）と予約語を区別する必要もあるので、t_IDENT内は以下のように予約語を判定してトークンのタイプを変更しています。
def t_IDENT(t):
r'[a-zA-Z][a-zA-Z0-9]*'
t.type = reserved.get(t.value, 'IDENT')
return t
無視したい文字列はt_ignore変数に設定します。stateを定義した場合はstateの分のignoreも設定する必要があります。
t_ignore = ' \t'
t_string_ignore = ' \t'
こちらは正規表現ではなく文字列として定義します。この無視したい文字列というのは「トリムしても構文上問題ない」文字列のことです。以下ではタブ文字と半角スペースを無視していますが、これらの文字列が構文として意味を持つ言語の場合は無視してはいけません。
また、トークン化できなかったときのエラーハンドリングも実装する必要があります。具体的にはt_error関数を定義すれば良いです。こちらもignoreと同様にstateの分も定義してください。
def t_error(t):
print "Illigal charactor '%s'" % t.value[0]
t.skip(1)
最後にlexのスクリプトに以下のコードを記述することで、トークンのデバッグができます。
# Tokenize
if __name__ == "__main__":
data = sys.stdin.read()
lexer.input(data)
while 1:
tok = lexer.token()
if not tok:
break
print tok
ply.yaccによる構文解析
まず、ply.yaccと上記で定義したlex.py、tokens.pyを読み込みます。import ply.yacc as yacc
from lex import lexer
from tokens import tokens
基本的には p_{expression}の関数名で記述すれば良くて、関数のdocstringを使ってBNF記法で表現していきます。以下ではルートのp_mainでstatement_listに格納しています。引数pは各規則のINDEXになります。p_mainだと p[0]がmain、p[1]がnewline_or_empty、p[2]がtranslation_units、p[3]がnewline_or_emptyに対応します。関数の処理は規則にマッチしたときのアクションを記述します。基本的に右辺の要素を左辺に代入するか、右辺の要素をグローバル変数に格納する、といった流れになります。各規則の処理で構文木を作成していくことになります。
def p_main(p):
'''
main : newline_or_empty translation_units newline_or_empty
'''
global statement_list
statement_list = p[2]
def p_translation_units(p):
'''
translation_units : translation_unit
| translation_units newline translation_unit
'''
print len(p)
if len(p) == 2:
p[0] = [p[1]]
else:
p[0] = p[1] + [p[3]]
全体の流れとしては以下の通りです。
- 改行区切りで記述されたコードを構文木を創りながらtranslation_unitの単位に集約
- それらをグローバル変数statement_listに追加
- 各statementをevalして一行ずつ実行
data = sys.stdin.read()
yacc.yacc()
yacc.parse(data, lexer=lexer)
for statement in statement_list:
statement.eval()
規則がマッチしたときに（＝関数内の処理実行時）、四則演算をしても良いのですが、変数評価などはstatement実行時に評価されるべきなので、四則演算用のクラス（CalculateStatement）に格納してevalが呼び出されたときに評価しています。
def p_number_expression(p):
'''
number_expression : term
| number_expression ADD term
| number_expression SUB term
'''
if len(p) == 2:
p[0] = p[1]
else:
p[0] = CalculateStatement(p.lineno(0), p[2], p[1], p[3])
class CalculateStatement(Statement):
def __init__(self, lineno, operator, left, right):
super(CalculateStatement, self).__init__(lineno)
self.type = StatementType.EXPRESSION
self.left = left
self.right = right
self.operator = operator
def eval(self):
if self.operator == '+':
return BasicType(self.left.eval().value + self.right.eval().value)
elif self.operator == '-':
return BasicType(self.left.eval().value - self.right.eval().value)
elif self.operator == '*':
return BasicType(self.left.eval().value * self.right.eval().value)
elif self.operator == '/':
return BasicType(self.left.eval().value / self.right.eval().value)
elif self.operator == '%':
return BasicType(self.left.eval().value % self.right.eval().value)
変数の割当も同様で、こちらはグローバル領域に変数を格納しています。
## statement.py
from storage import storage
class AssignStatement(Statement):
def __init__(self, lineno, ident, expression):
super(AssignStatement, self).__init__(lineno)
self.type = StatementType.ASSIGN
self.ident = ident
self.expression = expression
def eval(self):
storage.variables[self.ident] = self.expression
## storage.py
class Storage():
def __init__(self):
self.variables = {}
self.user_functions = {}
self.global_functions = {}
storage = Storage()
これで変数の格納や四則演算ができます。今回のサンプルコードでは値の表示ができないので、以下のようにyacc側でstorage.pyを読み込んで、storageの値をevalしてあげれば、変数の値を確認することができます。
from storage import storage
print storage.variables
print storage.variables['c'].eval().value
こんな感じで手軽に俺言語を作れるので、トークナイズや構文解析などを勉強したい人にはオススメです！
