Hatena::Groupbugrammer

蟲!虫!蟲!

Esehara Profile Site (by Heroku) / Github / bookable.jp (My Service)
過去の記事一覧はこちら

なにかあったら「えせはら あっと Gmail」まで送って頂ければ幸いです。
株式会社マリーチでは、Pythonやdjango、また自然言語処理を使ったお仕事を探しています

 | 

2011-10-21

[]PythonLex + Yaccでオリジナル言語を作るための第一歩についての覚書 22:49

 プログラミング言語を勉強するにあたって、比較的初心者の練習向けの、実装するべきプログラミング言語というのが二つくらいあって、一つがLisp処理系で、もう一つがBrainF*ck処理系です。BrainFuck処理系は、Wikipediaにも書いてあるとおり、「おっぱい言語」や「ジョジョ言語」、あるいは肉体言語 Tython - 質のないDiary Hなど、多くの場所で使われています。

 使われている理由としては単純で、Byte配列と、そのポインタ、そしてポインタを操作し、出力し、場合によっては反復するという単純な構成、さらにはその命令には8文字しか使われていないから、という理由があげられます。

 さて、誰しもが「プログラミング言語を作りたい!」と思ったことはあると思います。プログラミング言語処理系として有名なのは、LexYaccです。詳しい解説は下のところにあります。

 プログラミング言語を作る

 ここではC言語が使われていて、さすがにC言語だとわからないよね、何かPythonとかでも同じような実装があればいいよね、という話になると思うんですけど、実はPythonにもLexYacc処理系があります。その名も「PLY(Python,Lex,Yacc)」という名前です。

 J:COM NET加入者向けホームページサービス 終了のお知らせ

 そこで、Lex + Yaccの使い方を、オリジナルなBrainF*ckとして、HtmlF*ckというテンプレートエンジンを作ることによって、学ぼうかな、というのが今日の目的です。

BrainF*ckに影響されたテンプレートエンジン:HtmlF*ck

 そこで、今回作る言語の仕様を決定します。ポイントはBrainF*ck的にHtmlが書ける「HtmlF*ck」というものを作ってみましょう。さすがに全ての要素をサポートするのは難しいので、簡単にhead,body,div,pあたりを実装しましょう。

まずLexの使い方

 Lexの使い方は非常に簡単です。Lex文字列を分割し、トークンにします。

 トークンについては、正確な理解はともかく、「こういう文字列はこういう名前ですよ」みたいなことに考えるといいんじゃないかと。

tokens = (
        'STRING'
        ,'P_Start'
        ,'P_End'
        ,'ID'
        ,'CLASS'
        ,'HEAD'
        ,'BODY'
        ,'DIV_Start'
        ,'DIV_End'
        )

#Define Token
t_STRING = r'\".*?\"'
t_P_Start = r'P'
t_P_End   = r'\/P'
t_ID = r'\#'
t_CLASS = r'\.'
t_HEAD = r'\@'
t_BODY = r'\&'
t_DIV_Start = r'\('
t_DIV_End = r'\)'

#Token Parse Error
def t_error(t):
    t.lexer.skip(1)

lex.lex()

 Lexの宣言自体はこれで終了。Tokenの名前と、"t_"を追加したトークンの変数が1対1で対応している。

 あと、トークンの中身は正規表現でかかれます。上記の場合なら、""でかこまれていたらSTRINGという感じ。

Yaccを使ってみよう

 さて、Yaccの宣言。イメージ的にはしたのURLがわかりやすいかな。

 プログラミング言語を作る/yaccとlex

def p_statement_expr(t):
    "statement : expression"
    print "<html>\n" + t[1] + "\n</html>"

 俺の言葉で直すと、 1 + 1は、 "NUMBER PLUS NUMBER"というトークンに分解され、それがさらに別のトークンに書き直されていく、と理解してる。例えば"RESULT"とかね。で、最終的にRESULTがstatementで一つになった場合、始めて出力するという経路をとるんだと思う。(この場合だと、expression一つになった場合)

 では、トークンをどのようにして書き直すのか。

