はじめに
へび年なので Python を学ぼうと思い、とりあえずパーサコンビネータを書いてみました.
どうやら昔にインストールだけしていたらしく、Python 3.11.3 を使用しました.
私のプログラミング遍歴を書いておくと、C++生まれ、Java 育ち、JavaScript と C# への留学経験あり、と言ったところです.
ソースコード
Python について学んだことや思ったことをコメントとして書いている.
docstring を含むコメントを除くと、パーサコンビネータ部分は100行ちょっと.
貧弱ではあるが、最低限のパースはできる位の記述だと思う.
動作確認として数式のパースを簡単に試している.
# Python のコメントは # 始まり.
# スクリプト感が強い. 実際スクリプトなんだけど.
'''
longstring を変数に格納せず使用することで
ブロックコメントのように使うこともできる.
使うことはできるが非推奨.
しかしドキュメントコメントはこのスタイルで書くものらしい.
なんでブロックコメントそのものが存在しないの？
'''
# 中括弧ではなく、コロンとインデントを使う
# インデントはスペースよっつ分が基本らしいが、
# スペースふたつでもいいらしいのでとりあえず書きなれた方を使っていく.
#
# Python にも Java の lombok みたいなのがあって、Python 3.7 以降ならば
# from dataclasses import dataclass # とした上で
#
# @dataclass
# class ParseOk
# ok: bool
# consumed: int
# value: object
#
# と書くことで lombok の @Data と @AllArgsConstructor を付けたのと
# ほぼ同様の効果を得られるらしい.
# __init__, __repr__, __eq__ などを書かなくていいのはいいけど、
# 存在を知ったのは書き終えた後なので今回は試さない.
class ParseOk:
'''パース結果(成功時)
成功時におけるパース結果
Attributes:
ok (bool): パース成功か？
consumed (int): 消費した要素数(失敗時は 0)
value (T): 値(失敗時は None)
'''
# ↑みたいに def foo: の行の直後に longString を置くことでドキュメントコメント扱いになる.
# ドキュメントコメントの書き方にはいくつかの流派があるらしい.
# 使い捨てのソースで真面目に書くのは面倒なので以降は適当に書く.
# いや、こういうところできちんと練習しておくべきではないか？
# コンストラクタは __init__(self) で定義する
# 暗黙的に this という変数が使えるようになるのではなく、
# 明示的に self という引数があるかのように書く.
# コンストラクタでないメソッドでも同様で、第一引数は self とする.
# 以下のように、引数の型を明示することもできる:
# def __init__(self, consumed: int, value: Any):
# 型を書きたいなら python 使わないのでは？
def __init__(self, consumed, value):
# 文末にセミコロンを使えないわけではないが、非推奨らしい
self._consumed = consumed
self._value = value
# toString に相当するメソッドとして、__str__ がある.
# __repr__ や __format__ も文字列を返すのだと思うが、
# 単純に文字列へ変換したいだけならとりあえず __str__ だけ覚えておけばよさそう？
def __str__(self):
return f'ParseResult{{ ok: {self.ok}, consumed: {self.consumed}, value: {self.value} }}'
# @property を付けることで getter を定義できる.
# こういう @ 始まりのものをデコレータといい、他にも色々ある.
# デコレータを自分で定義することもできるようだが、パーサコンビネータでは不要か.
# @staticmethod とかは使えるかもしれないけど、今回は試さない.
# cf. get ok() { return true; } // in JavaScript
@property
def ok(self):
# bool のリテラルは true ではなく True
return True
@property
def consumed(self):
return self._consumed
@property
def value(self):
return self._value
# ParseResult というクラスを作っておいて、
# class ParseNg(ParseResult)
# と書くことで継承できる. (cf. class ParseNg extends ParseResult /* in Java */)
# 型を強く意識するならば継承を使うけど、今回は試さないでいいか.
# パーサコンビネータとしてはエラー情報を持てるようにした方が親切だが、
# python の練習がしたいだけなのでスルー.
class ParseNg:
'''パース結果(失敗時)
失敗時におけるパース結果
Attributes:
ok (bool): パース成功か？
consumed (int): 消費した要素数(失敗時は 0)
value (T): 値(失敗時は None)
'''
def __init__(self):
# 空文として pass を書く
# python では { } ブロックやセミコロンを使わないので、空文を明示する必要がある.
# セミコロンでよくない？ セミコロンを使いたい... .
pass
def __str__(self):
return f'ParseResult{{ ok: {self.ok}, consumed: {self.consumed}, value: {self.value} }}'
@property
def ok(self):
# false ではなく False
return False
@property
def consumed(self):
return 0
@property
def value(self):
# null ではなく None
# パーサコンビネータとしては例外を投げてもいいと思う
return None
# パーサについて
# 以下の型を持つ関数とする:
# (string source, int position) -> ParseOk/ParseNg
# 引数の source はインデクサを使えるならば任意の一次元データとしてよい.
# バイナリファイルのパーサみたいなのもパーサコンビネータで書けるはず.
# そうすることの是非は脇に置いて.
# source[position] でアクセスするには、
# source の型が __getitem__(self, index: int) を実装していればよい？
def satisfy(test):
'''条件を満たす要素ひとつを消費するパーサ
現在の要素が条件 test を満足する場合に成功するパーサを返す.
成功時の値は現在の要素.
カーソル位置がソースの長さを越えている場合失敗.
'''
# ラムダ式は都度 lambda と書かなければならない.
# define は def と略しているのにどうして？？？ lam とかに出来なかったのかな.
# lambda arg0, arg1, arg2, ...: resultValue
# どうやら python のラムダ式は単一の式しか扱えないらしい.
# 開始早々題材を間違えた感じが凄い
# python の三項演算子は、valueIfTrue if condition else valueIfFalse のように書く.
# 文としては確かこれが自然なのだけれど、
# condition? valueIfTrue : valueIfFalse に慣れてしまった身には辛い.
# and/or/not として記号を使えないのもしんどくなってきた.
# 文字列の長さは len 関数で取得する.
return lambda source, position = 0: ParseOk(1, source[position]) if position < len(source) and test(source[position]) else ParseNg()
# is は予約語なので is_a とする
# python では関数やメソッド、変数をスネークケースで命名する.
def is_a(elem):
'''指定された要素ひとつを消費するパーサ
現在の要素が指定された要素 elem に一致する場合に成功するパーサを返す.
成功時の値は現在の要素.
カーソル位置がソースの長さを越えている場合失敗.
'''
return satisfy(lambda elem0: elem0 == elem)
def literal(lit):
'''指定された列を消費するパーサ
現在のカーソル位置から続く要素が指定された列 lit に一致する場合に成功するパーサを返す.
成功時の値は lit.
カーソル位置がソースの長さを越える場合失敗.
'''
# f = lambda arg0, arg1: resultValue
# というのは、
# def f(arg0, arg1):
# __return resultValue # _ はスペースの意
# に書き換えることができるので、
# 無名関数にこだわらなければ関数型プログラミングを実践できる.
def p(source, position = 0):
# for var_name in range(n) で区間 [0..n) に亘って処理することができる.
# source を str 型に限るなら source.startsWith(lit, position) としてもよい.
# list 型には startsWith がないからインデックスでアクセスする.
# 次のように書くこともできる:
# for i, elem in enumerate(lit):
# ここで、elem = lit[i] である.
# enumerate は iterable を引数に取るので、str でも list でも使えるはず？
for i in range(len(lit)):
if position+i >= len(source):
return ParseNg()
if source[position+i] != lit[i]:
return ParseNg()
return ParseOk(len(lit), lit)
return p
def eos(value = None):
'''ソースの末尾を期待するパーサ
現在のカーソル位置がソース末尾である場合に成功するパーサを返す.
成功時の値は value. 指定がない場合は None.
'''
return lambda source, position = 0: ParseOk(0, value) if position == len(source) else ParseNg()
def choose(p, q):
'''いずれかに一致することを期待するパーサ
p, q いずれかのパーサが成功した場合その結果を返す.
どちらも失敗した場合 choose も失敗する.
'''
def pdef(source, position = 0):
rp = p(source, position)
if rp.ok:
return rp
return q(source, position)
return pdef
def seq(p, q, combine = lambda lhs, rhs: lhs + rhs):
'''連続で一致することを期待するパーサ
パーサ p が成功した上で、q も成功した場合それらの結果を combine で結合して返す.
いずれかが失敗した場合 seq も失敗する.
combine を指定しない場合、__add__ 関数であるものとする.
'''
def pdef(source, position = 0):
rp = p(source, position)
if not rp.ok:
return rp
rq = q(source, position + rp.consumed)
if not rq.ok:
return rq
return ParseOk(rp.consumed + rq.consumed, combine(rp.value, rq.value))
return pdef
# supply_identity, accumulate, finish は Java の Collector に倣っている.
# パーサコンビネータとしてはひとつのオブジェクトにまとめるべきだと思う.
def repeat(p, min = 0, max = -1
, supply_identity = lambda: ''
, accumulate = lambda acc, val: acc + val
, finish = lambda x: x):
'''繰り返し成功することを期待するパーサ
p が min 回以上、max 以下の範囲で繰り返すことを期待するパーサを作成する.
supply_identity, accumulate, finish を指定しない場合、p の結果が文字列であるものとして
連結した値を返す.
Args:
p Parser: パーサ
min Integer: 繰り返しの最小回数 (inclusive)
max Integer: 繰り返しの最大回数. 無限回の繰り返しを許す場合負数. (inclusive)
supply_identity Function(() -> A): パーサの結果を簡約する際の初期値
accumulate Function((A, T) -> A): パーサの結果を簡約する関数
finish Function(A -> R): 簡約の結果を変換する関数
Raises:
ValueException: 「min が負数である」、または「max が非負であって、min 未満である」場合に送出.
'''
if min < 0:
# 例外を送出するには raise を用いる.
# cf. throw new IllegalArgumentException();
raise ValueError('min must be a netural number.')
# max in [0..min) のような条件を and なしで書けるのは python のいいところ.
if 0 <= max < min:
raise ValueError('max must be greater than min.')
def pdef(source, position = 0):
acc = supply_identity()
i = 0
consumed = 0
while max < 0 or i < max:
rp = p(source, position + consumed)
if not rp.ok:
break
acc = accumulate(acc, rp.value)
consumed += rp.consumed
# python ではインクリメント/デクリメントが使えない
i += 1
if min > i:
return ParseNg()
return ParseOk(consumed, finish(acc))
return pdef
def map(p, f):
'''値の変換を行うパーサ
パーサ p が成功したとき、その結果を関数 f によって変換する.
'''
def pdef(source, position = 0):
rp = p(source, position)
if not rp.ok:
return rp
return ParseOk(rp.consumed, f(rp.value))
return pdef
def lazy(supplier):
'''遅延評価を行うパーサ
循環参照がおきる場合のためのパーサを返す.
'''
return supplier()
# --------------------------
# 以下、サンドボックス
# --------------------------
def accumulate_list(list, elem):
list.append(elem)
return list
# 「lambda a, b: a.append(b)」と書いても append が None を返すため上手くいかない.
# 「lambda a, b: { a.append(b); return a; }」みたいな記述は出来ない.
# 従って、このケースでは def を用いて名前付き関数を定義しなければならない.
# python でがっつり関数型プログラミングをしようとすることが間違いなのだとは思うが、
# しかし (list, elem) => { list.append(elem); return list; } でさえ名前付き関数を要するのは
# ラムダ式の利便性を大きく損ねているのではないか？
# lambda list, elem: list.append(elem) or list
# みたいな書き方は筋が悪いし... .
# python が古い言語なのは分かるが、いちいち lambda と書かなければならない点も含めて
# どこか落ち着かない.
rep0 = repeat(literal('hom'), 0, -1, lambda: [], accumulate_list, lambda x: x)
result0 = rep0('homhomhomhomho')
print(result0)
print(f'ok: {result0.ok}')
print(f'consumed: {result0.consumed}')
print(f'value: {result0.value}') # value: ['hom', 'hom', 'hom', 'hom']
# --------------------------
# 構文解析と言えば数式
# --------------------------
# formula :: expr sp eos
# expr :: term (sp exprOp sp term)*
# term :: factor (sp termOp sp factor)*
# factor :: number / '(' sp expr sp ')'
# exprOp :: '+' / '-'
# termOp :: '*' / '/'
# number :: non-zero (non-zero / '0')*
# non-zero :: [1-9]
# sp :: ' '*
# eos :: !.
expr = None
sp = repeat(is_a(' '))
non_zero = satisfy(lambda ch: '1' <= ch <= '9')
number = seq(non_zero, repeat(choose(non_zero, is_a('0'))))
termOp = choose(is_a('*'), is_a('/'))
exprOp = choose(is_a('+'), is_a('-'))
factor = choose(number, seq(is_a('('), seq(lazy(lambda: expr), is_a(')'))))
term = seq(factor, repeat( seq(sp, seq(termOp, seq(sp, factor))) ))
expr = seq(term, repeat( seq(sp, seq(exprOp, seq(sp, term))) ))
formula = seq(sp, seq(expr, seq(sp, eos(''))))
src1 = ' 21 / 57 * 19 + 28 * 4 / 7 '
result1 = formula(src1)
print(f'parse [{src1}] as formula:')
print(result1)
print(f'ok: {result1.ok}')
print(f'consumed: {result1.consumed}')
print(f'value: {result1.value}') # value: 21 / 57 * 19 + 28 * 4 / 7
# --------------------------
# 計算できるようにする
# --------------------------
def l(a, _): # 左の値を選択
return a
def r(_, a): # 右の値を選択
return a
def t(a, b): # タプルを作成
# 丸括弧を使うとタプルになる. (a, b)
# tuple[0] で a、tuple[1] で b が取得できる.
# 複数の値を扱う方法として、他にリスト、辞書、namedtuple がある.
# リストの場合: [a, b] で作成 # list[0], list[1] で取得.
# 辞書の場合 : { 'foo': a, 'bar': b } で作成 # dict['foo'], dict['bar'] で取得
# namedtupleの場合:
# まず from collections import namedtuple とする必要がある.
# その上で、
# MyTuple = namedtuple('MyTuple', ['foo', 'bar']) # 型を定義
# myTuple = MyTuple(foo = a, bar = b) # MyTuple を作成
# print( myTuple.foo ) # ドット記法で取得できる
# print( myTuple.bar )
# みたいにして使う.
# 最早クラスを定義するのと大差なくない？
# JavaScript と比較するのが間違っているのだろうけど
# あっちは { foo: a, bar: b } で作成して obj.foo, obj.bar で取得だからなあ... .
# python の dict や namedtuple はいちいち引用符を書くのがしんどいかも.
return (a, b)
numexpr = None
numnumber = map(seq(non_zero, repeat(choose(non_zero, is_a('0')))), lambda a:float(a)) # 数値を読み込み、float にする
numfactor = choose(numnumber, seq(is_a('('), seq(lazy(lambda: numexpr), is_a(')'), l), r))
# '6 * 5 * 4 / 3 / 2 / 1' は
# 6 * (((((1 * 5) * 4) / 3) / 2) / 1) として計算する.
numterm = seq(numfactor, repeat( seq(sp, seq(termOp, seq(sp, numfactor, r), t), r)
, 0, -1
, lambda: 1
# y * x は y*x に、y / x は y/x として計算する
, lambda acc,tuple: acc * tuple[1] if tuple[0] == '*' else acc / tuple[1]
, lambda x: x
), lambda head,tails: head*tails)
# '6 + 5 + 4 - 3 - 2 - 1' は
# 6 + (((((0 + 5) + 4) - 3) - 2) - 1) として計算する.
numexpr = seq(numterm , repeat( seq(sp, seq(exprOp, seq(sp, numterm , r), t), r)
, 0, -1
, lambda: 0
# y + x は y+x に、y - x は y-x として計算する
, lambda acc,tuple: acc + tuple[1] if tuple[0] == '+' else acc - tuple[1]
, lambda x: x
), lambda head,tails: head+tails)
numformula = seq(sp, seq(numexpr, seq(sp, eos(), r), l), r)
src2 = src1
result2 = numformula(src2)
print(f'parse [{src2}] as numformula:')
print(result2)
print(f'ok: {result2.ok}')
print(f'consumed: {result2.consumed}')
print(f'value: {result2.value}') # value: 23.0
# 123 - 87 + 1406 - 15 = 1431
# src3 = '123-783/9+361/19*74-15'
# src3 = '123-783/9'
src3 = '123-783/9+361/19*74-15'
result3 = numformula(src3)
print(f'parse [{src3}] as numformula:')
print(result3)
print(f'ok: {result3.ok}')
print(f'consumed: {result3.consumed}')
print(f'value: {result3.value}') # value: 1426.9999999999998
# 361/19*74 を 361 * ((1/19) * 74) と計算するときに誤差が出る.