概要

• ノベルゲームエンジン ティラノスクリプトは、スクリプト言語 TyranoScript と、開発フレームワーク KAG(Kirikiri Adventure Gameシステム) の実行ランタイムである。
• TyranoScript は吉里吉里(古いゲームランタイム)に対する強力な後方互換性を持ち、これが一因となり言語仕様が曖昧になっている側面がある。
• 実行時異常耐性は少ないがエラー耐性が低く、これがゲームの開発体験を損なっている。
• 拡張機能は多いが補助ツールが少なく、これがゲームの開発体験を損なっている。
• TyranoScriptに厳密な言語仕様と周辺ツールを持ち込む目的で、 LALR(1) な Tyrano Parser を実装したい。
• 本記事から始まる幾つかの記事で、その実装の記録とアイデアを連ねる。

Background

自分は ノベルゲーム制作サークルCREO に長らくお世話になっている。 このサークルはノベルゲームエンジン ティラノスクリプト を用いてゲームを作成している。

このゲームエンジンは Electron を背景に持つマクロの実行と、ノベルゲームエンジンに関する基本的なフレームワークを保有する。フレームワークには jQuery を背景に持つアニメーション補助機能、Live2D 機能や AR 機能等、豊富な演出支援が搭載されており、これらは大変便利である。

一方で、ティラノスクリプトで用いられるテキスト形式のマクロ(TyranoScript)に対しての補助ツールが少ない問題がある。 TyranoScript 自体はテキストエディタで記入するプログラミング言語のようなものだが、一般的なプログラミング言語のエコシステムにあるような formatter, linter などが現状存在しない。

私のサークルで用いられているエコシステムの1つとして、VSCode 拡張機能に TyranoSyntax が実装されている。これは Syntax Highlighting、プレビューに関しては強力な支援を提供するが、後述する文法上の制限から、補完機能は全自動ではなく警告機能も一部制限されている。

これらを解消するため、TyranoScript の厳密な構文を新たに定め、構文解析器を実装し、エコシステムを提供することを目指す。

TyranoScript Parserに関するアイデア

途中からでもいいからアウトプットしておくとよいと指摘をもらったので、現在の状況や実装の進捗、アイデア等を書くことを本ブログの目標にする。

Tyrano Parserが欲しい理由

実行時ランタイムとしては極めて優れる TyranoScript であるが、開発中の体験があまりよろしくない。 特に、開発中の linting 機能が無いことが重大である。 リソースの存在チェックは TyranoSyntax で限定的に実装されているが、CFG に基づいた検証、型検証が無い点でとても困る。

また、チーム開発の観点から formatter が無いことも絶妙に不便だ。 私のサークルでは1ゲーム約3-5人のシステム開発人員がいるが、コーディング規則ではカバーしきれない部分がある。 口伝では正確にカバーしきれないので、厳密かつ機械的に処理したい。

その他愚痴だが、以下の困りごとも排除したい。

• TyranoScript では文字列を 必ずしも"で囲まなくてよい ため、実行時エラーで落ちないし置換にも困る。
• TyranoScript には Syntax Sugar(糖衣構文) が多数用意されており、言語仕様の曖昧性が原因で特定の環境でハマる。
• TyranoScriptのデバッガは実行する度に変数等の環境を初期化しないので、エンジン改変系のデバッグで困る。

現状の実装

現状のTyranoのparser (公式エンジン) は、以下の手順で処理を行う。

1. 起動時にTyranoScriptで書かれたプログラムを先頭から1文字ずつ読み込み、1行ずつ解析する
2. 糖衣構文またはタグ文法([tag])をタグとしてリストに格納し、それ以外を本文テキストとして格納する
   • コメント(;comment)
   • goto ラベル(*label)
   • タグ(@tag または [tag])
3. エントリポイントとなるファイルの先頭から、タグリストをnextOrderにより逐次実行する。
4. 実行する際、以下を検証する。
   • ビルトインのタグ(マスタータグ)のみ必須引数の存在チェックを行う
   • 参照パラメタ (&param) を、&を取り除きjavascript変数で中身を置換する

