TL; DR
- Toy言語のLanguage Serverを作成中
- 以下を実装済み
- シンタックスハイライト
- エラー表示
- 定義移動
- hoverの定義表示
- 補完
- エラートレラントパーサーを使用
はじめに
LLVM使ってプログラミング言語作ろう 
→せっかくならMLIRで抽象化しよう
→まずはチュートリアルのToy言語やろう
→Toy言語書きやすくしたいな...Language Server作るか←いまここ
テスト前だけ部屋が綺麗になることってあるよね
Toy言語とは？
おふざけはこのくらいにして本題に入ります。
MLIRはLLVMプロジェクトの1つで、LLVMよりも抽象的な中間表現です。
MLIRを使うことで、様々なコンパイラが内部表現を0から実装しなくても済むようになります。
......などと偉そうなことを言いましたが、私はまだ入門したてで良く分かっていません。
そんな初心者でも雰囲気がつかめるように、MLIRには 「Toy」というチュートリアル用の言語 が用意されています。
MLIRが得意なベクトル、行列計算の抽象化を学べるよう、多次元配列（テンソル）を第一級オブジェクトとして扱えます。
var a = [[1, 2], [3, 4]];
一方、言語仕様を簡単にするため構文や言語機能は簡略化されています。
- 型は以下のみ
- float
- floatのテンソル
- 構造体
- if文、for文なし
- 再代入不可
- 組み込み関数は
printとtranspose(転置)のみ
def main() {
# 変数 `a` をshape（※各次元の要素数） <2, 3>で定義し、リテラル値で初期化する。
# shapeは与えられたリテラルから推論される。
var a = [[1, 2, 3], [4, 5, 6]];
# bはaと同一であり、リテラルのテンソルは暗黙的に「reshape」（異なるshapeに変換）される：
# 新しい変数を定義を定義することでテンソルを「reshape」できる（要素数が一致する必要がある）。
var b<2, 3> = [1, 2, 3, 4, 5, 6];
# 組み込み関数はtranspose(), print()のみである。以下では結果を表示する前に
# aとbを転置し要素ごとに掛け算している
print(transpose(a) * transpose(b));
}
作った機能
現在このToy言語のLanguage Serverを開発しています。
TypeScript製で、基本的にVSCode向けです。
まだ作成中ですが、完成したらExtensionとして公開予定です。
シンタックスハイライト
変数、関数定義
（画像では伝えられないのですが、クリックすると定義個所へジャンプします）
補完
エラー表示
実装
VSCode公式のLanguage Server開発ガイドを参考に実装しました。
lexer
まずはlexerで字句解析をします。
実装: https://github.com/Syuparn/toy_lsp/blob/main/server/src/lexer.ts
凝ったことはしていませんが、この後の処理のために
-
COMMENTコメント -
UNKNOWN処理失敗した良く分からない文字列
も有効なトークンとして扱います。
コメントはシンタックスハイライトのため、UNKNOWN は処理を打ち切らないためです。
通常のコンパイラやインタプリタであれば、変なソースコードにはエラーを出して即時終了して構いません。一方、Language Serverの場合、書きかけの状態や1つのtypoで補完やシンタックスハイライトが使えなくなっては困ります。そのため、不正な入力でも止まらない設計（エラートレラント）にする必要があります。
この後紹介するパーサーも同様です。
シンタックスハイライト
Semantic Tokensを使用します。詳細は以下の記事が分かりやすかったです。
Toyでは構文上で役割が変わるトークンがほぼ無いため、lexerさえあれば実装できました。
// ソースコード
const text = document.getText();
// lexerでトークンを得る
const tokens = tokenizeAll(params.textDocument.uri, text);
// ...
for (let i = 0; i < tokens.length; i++) {
const token = tokens[i];
const nextToken = i + 1 < tokens.length ? tokens[i + 1] : undefined;
// Language Server上のToy処理系のトークンをSemantic Tokenの型に変換
const tokenType = getTokenType(token.kind, nextToken?.kind);
if (tokenType === -1) {
continue; // unknownは色を付けない
}
const line = token.location.range.start.line;
const char = token.location.range.start.character;
const length = token.text.length;
builder.push(line, char, length, tokenType, 0);
}
1つだけ考慮すべきトークンが IDENTIFIER でした。変数の場合 (foo) と関数呼び出し(foo())の場合で色を分ける必要があります。
今回は素朴に、「後ろに ( が来る場合は関数呼び出し」というふうに実装しました1。
if (kind === 'IDENTIFIER') {
if (nextKind === '(') {
return tokenTypes.indexOf('function');
}
return tokenTypes.indexOf('variable');
}
parser
続いてパーサーの実装です。先ほども触れましたが、構文エラーが起きても最後まで処理を続ける（エラートレラント）ようにしています。
実装: https://github.com/Syuparn/toy_lsp/blob/main/server/src/parser.ts
実装にはRubyのパーサーPrismを参考にしています。
Prismのエラートレラントパーサーについては以前別記事にもまとめています。
ざっくりいうと、構文エラー（=直前のトークンと比較して想定外のトークンを見つけた）の場合、エラーを記録してパースを続けます。
expect
トークンを消費する際に、期待した型であるかどうかをチェックします。
期待通りでなければ診断（エラーメッセージ）を追加し消費はしません。
expect(tokenKinds: TokenKind[], errMessage: string) {
if (!tokenKinds.includes(this.peekToken.kind)) {
this.addDiagnostic(errMessage);
this.curToken = this.dummyToken(this.curToken);
return;
}
こうすることで、トークンが欠けている場合でも最後までパースを続けることができます。
def f( {}
')' is missing
実装は以下の通りです。
parseFunction() {
// ...
if (this.match(['IDENTIFIER'])) {
this.nextToken();
name = this.curToken.text;
} else {
// ...
}
this.expect(['('], "'(' is missing");
const params = this.parseParameters();
// ここで ) が抜けててexpectを満たさない（エラーメッセージのみ記録し次に進む）
this.expect([')'], "')' is missing");
// 次はexpectを満たすので正常動作に戻る
this.expect(['{'], "'{' is missing");
const body = this.parseBody();
this.expect(['}'], "'}' is missing");
return new FunctionAST(loc, name, params, body);
}
expectの後も処理が続くため、エラーが起こってもASTが生成されます。
FunctionAST(
loc, // location
'f', // 関数名
[], // 仮引数一覧
[], // ボディの文一覧
)
missing node
一方、間違いが多すぎて復旧できない場合もあります。その場合は、ASTに MissingNode というダミーのノードを挿入し、構文の終了トークンまで読み飛ばします。
// 関数定義のボディ中の文をパース
parseStatement() {
switch (this.curToken.kind) {
// ...
case 'def': {
const loc = this.curToken.location;
// Toyにはクロージャはないため、関数定義中にdefが出てきたら復帰不能と判断し "}" まで読み飛ばす
this.addDiagnostic('function cannot be defined inside functions');
while (!this.match(['}'])) {
this.nextToken();
}
return new ExprStmtAST(loc, new MissingAST(loc));
}
// ...
}
}
エラー表示
先ほどパーサーが記録した診断結果をそのまま返します。
connection.languages.diagnostics.on(async (params) => {
const document = documents.get(params.textDocument.uri);
if (document !== undefined) {
// 診断結果（エラー表示）
return {
kind: DocumentDiagnosticReportKind.Full,
items: await validateTextDocument(document),
} satisfies DocumentDiagnosticReport;
} else {
// ...
}
});
// 診断の本体
async function validateTextDocument(textDocument: TextDocument): Promise<Diagnostic[]> {
const settings = await getDocumentSettings(textDocument.uri);
const text = textDocument.getText();
const tokenizer = new Tokenizer(textDocument.uri, text);
const parser = new Parser(tokenizer);
parser.parseModule();
// パーサーの診断結果をLanguage Serverの形式に変換
const diagnostics: Diagnostic[] = parser.diagnostics
.slice(0, settings.maxNumberOfProblems)
.map((d: ToyDiagnostic) => ({
severity: DiagnosticSeverity.Error,
range: d.location.range,
message: d.message,
source: 'ex',
}));
return diagnostics;
}
定義の場所へ移動
実装: https://github.com/Syuparn/toy_lsp/blob/main/server/src/declarations.ts
ASTから対象ノードを検索し、位置情報を取得します。
取得対象は以下の2つです。
- 変数定義
- 関数定義
まず最初に、探すスコープを特定するため、VSCodeのカーソルがASTのどの要素にいるのかを特定します。
const current = this.findCurrentAST(cursor);
if (!current) {
// current position is not an identifier
return [];
}
続いて、関数、変数それぞれについて同じ名前の要素を検索します。
関数定義
Toyにはクロージャがないため、素朴にトップレベルの関数定義ASTから名前が一致するものを検索します。
findFuncDecl(expr: CallExprAST): ExprAST[] {
for (const func of this.ast.funcs) {
if (func.name === expr.callee) {
return [func];
}
}
return [];
}
変数定義
変数定義は
- 変数定義文
- 仮引数
の2つの可能性があるため、それぞれ探します。いずれも探索範囲は（エディタのカーソルと）同じ関数内のため、引数で現在の関数定義を受け取っています。
findVariableDecl(expr: VariableExprAST, func: FunctionAST): ExprAST[] {
// NOTE: since toy does not have closure, variable should be defined in the same function
const param = this.findParam(expr.name, func);
if (param) {
return [param];
}
const variable = this.findVarDecl(expr.name, func);
if (variable) {
return [variable];
}
return [];
}
関数定義の場合、仮引数一覧を名前比較します。
findParam(name: string, func: FunctionAST) {
for (const param of func.params) {
if (param.name === name) {
return param;
}
}
}
変数定義文の場合、ボディの文一覧から、同名の変数を定義する変数定義文を探します。
findVarDecl(name: string, func: FunctionAST) {
for (const stmt of func.body) {
if (stmt instanceof VarDeclStmtAST && stmt.name === name) {
return stmt;
}
}
}
後は上記をLanguage Serverの connection.onDefinition に組み込めば完成です。
connection.onDefinition((params: DefinitionParams): Location[] => {
const document = documents.get(params.textDocument.uri);
if (!document) {
return [];
}
const text = document.getText();
const tokenizer = new Tokenizer(params.textDocument.uri, text);
const parser = new Parser(tokenizer);
const ast = parser.parseModule();
return new DefinitionFinder(ast).findLoc(params.position);
});
定義表示
大まかな処理は「定義の場所へ移動」と同じで、位置の代わりに定義の文字列表示を返します。
最後に、Definition同様に、Language Serverの connection.onHover に組み込みます。
補完
こちらも同様の流れで、名前が部分一致する変数名、関数名一覧を返しています。
ただし、組み込み関数の transpose, print も補完候補に加えています。
同様にLanguage Serverの connection.onCompletion に組み込みます。
おわりに
以上、Toy言語のLanguage Serverの紹介でした。
山場の意味解析が残っているので、まとまった時間が取れたら改めて挑戦したいと思います。
-
Toyの関数は第一級ではないため、関数オブジェクトが変数に代入されることは考慮不要です（もし考慮が必要な場合、構文解析と意味解析も必要）。 ↩