vim-jp » Vim Advent Calendar 2012 ujihisa 8

Vim Advent Calendar 2012 ujihisa 8

Posted at 2013/03/31

Vim Advent Calendar 2012 の120日目の記事です。昨日はmanga_osyoさんによるtextobj-multiblock つくったでした。この記事にもあるように、Vim Advent Calendar 2012はまだまだ執筆者を募集中です。

ところで、二日ほど前にLALR(1)の言語の構文解析をVim scriptで行うという記事があったのを覚えておいででしょうか。

vim scriptで字句解析！と組み合わせて使っていただければいろいろできるかもしれません。

というわけで、実際にやってみましょう。今年のVim Advent Calendarの2つの記事をまとめた集大成です。

ゴール

s:calc('1 + 2 * (3 + 4)')
#=> 15

となるような関数s:calcを持つファイルcalc.vimを作ります。足し算より掛け算の方が演算子結合順序が強く、また括弧もあるというものです。

一旦トークン列に分解し、その後パースしつつ各ノードを評価してひとつの値に畳み込む、という一般的かつ簡単な方法でやっていくことにしましょう。

Lexer

まずは字句解析です。ひとかとまりの文字列を、トークンのListに変換します。

http://qiita.com/items/a5ead41d4a1d4cbaeb74

rbtnnさんが作成したVital.Lexerを用います。vitalを用いるので、まずは開発用に&rtpに入っているvitalをそのままvital#of('vital')を通して利用しましょう。

lexer.vim

let s:L = vital#of('vital').import('Text.Lexer')
let s:rule = [
      \ ['id','\d\+'], ['whitespace','\s\+'],
      \ ['pls', '+'], ['ast', '*'],
      \ ['l_pare', '('], ['r_pare', ')']]
function! s:lex(str)
  return s:L.lexer(s:rule).parse(a:str)
endfunction

かなり短くかつ宣言的に記述することができました。

echo s:lex('1 + 2 * (3 + 4)')

を行うと

[{'label': 'id', 'col': 0, 'matched_text': '1'},
 {'label': 'whitespace', 'col': 1, 'matched_text': ' '},
 {'label': 'pls', 'col': 2, 'matched_text': '+'},
 ... ]

といった辞書のリストが得られます。無事字句解析ができているようです。

さて、読者皆様はparse()関数の突然の登場に面食らったのではないでしょうか。この関数は構文解析器とは何の関係もありません。この名前が非常にまぎらわしいとのことで、vitalのissueにチケットを作成しておきました。 https://github.com/vim-jp/vital.vim/issues/48

Parser

続いて構文解析です。

http://uwanosora.hatenablog.jp/entry/2013/03/28/000633

uwanosoraさんが作成したkp19ppはC++で記述されており、g++とmakeがあればビルドできます。実際に必要なのは生成されるkp19ppコマンドです。

自分でインストールしてPATHを通すのが面倒に感じた読者の方もいらっしゃることでしょう。そんなこともあろうかと、Gentoo用にパッケージ化しておきました。ぜひご利用ください。

https://github.com/ujihisa/overlay

このoverlayを追加して

$ sudo emerge kp19pp

すると/usr/bin/kp19ppが利用可能になります。

kp19ppは独自の言語です。kp19pp用の簡単なsyntax / indent / ftdetect / ftpluginをセットにしたプラギンを作っておきました。これを用いることでパーサを簡単に記述できるようになります。

https://github.com/ujihisa/ft-kp19pp.vim

さあ早速パーサを記述しましょう。

parser.vim.kpg

<token_desc> token{
    <left>{
        ast;
        pls;
    }
    l_pare, r_pare;
    id<type_expr>;
}

<grammar> grammar{
    E<type_expr>
        : [make_pls] E(0) pls E(1)
        | [make_mlt] E(0) ast E(1)
        | [make_exp] l_pare E(0) r_pare
        | [make_id]  id(0)
        ;
}

Advent Calendarの該当記事からそのままもってきました。さあこれからVim scriptを生成しましょう。

$ kp19pp -vimscript parser.vim.kpg parser.vim

これでVim scriptのparser.vimファイルが生成されました。つづいて各アクションmake_plsなどを記述しましょう。

let s:semantic_action = {}
function! s:semantic_action.make_mlt(arg_0, arg_1)
    return a:arg_0 * a:arg_1
endfunction

function! s:semantic_action.make_pls(arg_0, arg_1)
    return a:arg_0 + a:arg_1
endfunction

function! s:semantic_action.make_id(arg_0)
    return a:arg_0
endfunction

function! s:semantic_action.make_exp(arg_0)
    return a:arg_0
endfunction

function! s:semantic_action.syntax_error()
    echo 'error!'
endfunction

これで構文解析器と評価器は完成です。

結合

Vital.Lexerを用いて作成した字句解析器とkp19ppを用いて作成した構文解析器とそれに適用するよう作成した評価機のすべてを組み合わせましょう。

$ cat lexer.vim parser.vim > calc.vim

つづいてメイン処理です。

let s:p = copy(s:parser)
call s:p.ctor(s:semantic_action)

let xs = s:lex('1 + 2 * (3 + 4)')
call filter(xs, 'v:val.label !=# "whitespace"')
for x in xs
  call s:p.post(s:token[x.label], x.matched_text)
endfor
call s:p.post(s:token.token_0, 0)

if s:p.accept()
  echo s:p.accepted_value
endif

(逐次パーサにトークン列をひとつずつ渡すより前にfilter()で空白文字を削除しています。これは別にforの中で条件分岐しても良いです。)

あとは実行すると正しい計算結果が得られるはずです。:source calc.vimで実行できます。

で、gif動画作ってみました。それなりの長さですので、気を引き締めてお楽しみください。

ujihisa

もどる

vim-users.jp

Vim Advent Calendar 2012 ujihisa 8

ゴール

Lexer

Parser

結合