chakokuのブログ(rev4)

テック・コミック・ごくまれにチャリ

VTL(Very Tiny Language)を理解するためBNFを定義してソース自動生成してみた

技術ネタ

VTLの言語仕様がいまいち理解できず、自分なりに理解すべくBNF風に文法を定義して、定義したBNFを使ってソース自動生成してみた。

#!/usr/bin/python
import random
import re

VERB = False

BNF = {   
 '<SRC>'    : ('<STMT>',),
 '<STMT>'   : ('<ASSIGN>','<OUTPUT>','<INPUT>','<STMT>_SP_<STMT>'),
 '<ASSIGN>' : ('<VAR> = <TERM0>','<ARRAY> = <TERM0>'),
 '<INPUT>'  : ('<VAR> = ?','<ARRAY> = ?'),
 '<OUTPUT>' : ('? = <TERM0>','? = <TERM0> ;'),   # ; means no LF
 '<TERM0>'  : ('<TERM>','<EXP0>'),
 '<TERM>'   : ('<VAR>','<ARRAY>','<NUMBER>','<EXP>','<STRING>'),
 '<VAR>'    : ('<USER_VAR>','<SYS_VAR>'),
 '<ARRAY>'  : (':<VAR>)',),
 '<NUMBER>'  : ('1','2','3','4','5'),
 '<STRING>'  : ('"hello"','"bye"','""'),
 '<USER_VAR>' : ('A','B','Z','a','z'),
 '<SYS_VAR>'  : ('%','$','#'),

 '<EXP0>'  : ('<1OP> <TERM>','<EXP>'),
 '<EXP>'  : ('<TERM> <2OP> <TERM>','(<1OP> <TERM>)','(<EXP>)'),
 '<2OP>'  : ('*','/','+','-','>','<','=') ,
 '<1OP>'  : ('+','-','!') ,


}

def gen_vtl_src():
    src = '<SRC>'
    matched = True
    while(matched):
      if VERB:
         print "-------------------"
         print "SRC:",src
         print "-------------------"
      matched = re.match(".*(<[A-z0-9]*>).*",src)
      if matched:
         lavel = matched.group(1)
         value = get_next(lavel)
         src = src.replace(lavel,value,1)  # specify replace only once
         if VERB:
             print "{:s} -> {:s} : {:s}".format(lavel,value,src)
    return src

def get_next(lavel):
    next = BNF[lavel]
    if len(next) == 1:
          return next[0]
    else:
          return next[int(random.random()*len(next))]

for x in range(100):
   src = gen_vtl_src()
   print "---------------------"
   print src.replace('_SP_','\n')

上記文法（BNF風）がVTLを正しく表現しているかどうかは分からないけど、、自動生成されたソースは以下

% = (! "")
B = :A)
:#) = ! :Z)
$ = :#)
? = ((! #))
? = + :$)
? = - 4
A = ((- :B)) < Z)
? = (((1 < "")))
? = ! :a) ;
? = ((- # = $)) / :B)
? = 3 ;
:z) = ?
? = 3 = z ;
z = ?
:#) = ?
:Z) = 5
? = ! ""
? = :a) ;
% = :$)
A = ?
? = "hello" ;
z = - :B)
:z) = ?
? = 2
? = (- a)
:#) = + %
? = ! :z) ;
% = - "bye"
# = ?
z = + A * ""
? = (((! "hello"))) ;
? = "hello" ;
? = :#) ;
$ = ?
# = ?
B = :%)
:#) = :#) + ""
:z) = ?
z = ?

文字列/文字(string/ascii code)入出力がまだ変なのと、、否定の単項オペレータ、！はVTLでは使えなさそうなので、もう少し修正が必要だが、だいたいこんな感じかと。あと、行番号も抜けているが、、まぁそれは表現上だけか。文字列の算術演算とかもできてしまうが、、これは構文解析時にエラーとして排除するか、実行時に無視する（NULL文字列は数字の0とみなし、NULL文字以外は１と見なす？）か。。

自作パーザが正しいかどうかは上記の生成されたソースを読み込ませて、構文木がまで辿れたら、だいたいOKと言える。完全性をどうやって担保したらいいのかは不勉強で分からず。

■改訂版仕様
行番号も仕様として規定

