昨日(6日目)はseiketkmさんの「未来からやってきたロボホンのアプリを開発したよ」でした。
この記事はTech-Circle Hands on Advent Calendar 2016の７日目の記事です。

今回はPythonの字句解析/構文解析ライブラリであるPLY(lex+yacc)を使ってオリジナル言語を作成してみたいと思います。

オリジナル言語といえば以前、ドナルド・トランプ氏をイメージしたプログラミング言語であるTrumpScriptなるものが公開されました。https://github.com/samshadwell/TrumpScript

TrumpScriptは以下のような特徴があります。

浮動小数点型は使えず整数のみ。アメリカは中途半端なことはしない。
数値は100万より大きくなくてはいけない。それより小さい数字は取るに足らない。
importは使えない。全てのコードはアメリカ製でなければならない。

など…。
このようにドナルド・トランプ氏を忠実に再現したセンス溢れる言語となっています。

そこで今回はTrumpScriptに対抗して、日本の誇るべきトップシンガーソングライターであるピコ太郎のヒットソング、ペンパイナッポーアッポーペンPPAPをイメージした「PPAPScript」を作成しようと思います。

PPAPScriptの仕様

プログラムの開始は必ず「PPAP」で開始する
使用可能な変数名は「pen」「pineapple」「apple」の組み合わせのみ(大文字小文字は無視)
変数を宣言する際はかならず「I_have_a」または「I_have_an」を変数の前につける(例：I_have_a pen = 10)
出力関数は「Ah!」(合体している時に唸っているやつ？)とする(例：Ah! apple + pen)
普通の四則演算
普通のコメントアウト(# apple + pen)

ざっと思いついた仕様がこんな感じです。

plyとは

PPAPScriptを実装する前に今回使用するplyの説明をします。
plyはlexとyaccをPythonによって実装し、モジュールとして一つにまとめたPythonライブラリです。

lex：字句解析を行うツール
yacc：構文解析を行うツール

導入方法

plyの導入はpipで行うことができます。python3にも対応しています。

$ pip install ply

ここからlex.pyおよびyacc.pyにおける最低限の使い方を説明します。

lex.pyの解説

字句解析を担うlex.pyの解説です。

1.lexをインポートします。

import ply.lex as lex

2.解析したい字句を「tokens」という変数にタプル形式で定義します。

tokens = (
    'NUMBER',
    'PLUS',
    'MINUS',
    'TIMES',
    'DIVIDE',
    'LPAREN',
    'RPAREN',
)

3.正規表現による字句解析ルールを定義します。

定義の方法は２つあります。いずれの方法でも変数名および関数名の命名規則は t_(トークン名) という形式で定義をします。

シンプルな字句解析ルールの定義

t_PLUS   = r'\+'
t_MINUS  = r'-'
t_TIMES  = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'

字句解析の際に処理を行う場合

関数の一行目に正規表現を定義します。引数には必ずLexTokenオブジェクトが渡されます。これがマッチした字句のオブジェクトになります。
以下の例では正規表現のルールにマッチしたトークンの値をint型に変換しています。

def t_NUMBER(t):
    r'\d+'
    t.value = int(t.value)
    return t

4.不必要な文字列をスキップします。

t_ignoreという特殊な変数によってある文字列をスキップさせることができます。
以下の例ではスペースとタブをスキップしています。

t_ignore = ' \t'

5.トークンを破棄する構文を定義します。

t_ignore_COMMENTという特殊な変数を使うことによりコメント化の正規表現ルールを定義できます。

t_ignore_COMMENT = r'\#.*'

6.エラーハンドリングを定義します。

t_error関数ではどの字句にもマッチしなかった場合呼び出されます。

def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(t)

7.ビルドします。

lex()でビルドを行います。
これにて字句解析の準備は完了です。

lex.lex()

yacc.pyの解説

構文解析を担うyacc.pyの解説です。

1.yaccをインポートします。

import ply.yacc as yacc

※この時点でlexによって定義したtokensが読み込まれていることに注意してください。

2.構文解析ルールを記述します。

以下の例は足し算の構文ルールを定義しています。

def p_expression_minus(p):
    'expression : expression PLUS term'
    p[0] = p[1] - p[3]

以下が定義する際のルールになります。

関数の命名規則は p_から始まる。
構文ルールは関数の一行目にドキュメンテーション文字列で定義します。
構文ルールは非終端記号 : 非終端記号または終端記号の組み合わせ

def p_expression_minus(p):
    'expression : expression MINUS term'
    # 非終端記号  : 非終端記号  終端記号 非終端記号

定義した関数の引数には構文ルールで定義した記号の配列が渡されます。左がから順番にindexが対応しています。
p[0]へ代入することにより開始記号へ向かって値を返していくことになります。

def p_expression_minus(p):
    'expression : expression MINUS term'
    #  p[0]         p[1]     p[2] p[3]

    p[0] = p[1] - p[3]

一番最初に定義してある関数の非終端記号が開始記号となります。以下の場合だとstatementが開始記号になります。

def p_statement_assign(p):
    """statement : NAME EQUALS expression"""
    names[p[1]] = p[3]


def p_expression_minus(p):
    'expression : expression MINUS term'

    p[0] = p[1] - p[3]

3.構文ルールを合成します。

以下のように似たような構文ルールはひとまとめにすることができます。

def p_expression_binop(p):
    """expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression"""
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]
    elif p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]