この実装は簡易的なスクリプト言語であれば「まあいいとおもう」という実装だが、実際には以下の実装上の問題がある。

• 字句解析と構文解析の分離がない
• AST(抽象構文木) を生成しない
• []不一致を検出した際に、単純に末尾の]を削除するだけ
• 型システムがない
  • しかも javascript の挙動により動的解決されてしまう
• 種々のエラーが発生しても、行番号以外報告されない
  • パニック以外の例外処理ができてほしい

実行時に動くことだけを保証しているので、スクリプトが壊れていたらエラーで落ちてかまわないという設計しそうかもしれない。 しかし、テキストエディタで書いている以上(wordなら校正もかけてくれるけどね！)、壊れてても”なんかいい感じ”AST を作って、そこから補完・lint・format を動かしたい。エラーも実行前に静的解析してほしい。

加えて、次項に重大な問題がある。

文脈自由文法

ここで少し、偉大な先達の事例に目を向けてみたい。プログラミング言語の王様、C言語である。 一般に「C言語の文法は文脈自由(Context Free)ではない」と言われている 。

なぜか。根本的な原因は幾つかの文が文脈情報を持っていないと区別できない点にある。例えば、以下の有名な例を見てほしい。

typedef size_t t;
int m;

v = (t)*ptr;
x = (m)*a;

後半の2文は、 t や m が「型」として定義されているか、「変数」として定義されているかによって、キャスト式なのか、単なる掛け算なのかが変わってくる 。 我々は文脈によってtがtypedefされた型名であり、mが変数であることを知っているが、これを知らないと正しい構文木を構築できない。

TyranoScriptでも同じ問題が存在して、[macro]タグによって新たな関数を定義できる点だ。 タグの引数が変数なのか、文字列なのか、あるいはマクロの展開結果なのか、この類は文脈抜きに分からない。 マクロの再定義(C言語でいうところの、関数の2重実装)が許可されており、すなわち[macro]タグが来るたびにマクロの中身が変わる可能性がある。

余談だが、実はTyranoScriptのパーサーの都合か、マクロ名には[[sample]]のように空白以外のすべての文字が許容されている。

ではどうする必要があるのか

TyranoScriptの文法は手書きパーサーであるが、手書きパーサーの自由度が高すぎるのが問題の一つであると思われる。 実際TyranoScriptはあまり構造化されておらず、4000行近いメインスクリプトの各所に処理が散らばっており、これに起因する脆弱性やバグが存在する(未公表)。

したがって、自由度が低い(表現能力が低い)パーサーと処理系を考える必要がある。 具体的には、 PEG, LALR(1) を考慮に入れる。 正規表現は考慮に入れない。

ここで、Ruby の Lrama を書いている かねこにっき氏 の記事を参考にする。

PEG は deterministic な parse 失敗情報を得られないので、失敗ルールを列挙する必要があるようだ。 これは今回の都合上若干面倒なので避けたい。 TyranoScriptは厳格な言語仕様が存在しないが、既存のTyranoScriptが正確にparse出来ないと困る。 失敗ルールを列挙したところで、正となる実装が確定的に明らかになっていないとやりづらいだろう。

であるからして、 LALR parser を前提に実装を試みる。

実装状況

• 文法読み込みから表生成、デバッグ用可視化まで一通り動く。bison 互換っぽい文法定義を読んで生成物をRustの tyrano-parser クレートとして吐き出す。
• parser generatorは GrammarParser → TableGenerator で LALR(1) テーブルを構築し、コードにして生成する。

もう少し詳しく

• build: grammar を読む → TableGenerator で Action/Goto Table 生成 → コード書き出す。
• check: grammar を読み、テーブル生成だけ行って競合確認を済ませる。標準出力に生成数を表示する。
• graph: LR オートマトンの DOT 出力 (graphvizの形式) で出力する。

スキャナ/デバッガ周り

• Scanner は TyranoScript 特有のモードを持つ。[iscript]/[html] ブロックだけは明らかに文法が変わるので、ここでモードを切替ながら tokenize する。ブロックコメントはモードに関わる前処理で捌く。
• ジェネレータ由来のパーサーで CST を生成。
• パーサー由来の CST で S式 で出力する。