BNF = {   
 '<SRC>'    : ('<LINES>',),
 '<LINES>'  : ('<LINE>','<LINE>_NL_<LINES>'),
 '<LINE>'   : ("<LINE_NUMBER> <STMT>",),
 '<STMT>'   : ('<ASSIGN>','<OUTPUT>','<INPUT>'),
 '<ASSIGN>' : ('<VAR> = <TERM0>','<ARRAY> = <TERM0>'),
 '<INPUT>'  : ('<VAR> = ?','<ARRAY> = ?'),
 '<OUTPUT>' : ('? = <TERM0>','? = <TERM0> ;',  # ; means no LF
               '$ = <TERM0>','$ = <TERM0> ;'), # $ means putchar(ch)
 '<TERM0>'  : ('<TERM>','<EXP0>'),
 '<TERM>'   : ('<VAR>','<ARRAY>','<NUMBER>','<EXP>','<STRING>'),
 '<VAR>'    : ('<USER_VAR>','<SYS_VAR>'),
 '<ARRAY>'  : (':<VAR>)',),
 '<NUMBER>'  : ('1','2','3','4','5'),
 '<LINE_NUMBER>'  : ('100','200','300','400','500'),
 '<STRING>'  : ('"hello"','"bye"','""'),
 '<USER_VAR>' : ('A','B','Z','a','z'),
 '<SYS_VAR>'  : ('%','$','#'),

 '<EXP0>'  : ('<1OP> <TERM>','<EXP>'),
 '<EXP>'  : ('<TERM> <2OP> <TERM>','(<1OP> <TERM>)','(<EXP>)'),
 '<2OP>'  : ('*','/','+','-','>','<','=') ,
 '<1OP>'  : ('+','-','!') ,
}

WhiteSpaceは空白(0x20)一文字だけに制限（ミニマムサイズが至上命題のため）。上記ルールで生成されたソースは以下

500 :z) = ?
---------------------
500 ? = 2 ;
---------------------
200 ? = ((("bye" * ((- Z < (- 5))))))
300 Z = ?
---------------------
500 z = ?
500 :B) = ""
---------------------
400 $ = (- "bye") ;
---------------------
500 ? = - "bye" ;
400 $ = 4
200 :%) = Z / (% < "bye")
400 :z) = ?

■追加
BNFを見ながらパーザを作ってみて、解析しにくい所、コード最小化最優先でさらにルール見直し

BNF = {   
 '<SRC>'    : ('<LINES>',),
 '<LINES>'  : ('<LINE>', '<LINE>_NL_<LINES>'),
 '<LINE>'   : ("<LINE_NUMBER> <STMT>",),
 '<STMT>'   : ('<ASSIGN>', '<OUTPUT>', '<INPUT>'),
 '<ASSIGN>' : ('<VAR>=<EXP>','<ARRAY>=<EXP>'),
 '<INPUT>'  : ('<VAR>=?','<ARRAY>=?'),
 '<OUTPUT>' : ('?=<EXP>', '?=<EXP>;',  # ; means no LF
               '$=<EXP>', '$=<EXP>;'), # $ means putchar(ch)
 '<EXP>'  : ('<PRIM_EXP><OP><EXP>', '<PRIM_EXP>'),
 '<PRIM_EXP>' : ('<VAR>', '<ARRAY>', '<NUMBER>', '<STRING>', '(<EXP>)'),
 '<VAR>'    : ('<USER_VAR>', '<SYS_VAR>'),
 '<ARRAY>'  : (':<VAR>)',),
 '<OP>'  : ('*', '/', '+', '-', '>', '<', '=') ,
 '<NUMBER>'  : ('1', '2', '3', '4', '5'),
 '<LINE_NUMBER>'  : ('100', '200', '300', '400', '500'),
 '<STRING>'  : ('"hello"', '"bye"', '""'),
 '<USER_VAR>' : ('A', 'B', 'Z', 'a', 'z'),
 '<SYS_VAR>'  : ('%', '$', '#'),
}

■追記(180421)

Pythonで実装したVTLがボチボチ動くようになった。言語仕様のリファレンスとしている、VTL2(Altair_680-VTL-2)のサンプルコードを打ち込んでエラーなく動作するかを確認

http://www.altair680kit.com/manuals/Altair_680-VTL-2%20Manual-05-Beta_1-Searchable.pdf
これはスターシューターというシンプルなゲームで、星印めがけて打つと、星は縦横4方向に広がる。星を選んで打って、盤の外周をぐるっと星で囲めば上がりというゲーム（らしい）

$ ./vtl.py test/startshooter.vtl
Welcome to VTL
(V0.05 2018/4/7_0500)
CMD:RUN
A - . . . . .
B - . . . . .
C - . . * . .
D - . . . . .
E - . . . . .
    1 2 3 4 5

YOUR MOVE --C
3



A - . . . . .
B - . . * . .
C - . * . * .
D - . . * . .
E - . . . . .
    1 2 3 4 5

YOUR MOVE --