自作PEGパーサーコンビネータでCalcの実装

自作のPEGパーサーコンビネータで、よくあるCalcのサンプルを作ってみた。
左再起のサポートとか文法の拡張とかはなく、PEGの基本的なオペレータしか実装していない。しかし、マッチしなかった場合もNoneや空リストを返してASTのノードの位置を極力固定するという仕様によって、セマンティックアクションは比較的シンプルに実装できるんじゃないかと思う。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import unicode_literals
from peg import GrammarBuilder, Parser


def calcgrammar():
    g = GrammarBuilder()

    def number():
        return g.regexp(r'\d+')

    def factor():
        return [('(', expression, ')'), number]

    def term():
        return factor, g.repeat0(['*', '/'], factor)

    def expression():
        return term, g.repeat0(['+', '-'], term)

    def program():
        return expression

    return g.build(program)


class Calc(object):

    def number(self, t):
        return int(t)

    def factor(self, t):
        if isinstance(t, list):
            return t[1]
        else:
            return t

    def term(self, t):
        x = t[0]
        for op, r in t[1]:
            if op == '*':
                x *= r
            else:
                x /= r
        return x

    def expression(self, t):
        x = t[0]
        for op, r in t[1]:
            if op == '+':
                x += r
            else:
                x -= r
        return x


p = calcgrammar()
s = '3 - 2 - (1 + 3 * 4)'
accepted, t = p.parse(Parser(s, semantics=Calc()))
print(t)

TkinterのTreeViewで行の折り返しをどうするか

f:id:paleman:20190323142749p:plain

USIエンジンをバックグラウンドで動かして、bestmoveとかscoreとかpvを表形式で出力するところまではできた。
問題は行折り返しをどうするか。横スクロール付けてもあんまり意味がないという。

個人的には、エンジンを非同期で動かすとかよりもこっちの方がやっかい。

stackoverflow.com

さすがにこれは面倒臭い。もっと楽な方法模索中。

FreeBSDユーザーな自分のための棋譜検討ソフト

WindowsMacであればいろんなソフトが揃っていて困らないんでしょうけど、私のようなFreeBSDユーザーにとってはwineとかmono使ってwindowsアプリを動かすしか方法がなく、それもなあということで渋々(?)自作することになった。

まずは、CLIで操作する簡単なものを作成した。

black(80/180)? s
#80/180 white: 8d7e (132)
9 8 7 6 5 4 3 2 1
. n . . . . . n l  a
. r . . . g k . .  b
. . . . s p . p .  c
. . P . p s p . p  d
l . g p . . b . .  e
p P R . P . . . .  f
. . N . . P P . P  g
. . G . S . S K .  h
L . . . . G . N L  i
black: Px2
white: Px3 Bx1

black(80/180)?

github.com

しかし、さすがにasciiテキストではわかりにくいし、将棋わかるけどコンピュータには詳しくない人に局面を伝えるには無理がある。
ということで、次はPythontkinterを使って、多少見栄えのあるフロントエンドを作ることにした。
f:id:paleman:20190309154603p:plain
github.com

PlayOKのPSNYahoo!モバゲーの独自のKIFが読めるように適当に雑なパーサーを書いた。
それから、2chとかに貼られているKI2を読めるようにするかということで、本格的にPEGを利用。

PEGもArpeggioだとかTatSuだとかいろいろ選択肢がある中、なぜか自作。
PEGのオペレータの名前は、and, notが予約語で使えないので、RubyのParsletに倣ってpresent, absentという単語を使うことにした。

NezというPEGの文法そのものを拡張してアドホックなセマンティックアクションを減らす方法とかも考えたが、そこまでやらなくてよいことがわかった。
棋譜のパースという特殊な事情を考えれば、ASTの構築はdefaultで全部構築すればよく、optional, zero-or-moreの場合にマッチしなかった場合には、あえてNoneや空のリストをそのまま返すといった単純な方が都合がよいことがわかった。

例として、以下の文法があったとする。

e1 e2? e3