def p_expression(t):
    """
    expression : P_Start_Parse expression P_End
               | DIV_Start_Parse expression DIV_End
               | HEAD expression HEAD
               | BODY expression BODY
    """
    if t[3] == "/P":
        t[0] = t[1] + t[2] + "\n</p>"
    if t[3] == ")":
        t[0] = t[1] + t[2] + "\n</div>"
    if t[1] == "@" and t[3] == "@":
        t[0] = "<head>" + t[2] + "</head>"
    if t[1] == "&" and t[3] == "&":
        t[0] = "<body>" + t[2] + "</body>"

 上記のトリプルクオーテーション("""のことね)で囲まれた部分が、「こういうパターンのときは、ここの関数を呼び出して、さらにexpressionというトークンに書き直しますよ」という宣言になっている。つまり、普段のPythonだったらドキュメントになっているところですけど、ここは無視してはいけなくて、ちゃんと書かなければいけない。次に実際にパターンで呼び出されたときの値が、それぞれ格納されています。

 ただ、トークンごとに分割されているわけじゃないので、実際に条件分岐をするときは、値をみてあげるわけ。(もし、それが面倒くさいなら、別にdefを宣言する必要がある)

 で、基本的には引数で宣言された配列の[0]が戻り値となり、その次から順番に値が入っていくようす。

 さて、上記を見たところ、P_Start_ParseはLexの部分では宣言していないトークンだということに気がついている人がいると思う。実はこのトークンは別のところで宣言しているので、そこを見てみよう。

 そうそう、ついでですけど、Yaccで使われる関数は、"p_"で始まるというきまりになっているようです。

def p_expression_P(t):
    """
    P_Start_Parse : P_Start ID_AND_CLASS
                  | P_Start

    """
    if len(t) == 3:
        t[0] = "<p" + t[2] + ">\n"
    else:
        t[0] = "<p>\n"

 つまり、 "hoge : fuga"というのは、"hoge = fuga"とも呼べるわけで、「このパターンなら、このパターンにしてくださいね」というような言い方ができるわけで、"|"で他のパターン。つまり、この場合だとP_Startと判断されたトークン(この場合なら"P"か、P + ID_AND_CLASSの場合)というわけ。ついでなので、ID_AND_CLASSも見てみよう。

def p_expression_ID_AND_CLASS(t):
    """
    ID_AND_CLASS : ID_R
                 | CLASS_R
                 | ID_R CLASS_R
                 | CLASS_R ID_R
    """
    if len(t) == 3:
        t[0] = t[1] + t[2]
    else:
        t[0] = t[1]

def p_expression_ID(t):
    """
    ID_R : ID STRING
    """
    t[0] = " id = " + t[2] 

def p_expression_CLASS(t):
    """
    CLASS_R : CLASS STRING
    """
    t[0] = " class = " + t[2]

 このように、どんどんと連鎖して書き直されていっているんだと思う。

例えばどういう挙動をしているのか

 わかりやすく、例えばこういう命令を書いてみよう。

P#"hoge""fuga"/P

 この場合、次のようなトークンのリストで書き直されます。

P_Start CLASS STRING STRING P_End

 まず最初にマッチするパターンを探します。例えば、この場合だと、CLASS STRINGとSTRINGはマッチしそうですね。そこで、パターンに合わせて変換します。

P_Start CLASS_R expression P_End

 さらに、CLASS_RがID_AND_CLASSに変更できそうですね。

P_Start ID_AND_CLASS expression P_End

 そうすると、P_Start ID_AND_CLASSが変更できそうです。

P_Start_Parse expression P_End

 すると、全体が変換できるので

expression

 expression一つになったので、最後のトークンにして終了

statement

 ……という筋道をたどるわけです。

あなたも言語を作ってみませんか?

 というわけで、簡単にPython実装のYACCLEXの使い方について流しました。本当は右結合とか、左結合とかいろいろなことがあって、言語自体を実装するのはかなり難しいところではあるんですが、簡単なスクリプトを作るためにはこれで十分じゃないかなーと思うわけです。あと、これだけだと、パターンに当てはまらないもの(例えばP/Pとか)は、どこのパターンにも属することが出来なくて、簡単にエラーになってしまうので、そこのあたりの実装も考えるべきですね。

 なにはともあれ、あなたもYACCLEXを覚えて、自分のオリジナルな言語を作ってみるのもいいですよ。ちなみに、英語になるけれど、PythonYACC/LEX実装のBrainF*ckは下のところにあります。

Loading...

実装の参考ソース

HTMLF*CK ? GitHub

LadiLadi2012/08/24 04:39Keep on wirtnig and chugging away!

kkplcsokkplcso2012/08/24 19:07wSoxwa <a href="http://uzjcaitkilfv.com/">uzjcaitkilfv</a>

sanqvcsanqvc2012/08/25 00:53mTv6yv , [url=http://iqethiunrcne.com/]iqethiunrcne[/url], [link=http://ywcplylmrgmd.com/]ywcplylmrgmd[/link], http://oqgbqgfikomf.com/

fkgiaqfkgiaq2012/08/26 14:35Hcwh9u <a href="http://ljcxwbkvzbwz.com/">ljcxwbkvzbwz</a>

frcmukfrcmuk2012/08/27 04:55AUqa4i , [url=http://bpghpmevhvjk.com/]bpghpmevhvjk[/url], [link=http://ibyokpuzgddm.com/]ibyokpuzgddm[/link], http://sfdulvcicopc.com/

 |