4.エラーハンドリングを定義します。

lexと同様でどの構文ルールにもマッチしなかった際に呼び出されます。

def p_error(p):
    print "Syntax error in input"

5.パースを行う。

yacc()でparaserオブジェクトを作成して、parser.parse()で構文解析を行う。引数には構文解析したい文字列を渡します。

parser = yacc.yacc()
parser.parse(data)

PPAPScriptを実装

実装に関してはplyのリポジトリにあるREADMEのExampleをベースにして作成していきます。
https://github.com/dabeaz/ply/blob/master/README.md

プログラムの開始は「PPAP」で開始する

yacc.parse()を実行する部分でフラグの制御をします。

# Started flag is true by "PPAP" command
has_started = False

def parse(data, debug=0):
    if data == "PPAP":
        global has_started
        has_started = True
        print("Started PPAPScript!")
        return

    if has_started:
        return yacc.parse(data, debug=debug)
    else:
        print('PPAPScript run by "PPAP" command.')
        return

変数(t_NAME)の字句解析によって「PPAP」が引っかかるため正規表現で「PPAP」が無視されるようなバイパスを作成します。

def t_NAME(t):
    r"""(?!PPAP)[a-zA-Z_][a-zA-Z0-9_]*"""
    return t

使える変数名は「pen」「pineapple」「apple」の組み合わせのみ(大文字小文字は無視)

変数名の制限はlexの正規表現で弾けばいいのですが、専用のエラーメッセージを出したいのでreモジュールを使用してエラーハンドリングを行います。

def t_NAME(t):
    r"""(?!PPAP)[a-zA-Z_][a-zA-Z0-9_]*"""
    pattern = re.compile(r'^(apple|pineapple|pen)+', re.IGNORECASE)
    if pattern.match(t.value):
        return t
    else:
        print("This variable name can't be used '%s'.\n "
              "Variable can use 'apple', 'pineapple', 'pen'." % t.value)
        t.lexer.skip(t)

変数の宣言代入はかならず「I_have_a」または「I_have_an」をつける

defで定義しているのは字句解析の優先順位をつけるためです。（lexはdefで定義された順序で優先される）
今回の場合はt_NAMEより先に定義が必要となります。

def t_DECLARE(t):
    r"""I_have_(an|a)"""
    return t

出力関数は「Ah!」とする

lex、yaccともに普通の定義を行います。

def t_PRINT(t):
    r"""Ah!"""
    return t

def p_statement_print_expr(p):
    """statement : PRINT expression"""
    print(p[2])

PPAPScriptの実行

完成品を以下のリポジトリで公開していますのでクローンしてきます。
PPAPScript

$ git clone https://github.com/sakaro01/PPAPScript.git

plyをインストールします。

$ pip install -r requirements.txt

PPAPScriptを実行します。

$ python ppapscript.py

対話形式で遊んでみます。（現状は対話形式のみ）

まとめ

plyを使うことによって手軽にオリジナル言語を作ることができました。
TrumpScriptのようにたくさんの仕様を考えられなかったのが少し残念でした。(何か面白い仕様を思いついた方、Issue、PullRequest待ってます！ PPAPScript)

次回

次回Tech-Circle Hands on Advent Calendar 2016の担当は私の同期のKoga Yutaです。
おそらくロボットです。今回の記事を応用してオリジナルのロボット命令言語などを作ってみても面白いかもしれませんね。

参考

BppLOG: ドナルド・トランプ氏をイメージしたプログラミング言語「TrumpScript」が滅茶苦茶すぎる http://tkybpp.hatenablog.com/entry/2016/07/26/150000
Github: ply https://github.com/dabeaz/ply
TYPEA.INFO: Python PLY http://typea.info/tips/wiki.cgi?page=Python+PLY
OKIソフトウェア：LY (Python Lex-Yacc) で作る Algol 60 処理系 http://www.oki-osk.jp/esc/ply-algol/

PythonでPPAP(ペンパイナッポーアッポーペン)をイメージしたオリジナル言語 「PPAPScript」を作ってみた