入力が e1 e3だった場合に、e2が省略されたことをセマンティックアクション側で知るには、e2の位置にe2がくるのかe3がくるのかを判定しなければいけない。さらにe3の処理を行う場合にはe2があった場合と省略された場合で処理対象のASTを1つずらす必要が出てくる。

そこで、e2?でe2にマッチしなかった場合に、Noneを返すようにする。

[e1, None, e3]

そうすると、e2の位置にあるオブジェクトはNoneかe2になるので、セマンティックアクションを実行する関数は固定位置にパースしたASTがあるかないかを判定するだけで済む。ASTにTag付けして識別する必要がなくなる。

zero-or-moreも同様に0マッチの場合に空listになるようにする。

e1 e2* e3
[e1, [], e3]

この方法はメリットもあるが、当然デメリットもある。
逆にASTを構築したくない場合に、いちいちflattenしないといけなくなる。
特にzero-or-moreの場合、必要以上に構造が入れ子になってしまい、ただ単にリニアなASTのノードの羅列だけ欲しい場合に邪魔になってしまう。

どちらの方がよいかは対象のドメインによって変わってくる。
どのドメインにも適用できる汎用PEGパーサー(コンビネータ or ジェネレータ)というのは難しい。

Google+からの記事移行完了

Google+は2013年の4月あたりからやりはじめて、2014年から2015年あたりでちょこちょこと更新していた。

2016年は何をしていたのか記憶になく、2017年からはしょうもない変な歌の動画を見つけてはほくそ笑んでいた。

データの形式について [from G+ 2015-01-14]

[2019-03-09追記]

私がこの記事を書いた時に気にしていたのは、シンタックスというよりセマンティクスだった。
1日後、twitterでJKFの作者の方といろいろ議論できたのはいい思い出。

togetter.com

昔、Yahoo!知恵袋で見た時、私はかなり共感したんだけど反応がほとんどなく、あまり気にしている人が少ないのかなと思って控えていた。

detail.chiebukuro.yahoo.co.jp

[2015-01-14当時の内容]

Notationというのはあくまでも記法のことである。

2つの形式A, Bがあったとして、その2つは表現が異なるだけで、その意味するところが同じなのであれば、等価変換可能である。BtoA(AtoB(Data)) = Data である。

しかし、片方の形式にしかない情報があるのだとすれば、変換によって情報が失われる。もしくは変換後の情報が足りず不完全となる。A∩B の部分しか情報が残らない。

従って、2つの形式変換のソフトウェアを多数作るのではなく、すべての情報を包含したデータ交換のための形式を定義し、そのデータ交換用の形式を中心として、複数の形式変換を行う。

データ交換用の形式を定義するにあたって、

  1. まず、このドメインにおいて必要な情報とは何かを定義する。存在するすべての形式が保有可能である情報の和集合を取る。
  2. その情報を表現するための記法(表現形式)を定義する。

すべての形式を包含する情報の定義に失敗すると、様々な形式がある中の一形式に成り下がるので注意が必要である。

完全なものを最初から定義するのは難しい。よって、段階的に拡張する戦略を取る。これは、バージョン間の互換性を考慮して設計しなければならない。大きな技術革新が起きると、バージョン間の互換性がなくなりやすい。

主にデータの交換を目的とする形式ではあるが、データの保存形式として利用することも可能である。その場合の要求として、

  • 古いバージョンのみサポートするソフトウェアに対して、新しいバージョンのデータが入力されるとき、拡張部分は無視されること。
  • 新しいバージョンをサポートするソフトウェアに対して、古いバージョンのデータが入力されるとき、古い形式に従って処理されること。可能であれば、古いバージョンのデータには単純に拡張された部分がないだけで、ソフトウェア側でバージョンの違いによる特別な分岐処理は行わないのが望ましい。

チェスのクエリー言語 [from G+ 2015-01-13]

www.gadycosteff.com

チェスのクエリー言語がCQLならば、将棋のクエリー言語はSQL
おっと、別物になってしまうので、YaSQLで。

sourceforge.net

おっと、これもかぶってしまうので、じゃあ、YaYaSQLで。